According to Wikipedia if we assume AC we define a cardinals number to be an ordinal that is not in bijection with any smaller ordinal.

Without AC, one takes the cardinality of a set $X$ to be the set of all sets that are in bijection with $X$ and are of minimal rank.

Why does one need AC for the first definition?

Thank you for your help.


Abstractly, the cardinality of a set $X$ is an object $|X|$ such that given any two sets $X, Y$ the equality $| X | = | Y |$ holds iff $X \approx Y$ (there is a bijection between $X$ and $Y$). An object is called a cardinal if it is the cardinality of a set.

Now, some basic observations:

  • If a set $X$ can be well-ordered, then there is a least ordinal $\alpha$ such that $X$ admits a well-ordering of order-type $\alpha$.
  • If $X$ admits a well-ordering of order-type $\alpha$, then $X \approx \alpha$.
  • If $X \approx Y$, then $X$ can be well-ordered iff $Y$ can be well-ordered. Furthermore, in this case $X$ admits a well-ordering of order-type $\alpha$ iff $Y$ does.

From these observations it follows that if to each well-orderable set $X$ we define its cardinality $|X|$ to be the least ordinal such that $X$ admits a well-ordering of order-type $\alpha$, then within the class $\mathbf{WO}$ of well-orderable sets we have that $| X | = |Y|$ iff $X \approx Y$.

Now, if AC holds, then every set can be well-ordered, and the above gives an appropriate definition of cardinality of a set.

However, if AC does not hold, then there is some set $X$ which cannot be well-ordered. How should we then assign a cardinality to $X$? Note that if we assign $|X|$ to be some ordinal $\alpha$, then the biconditional $$|X| = |Y| \Longleftrightarrow X \approx Y$$ must fail for some set $Y$, namely the set $\alpha$: As $X$ cannot be well-ordered, $X$ cannot be equipotent with any ordinal, in particular $\alpha$. It follows that the above scheme of defining the cardinality of a set to be some ordinal cannot be continued in a manner consistent with the desired properties of the assignment.

  • $\begingroup$ Would it be correct to say that the essence of this answer is this: If we say: $$\{\alpha : \vert X\vert = \vert \alpha \vert\}$$ has a minimal element because of the well-ordering of $\mathbf{Ord}$, hence $$\vert W\vert =\text{least ordinal such that $\vert W\vert = \vert \alpha \vert$}$$ is well-defined without the axiom of choise. Then we have forgotten to take in to account that $$\{\alpha : \vert X\vert = \vert \alpha \vert\}$$ can be empty and only non-empty subsets of $\mathbf {Ord}$ must have a minimal element? $\endgroup$ – gebruiker Jun 9 '16 at 15:21
  • $\begingroup$ I upvoted your answer but it seems a bit difficient. It's obvious that can define cardinals as equivalence classes in NBG but maybe you should also state whether you can give a formal definition of a cardinal number in ZF just like math.stackexchange.com/questions/80159/… does for ordinal numbers and I think the answer is you can't find a formal definition that you can prove works. The axiom of choice is actually provable in NBG so maybe you were working in a weak version of NBG where it's not provable. $\endgroup$ – Timothy Jan 5 '18 at 23:56
  • $\begingroup$ My mistake. Your answer doesn't seem to answer the title of the question but does answer what the details of the question asks. Another question which actually asks what I thought this one asked already exists at math.stackexchange.com/questions/53770/…. $\endgroup$ – Timothy Jan 6 '18 at 0:35

The question is what does one try to achieve in the definition of "cardinal". This is the same as asking whether or not a partial order should be reflexive or not. Both answers depend on what you are trying to achieve.

When the axiom of choice is assumed every set can be well-ordered and therefore all the cardinals are ordinals anyway.

When the axiom of choice is not assumed, or when its negation is assumed [read: can be proved from the assumed axioms] then there are sets which cannot be well-ordered and their cardinal is defined by using Scott's trick.

Cardinal numbers are, in my opinion, numbers which represent the size of a set. We don't always have to have a deep and thorough grasp on how these things represent a size. But we want the notion to be coherent with how we think about addition, multiplication, and even exponentiation. Furthermore equicardinality means that the two sets have the same size.

Now comes the choice of the people working with the definition, which (as I remarked before) is similar to the choice of having zero as a natural number. Do you want cardinals to represent size, or do you want them to represent a well-ordered size? Both options are viable.

If one assumes that only well-ordered sets have cardinals then in some sense non well-ordered sets are like non-measurable sets (and the Hartogs and Lindenbaum numbers are like inner and outer measure). These sets become a pathology, and ignored whenever cardinality is discussed. But there is a big downside, cardinal exponentiation is not defined anymore, and even the real numbers may not have a cardinal. Even more, Cantor's theorem makes no sense because it involves cardinals of arbitrary sets and their power sets.

If one assumes that cardinals can be assigned for every set then one loses the simple and nice definition of addition and multiplication as "maximum". One might argue that infinite sums and products may no longer make sense, but that would be true even in the previous case.

Considering all the above, I prefer to assume all sets have cardinality rather than treating cardinality as a pathology.

To read more:

  1. Defining cardinality in the absence of choice
  2. There's non-Aleph transfinite cardinals without the axiom of choice?
  3. Non-aleph infinite cardinals
  4. Possible inaccuracy in Wikipedia article about initial ordinals

You can make the first definition whether you have AC or not, but without AC you cannot then guarantee that every set has a cardinality: only well-orderable sets will have one.

  • $\begingroup$ That's what I told Asaf yesterday. But then I looked at Wikipedia and it does say that one defines cardinals differently in the absence of choice. $\endgroup$ – Rudy the Reindeer Dec 14 '12 at 7:21
  • $\begingroup$ Then what I wrote in the linked comments is correct? (i) does not need AC? $\endgroup$ – Rudy the Reindeer Dec 14 '12 at 7:22
  • 2
    $\begingroup$ @Matt: Sure: any infinite Dedekind-finite set. $\endgroup$ – Brian M. Scott Dec 14 '12 at 7:40
  • 2
    $\begingroup$ @Brian: Do you mean like Pope Alexander VI? $\endgroup$ – Asaf Karagila Dec 14 '12 at 8:44
  • 1
    $\begingroup$ Oh! There was that Pope who was a pregnant woman. Surely that was one pathological cardinal... Besides, is the Pope a large cardinal? Thinking about it, I don't think I have any access to any cardinal at all. So in some way they are all inaccessible to me... $\endgroup$ – Asaf Karagila Dec 14 '12 at 21:31

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.