Let $C = \{0, 1, 2, \ldots, \aleph_0, \aleph_1, \aleph_2, \ldots\}$. What is $\left|C\right|$? Or is it even well-defined?
$\begingroup$
$\endgroup$
6
-
10$\begingroup$ It's not well-defined (like "cardinality of the set of all sets" etc). $\endgroup$– Grigory MCommented Aug 3, 2010 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 HiltonCommented Aug 4, 2010 at 13:10
-
$\begingroup$ @Affan: You could just ask a question. $\endgroup$– kennytmCommented Aug 4, 2010 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 HiltonCommented Aug 4, 2010 at 14:02
-
5$\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 MCommented Aug 4, 2010 at 14:15
|
Show 1 more comment
4 Answers
$\begingroup$
$\endgroup$
11
$C$ is not a set—it is, in fact, 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.
answered Aug 3, 2010 at 20:01
-
6$\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$– SamuelCommented Aug 3, 2010 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$ Commented Aug 3, 2010 at 21:33
-
2$\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$ Commented Aug 3, 2010 at 21:40
-
5$\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$ Commented Aug 4, 2010 at 19:39
-
2$\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$ Commented Apr 18, 2014 at 4:46
$\begingroup$
$\endgroup$
2
This is "Fact 20" on page 10 of
http://alpha.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.
answered Aug 3, 2010 at 23:20
-
$\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$– JoriCommented Nov 3, 2016 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$– mmwCommented Dec 6, 2016 at 14:24
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
4
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).
-
$\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$ Commented Aug 4, 2010 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$ Commented Aug 5, 2010 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$– SamuelCommented Aug 5, 2010 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$ Commented Aug 5, 2010 at 14:46