This is the personal website of Jason Zhang.
Note: Turns out, the ideas here are much more interesting than I thought. A follow up paper is being written.
I want to discuss a paper about multisets that I read awhile back. Specifically, the idea of the cardinality of infinite multisets. So, I want to cover some information about multisets, a review and interpretation of the paper, and my own ideas regarding this concept. The paper is titled “Infinite multisets: Basic properties and cardinality” by Milen V. Velev. All contents of this blog are adapted or in direct response to that paper.
We first develop a bunch of machinery to help us analyze multisets, most of which is found in the paper itself. If you have already read it, please skip to the Evaluation section.
Definition. A multiset \(A\) is a an ordered pair \(A = (A^{*}, m_{A})\) where \(A^{*}\) is a set of elements (called the root set) and \(m_{A} : U \rightarrow \textrm{Card}\) where \(U\) is the universe. The function sends every element of \(A^{*}\) to a nonzero cardinal denoting that element’s multiplicity, and everything else to \(0\).
We can generalize this definition later, but for now it is sufficent. To distuinguish between a set and a multiset, we will write a given set \(A = \{\dots\}\) and a multiset \(A = [\dots]\). I write a multiset using square brackets because of the limitations of typesetting on markdown files. Sorry!
So, an example of a multiset would be \(A = [1,1,2]\) where \(A^{*} = \{1,2\}\) and \(m_{A}(1) = 2\) and \(m_{A}(2) = 1\). We will write \(A = [1,2]_{2,1}\) to be a bit more general. That is, \(A = [a_{1},a_{2},\dots]_{m_{A}(a_{1}),m_{A}(a_{2}),\dots}\).
Recall the usual definition of cardinality in choice-environments.
Definition. Two sets \(X\) and \(Y\) have the same cardinality if and only if there exists a bijective function \(f : X \rightarrow Y\). In which case we say \(\|X\| = \|Y\|\).
How can we define cardinality for multisets? There obviously isn’t a correspondence from \([1,1]\) to \([1]\). Let us try to sum the multiplicities.
Definition. For all multisets \(A\), we let \(\mu(A) = \sum_{a \in A^{*}} m_{A}(a)\).
However, at least by the paper, this will NOT be our definition of cardinality. The paper gives us this example to show us why isn’t a proper generalization:
Example. Consider the multiset \(A = [a]_{3}\) and \(B = [a,b]_{2,1}\). Although \(\mu(A) = \mu(B)\), but there is no bijection. In fact, the notion of a bijection doesn’t even make sense!
We will define a proper generalization later. For now, let us define some basic things.
Definition. For all the definitions below, let \(A\) and \(B\) be multisets.
We run into an interesting conundrum. The complement possibly implies negative multiplicities. Could this be an issue? Of course, we could instead define it with the universe and such but such a notion isn’t also well defined. What multiplicity should each element of the universe have? As such, we will amend our definition of a multiset to allow for strange multiplicities. Now, any rational number along with the cardinals work. This means there is such a notion as \([a]_{-\frac{1}{2}}\). As there is already a plethora of work done on this, we will continue by. The paper proceeds to provide a definition for the cartesian product, domain, range, etc. I recommend you read the actual paper to process that information and check over it yourself, we will be proceeding straight into the actual content of the paper from hereon. I will give any definitions that we need often but I again encourage you to read the paper yourself.
The paper itself defines domain and range for relations on multisets, we will not be doing that and we will be going straight into functions. Simply put, a relation \(f\) is a function if and only if for every element \([a]_{r}\) in \(\textrm{Dom} f\), there exists exactly one element \([b]_{l}\) in \(\textrm{Ran} f\) such that \([a,b]_{r,l}\) is in \(f\) with the pair occuring \(m_{1}(a,b)\) times. 2 Let \(A\) and \(B\) be multisets for all the following definitions.
Definition. The multiset function \(f\) is said to be m-injective if and only if \(f : A^{*} \rightarrow B^{*}\) is injective and \(\mu(A) \leq \mu(B)\).
Definition. The multiset function \(f\) is said to be m-surjective if and only if \(f : A^{*} \rightarrow B^{*}\) is surjective and \(\mu(A) \geq \mu(B)\).
Definition. The multiset function \(f\) is said to be m-bijective if and only if \(f : A^{*} \rightarrow B^{*}\) is bijective and \(\mu(A) = \mu(B)\).
From here, we can define cardinality as usual with m-injectivity now. I again recommend reading the actual paper for more in-depth explanations regarding this. Some interesting things arise.
Example. Consider the multisets \(A = [a,b,c]_{1,1,1}\) and \(B = [x,y]_{2,1}\). There is a m-surjection but no m-injection, thus we say that \(\|A\| > \|B\|\).
Let us identify a bunch of new infinities. I will be notating slightly differently than in the paper.
Definition. Let \(\mathcal{M}_{1} = \|[1]_{\aleph_{0}}\|\). We write \(\mathcal{M}_{n+1} = \|[1]_{\mathcal{M}_{n}}\|\). More generally, define the function \(\mathcal{M}(S) = \|[1]_{S}\|\).
Theorem. \(\aleph_{0} > \mathcal{M}_{1} > \mathcal{M}_{2} > \mathcal{M}_{3} > \cdots > 1\).
Proof. We will first prove that \(\mathcal{M}_{n} > \mathcal{M}_{n+1}\), and then prove \(\mathcal{M}_{n} > 1\). For the first claim, proceed by induction on \(n\). First, let us discuss \(\aleph_{0}\), which can be thought of as \(\mathcal{M}_{0}\). We can easily realize that \(f : \mathcal{M}_{1} \rightarrow \aleph_{0}\) is m-injective (there is an injection upon the root sets and the multiplicities are equal), but not m-surjective (the root sets do not admit a surjection). We just need to show that \(f : \mathcal{M}_{n+2} \rightarrow \mathcal{M}_{n+1}\) is m-injective but not m-surjective given \(\mathcal{M}_{n} > \mathcal{M}_{n+1}\). The mapping on the root sets are just singleton to singleton, which obviously exists. Realize that \(f\) must be m-injective because \(\mathcal{M}_{n+1} < \mathcal{M}_{n}\) (by the induction hypothesis), so the multiplicity is less as desired. Now we need to show that \(\mathcal{M}_{n} > 1\) generally. Again, proceed inductively. The base case is trivial, and \(\mathcal{M}_{n+1} = \|[1]_{\mathcal{M}_{n}}\|\), in which \(\mathcal{M}_{n} > 1\) by induction hypothesis so \(\mathcal{M}_{n+1} > 1\). \(\Box\)
This theorem idea can be extended to more general \(S\).
We have essientally identified an infinity that is somehow less than \(\aleph_{0}\) but still nonetheless an infinity. Such idea of course makes no sense in the usual set theory. The paper then goes on to play around with rational and negative multiplicities. But the core idea is indeed the \(\mathcal{M}\) function,
I will now express a lot more of my own ideas.
The paper claims that De Morgan’s Law holds, but I believe this is false. The problem lies within the fact that \(\bar{A} = (A^{*}, -m_{A})\), so the root set is still the same. In the author’s proof of the De Morgan’s law, the root set becomes \(\bar{A^{*}}\), but this isn’t the case with our definition. Unless I am misunderstanding the concept of negative multiplicities. Consider \(A = [1,2]_{1,1}\) and \(B = [2,3]_{2,1}\). \(\bar{A \cup B} = [1,2,3]_{-1,-2,-1}\), and \(\bar{A} \cap \bar{B}\) is completely messed up. It should be \((A^{*} \cap B^{*}, \min(-m_{a},-m_{b}))\) as per our definition, but the root set is \(\{2\}\) while our multiplicity function tells us that there should be a \(-1\) involved with the elements \(1,3\). According to our definition, we should disregard those two which would give us \([2]_{-2}\). But if we allow it, then De Morgan’s Law appears to work (at least for the cases I checked, I could be wrong). Regardless, the definition is messed up. It seems that the concept of a root set is impeding our multiset definition, so perhaps we should simply define a multiset by the multiplicity function. So we would define as so:
Definition. A multiset \(A\) is a function \(m_{A} : U \rightarrow \mathbb{No}\).
I am a bit skeptical with the use of the surreals here, but I’m sure it is possible to make this work out. Alas, the concept of fuzzy multisets are inherently weird, especially in the infinite case. Perhaps a better way would just be sending members of \(U\) into the proper class \(\mathrm{Card}\), but we loose the fuzzy-ness and negative-ness of the multisets. To be fair, this is probably a better way to think of multisets as negative membership doesn’t make much sense in the first place.
Theorem. \(<\) is not a linear ordering of the M-Cardinals.
Proof. Consider the m-cardinal \(\kappa\) with the usual \(\aleph_{0} = \|\mathbb{N}\|\).3 We let the multiset \(S = [1]_{\aleph_{1}}\) with \(\kappa = \|S\|\). We claim there is no m-injection from \(S\) onto \(\mathbb{N}\), and vice-versa. There is an injection from the root set \(S^{*}\) onto \(\mathbb{N}\), but \(\mu(S) > \mu(\mathbb{N})\). It’s more hopeless for \(\mathbb{N} \rightarrow S\), there isn’t even an injection on the root sets. Hence \(\kappa \nleq \aleph_{0}\) and \(\aleph_{0} \nleq \kappa\). \(\Box\)
Despite not being linearly ordered, we still want to be able to analyze the m-cardinal structure since it leads to interesting ideas. So we will attempt to discern the structure of the m-cardinals. We can easily see that every M-Cardinal can uniquely be identified by an ordered pair \((a,b)\) where \(a\) is the cardinality of the root set and \(b\) is the multiplicity such that \((a,b) \leq (c,d)\) whenever \(a \leq c\) and \(b \leq d\) (as per the definition of m-injectivity).
Theorem. The M-Cardinals form a lattice.
Proof. Suppose we have two m-cardinals, \(\lambda = (a,b)\) and \(\kappa = (c,d)\). We claim that \(\xi = (a \wedge c, b \wedge d)\) works for the join element. When \(a,b,c,d\) are cardinals but not m-cardinals themselves, the \(\wedge\) simply is the \(\max\) between the two. So we sort of inductively build up for the join element. An analogous case is \(\vee\) and \(\min\) for the meet case. Essientally, we want \(\xi\) to be the least upper bound for \(\lambda\) and \(\kappa\). Therefore, \(\xi\) must be a least upper bound and the only least upper bound. It is easy to see \(\xi\) is a least upper bound. Let \(\gamma = (e,f)\). Suppose \(\gamma < \xi\). So \(e < a \wedge c\), which obviously results in a contradiction. A similar idea applies to prove that it is the only upper bound. So this completes the proof. \(\Box\)
With this new treatment of the M-Cardinals, we can easily prove many of the other theorems associated with M-Cardinals.
I argue that the trivial notion for m-cardinality, the multipicity \(\mu\), is a better formulation. The argument is as follows:
Argument. Consider a multiset \([a,b,c]_{2,3,1}\). We can think of this multiset as \(\{\{a_{1},a_{2}\},\{b_{1},b_{2},b_{3}\},\{c_{1}\}\}\). Let us unpack the elements to recieve \(\{a_{1},a_{2},b_{1},b_{2},b_{3},c_{1}\}\). Of course, we can recover the cardinality of the root set and the multiplicity. However, the only intuitive notion of size here is with the unpacked version. It makes no sense to consider both; only one. In which case it makes much more sense to check the multiplicity instead of the cardinality of the root set. There are 6 elements of \([a,a,b,b,b,c]\), not 3. So \(\mu\) is still a better measure.
All the weird behavior regarding M-Cardinals disappear with this interpretation, assuming we disregard fuzzy and negative multisets. In fact, there is now (trivially) a bijection that preserves order. Including these fuzzy multisets, there is now other weird behavior that arises (weird infinite sums such as \(1-1+1-1+1-1+\cdots\)). However, to my knowledge, there is no good way to get rid of this behavior.
Perhaps an abuse of notation, however functions will be treated like numbers in the sense that for functions \(f,g : X \rightarrow Y\), we say that for some function \(h : Y \times Y \rightarrow Y\), the notation \(h(f,g)\) denotes the same as \(h_{f,g} : X \rightarrow Y\) such that for every \(x \in X\), \(h_{f,g}(x) = h(f(x),g(x))\). ↩
As per the paper, \(m_{1}(a,b)\) denotes the count of first coordinate in the ordered pair. ↩
I identify \(\mathbb{N}\) to be the representative of \(\aleph_{0}\) purely for the sake of formality. Despite the naturals usually being considered a set, we can cast it to a multiset simply by having \(m\) send all elements to \(1\). ↩