How Do we Know the Cardinality of a Set?

Question

I recently had a discussion in a comment section here about the cardinality of the empty set. He claimed that cardinality to equal zero. I claimed that we didn't know such. My claim merely came as that people just assume the empty set to have zero cardinality. As far as I can tell we only know about the cardinality of a set, because of a bijection, a surjection, or an injection. I do not see how we can have any function either from or to the empty set, since it does not have any members. How do we know the cardinality of a set?

Added question:

Some of the answers here talk about the axiom of choice and other principles, which as far as I can tell from the arguments made, constructivist mathematicians do not accept. How would a constructivist go about evaluating the cardinality of the empty set, or does that not come as possible?

The empty set is itself a function. Edit: and itself a cardinal, if I'm not mistaken. — Git Gud, Sep 16 '13 at 16:40
Can you give your definition of carnality ? For finite sets I use the definition of how many elements are in the set, in the case of empty set it's $0$ — Belgi, Sep 16 '13 at 16:46
@Belgi And how do you know how many elements are in a set? I find that definition very ambiguous. A cardinal number is an ordinal number that isn't equinumerous to any ordinal number inferior to itself. Having established this the cardinality of a set can be defined as the only cardinal that is equinumerous to the given set. — Git Gud, Sep 16 '13 at 16:49
@GitGud - I studied only basic set theory, since the question was tagged as such I explained it in the way it was explained to me. I realize this isn't very good as a definition, but I hoped it would of helped the OP — Belgi, Sep 16 '13 at 16:55
A set has cardinality $\ge1$ if and only if it has a member. Ergo $\varnothing$ has cardinality $0$. — anon, Sep 16 '13 at 23:58
@anon From your statement I only infer that the empty set does not have cardinality greater than 1. You'd need an argument that shows that if a set has a cardinality less than 1, then it will have cardinality 0 for your argument to go through to completion. — Doug Spoonwood, Sep 17 '13 at 00:10
@anon There is no definition of cardinality in general, unless you have a predetermined notion of what it means for an element to belong to a set. Consider a universe of discourse such as {1, 3, 5, 6} and a subset {(1, .2), (3, 1), (5, .4), (6, 0)} :=A, where ".2" "1" and ".4" indicate the values of the membership function. One notion of cardinality for a fuzzy subset A implies that A has cardinality of 1.6. Set A still has at least 3 elements. Thus, the notion of cardinality I consider as relative to a function of some sort. But, the empty set has no subsets other than itself. So... — Doug Spoonwood, Sep 17 '13 at 02:47
either the notion of a characteristic function for evaluating classical sets breaks down at some point (I don't see how it breaks down for infinite sets), or the empty set has no cardinality at all. All the arguments I've seen here seem rather indirect. The characteristic function way of evaluating the cardinality of sets does come as direct. I don't see how it breaks down. Consequently, at least so far, I remain convinced that the concept of cardinality simply does not apply to the empty set in any proper sense. We can still assume it equal to 0, but I see no way to prove it properly. — Doug Spoonwood, Sep 17 '13 at 02:51
This isn't the first time you've taken evasive maneuvers to a different arena with different rules so you can comment on straw issues that don't apply to the original context as part of a broader contrarian campaign to feign dumb about basic concepts. Oh well, I don't know what I expected. I'll leave you to your whatever you're actually trying to do. — anon, Sep 17 '13 at 03:08
@anon I assure you I'm not feigning. I believe that either the arguments in the answers below make subtle errors (perhaps by assuming certain equivalences without understanding the precise conditions between them) in reasoning or it comes as inconsistent to accept the cardinality of the empty set as 0 on the basis of constructivist principles. Either way, the hypothesis that the empty set does NOT have any cardinality at all remains in place. What consequences follow from that hypothesis? — Doug Spoonwood, Sep 17 '13 at 03:41
Since you want constructivist principles, etc., please write down in full the system that you are working in. This should include any non-classical logic laws (and the list of the ones omitted from classical logic as well); and what sort of axioms your set theory has (because talking about sets requires you to have some theory about sets from the start). Then it might be possible to give you a satisfactory answer. — Asaf Karagila, Sep 17 '13 at 09:30
@GitGud If there does exist such a thing as the empty set, I think it can viewed as a function between (a certain class of indicator) functions. — Doug Spoonwood, Sep 19 '13 at 01:43
@DougSpoonwood I'm afraid I can not discuss this with you. To me the existence of the empty set is an axiom and I'm sure you know this, So your objections are deeper than my knowledge. — Git Gud, Sep 19 '13 at 05:56
@GitGud Every assumption or axiom can get questioned. If the empty set qualifies as a function, and a function can get represented by a set of ordered pairs, then what I've written below in some sense shows you what the empty set with respect to a finite universe of discourse looks like. — Doug Spoonwood, Sep 19 '13 at 23:58
@AsafKaragila As I understand things, it isn't necessarily required to write down the full system to adhere to constructivist principles. If you can compute something, you've worked under constructivist principles. Some other people's answers here may have allowed a computation of cardinality for (an) empty set. I know my answer did allow such computations up to the point where I made argued via induction. Though, such an argument makes it clear that many more computations can get made. — Doug Spoonwood, Sep 20 '13 at 22:01
Doug, if your name is Nelson, then people probably know your axiomatic system. Sadly your name is Doug, so people don't know, and this means that you have to tell them what you are thinking about, otherwise it is impossible to guess. — Asaf Karagila, Sep 20 '13 at 22:05
@AsafKaragila I did tell them here, after I had thought of it. — Doug Spoonwood, Sep 21 '13 at 03:26

score 12 · Accepted Answer · answered Sep 16 '13 at 17:05

12

From a standard set-theoretic point of view:

The empty set, which in this answer I will (mostly) denote by $0$, is transitive and well-ordered by $\in$, so by definition it is an ordinal. If $\alpha\ne 0$ is an ordinal, then $0\in\alpha$, so $0<\alpha$, and $0$ is therefore the smallest ordinal. If $A$ can be well-ordered, the cardinality of $A$ is by definition the smallest ordinal $\alpha$ such that there is a bijection between $A$ and $\alpha$. Let $A=0$. Then $A\times 0$ is vacuously a bijection from $A$ to $0$, and $0$ is the smallest of all ordinals, so $|A|=0$, i.e., $|\varnothing|=0$.

answered Sep 16 '13 at 17:05

Brian M. Scott

616,228

Why the single use of $\varnothing$ instead of $0$ for the empty set? I don't mind either notation, but surely one should be consistent. – Ilmari Karonen Sep 16 '13 at 22:29
2

@Ilmari: Because Doug asked about the cardinality of the empty set, and at the end I wanted for absolute clarity to emphasize that it was indeed the empty set as we normally think of and represent it about which I had been talking right along. The question was sufficiently naïve that I thought it a good idea to do so. – Brian M. Scott Sep 16 '13 at 22:31

score 11 · Answer 2 · answered Sep 16 '13 at 17:40

11

While the second given with reference to ordinals are correct, here is one without them.

Recall that if the cardinality of $x$ is larger than the cardinality of $y$, then there is an injection from $y$ into $x$.

If the cardinality of the empty set is not zero, then it is at least $1$, meaning there is an injection from $\{1\}$ into the empty set. Call this injection $f$, therefore $f(1)\in\varnothing$ which is a contradiction. Therefore the cardinality of the empty set is indeed $0$.

answered Sep 16 '13 at 17:40

Asaf Karagila

393,674

2

Eh? If it's not zero, then it's at least one? Where's that coming from? What are zero and one without ordinals? – dfeuer Sep 16 '13 at 18:51
3

Oh lord, how did generations of mathematicians used the natural numbers and compared sizes before the ordinals??? :( – Asaf Karagila Sep 16 '13 at 18:56
1

The OP is, after all, asking how to prove that the empty set has $0$ elements.... – dfeuer Sep 16 '13 at 19:36
I forgot, after all, that Cantor invented sets and "zero". Oh, wait, von Neumann invented zero. But Zermelo invented the empty set... :| – Asaf Karagila Sep 16 '13 at 19:39
1

From the "keep it simple" perspective: "The empty set has no elements. That is, it has $0$ of them. In fancy words, its cardinality is $0$". – dfeuer Sep 16 '13 at 20:23
I do NOT see how it follows that if the cardinality of the empty set is not zero, then it comes as equal to at least 1. It seems to me that it could have just not have cardinality at all. I see no reason to assume that every set has cardinality. That all said, at least this proof is very clearly not a constructive one. Also, if you assume every set has cardinality, and we have a linear ordering for the cardinality of sets, I do think your argument works. – Doug Spoonwood Sep 17 '13 at 03:57
1

@Doug: If you want a complete answer then you will have to write what is your definition of cardinality. Generally speaking, cardinality is just an equivalence relation on sets. So every set must have a cardinality. – Asaf Karagila Sep 17 '13 at 06:18

goblin GONE · Answer 3 · 2013-09-17T00:28:46.047

5

The usual definition of a function $f : X \rightarrow Y$ is: a relation $f \subseteq X \times Y$ such that for all $x \in X$ there exists unique $y \in Y$ such that $(x,y) \in f.$ Under this definition, there is a unique function $f : \emptyset \rightarrow Y$ for each set $Y,$ namely the empty relation.

Furthermore, we can define that a function $f : X \rightarrow Y$ is injective iff for all $y \in Y$, there is at most one $x \in X$ such that $(x,y) \in f$. Under this definition, the unique function $f : \emptyset \rightarrow Y$ is indeed injective.

Finally, I think a good definition of $X \lesssim Y$ is the existence of an injection $X \rightarrow Y$.

So, if you accept the above definitions, then you must agree that, since there is an injection $\emptyset \rightarrow Y$ for all sets $Y$, thus by definition we have $\emptyset \lesssim Y$.

Now. Let $X \cong Y$ mean that there exists a bijection $X \rightarrow Y.$ You need to show the following.

$\lesssim$ is compatible with $\cong$
So too are the operations $\uplus$ and $\times,$ defined in the usual way.

If you've done that, you're nearly there! Let $|*|$ denote a function such that $X \cong Y$ iff $|X| = |Y|$, and enforce the definitions of order, addition and multiplication.

$$X \lesssim Y \iff |X| \leq |Y|$$

$$|X \uplus Y| = |X| + |Y|$$

$$|X \times Y| = |X| \cdot |Y|$$

This is legal because we proved compatibility with $\cong.$

Finally, after all that work, you can (and should) prove that an initial portion of the cardinal numbers satisfies the Peano axioms. To do this, you'll have to take $|\emptyset|$ as your $0.$ Furthermore, it shouldn't be too hard to show that no other choice will work, since after all we already know that $\emptyset \lesssim Y$ for every set $Y$, so in general we have $|\emptyset| \leq |Y|.$

edited Sep 17 '13 at 00:28

answered Sep 16 '13 at 16:53

goblin GONE

67,744

It seems to me that you're just defining equinumerosity or cardinality between sets, but I don't see how you're actually defining a cardinal. – Git Gud Sep 16 '13 at 16:55
@GitGud, the cardinal numbers can be viewed as the image of the $|*|$ function, which is any function such that $X \cong Y$ iff $|X|=|Y|$. Von Neumann's approach is the standard example of such a function. – goblin GONE Sep 16 '13 at 16:56
I understand now. But this is dependent on the function $|*|$. I prefer the approach I described in the comments to the question. – Git Gud Sep 16 '13 at 17:05
@GitGud, yes that's the standard approach, and for good reason. However, here's how I would phrase it. Assuming the axiom of choice, every set is well-orderable. So we can define $|X|$ as the least ordinal number $\alpha$ such that we can find a surjective function $f : \alpha \rightarrow X.$ We can then prove that $|X| = |Y|$ iff $X \cong Y$, which is the property we really need of $|*|$. – goblin GONE Sep 16 '13 at 17:12
@GitGud, regarding the non-uniqueness of $||$ as defined in my answer, a question I asked the other day is pertinent. If we can extend the universe as we please, then the uniqueness issue essentially disappears. The trick is, you dynamically extend with a class of cardinal numbers $\mathrm{Card}$ disjoint from $\mathrm{Set}$ and assert that $|| : \mathrm{Set} \rightarrow \mathrm{Card}$ and that $|X|=|Y|$ iff $X \cong Y$. – goblin GONE Sep 16 '13 at 17:53
@GitGud, lol. So wait, you like the idea of extending with a new class $\mathrm{Card}$? In my experience, mathematicians trained in a more classical school of thought generally don't like this idea. – goblin GONE Sep 16 '13 at 18:24
No, I like that you worry about this sort of thing. I prefer the classical idea. – Git Gud Sep 16 '13 at 18:26
"The usual definition of a function f:X→Y is: a relation f⊆X×Y such that for all x∈X there exists unique y∈Y such that (x,y)∈f. Under this definition, there is a unique function f:∅→Y for each set Y, namely the empty relation." I don't accept this definition. Suppose Y and X both the empty set. For all x∈X there does NOT exist a unique y∈Y. So, I don't see how the definition makes any sense. – Doug Spoonwood Sep 17 '13 at 14:43
@DougSpoonwood, presumably it depends on the background logic / axiomatic system. However, if we confine our discussion to classical first-order ZFC, everything goes through as I've described. In particular, let $X$ and $f$ denote empty sets (no need to prove they're equal) and suppose $Y$ is fixed but arbitrary. We will show that $f$ is a function $X \rightarrow Y$. We need to check two conditions, namely that [0] $f \subseteq X \times Y$, and that [1] $\forall x \in X, \exists! y \in Y : (x,y) \in f$. – goblin GONE Sep 17 '13 at 16:03
Condition [0]. Suppose $p \in f$. Then since $f$ is empty, this entails a contradiction. But classical logic is subject to the principle of explosion, so its certainly true that $p \in X \times Y.$ Discharging, we have that $\forall p(p \in f \rightarrow p \in X \times Y)$, which is just longhand for $f \subseteq X \times Y$, as required. – goblin GONE Sep 17 '13 at 16:03
Condition [1]. We wish to show that $\forall x \in X ,\exists ! y \in Y : (x,y) \in f.$ This is shorthand for $\forall x(x \in X \rightarrow \mbox{ something }),$ where the something is irrelevant. Now in general, $x \in X$ is false, since $X$ is empty. Thus the statement of interest is equivalent to $\forall x(\bot \rightarrow \mbox{ something })$. But in classical logic, false implies everything, or more precisely, $(\bot \rightarrow \mbox{ whatever })$ is equivalent to $\top$. So the statement of interest is just longhand for $\forall x \top,$ which is classical equivalent to $\top$. – goblin GONE Sep 17 '13 at 16:04
Of course, if you don't accept classical logic and/or ZFC, that's fine too. Perhaps in your favoured system, $\emptyset$ simply has no cardinality. – goblin GONE Sep 17 '13 at 16:06
@user18921 "But classical logic is subject to the principle of explosion" The principle of explosion can get formalized as CKpNpq. Since you have a contradiction, and since the rule of uniform substitution applies, I have the option of inferring the negation of the statement you've made also. That is, by the principle of explosion I can infer it is not the case that "p∈X×Y". It is thus not certainly true that "p∈X×Y", though you may infer it at such a point... – Doug Spoonwood Sep 17 '13 at 16:40
"But in classical logic, false implies everything, or more precisely, (⊥→ whatever ) is equivalent to ⊤ . So the statement of interest is just longhand for ∀x⊤, which is classical equivalent to ⊤ ." Sure, you can do that. But, in classical logic (⊥→ whatever), and that "whatever" can come as ⊥. Thus, in classical logic I can use a case-by-base analysis that you've given me to infer that the empty set has no cardinality at all. And thus since the case-by-case analysis can lead to a contradiction either way, I infer a contradiction from some unstated assumption. – Doug Spoonwood Sep 17 '13 at 16:42
@DougSpoonwood, I'm not sure I really get what you're saying. I mean sure, by the principle of explosion you can infer $p \notin X \times Y,$ and thus that $\forall p(p \in f \rightarrow p \notin X \times Y)$. So? It doesn't help us prove that $f \subseteq X \times Y$, so its not very helpful. – goblin GONE Sep 17 '13 at 17:01

rschwieb · Answer 4 · 2013-09-16T17:13:57.227

3

Cardinality is determined by an equivalence relation on sets, and the emptyset is also a set.

It just happens that the equivalence class of $\emptyset$ happens to have just one element, and the only function from $\emptyset\to\emptyset$ is an "empty function" (thinking of functions from $X\to Y$ as special subsets of $X\times Y$).

edited Sep 16 '13 at 17:13

answered Sep 16 '13 at 16:53

rschwieb

153,510

If the intent of the answer is to give something better than intuition, I don't think I follow. An equivalence relation is a binary relation on a set. Which set is this you're thinking about? – Git Gud Sep 16 '13 at 16:56
1

@GitGud - I think rschwieb means the relation that $A~B$ iff there exist a bijection between them, although it isn't defined on a set (but rather on the class (I think thats the term that I'm abusing here) of all sets) – Belgi Sep 16 '13 at 17:02
@Belgi That makes sense intuitively, but I don't know to formalize it exactly because we're dealing with a proper class. – Git Gud Sep 16 '13 at 17:04
Dear @GitGud : Belgi's description is what I mean. There is no real restriction against thinking of this as an equivalence relation on the class of sets. The Cartesian product of a proper class with itself can still be defined (it's just not a set is all) and you can still think about subclasses of it satisfying the axioms for an equivalence relation. – rschwieb Sep 16 '13 at 17:05
Yes, there is a restriction against equivalence relations being on proper classes. However, an equivalence relation can be a proper class, which is all you need here. – Brian M. Scott Sep 16 '13 at 17:06
@BrianM.Scott How do you define a relation in the context of proper classes? – Git Gud Sep 16 '13 at 17:07
@BrianM.Scott I don't see how your last sentence meshes with what your first sentence claims. Can you add details about what the restriction is? Thanks. – rschwieb Sep 16 '13 at 17:09
2

@GitGud: By a formula. In this case $x\sim y$ means the rather long, involved formula that expresses ‘there is a bijection between $x$ and $y$’. – Brian M. Scott Sep 16 '13 at 17:10
@BrianM.Scott Ah! Thanks. – Git Gud Sep 16 '13 at 17:11
@rschwieb: $|x|=|y|$ can be thought of as $\langle x,y\rangle\in\mathbf{EQ}$, where $\mathbf{EQ}$ is a relation on sets that is itself a proper class, but that’s an abbreviation for $\varphi_{\mathbf{EQ}}(x,y)$ for some formula $\varphi_{\mathbf{EQ}}(x,y)$ that says that there’s a bijection between $x$ and $y$. The point is that even if you think of it as a proper class, it’s a proper class of sets. There is no mechanism for forming a proper class of proper classes, which is what you’d need in order to have a relation on proper classes. – Brian M. Scott Sep 16 '13 at 17:15
Dear @BrianM.Scott : So it's fine to do this with a proper class of sets, but there are classes (not of sets) for which it is not OK? Maybe one can make some clever paradox otherwise? – rschwieb Sep 16 '13 at 17:22
There’s no mechanism in $\mathsf{ZF}$ (or, so far as I know, any of the other relatively standard axiomatizations) even for talking about a collection of proper classes. – Brian M. Scott Sep 16 '13 at 17:28
Dear @BrianM.Scott I'm still trying to see why a class of sets should be exceptional compared to other classes with regards to what we're doing :S – rschwieb Sep 16 '13 at 18:04
There are no other proper classes in any of the usual axiomatizations. Every class, proper or not, has only sets as elements. – Brian M. Scott Sep 16 '13 at 18:04
Dear @BrianM.Scott : That's what I thought, and why I was confused. But now I'm seeing that it looks like you meant the restriction is not on entities are used but on what is done. Is it that the "cross product" of the classes can't be formed? We're just not equipped with a way to make a collection of pairs of sets for a class of sets? Maybe this is where my intuition was breaking down about what can't be done for classes. – rschwieb Sep 16 '13 at 18:15
The restriction is on entities. If $x$ and $y$ are entities such that $x\in y$, then $x$ must be a set. – Brian M. Scott Sep 16 '13 at 18:38
Dear @BrianM.Scott : That was a yes/no question. Is that a "no you can't do cross products of classes because that would entail membership between things that aren't sets"? This is also a yes/no question. – rschwieb Sep 16 '13 at 19:16
There is no problem forming $A\times B$ for proper classes $A$ and $B$, but that doesn’t help you to form a relation on proper classes; it merely allows you to form a relation on sets that is itself a proper class. – Brian M. Scott Sep 16 '13 at 19:23
Dear @BrianM.Scott : Now that really has me flattened. What's the difference between a relation on sets and a relation on the proper class of sets? – rschwieb Sep 16 '13 at 20:52
That’s not what I was contrasting. You can form a relation on sets, even on a proper class of sets. You cannot form a relation on proper classes, i.e., one that relates proper classes to one another. (You can sometimes express an instance of a relation: for example, if in $\mathsf{ZF}$ you have proper classes $\mathbf{A}$ and $\mathbf{B}$ defined respectively by formulas $\varphi(x)$ and $psi(x)$, then $\varphi(x)\to\psi(x)$ can be thought of as expressing the relationship $\mathbf{A}\subseteq\mathbf{B}$.) – Brian M. Scott Sep 16 '13 at 21:04

How Do we Know the Cardinality of a Set?

4 Answers4