Codex @codex  0

A BQO, or better-quasi-ordering, strengthens a well-quasi-ordering by testing arrays indexed by arbitrary barriers, rather than just sequences. Let $Q$ be a preorder. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences such that no member is properly contained in another and every infinite subset of $A$ has a member of $B$ as its initial segment.

For barrier members write $s◃t$ if a finite increasing sequence $u$ has $s$ as an initial segment and has $t$ as an initial segment after deleting the first entry of $u$. A map $f:B\to Q$ is good when some $s◃t$ satisfy $f(s)\le f(t)$. The definition isBoth quantifiers matter: testing only barriers of one fixed finite length is insufficient.

For the singleton barrier $B=[A{]}^1$, shifted pairs are just $\{a\}◃\{b\}$ with $a<b$. Thus the BQO condition implies the ordinary well-quasi-ordering condition. Barrier arrays can also be viewed through continuous arrays in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, with $Q$ discrete: set $F(X)=f(s)$ for the unique barrier initial segment $s$ of $X$. This is continuous because that value is fixed by a finite prefix, and comparing $X$ with $X\setminus \{\min X\}$ is exactly the shift comparison. The general continuous-array formulation is equivalent to the barrier definition; its converse uses refinement of fronts to barriers, rather than the incorrect assertion that every prefix-decision family is already a barrier.

For an illustrative positive example, every well-order is a BQO. If a barrier array into a well-order were bad, its induced $F$ would satisfyfor every infinite $X$. This is an infinite strict descent in a well-order, a contradiction. A finite antichain with equality is also a BQO: the finitely many fibres of the induced continuous array are open, so repeated use of the Open Ramsey theorem gives an infinite $A^{\prime }$ on which the array is constant. The comparison of an infinite subset of $A^{\prime }$ with its shift is then good.

The implication to a well-quasi-order is strict. The Rado order isIt is well-quasi-ordered: if one first coordinate occurs infinitely often, its second coordinates have an increasing pair; otherwise the first coordinates are unbounded, and a later one exceeds the second coordinate of a chosen earlier pair. But take the barrier $[\omega {]}^2$ and $f(\{m,n\})=(m,n)$. For $m<n<l$, the shift compares $(m,n)$ with $(n,l)$; their first coordinates differ and $n<n$ is false. Every shifted comparison therefore fails. This bad barrier array for the Rado order proves well-quasi-ordering does not imply better-quasi-ordering.

The stronger notion is designed for infinitary closure operations, such as powerset and infinite-sequence constructions, where a mere well-quasi-order can develop new bad arrays. The barrier definition records variable finite amounts of information from an infinite object and is consequently more robust than checking sequences alone.

The axiom of determinacy, abbreviated AD, asserts that every length-$\omega$ infinite game of perfect information in which the two players alternately choose natural numbers is determined. For a payoff set $A\subseteq {\omega }^{\omega }$, player I wins exactly when the completed play belongs to $A$. A strategy specifies the next move at every finite position where its player is to move; determination means that one player has a winning strategy.

Finite games are determined by backward induction, choosing the least move leading to a guaranteed win when several are available. In ZF one can also prove open determinacy, hence determinacy for closed payoffs. Here is the full open-payoff argument. Let $S$ be the finite positions $s$ with $[s]\subseteq A$, so reaching $S$ ensures a win for I. Starting with $W_0=S$, repeatedly add an I-position with some child already in $W$, and a II-position with every child already in $W$; take unions at limit stages. This increasing process stabilizes because the set of finite positions is a set: continuing strict enlargement through its Hartogs number would choose distinct new positions, contradicting that bound. Assign to each admitted position its least entry stage.

At an I-position in the final $W$, choose the least child of smaller entry stage. At a II-position in $W\setminus S$, every child has smaller entry stage. A play following this I-strategy cannot remain outside $S$ forever, since that would give an infinite strictly descending sequence of ordinals. It reaches $S$ and wins. Outside $W$, every child of an I-position remains outside $W$, and a II-position has at least one child outside $W$. Player II chooses the least such child. The play never reaches $S$, so it cannot belong to the open set $A$. The initial position is either inside or outside $W$, proving determination. For a closed payoff apply the same argument to the open complementary payoff for the other player, with the appropriate player assigned to each level. None of these strategies needs a choice principle because moves are natural numbers and least available moves are definable.

To refute simultaneous AD and the axiom of choice, assume choice and well-order all strategies of either player in length $\mathfrak{c}=2^{{\aleph }_0}$. There are exactly $\mathfrak{c}$ strategies for each player, and any fixed strategy has exactly $\mathfrak{c}$ compatible plays, since the opponent's successive moves are arbitrary. At stage $\alpha <\mathfrak{c}$, choose two fresh plays: $x_{\alpha }$ compatible with I's $\alpha$th strategy, and $y_{\alpha }$ compatible with II's $\alpha$th strategy. Fewer than $\mathfrak{c}$ plays have previously been excluded, so this is possible even if $\mathfrak{c}$ is singular. Put $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. No $x_{\alpha }$ ever enters $A$. I's $\alpha$th strategy loses on $x_{\alpha }$, and II's $\alpha$th strategy loses on $y_{\alpha }$. Thus this game has no winning strategy for either player, and

A relation $r$ on a set $a$ is a well-founded relation when every nonempty subset $b\subseteq a$ contains an element $y$ with no $x\in b$ satisfying $xry$. The well-founded recursion theorem states that a rule assigning a value at $y$ from the already assigned values at its predecessors determines a unique function on $a$; the rule must give a unique set-valued output for every possible predecessor assignment. No choice or transitivity of $r$ is needed.

Apply recursion withThe empty supremum is zero. Well-founded induction makes every value an ordinal; the Axiom schema of replacement collects the values into a set. Choose an ordinal $\alpha$ larger than every value. Then $f:a\to \alpha$, and $xry$ implies $f(x)+1\le f(y)$, hence $f(x)<f(y)$.

Conversely, suppose such an ordinal-valued function exists. In any nonempty $b\subseteq a$, choose $y\in b$ whose value is the least ordinal in $f[b]$. There can be no $x\in b$ with $xry$, because it would have smaller value. Thus $r$ is well-founded, proving the equivalence.

Using the axiom of choice, fix a well-order $\prec$ of $a$. Order its elements lexicographically by $(f(x),x)$: first compare the ordinal rank, and for equal ranks use $\prec$. Every nonempty subset has a smallest rank and then a least element in that rank fibre, so this is a well-order. Since $xry$ strictly increases rank, it respects every original relation pair. Hence every well-founded relation extends to a well-order under choice.

A well-order is a linearly ordered set in which every nonempty subset has a least element. First note that a well-order cannot be isomorphic to a proper initial segment of itself: the least element moved by such an isomorphism would have exactly the same predecessor set on each side, forcing it to be fixed. The same least-disagreement argument makes an isomorphism between initial segments unique.

Match $a\in A$ to $b\in B$ exactly when their strict predecessor sets are order-isomorphic. The preceding observation makes each match unique. Matches preserve order and fill initial segments on both sides, since restricting an isomorphism matches every earlier element. If both sides had an unmatched element, take the least unmatched $a$ and $b$. Their predecessor sets would be exactly the already matched segments, so they too would match, a contradiction. Therefore the matching exhausts at least one well-order and gives an isomorphism of that whole set onto an initial segment of the other. Uniqueness follows from the same predecessor-set argument. The whole set is allowed as an initial segment; this includes equal order types.

For ordinal division, let $\beta >0$ and chooseThis supremum is a set ordinal because $\beta \eta \ge \eta$ bounds the displayed ordinals by $\alpha$. Strict increase and continuity of multiplication in the right argument imply $\beta \gamma \le \alpha <\beta (\gamma +1)$. Take the order type $\delta$ of the remaining tail of $\alpha$ after its initial segment of type $\beta \gamma$. Then $\alpha =\beta \gamma +\delta$; if $\delta \ge \beta$ it would contradict the strict upper inequality. ThusThe half-open intervals $[\beta \eta ,\beta (\eta +1))$ are disjoint, so $\gamma$ is unique, and uniqueness of the tail gives uniqueness of $\delta$. This is left-divisor ordinal division: the order of multiplication cannot be interchanged.

Apply it with $\beta =\omega$. The remainder is finite. A nonzero remainder makes $\omega \gamma +\delta$ a successor, while a nonzero $\omega \gamma$ is a limit: for successor $\gamma$ it ends in a full block of type $\omega$, and for limit $\gamma$ it is the supremum of the earlier blocks. Consequently

The induced ordering on $x$ is a well-order. By transfinite recursion define $h(t)=\{h(s):s\in x,s<t\}$ for $t\in x$. Induction shows that each $h(t)$ is an ordinal, that these values strictly increase, and that their range is the ordinal $\mu (x)={\bigcup }_{t\in x}(h(t)+1)$. The map $h$ is an order isomorphism from $x$ to this ordinal. Any order isomorphism between ordinals must fix their elements successively, so this ordinal is unique.

An increasing map $j:\kappa \to \lambda$ between ordinals satisfies $j(\xi )\ge \xi$ by induction: its predecessors include $j(\eta )$ for all $\eta <\xi$. Hence $\kappa \le \lambda$. Apply this to the inclusion $x\subset y$, transported through their order isomorphisms, and then to $y\subset \alpha$. It follows that $\boxed{\mu (x)\le \mu (y)\le \alpha }$.

If each $x_n$ is an initial segment of later $x_m$, uniqueness makes their ordinal enumerations compatible: the enumeration of $x_m$ restricts to that of $x_n$. Their union is consequently an order isomorphism from ${\bigcup }_n{x}_n$ to ${\bigcup }_n\mu (x_n)$. This proves the asserted equality. Without the initial segment condition it fails: in $\alpha =\omega +1$, take $x_n=\{0,\dots ,n-1\}\cup \{\omega \}$. Then $\mu (x_n)=n+1$, whose union is $\omega$, but $\mu ({\bigcup }_n{x}_n)=\omega +1$.

For decreasing sets, $\mu (x_n)$ is a nonincreasing sequence of ordinals. Its set of values has a least member, attained at some $n_0$; all later values must equal it. Hence the sequence is eventually constant. The intersection formula nevertheless fails: take $x_n=\{n,n+1,\dots \}\subset \omega$. Every $x_n$ has order type $\omega$, whereas their intersection is empty and has order type zero. Thus $\mu ({\bigcap }_n{x}_n)=0\ne {\bigcap }_n\mu (x_n)=\omega$.

The map $\beta \mapsto {\omega }^{\beta }$ is strictly increasing and continuous at limit ordinals. Also ${\omega }^{\beta }\ge \beta$, so the set $S=\{\beta :{\omega }^{\beta }\le \alpha \}$ is nonempty and bounded by $\alpha$. If $\sup S$ is a successor, it is already in $S$; if it is a limit, continuity gives ${\omega }^{\sup S}={\sup }_{\beta \in S}{\omega }^{\beta }\le \alpha$. Thus $S$ has a greatest element $\beta$.

The initial segment of the well-order $\alpha$ of order type ${\omega }^{\beta }$ leaves a tail of some order type $\gamma$, giving ${\omega }^{\beta }+\gamma =\alpha$. For fixed left summand, ordinal addition is strictly increasing in its right argument, so this $\gamma$ is unique.

Maximality gives $\alpha <{\omega }^{\beta +1}={\omega }^{\beta }\omega$. Choose the least positive integer $m$ such that $\alpha <{\omega }^{\beta }m$. Then $m\ge 2$ and ${\omega }^{\beta }(m-1)\le \alpha$. If $\gamma \ge {\omega }^{\beta }(m-1)$, monotonicity of ordinal addition would give $\alpha ={\omega }^{\beta }+\gamma \ge {\omega }^{\beta }m$, a contradiction. Hence $\gamma <{\omega }^{\beta }(m-1)\le \alpha$. If $\alpha$ is not a power of $\omega$, both ${\omega }^{\beta }$ and $\gamma$ are nonzero and smaller than $\alpha$, proving decomposability.

Conversely, prove by transfinite induction that any two ordinals below ${\omega }^{\beta }$ have sum below ${\omega }^{\beta }$. For $\beta =0$ the only smaller ordinal is zero. For $\beta =\delta +1$, choose finite $m,n$ with $x<{\omega }^{\delta }m$ and $y<{\omega }^{\delta }n$. Monotonicity gives $x+y<{\omega }^{\delta }(m+n)<{\omega }^{\delta +1}$. For limit $\beta$, choose $\delta <\beta$ sufficiently large that $x,y<{\omega }^{\delta }$, and apply the induction hypothesis. Thus the nonzero indecomposable ordinals are exactly the powers of $\omega$.

The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model. The Upward Lowenheim-Skolem theorem says that an infinite structure $M$ in a language $L$ has an elementary extension of every prescribed infinite cardinality $\kappa \ge \max (|M|,|L|,{\aleph }_0)$.

Add constants $c_a$ for all $a\in M$ and the elementary diagram of a structure of $M$: every sentence with these constants true in $M$. Add $\kappa$ further constants $d_i$ and sentences $d_i\ne d_j$ for $i\ne j$. Any finite subset is satisfiable in $M$, by choosing the finitely many new constants distinctly, since $M$ is infinite. Compactness gives a model containing an elementary copy of $M$ and at least $\kappa$ elements.

For the exact cardinality, start with that copy and all the $d_i$, a set of cardinality $\kappa$. For every existential formula with parameters from this set that holds in the large model, choose one witness. Also close under the language's functions. Repeat countably many times. At each stage there are at most $\kappa$ formulas and finite parameter tuples, so the union still has cardinality $\kappa$. Every existential formula true in the large model with parameters in the union has a witness in the union; an induction on formulas proves that this substructure is elementary. This establishes the exact-size statement without assuming an unproved downward theorem.

A dense total order with $a<b$ is not a well-order: the nonempty set $\{x:a<x\}$ has no least element, since density supplies a point strictly between $a$ and any proposed least element.

In the strict-order language, the required axioms areThese axiomatize dense total orders, allowing endpoints. If more than one point is required, add $\exists x\exists y(x<y)$. For a non-strict poset language replace $x<y$ by $x\le y\wedge x\ne y$.

Well-orders are not first-order axiomatisable. Suppose a theory $T$ axiomatized them. Enlarge the language by constants $c_0,c_1,\dots$ and addEvery finite subset of the resulting theory has a model in the well-order $(\mathbb{N},<)$: assign its finitely many constrained constants to a sufficiently long finite descending chain. Thus the compactness theorem supplies a model of $T$ with an infinite descending chain. The set of the $c_i$ has no least element, contradicting well-ordering. This shows why the second-order assertion that every nonempty subset has a least member cannot be replaced by a first-order theory in the poset language.

Let $x={\tau }_G$ be any set in the extension. The set $D=\{\sigma :\exists p((\sigma ,p)\in \tau )\}$ belongs to $M$. Ground-model choice well-orders it, so fix an enumeration $⟨{\sigma }_{\xi }:\xi <\theta ⟩$ by an ordinal in $M$. In $M[G]$, takeEvaluation gives a surjection $\xi \mapsto ({\sigma }_{\xi }{)}_G$ from $I$ onto $x$. This is a set function by the ZF part of the forcing theorem; no extension choice is needed. For each $y\in x$, take its least preimage ordinal. Distinct $y$ have distinct least preimages, which well-order $x$ by their inherited ordinal order. Since every extension set has a forcing name, every set in $M[G]$ is well-orderable. ThereforeThis choice preservation by well-ordered names tolerates repeated evaluations, because the least-index step removes them canonically.

Replace the strict partial order by its reflexive closure $\le$. Partially order all partial orders on $X$ extending $\le$ by inclusion. A chain has an upper bound given by its union: transitivity and antisymmetry each concern finitely many pairs, which all lie in one member of the chain. By Zorn lemma there is a maximal extension $R$.

If $a,b$ are incomparable under $R$, defineThis adds $a{R}^{\prime }b$. It is transitive: composing an old pair with a new one stays in the added set; composing two new pairs would require $bRa$, which is impossible. It is antisymmetric: an added pair and a reverse old pair would again imply $bRa$, and two reverse added pairs would do the same. Thus $R^{\prime }$ is a larger partial order, contradicting maximality. Therefore $R$ is total, and removing its diagonal gives a total order extending the original strict order.

A well-founded relation has a minimal element in every nonempty subset; with the axiom of choice this is equivalent to having no infinite strictly descending sequence. If an extension is a well-order, its least element in any nonempty subset is minimal for the original relation, so the original order must be well-founded.

However not every total extension need be a well-order. Take the empty strict order on $\mathbb{N}$, which is well-founded. Its extension defined by $x\prec y$ if $x>y$ in the usual order is total and has no least element.

For a finite position $s\in A^{<\omega }$, let $[s]$ be the cylinder set of infinite plays extending $s$. Because the factors have the discrete topology, these cylinder sets form a basis for the product topology. PutMembership in $D$ means that I has already secured the outcome, regardless of future moves. Since $G$ is an open set, a play belongs to $G$ exactly when one of its prefixes belongs to $D$.

Build the winning-position attractor in an infinite game by transfinite recursion. Start with $W_0=D$, use unions at limit ordinals, and setThis sequence is increasing: the defining operation is order-preserving, and $W_0\subseteq W_1$. It stabilizes at some ordinal. Indeed, if it strictly increased at every successor stage below the successor cardinal number of $|A^{<\omega }|$, choosing one newly added position per stage would inject that larger cardinal into $A^{<\omega }$. Denote the stable set by $W$. This constructs the needed fixed point directly, without an appeal to an unstated fixed-point theorem.

Every position in $W$ has a least entry ordinal, its rank. Rank zero means membership in $D$. A positive rank is a successor $\alpha +1$: at an I-position some extension belongs to $W_{\alpha }$, while at a II-position every extension does. If the empty word belongs to $W$, I always chooses an extension of smaller rank until $D$ is reached. II's choices also decrease rank before that happens. There is no infinite strictly decreasing sequence of ordinals, so some finite prefix lies in $D$. This is a winning strategy in an infinite game for I.

If the empty word is outside $W$, the fixed point equation says that every extension of an I-position outside $W$ is still outside $W$, and that a II-position outside $W$ has at least one extension outside $W$. II chooses such an extension. Every resulting prefix avoids $D$, hence the whole play avoids $G$ by openness. This is a winning strategy in an infinite game for II.

The choices can be made simultaneously by fixing a well-order of $A$, as allowed by the usual axiom of choice. The argument does not assume that $A$ is countable. Every such open game is determined:

The Freiling theorem givesFirst assume the Continuum hypothesis and fix a well-order $(r_{\alpha }{)}_{\alpha <{\omega }_1}$ of the real numbers. Define $f(r_{\alpha })=\{r_{\beta }:\beta \le \alpha \}$. Each value is countable. For any pair, one index is at most the other, so at least one of $x\in f(y)$ or $y\in f(x)$ holds. The same holds for $x=y$, since $x\in f(x)$. This violates the Freiling axiom of symmetry.

Conversely, assume $|\mathbb{R}|>{\aleph }_1$ and let $f$ assign a countable set to each real. Choose $X\subseteq \mathbb{R}$ of cardinality ${\aleph }_1$. By infinite cardinal arithmetic,Choose $y$ outside this union. Since $f(y)$ is countable and $X$ is uncountable, choose $x\in X\setminus f(y)$. Then $y\notin f(x)$ and $x\notin f(y)$, with $x\ne y$. This proves the Freiling axiom of symmetry and completes both implications.

The cardinal bound for an increasing chain of countable sets is $\boxed{|X|\le {\aleph }_1}$. If $X$ is countable, there is nothing to prove. Otherwise choose $Y\subseteq X$ with $|Y|={\aleph }_1$, and for every $y\in Y$ choose an index $i(y)$ such that $y\in X_{i(y)}$.

For any $i\in I$, its countable $X_i$ cannot contain all of $Y$, so choose $y\in Y\setminus X_i$. Since $I$ is a linear order, comparison of $i$ and $i(y)$ forces $i<i(y)$: the other direction would imply $y\in X_i$. Therefore $X_i\subseteq X_{i(y)}$. The selected family is cofinal among the original sets, andBy infinite cardinal arithmetic, this union of ${\aleph }_1$ countable sets has cardinality at most ${\aleph }_1$. No well-order or cofinality assumption on $I$ was used; a linear increasing union of countable sets has the same bound even for an arbitrary linear index order.

The continuum hypothesis holds. Let $A$ be the assumed Lusin set of cardinality $\mathfrak{c}=2^{{\aleph }_0}$. If $\mathfrak{c}>{\aleph }_1$, choose $B\subseteq A$ with $|B|={\aleph }_1$. The size assumption makes $B$ a meagre set, but then $A\cap B=B$ is uncountable, contradicting the Lusin set property. ThusOne can also use (d) directly: well-order $A$ in type $\mathfrak{c}$. Each proper initial segment has size below $\mathfrak{c}$, so is meagre and consequently countable, since it is a subset of the Lusin set. These initial segments form a linear increasing union of countable sets equal to $A$. The bound in (d) gives $\mathfrak{c}\le {\aleph }_1$.

Use the well-order of the natural numbers to list $A$ in increasing order. Define recursivelyThe remaining set is nonempty because $A$ is infinite and only a finite set has been removed. Each chosen value is larger than the preceding one, so $f$ is an injective function.

To prove it is a surjective function, fix $a\in A$. If $a$ were never selected, every selected minimum would be at most $a$. This would put infinitely many distinct values into the finite set $\{0,\dots ,a\}$, a contradiction. HenceThe increasing enumeration of an infinite subset of natural numbers uses no arbitrary choice: each next element is the uniquely determined minimum.