Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Thomas Jech, such as many other mathematicians, demonstrates $AC \rightarrow ZL$ via transfinite induction. He says:

Proof. We construct (using a choice function for nonempty sets of P), a chain in P that leads to a maximal element of P. We let, by induction, $a_\alpha =$ an element of P such that $a_\alpha > a_\beta$ for every $\beta < \alpha$ if there is one. Clearly, if $\alpha > 0$ is a limit ordinal, then $C_\alpha = \{a_\beta : \beta < \alpha \}$ is a chain in P and $a_\alpha$ exists by the assumption. Eventually, there is $\theta$ such that there is no $a_{\theta + 1} \in P$, $a_{\theta + 1} > a_\theta$. Thus $a_{\theta}$ is a maximal element of P.

I have a question regarding this demonstration: Under what argument does Jech justify the existence of $\theta$?

In another question, Asaf Karagila argues that this process of choosing and adding elements to the chain must stop because, otherwise, we would have an injection from the proper class of Ordinals to P. Why can't this be?, why can't we have an injection from a proper class to a set?

I'm sorry if this questions seem naive, I'm still quite immature in my mathematical knowledge.

share|improve this question
    
Proper classes are "too big to be sets". Since injections conserve size, a proper class can't be injected into a set. Leaving proper classes away, Pick an ordinal $\kappa$ whose cardinality is strictly greater than that of $P$. Then you can't inject $\kappa$ into $P$, and the process must hence stop before you reach $\kappa$. –  Daniel Fischer May 4 at 16:30
    
@DanielFischer Thanks, a lot. –  Miguelgondu May 4 at 16:31

1 Answer 1

up vote 4 down vote accepted

This is known as Hartogs theorem.

Every set $X$ has an ordinal $\alpha$ such that there is no injection from $\alpha$ into $X$.

In particular, it follows that there is no injection from the class of ordinals into a set.

The proof is not very difficult, but not quite trivial. It has been covered over this site several times. The idea is that you consider subsets which can be well-ordered, collect those of the same order type into equivalence classes, and construct a well-ordering which cannot be injected into $X$ itself. This well-ordering is a set, and therefore isomorphic to an ordinal.

But one can make other arguments, equally compelling.

Assume that there is an injection from the class of ordinals into $X$. Consider its range $Y$, then by separation $Y$ is a set. By replacement it follows that the class of ordinals is a set, which is a contradiction.

share|improve this answer
    
Sorry for asking this question this late, but why is it legal to consider a choice function that selects elements and builds them up in a chain? –  Miguelgondu Jul 25 at 14:46
    
I'm not sure what you mean by that. –  Asaf Karagila Jul 25 at 15:54
    
I'm not really talking about your answer but rather about Jech's demonstration. Why is it a valid construction?, is one allowed to consider such thing in ZFC?, why? –  Miguelgondu Jul 25 at 16:00
    
If you assume the axiom of choice, then given a family of non-empty sets, there exists a choice function for this family. So if we work in $\sf ZFC$ there is such choice function, and we can use one. –  Asaf Karagila Jul 25 at 16:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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