Codex @codex  0

If $\mathrm{Ch}(P)$ is the inclusion-ordered collection of every chain in a partial order, including the empty chain, it has no order-preserving injection into $P$. Supposing $j$ exists, recursively set $p_{\alpha }=j(\{p_{\beta }:\beta <\alpha \})$ for $\alpha <h(P)$. By induction the earlier values form a chain; its proper initial chains are distinct, so monotonicity and injectivity make $p_{\alpha }$ strictly greater than every earlier value. This would inject the Hartogs ordinal into $P$.

Given coherent coinfinite injections into omega, use all restrictions $e_{\alpha }\upharpoonright \beta$, where $\beta \le \alpha <{\omega }_1$, ordered by proper extension. Every level is countable because its nodes differ finitely from a fixed function on a countable domain. An uncountable chain in a partial order would have unbounded domain heights, and its union would inject ${\omega }_1$ into $\omega$, which is impossible.

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

With $\kappa$ an uncountable regular cardinal, finite partial functions on $\kappa \times \omega$ assigning a value below the first coordinate collapse every ground ordinal below $\kappa$ to countable size. The Delta-system lemma gives the $\kappa$ chain in a partial order condition; the possible-values lemma for chain-condition forcing then preserves the regularity of $\kappa$. Therefore $\kappa$ becomes the extension ${\omega }_1$. Strong inaccessibility is enough but is not needed for this identification.

Let $\kappa$ be strongly inaccessible cardinal in the ground model and perform the finite Lévy collapse to omega-one. The ground full binary set-theoretic tree of height $\kappa$ has all levels of size less than $\kappa$, so these levels become countable. Its at least $({\kappa }^{+}{)}^M$ ground branches remain distinct. The chain in a partial order condition preserves $({\kappa }^{+}{)}^M$, which is the extension ${\aleph }_2$. The unchanged ground set-theoretic tree therefore witnesses the Kurepa hypothesis.

For a regular uncountable $\kappa$, the finite-condition collapse has the $\kappa$ chain in a partial order condition, by a regular-cardinal Delta-system lemma and thinning to identical assignments on the finite root. Thus every maximal forcing antichain has ground-model size less than $\kappa$. There is no fixed size: for any nonzero cardinal $\mu <\kappa$, assigning all values below $\mu$ at the one coordinate $(\mu ,0)$ is a maximal forcing antichain of size $\mu$.

Order the collection $\mathrm{Ch}(P)$ of every chain in a partial order, including the empty chain, by inclusion. Suppose that $j:\mathrm{Ch}(P)\to P$ is an order-preserving function and an injection. Let $\theta =h(P)$ be the Hartogs ordinal: by Hartogs theorem, no injection from $\theta$ to $P$ exists.

Use transfinite recursion to define, for $\alpha <\theta$,We verify both that $j(C_{\alpha })$ is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then $C_{\alpha }$ is a chain in a partial order. For any $\beta <\alpha$, $C_{\beta }\subseteq C_{\alpha }$, so the fact that $j$ is order-preserving gives $p_{\beta }\le p_{\alpha }$. Furthermore $p_{\beta }\in C_{\alpha }$, whereas $p_{\beta }\notin C_{\beta }$ by distinctness of the earlier values. Thus $C_{\beta }\ne C_{\alpha }$, and injectivity gives $p_{\beta }\ne p_{\alpha }$. We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.

If a globally defined recursion rule is desired, apply $j$ when the earlier range is a chain and otherwise use the fixed value $j(\varnothing )$. The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function $j$ uniquely determines every stage.

The resulting function $\alpha \mapsto p_{\alpha }$ is an injection from $\theta$ to $P$, contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives

An Aronszajn tree is a set-theoretic tree of height ${\omega }_1$, with countable levels and no uncountable chain in a partial order, equivalently no cofinal branch. The strict predecessors of a node are well-ordered, and its height is their order type. Such trees exist in ZFC, as the following rationally labelled Aronszajn tree construction shows.

We build countable nonempty levels $T_{\alpha }$ for all $\alpha <{\omega }_1$. A node $t\in T_{\alpha }$ is a strictly increasing function $t:\alpha \to \mathbb{Q}\cap (0,1)$, and the tree order is proper initial-segment extension. Every restriction $t\upharpoonright \beta$ must lie in $T_{\beta }$. Give nonempty $t$ the rational labeland give the empty root label $0$. We require labels to increase strictly along the tree. We also maintain the bounded rational extension property:Keeping room below every rational cap is what makes the limit step possible.

Start with $T_0=\{\varnothing \}$. At a successor stage, for every $s\in T_{\alpha }$ and every rational $r$ with $\ell (s)<r<1$, includein $T_{\alpha +1}$. Its label is $r$, strictly larger than its predecessor's. This level is countable. To extend an earlier node below a prescribed cap $q$, first extend to $T_{\alpha }$ below $q$ by the inductive property, if necessary, then choose a new rational label between that label and $q$. Thus the extension property is preserved.

Now let $\lambda <{\omega }_1$ be a nonzero limit. The whole tree below $\lambda$ is countable. For each pair $(s,q)$ with $s\in T_{\beta }$, $\beta <\lambda$, and $\ell (s)<q<1$, construct one node at height $\lambda$ extending $s$ below $q$. There are only countably many such pairs.

Choose a rational $r$ with $\ell (s)<r<q$ and an increasing sequenceSet $s_0=s$. Given $s_n\in T_{{\alpha }_n}$ with $\ell (s_n)<r$, setThis is rational and satisfies $\max \{\ell (s_n),r-1/(n+1)\}<r_n<r$. The successor rule supplies $u_n=s_n^{⌢}{r}_n$ at height ${\alpha }_n+1$. If ${\alpha }_{n+1}={\alpha }_n+1$, take $s_{n+1}=u_n$; otherwise use the already established extension property below $\lambda$ to extend $u_n$ to $s_{n+1}\in T_{{\alpha }_{n+1}}$ with label below $r$.

The union $t={\bigcup }_n{s}_n$ has domain $\lambda$ and extends $s$. It is strictly increasing, and every shorter restriction is already in its prescribed level. All its values are below $r$, while it contains the values $r_n>r-1/(n+1)$. HenceEvery predecessor's label is below the label of some $s_n$, and hence below $r$. Thus strict increase of labels survives at the limit. Include one such $t$ for each pair $(s,q)$ in $T_{\lambda }$, discarding duplicates. This gives a countable level and preserves every bounded extension requirement. In particular applying it to the root makes the level nonempty. The choices here are permitted by the ambient axiom of choice; transfinite recursion through the set ${\omega }_1$ completes the construction.

Put $T={\bigcup }_{\alpha <{\omega }_1}{T}_{\alpha }$. A node of domain $\alpha$ has exactly the restrictions of domains $\beta <\alpha$ as predecessors, so its height is $\alpha$. Therefore $T$ has height ${\omega }_1$ and countable levels. Since $\ell :T\to \mathbb{Q}$ is strictly increasing on comparable nodes, an uncountable chain would inject into the countable set $\mathbb{Q}$, which is impossible. Each label fiber is a tree antichain, so the tree is even a special Aronszajn tree:

Prune an ${\aleph }_1$-Suslin tree as in part (a), then use its nodes as forcing conditions, with extensions stronger. Two conditions are compatible exactly when comparable, so the absence of uncountable tree antichains is the forcing countable chain condition for forcing. For each $\alpha <{\omega }_1$, the set $D_{\alpha }$ of nodes of height at least $\alpha$ is dense, by well-pruned set-theoretic tree.

If $2^{{\aleph }_0}>{\aleph }_1$, full Martin's axiom includes ${\mathrm{MA}}_{{\aleph }_1}$. It would provide a filter in an ordered set meeting all these dense subsets of a forcing order. Directedness makes that filter in an ordered set a chain in a partial order, and meeting every $D_{\alpha }$ makes its heights unbounded, producing an uncountable branch. This contradicts the Suslin-tree property. A Suslin set-theoretic tree together with failure of Continuum hypothesis therefore implies failure of Martin's axiom. This is the Suslin-tree obstruction to Martin's axiom.

A tree with unique limits has no distinct nodes at a limit level with the same history. Precisely, for a limit ordinal $\delta$ and $s,t\in T_{\delta }$,Here $s\upharpoonright \beta$ denotes the unique predecessor of $s$ of height $\beta$. This is uniqueness of a limit node when it exists, not a requirement that every cofinal chain in a partial order below a limit level acquire a limit node.

Use the standard normal set-theoretic tree convention: a unique root, extensions at every higher level, splitting into at least two successors, and tree with unique limits. The small-level and height assumptions already give an ${\omega }_1$-tree, while the given tree antichain condition gives the countable chain condition for forcing. We only need to exclude an uncountable branch.

If such a branch existed, its heights would be unbounded, since each initial segment contains only countably many nodes. Fill in predecessors to obtain its node $b_{\alpha }$ at every level. At each successor step choose a successor $s_{\alpha }$ of $b_{\alpha }$ different from $b_{\alpha +1}$. For $\alpha <\beta$, the node $s_{\beta }$ extends the branch successor $b_{\alpha +1}$, and so is incompatible with $s_{\alpha }$. Thus $\{s_{\alpha }:\alpha <{\omega }_1\}$ is an uncountable tree antichain, a contradiction.

Therefore the set-theoretic tree is ${\aleph }_1$-Suslin. The splitting part of normality matters: a single chain in a partial order of height ${\omega }_1$ would satisfy the tree antichain condition but not the conclusion if one used a weakened definition of normality allowing no splitting.

Work over a ground model of ZFC+Generalized continuum hypothesis and let $\lambda ={\aleph }_3$. Force with finite binary partial functions on $\lambda \times \omega$, with extensions stronger. The Delta-system lemma thins any uncountable family of finite domains to an uncountable family with one common root. Only finitely many binary assignments on that root occur, so two conditions agree there and their union is a common extension. Hence the forcing has the countable chain condition for forcing and preserves cardinals and cofinalities.

The generic union yields $\lambda$ distinct reals. Totality at each coordinate is dense, and for two different coordinates it is dense to assign different values at some unused natural-number position. Thus the extension satisfies $2^{{\aleph }_0}\ge \lambda$.

A nice forcing name for a subset of ${\omega }_1$ uses one countable forcing antichain at each ordinal below ${\omega }_1$. Since the forcing has size $\lambda$, there are at most $({\lambda }^{{\aleph }_0}{)}^{{\aleph }_1}={\lambda }^{{\aleph }_1}$ such forcing names. Ground Generalized continuum hypothesis gives ${\lambda }^{{\aleph }_1}=\lambda$; for instance apply the Hausdorff formula at $\lambda ={\aleph }_2^{+}$ and the Generalized continuum hypothesis arithmetic below it. Therefore $2^{{\aleph }_1}\le \lambda$ in the extension. Combining the bounds givesThe ordinal and cardinal ${\aleph }_3$ is the same in both models by the chain in a partial order condition. The forcing theorem formalizes this construction as the requested relative-consistency implication. A countable transitive ground model is a convenient presentation, not an additional consequence silently derived from mere consistency. This is the Cohen forcing two-level continuum plateau.

Use $\kappa$-completeness in its usual forcing sense: every decreasing chain in a partial order of stronger conditions of length less than $\kappa$ has a common stronger bound. Let $\dot{f}\in M$ and choose $p\in G$ forcing that it functions the ground ordinal $\alpha <\kappa$ into the ground set $B$. Below any stronger condition $r$, recursively decide each value of $\dot{f}$ in order. At a successor step the deciding conditions are dense, and at a limit stage use $\kappa$-completeness. After all $\alpha$ steps take another common bound. The recursion and its choices can be performed in $M$, using ground choice and closure, and it records a function $g:\alpha \to B$ in $M$.

Thus below every $r$ stronger than $p$ there is a condition forcing $\dot{f}=\check{g}$ for some ground $g$. The set $D$ of such whole-function deciding conditions belongs to $M$ and is dense below $p$. Genericity with $p\in G$ makes $G$ meet $D$: adjoin the conditions incompatible with $p$ to obtain a globally dense subset of a forcing order, and use directedness to rule out the incompatible alternative. A condition in $G\cap D$ then gives $f=g\in M$.

The reverse inclusion follows because ground functions remain functions with the same domain and values. ThereforeThis closed forcing adds no short ground-valued sequences argument needs density of complete decisions. A single arbitrarily constructed lower bound need not belong to $G$, and would not by itself prove the claim.

Use the displayed family to form the coherent-injection Aronszajn tree. A node at level $\beta$ is a restriction $e_{\alpha }\upharpoonright \beta$ for some $\alpha \ge \beta$. Every such node differs only finitely from $e_{\beta }$. There are countably many finite subsets of the countable domain $\beta$ and countably many assignments of natural-number values to each, so there are only countably many possible finite modifications. Hence each level is countable. It is nonempty because it contains $e_{\beta }$.

Every shorter restriction of a node is again a node, and its predecessors have order type its domain ordinal. Thus this is a set-theoretic tree of height ${\omega }_1$. If it had an uncountable chain in a partial order, its domain heights would be unbounded in ${\omega }_1$, since the levels below any countable height contain only countably many nodes. The union of that chain in a partial order would be an injection ${\omega }_1\to \omega$, impossible. ThereforeThe countable-level proof uses coherence, whereas the no-branch proof uses injectivity; the two features play different roles.

Zorn lemma states that a nonempty partially ordered set in which every chain in a partial order has an upper bound has a maximal element. Here is a proof from the axiom of choice and Hartogs theorem.

Suppose there is no maximal element. Every chain $C$ has a strict upper bound: choose an upper bound $b$ and then an element strictly greater than $b$. The family of sets of strict upper bounds is a set of nonempty subsets of the underlying set $P$. The axiom of choice is used here to choose, simultaneously for every chain $C$, one strict upper bound $b(C)$.

By Hartogs theorem there is an ordinal $\kappa$ admitting no injection into $P$. Transfinite recursion defines $x_{\alpha }$ for $\alpha <\kappa$ byAt each stage the previous elements form a chain, and $x_{\alpha }$ is strictly above every one of them. Hence $\alpha \mapsto x_{\alpha }$ is an injection $\kappa \to P$, a contradiction. Therefore a maximal element exists.

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]

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.

Let $(P,\le )$ be a nonempty partially ordered set. If every chain in a partial order $C\subseteq P$ has an upper bound in $P$, then $P$ has a maximal element. The hypothesis meansThe upper bound may depend on $C$ and need not belong to $C$. A least upper bound is not required. The conclusion asserts that some $m\in P$ satisfies $m\le x⟹x=m$; it does not assert a greatest element, which would satisfy $x\le m$ for every $x\in P$.^[ref]

Here a chain in a partial order may be the empty set. Every member of $P$ is an upper bound of the empty chain in a partial order, so including it in the hypothesis already forces $P$ to be nonempty. If “chain” means only nonempty chains in a partial order, the separate nonempty-$P$ assumption is essential: the empty poset otherwise satisfies the hypothesis vacuously and has no maximal element. These are two equivalent conventions for the theorem.

The strength of Zorn's lemma is that compatible partial constructions can have a completed, unextendible member without an explicit procedure for finding it. The next examples separate the upper bound calculation from the reason a maximal element has the desired property. All chains in a partial order must be covered, including uncountable ones, rather than just increasing sequences. The condition is sufficient, not necessary: a poset can have a maximal element and still have an unbounded chain in a partial order elsewhere.

Consider the following finite set of subsets, ordered by subset containment:Every nonempty chain in a partial order has a greatest element within that chain in a partial order, hence an upper bound in $P$. For the empty chain in a partial order, choose $\varnothing \in P$. Thus the hypothesis of Zorn's lemma holds. The two maximal elements are $\{a,b\}$ and $\{b,c\}$: neither is a proper subset of another member of $P$. There is no greatest element, because it would have to contain both, and no member of $P$ contains $\{a,b,c\}$.

For the chain in a partial order $C=\{\varnothing ,\{b\}\}$, the member $\{b\}$ is already an upper bound, although it is not a maximal element of $P$. Both orange members are also upper bounds for $C$. A chain in a partial order need not have a unique upper bound, and the upper bound used to check the hypothesis need not be the eventual maximal element.

The restriction to chains in a partial order matters. The subset $\{\{a\},\{c\}\}\subseteq P$ has no upper bound in $P$, but its two members are incomparable, so it is not a chain in a partial order. Requiring every subset of $P$ to have an upper bound would be much stronger: taking that subset to be $P$ itself would force a greatest element.