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.

Recently I was looking for various formulations of strong Global Choice in NBG (not assuming Foundation, necessarily), apart from the existence of a well-ordering on the universe or the guarantee of a class of representatives of a given relational class (under Foundation these are well-known to be equivalent to weak Global Choice, which demands the existence of a universal choice or selection functional class). In the same vein, are there "class" versions of "Zorn"'s Lemma, the Knaster-Tarski and Bourbaki-Kneser Theorems ? Any help or insightful comments would be appreciated !

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Rubin H., Rubin, J.E. Equivalents of the Axiom of Choice, II North-Holland, 1985 pp.271-278 "Class Forms"

Some examples from the list:

  1. (CAC1) If $S$ is a class of non-empty sets then there is a function $F$ that for every $x\in S$, $F(x)\in x$.

  2. (CM1) If $R$ is a partial ordering relation on a non-empty class $X$ and if every subclass of $X$ which is linearly ordered by $R$ has an $R$-upper bound, then $X$ has an $R$-maximal element.

  3. (CWO3) Every class can be well ordered

  4. (CWO1) There exists a function $F$ such that for every $x$, $F(x)$ well orders $x$.

It goes on, of course, and has many generalizations of known choice equivalences to class form.

Axiom E: There is a function $F$ such that $F(x) \in x$ for every non-empty set $x$. (Taken from Jech, T. Set Theory Springer, 2003 p.70)

  • Obviously CAC1 implies E, since $V\setminus\{\varnothing\}$ is a non-empty class. In the other direction, simply take $F\cap (S\times V)$, which is a function from $S$ into the elements of $S$.

  • As well CWO1 implies E in a pretty clear manner. In the other direction, note that E implies AC for sets, therefore we can well order every set in $V$. We can define a function $x\mapsto\{f\colon x\to|x|\Big| f\ \text{ bijection}\}$, and the choice would choose one well ordering from the range of this class. Therefore if we can choose, we can choose a well ordering.

(Due to lack of time at the moment I will add the proof for CAC1 equivalent to CM1 (Zorn's lemma for classes) later.)

  • Assume CWO1, and let $(A,R)$ be a partially ordered class, that every $R$-chain in $A$ has an upper bound. By CWO1 the class $A$ can be well ordered, denote such well ordering as $<$, without the loss of generality the order type is $\operatorname{Ord}$. Let $x\in A$, then $C_0=\{x\}$ is a chain in $R$, take the $<$-least element which is an upper bound for $C_0$. By transfinite induction, carry on in making the chains longer and longer.
    Suppose by contradiction that there is no maximal element, then $R$ has an unbounded chain of length $\operatorname{Ord}$, in contradiction to the fact every chain is bounded.

  • In the other direction, suppose CM1. Let $A$ be the class of choice functions, and $f\le g$ if $f\subseteq g$. Let $C$ be a chain in $<$, note that $C$ defines a function. If $\operatorname{Dom}(C)\neq V\setminus\{\varnothing\}$, then there is some non-empty $x\in V\setminus C$. Then $\bigcup C\cup\{\langle x,y\rangle\}$, for some $y\in x$ is an upper bound for $C$. (while $\bigcup C$ is not literally defined, it can be easily written as the $\lbrace y\mid\exists z\in C(y\in z)\rbrace$). Therefore there exists a maximal element in $A$, which is a choice function on $V\setminus\{\varnothing\}$.

share|improve this answer
    
Thank you already, Asaf Karagila: (CAC1) is, of course, the weak form (Gödel's axiom E, I believe), and only known to be equivalent to the strong in case one has regularity (as mentioned); (CWO1) it seems to me, would fall into the same category (weak form), and I believe I mentioned the well-ordering principle (CWO3) (which is indeed equivalent to the strong version), which only leaves (CM1), i.e. a class version of Zorn (et al.). As I don't have access to a copy of Rubin/Rubin's book at present, could you enlighten me as to how Zorn is proven in this case ? Kind regards ! Stephan F. Kroneck. –  bonnbaki Sep 8 '11 at 9:43
    
P.S. My problem is that in all the derivations of Zorn's lemma in set form that I know of, one cannot get around forming power sets in one way or other (be it using the Bourbaki-Kneser fixed point theorem for completely ordered posets, or Kneser's proof), clearly not an option for classes. In truth, what is neede is the ability to form the union (of a self-indexed) class of classes. Or is there some trick in finding the correct predicative description of the class required in the respective proofs ? Kind regards ! Stephan F. Kroneck. –  bonnbaki Sep 8 '11 at 9:49
    
I have added some proofs to show that regularity is not needed. –  Asaf Karagila Sep 8 '11 at 10:19
    
Thank you again, Asaf Karagila ! As mentioned in my original question and the follow-up, I am aware of the relationships between conditions (CAC1), (CWO1) and (CWO3) (no problem proving that); new to me is only (CM1) (which I've been trying to prove on my own, but see aforementioned snags; which, by the way, I also encounter when trying to generalize the Knaster-Tarski fixed point theorem to classes, in hope providing a simple proof of Schröder-Bernstein for classes, despite the moot nature of this result). (ctd.) –  bonnbaki Sep 8 '11 at 11:45
    
How does the condition that every surjective functional class should have a right inverse fit in, for instance ? Kind regards - Stephan F. Kroneck. –  bonnbaki Sep 8 '11 at 11:49
show 6 more comments

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.