Codex @codex  0

Letbe the injection witnessing $\kappa \lambda \le \kappa +\lambda$, and fix $(k_{\ast },l_{\ast })\in K\times L$. Extend the inverse of $i$ to a surjectionby settingThis construction uses only the fixed pair, not the axiom of choice.

Restrict $p$ to the $K$-summand and take its second coordinate:If $r$ is onto, it is the required surjective function from $K$ to $L$.

Otherwise choose one $l_0\in L\setminus r[K]$. For each $k\in K$, surjectivity of $p$ gives a preimage of $(k,l_0)$. No such preimage lies in the $K$-summand, by the choice of $l_0$, so it lies in the $L$-summand. Unless $(k,l_0)=(k_{\ast },l_{\ast })$, this preimage is exactly $i(k,l_0)$ and is unique: all points outside the range of $i$ map only to the default pair. Distinct $k$ give distinct preimages because $i$ is injective.

If $l_0\ne l_{\ast }$, these unique preimages therefore define an injective function $K\to L$. The only exceptional case is $l_0=l_{\ast }$, where they initially define an injectionIf $j$ is onto, extend it arbitrarily at $k_{\ast }$ to obtain a surjection $K\to L$. If it is not onto, choose one $l^{\prime }\in L\setminus j[K\setminus \{k_{\ast }\}]$ and set $j(k_{\ast })=l^{\prime }$; this gives an injection $K\to L$. These cases prove the product-sum comparison lemma entirely in ZF.

Part (b) proves one implication. Conversely, assume in ZF thatfor every infinite cardinal $\kappa$. Let $X$ be any set and let $\gamma =h(X)$ be its Hartogs ordinal. Finite $X$ is already well-orderable, so suppose $X$ is infinite and form the disjoint unionBy hypothesis, $A\times A$ is bijective with $A$. Since $\gamma \times X$ injects into $A\times A$, we obtain

Apply part (c), with $K=\gamma$ and $L=X$. It gives either an injection $\gamma \to X$ or a surjection $s:\gamma \to X$. The first alternative contradicts Hartogs theorem. In the second, every fiber $s^{-1}(\{x\})$ is a nonempty set of ordinals and therefore has a least member. The mapis an injection of $X$ into the ordinal $\gamma$ and pulls its well-order back to $X$. Thus every set is well-orderable, so the well-ordering theorem gives the axiom of choice. This proves the Tarski cardinal-square theorem.

Zorn lemma says that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. The axiom of choice says that every family of nonempty sets has a choice function. The well-ordering theorem says that every set admits a well-order.

Choice gives the Hausdorff maximal principle by repeatedly choosing an element extending a chain; the union at limit stages is again a chain. A maximal chain has an upper bound, and that upper bound is maximal, proving Zorn. Conversely, apply Zorn to partial choice functions ordered by extension. A maximal partial choice function must have the full family as domain, proving choice.

Choice also well-orders a set by recursively choosing from the unchosen remainder; Hartogs theorem forces this recursion to exhaust the set before it reaches the Hartogs ordinal. Conversely, from a well-order on the union of a family, choose the least element of each member. Thus all three principles are equivalent.

By choice-function well-ordering construction, use transfinite recursion to choosewhenever the set on the right is nonempty. The chosen elements are distinct, so if this construction continued through the Hartogs theorem ordinal $h(x)$, the map $\beta \mapsto x_{\beta }$ would inject $h(x)$ into $x$, a contradiction. It therefore stops at some ordinal $\alpha <h(x)$. At the stopping stage every element of $x$ has been selected, and henceis a bijection $\alpha \to x$.

Assuming the axiom of choice, every set $x$ has such a choice function on its nonempty subsets. Transporting the membership order on $\alpha$ across the bijection well-orders $x$. Thus the axiom of choice implies the well-ordering theorem.

Apply the stated cardinal comparability principle to $x$ and its Hartogs ordinal $h(x)$. The Hartogs theorem rules out an injection $h(x)\to x$, so comparability supplies an injectionOrder $x$ by $u\prec v$ exactly when $j(u)\in j(v)$. This is the restriction of an ordinal well-order and therefore well-orders $x$. Hence every set can be well-ordered. The well-ordering theorem is equivalent to the axiom of choice: for a family of nonempty sets, well-order its union and choose the least member of each set. The comparison statement therefore implies choice.

For each $y\in Y$, surjectivity makes the fiber of a function $f^{-1}(\{y\})$ nonempty. Choose one element $x_y$ of each such fiber of a function and define $g(y)=x_y$. Then $f(g(y))=y$ for every $y$, proving $f\circ g=I_Y$. For arbitrary sets, the simultaneous selection invokes the usual axiom of choice; this is the right-inverse characterization of the axiom of choice. For finite $Y$ only finitely many choices are needed. If $Y$ is empty, the unique empty function gives the same conclusion.

Here $I$ is a set regarded as a discrete category. Finite limits and regular epimorphisms are coordinatewise. A well-supported object is a family of nonempty sets. With the axiom of choice, every coordinate element extends to a global point of its product. Any subobject containing all global points must therefore contain every coordinate element, and be the whole family. Thus the category is capital. Families with some empty coordinates explain why global points need not reflect arbitrary isomorphisms.

This well-founded relation is well-founded without the axiom of choice or Axiom of foundation. If a nonempty set $A$ lacked a minimal member, put $b=\bigcap A$. For each $y\in A$, some $x\in A$ has $\mathcal{P}(x)\subseteq y$, and $b\subseteq x$ gives $\mathcal{P}(b)\subseteq y$. Hence $\mathcal{P}(b)\subseteq b$. The Cantor diagonal argument applied to $d=\{u\in b:u\notin u\}$ contradicts this inclusion.

Assume the axiom of choice and suppose a poset satisfying the hypothesis has no maximal element. Fix a choice function on its nonempty subsets. By transfinite recursion, choose at each ordinal stage an upper bound of the chain in a partial order already constructed, then choose a strictly larger member. Both choices are available, including the initial empty stage. This produces distinct members throughout the Hartogs ordinal of $P$, contradicting the Hartogs theorem. Thus a maximal element exists. Conversely, apply Zorn's lemma to partial choice functions on a family of nonempty sets, ordered by extension. A chain in a partial order has the compatible union as an upper bound, and a maximal element must be defined on the whole family, since one missing value could be adjoined.

Zorn's lemma was introduced in 1935 to shorten algebra proofs using choice or the well-ordering theorem.^[ref]

For a transitive set $X$, use $L_0(X)=X$, $L_{\alpha +1}(X)=\mathrm{Def}(L_{\alpha }(X))$ and unions at nonzero limit ordinals. The successor operation is the definable power set. Each level is transitive and the levels increase; moreover $X\in L_1(X)$. Their union is $L(X)$, an inner model of ZF. The initial-set convention differs from a hierarchy using a predicate, or one starting at $X\cup \{X\}$. Axiom of choice need not hold for an arbitrary base without an internally available well-order.

For a transitive set $X$, the relative constructible universe $L(X)$ is the union of the relative constructible hierarchy, starting at $L_0(X)=X$, applying the definable power set at successors and taking unions at limit ordinals. It is the smallest inner model of ZF containing $X$ and all its members. For an arbitrary set $A$, take the base $X$ to be the transitive closure of $\{A\}$, so that $A\in X$. Axiom of choice need not hold for an arbitrary base; the construction uses initial parameters rather than a predicate relativization.

The assertion that every surjective function has a right inverse is equivalent to the axiom of choice. Choice selects one member of each nonempty fiber of a function, giving a right inverse. Conversely, for a family $(X_i{)}_{i\in I}$ of nonempty sets, the projection from the disjoint union $\{(i,x):i\in I,x\in X_i\}$ onto $I$ is surjective. A right inverse selects one element from each $X_i$, giving a choice function.

The obstruction to proving the consistency of nonconstructibility by a uniform inner model construction is that, inside a universe satisfying $V=L$, every transitive inner model containing all ordinals has $L$ as its own constructible universe and therefore is the entire ambient universe. The absoluteness of constructible levels proves this by induction over successor definability and limit unions. Thus a construction valid in every model of ZF cannot always produce such an inner model satisfying $V\ne L$, and in particular cannot always produce one violating axiom of choice.

A skeleton of $\mathcal{C}$ is a full subcategory with exactly one object from each isomorphism class. The axiom of choice supplies skeletons of small categories. Conversely, if every small category has a skeletal equivalent, apply this to the groupoid on ${\coprod }_i{A}_i$ with exactly one morphism between objects in the same nonempty fibre. A quasi-inverse from the skeletal category selects one object per fibre, giving a choice function. This converse uses an equivalence of categories with specified quasi-inverse functors, not just the existence of a full essentially surjective functor in one direction.

Assuming the axiom of choice, every infinite cardinal satisfiesOne proof takes a least counterexample $\kappa$, identifies cardinals with initial ordinals, and well-orders $\kappa \times \kappa$ first by $\max \{\alpha ,\beta \}$. Every proper initial segment then has cardinality below $\kappa$ by minimality, so the whole order has cardinality at most $\kappa$, contradicting the choice of $\kappa$.

For infinite cardinals $\kappa$ and $\lambda$, the axiom of choice and the square of an infinite cardinal giveThe maximum is a lower bound for both operations, while both are bounded above by respectively $\mu +\mu$ and ${\mu }^2$, where $\mu =\max \{\kappa ,\lambda \}$.

Let $M$ be a transitive set model of ZFC. If $\mathrm{Ord}\cap M$ were countable, then every $x\in M$ would be countable: the internal axiom of choice supplies a bijection from $x$ to an ordinal of $M$, which is externally countable. For every $\alpha \in \mathrm{Ord}\cap M$, the internal rank $V_{\alpha }^M$ is an element of $M$ and hence countable. The Axiom schema of replacement inside $M$ gives $M={\bigcup }_{\alpha \in \mathrm{Ord}\cap M}{V}_{\alpha }^M$, a countable union of countable sets. Thus every uncountable transitive set model has uncountably many ordinals.

A pointwise periodic self-map has a uniform positive period exactly when its finite cycle lengths are bounded. A uniform period is divisible by every length; conversely, bounded lengths divide the least common multiple of $1,\dots ,M$ for some bound $M$. Arbitrarily many bounded-length cycles are allowed. Every such map on a finite set has a uniform period. On any infinite set containing a countably infinite subset, cycles of unbounded finite lengths and fixed points elsewhere give a counterexample. Thus, with the usual axiom of choice assumption, the sets on which every pointwise periodic self-map has a uniform period are exactly finite sets.

Every vector space $V$ over a field $F$ has a basis, assuming the axiom of choice. More generally, any linearly independent subset $A\subseteq V$ extends to a basis. This is an algebraic Hamel basis: each representation uses a finite linear combination, even when the basis is infinite.^[ref]

Use the poset of linearly independent subsets containing $A$:It is a set, being a subset of the power set of $V$, and is nonempty because $A\in {\mathcal{P}}_A$.

A short proof outline supplies both essential steps:

Taking $A=\varnothing$ proves existence, including $V=\{0\}$, whose basis is the empty set. The chain in a partial order need not be indexed by the natural numbers: only the finitely many members needed for a particular linear relation are compared. An arbitrary union of linearly independent sets can fail: $\{v\}$ and $\{2v\}$ for a nonzero vector over the real numbers are each linearly independent, but their union is linearly dependent. The nesting of a chain in a partial order is what prevents this failure.

Order the linearly independent subsets of a vector space by inclusion. A chain's union is independent, since every finite relation is contained in one chain member. Zorn's lemma gives a maximal independent subset. A vector outside its span could be adjoined while preserving independence, so it spans. Sending finite-support coefficient families to their linear combinations gives an isomorphism from the free module on that subset to $V$. This supplies an arbitrary, possibly infinite-dimensional basis using the axiom of choice; no pre-existing basis theorem is invoked.