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 !
Equivalent formulations of Global Choice in NBG (without Foundation)
1 Answers
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:
(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$.
(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.
(CWO3) Every class can be well ordered
(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\}$.
-
0Thank 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. – 2011-09-08
-
0P.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. – 2011-09-08
-
0I have added some proofs to show that regularity is not needed. – 2011-09-08
-
0Thank 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.) – 2011-09-08
-
0How does the condition that every surjective functional class should have a right inverse fit in, for instance ? Kind regards - Stephan F. Kroneck. – 2011-09-08
-
0@bonnbaki: I don't have a keyboard to properly add new material to my answer. However Canotr-Bernstein holds for classes without Axiom E. There is such thread on MathOverflow, and I trust you could find it. – 2011-09-08
-
0@ Asaf Karagila: thanks for your comment concerning Cantor-Schröder-Bernstein; I haven't checked MathOverflow (yet), but as written, the question is actually irrelevant, of course, as one would expect all proper classes to be bijective copies of the class $On$ of ordinal sets (I'm just looking for a proof which avoids the whole ordinal machinery; cp. my other question concerning ordinal numbers). Due to your first answer, my interest is now in seeing a proof of the "class" Zorn ... Thank you again for your time and input ! Kind regards - Stephan F. Kroneck. – 2011-09-08
-
0@bonnbaki: It appears that you are trying *really* hard to avoid ordinals, it is a bit weird, in the sense that working in NBG you avoid a von Neumann construction. May I ask for the movitation for this? – 2011-09-08
-
0@bonnbaki: I tried to add a proof, and I hope it is for your liking. – 2011-09-09
-
0@ Asaf Karagila: Thank you very much ! I was interested mostly in the first direction - your proof follows the intuitive idea I've seen in some texts (in the set case), and no, I've got no problem with transfinite induction here in this case. Would you happen to know of any other equivalents ? Kind regards - Stephan F. Kroneck. – 2011-09-09
-
0@bonnbaki: The list I pointed you at is a very long list. I can only suggest you try and find a copy, or perhaps Google Books can let you peek into the few pages I suggested. – 2011-09-09