23
$\begingroup$

Let $C = \{0, 1, 2, \ldots, \aleph_0, \aleph_1, \aleph_2, \ldots\}$. What is $\left|C\right|$? Or is it even well-defined?

$\endgroup$
  • 8
    $\begingroup$ It's not well-defined (like "cardinality of the set of all sets" etc). $\endgroup$ – Grigory M Aug 3 '10 at 18:27
  • $\begingroup$ As a side question, does anyone have any useful links (read: not wikipedia and easy to read links) on what cardinality is? I see it come up everywhere and would like to read up on it. Thanks $\endgroup$ – Tyler Hilton Aug 4 '10 at 13:10
  • $\begingroup$ @Affan: You could just ask a question. $\endgroup$ – kennytm Aug 4 '10 at 13:52
  • $\begingroup$ It would probably just get voted to close because its a "broad" topic, something wikipedia could do for me. $\endgroup$ – Tyler Hilton Aug 4 '10 at 14:02
  • 4
    $\begingroup$ @Affan well, wikipedia really does explain what cardinality is; and if after reading it you have some more specific question(s), you can ask them on this site $\endgroup$ – Grigory M Aug 4 '10 at 14:15
21
$\begingroup$

C is not a set - it is infact a proper class. If C were a set, then |C| would be defined. It then follows that |C| would be the largest cardinality, since there is a total order between all the cardinalities, and $|C| > \kappa$ for every cardinality $\kappa$ (every cardinality is equivalent to the set of all smaller cardinalities). But $2^{|C|} > |C|$ and so there cannot be a largest cardinal.

$\endgroup$
  • 5
    $\begingroup$ "every cardinality is equivalent to the set of all smaller cardinalities" Are you not confusing cardinalities with ordinals? If by "equivalent" you mean "has the same cardinality", then aleph_1 is not equivalent to the set {0,1,2,...,aleph_0}. $\endgroup$ – Samuel Aug 3 '10 at 20:45
  • $\begingroup$ @Samuel, you're right, I've mixed up between the two. Still, C is not a set, because a set cannot contain itself (en.wikipedia.org/wiki/Axiom_of_regularity), and in such a case I'm not sure what |C| even means. $\endgroup$ – Tomer Vromen Aug 3 '10 at 21:33
  • 1
    $\begingroup$ In fact, one can prove that C is not a set even if one drops the axiom of regularity. The idea is that one can prove directly that for any ordinal a, a is not an element of a. Then one considers X = the union of all sets in C. One can show that X is an ordinal which contains itself, giving the contradiction. $\endgroup$ – Jason DeVito Aug 3 '10 at 21:40
  • 4
    $\begingroup$ Based on all of the above, I think @KennyTM should accept another answer. I've thought of deleting the answer, but I wouldn't want the discussion in the comments to disappear. $\endgroup$ – Tomer Vromen Aug 4 '10 at 19:39
  • 1
    $\begingroup$ The idea of trying to get a largest cardinal out of the assumption is the right idea, but you go wrong by considering $|C|$ instead of considering $|\cup C|$. To compare cardinalities you want to look at subsets, not at elements: $X\subset Y \Rightarrow |X| \le |Y|$, but $X\in Y \not\Rightarrow |X| \le |Y|$. We know from this that $|\cup C|$ would be the largest cardinal (since every cardinal is contained in $\cup C$ as a subset). But to get that $|C|$ itself would be the largest cardinal is much deeper, requires bringing in ordinals, and essentially amounts to developing $\aleph$-numbers. $\endgroup$ – Marcel Besixdouze Apr 18 '14 at 4:46
16
$\begingroup$

This is "Fact 20" on page 10 of

http://math.uga.edu/~pete/settheorypart1.pdf

These are notes on infinite sets from the most "naive" perspective (e.g., one of the facts is that every infinite set has a countable subset, so experts will see that some weak form of the Axiom of Choice is being assumed without comment. But this is consistent with the way sets are used in mainstream mathematics). It is meant to be accessible to undergraduates. In particular, ordinals are not mentioned, although there are some further documents -- replace "1" in the link above with "2", "3" or "4" -- which describe such things a bit.

But I don't see why it is necessary or helpful to speak of ordinals (or universes!) to answer this question.

Added: to be clear, I wish to recast the question in the following way:

There is no set $C$ such that for every set $X$, there exists $Y \in C$ and a bijection from $X$ to $Y$.

This is easy to prove via Cantor's diagonalization and it sidesteps the "reification problem for cardinalities", i.e., we do not need to say what a cardinality of a set is, only to know when two sets have the same cardinality. I believe this is appropriate for a general mathematical audience.

$\endgroup$
  • $\begingroup$ Would this document be a nice introduction for an undergraduate to some further set theoretical results beyond the simple results that are usually included in the undergraduate curriculum (such as "R is uncountable", "power sets have larger cardinality", etc.). If not, what would you suggest? I'm currently reading Kamke in my spare time. It's really nice, but rather old fashioned. $\endgroup$ – Jori Nov 3 '16 at 23:14
  • $\begingroup$ Thanks for those notes. They are very useful. It is hard to find expositions which don't just identify cardinals with ordinals (Levy is an exception). But pedagogically, it seems that the concept of cardinal should be distinguished from the concept of ordinal, since a set's having an ordinal implies its wellorderability. $\endgroup$ – mmw Dec 6 '16 at 14:24
7
$\begingroup$

The most common way to define the cardinal number $|X|$ of a set $X$ is as the least ordinal which is in bijection with $X$. Then $C$ is an unbounded class of ordinals, and any such is necessarily a proper class. Since $C$ is not a set, it does not have a cardinality.

$\endgroup$
1
$\begingroup$

I may be wrong but it seems that C is not a set of all sets or anything similar. It has IMHO a trivial bijection into $\mathbb{Z}$ and therefore into $\mathbb{N}$.

I haven't met any paradox to forbid $|C| \in C$ ($\{1\}$ is such set).

$\endgroup$
  • $\begingroup$ It should be noted that the C as defined above is not necessary a set of all cardinalities. If (CH)[en.wikipedia.org/wiki/Continuum_hypothesis] is false (i.e. not accepted as an axiom - it is neither provable nor disprovable in set theory) the C shown is not the all cardinalities. $\endgroup$ – Maciej Piechotka Aug 4 '10 at 21:42
  • $\begingroup$ I don't understand what this has to do with CH. If the Axiom of Choice holds, then every cardinal is an aleph. But even without this, the OP probably just means a class formed by taking one set of every cardinality, which can be seen not to be a set. Anyway, how do you get $\mathbb{Z}$ as an answer? $\endgroup$ – Pete L. Clark Aug 5 '10 at 2:19
  • $\begingroup$ I take it Maciej interprets $\{0,1,\ldots,\aleph_0,\aleph_1,\ldots\}$ to mean it contains $n$ and $\aleph_n$ for each natural $n$, whereas the original poster means it contains $\aleph_\alpha$ for each ordinal $\alpha$, that is, $C=\{|X|:X\text{ is a set}\}$, which is similar to a construction of a set of all sets in that it ranges over all sets. $\endgroup$ – Samuel Aug 5 '10 at 12:09
  • $\begingroup$ The $C = {|X|: X is a set}$ is indeed not correctly defined. However that's not the usual meaning of the $\ldots$. I assumed that the meaning is $C = {n: n \in \mathbb{N} \lor n = \aleph_n' \land n' \in \mathbb{N} }$. $\endgroup$ – Maciej Piechotka Aug 5 '10 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.