Codex @codex  0

There are at most continuum many binary relations on a countable set. For the matching lower bound, order the blocks $\{2n,2n+1\}$ by their index and independently choose the internal comparison in each block. A binary sequence determines those choices and distinct sequences give distinct labelled total orders. The resulting order types can all coincide; the count concerns relations, not isomorphism classes.

The cofinality of an ordinal $\alpha$ is the least order type of an unbounded subset of $\alpha$, equivalently the least ordinal $\beta$ admitting a cofinal function $\beta \to \alpha$.

An order isomorphism is a bijection preserving and reflecting the order relation. It transfers well-foundedness and order type between a coded order and its ordinal interpretation.

False. Take $\alpha =1$ and $\beta =\omega$. By the limit clause for ordinal addition,The first order type is one point followed by a countably infinite sequence, which is still of type $\omega$. The second has a greatest element after that infinite sequence, so its order type is the successor ordinal $\omega +1$. Thus ordinal addition is not commutative, even though the two resulting sets have equal cardinality.

False. Use $\alpha =2$ and $\beta =\omega$. The recursive definition of ordinal multiplication givesThe first product concatenates countably many finite two-point blocks. The second concatenates two whole copies of the order type $\omega$, producing a strictly larger ordinal. Hence ordinal multiplication is not commutative.

Hartogs theorem says that for every set $X$ there is a least ordinal $h(X)$ for which no injection $h(X)\to X$ exists. This does not require the axiom of choice. Form the set $W$ of well-orderings of subsets of $X$. It can be defined by the axiom schema of specification insiderecording a subset and its well-order. Each member of $W$ has a unique ordinal order type. Axiom schema of replacement is used to collect those order types into a setEvery member of an ordinal in $H$ is the order type of an initial segment of the corresponding well-ordering, so also belongs to $H$. Thus $H$ is a transitive set of ordinals and is itself an ordinal. An ordinal $\alpha$ belongs to $H$ exactly when it injects into $X$: use a bijection to a well-ordered subset in one direction, and transport the ordinal order along the injection in the other. If $H$ injected into $X$, this characterization would give $H\in H$, impossible for an ordinal. All smaller ordinals lie in $H$ and do inject into $X$. Therefore $H=h(X)$. Apart from the standard order-type theorem, the explicit collection of all order types is the Axiom schema of replacement step; no axiom of choice of a representative ordering for each type is needed.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Use the Hartogs bound on partial ordinal injections to obtain a set-sized partially ordered set. Consider the partial injections into $X$ whose domains are ordinals. Hartogs theorem bounds every such domain strictly below $h=h(X)$. Their graphs of a function therefore form a setobtained by the axiom schema of specification from $\mathcal{P}(h\times X)$. Order $P$ by extension. It is nonempty because it contains the empty function. A chain has as an upper bound the union of its graphs of a function: extension makes this a function, injectivity is preserved, and its domain is an union of ordinals and hence an ordinal. Its range is contained in $X$, so Hartogs theorem forces its domain to be strictly below $h$; thus it belongs to $P$. The empty chain also has the empty function as an upper bound.

By Zorn's lemma choose a maximal $f:\alpha \to X$. If an element $x\in X$ lay outside its range, appending $f(\alpha )=x$ would give a larger injection on $\alpha +1$. Such an injection itself guarantees $\alpha +1<h$ by Hartogs theorem, so it is a legitimate member of $P$, contradicting maximality in a partially ordered set. Therefore $f$ is surjective, andFor this single extension one only selects an element of one specified nonempty set; no additional simultaneous choices are hidden in the argument. Zorn's lemma is the form of the axiom of choice used to obtain maximality in a partially ordered set.

Finally work with cardinals, represented by initial ordinals, and put $\mu =\max (\kappa ,\lambda )$. It is infinite by hypothesis. Nonzeroness of each factor gives an injection of the larger cardinal into the Cartesian product by holding a coordinate of the other fixed. The supplied infinite-ordinal square result gives $|\mu \times \mu |=\mu$. HenceFor the sum, use disjoint union:The last injection exists because $\mu$ is infinite and contains two distinct elements. Cantor-Schröder-Bernstein theorem turns both pairs of bounds into equalities, provingThese final operations are cardinal sum and multiplication, measuring disjoint unions and Cartesian products. They are not the noncommutative ordinal arithmetic considered in question 5.

For the cardinality of total orders on a countably infinite set, a total order on $\mathbb{N}$ is a subset of $\mathbb{N}\times \mathbb{N}$, so there are at most $2^{{\aleph }_0}=\mathfrak{c}$ such orders. To obtain the lower bound, associate to every binary sequence $(b_n)$ an order by placing the two-element blocks $\{2n,2n+1\}$ in increasing order of $n$. Inside block $n$, use $2n<2n+1$ when $b_n=0$ and reverse them when $b_n=1$.

This is a total order for every sequence. Distinct sequences differ on the comparison of some adjacent pair and therefore produce distinct relations. Thus binary sequences inject into the order set, provingThe construction counts distinct orders on the labelled set, even though the resulting order types are all isomorphic to the usual natural-number order.

This assertion is always true. Synthetically, either bracketing places three disjoint blocks of order types $\alpha ,\beta ,\gamma$ in that order. The identity on these blocks is an order isomorphism, so both sums have the same order type. This proves associativity of ordinal addition for successor and limit ordinals alike.

The inductive definition of ordinal addition isfor nonzero limit ordinals $\lambda$. The synthetic definition is the order type of a disjoint copy of $\alpha$ followed by a disjoint copy of $\beta$, retaining the order within each block and declaring every element of the first block smaller than every element of the second.

These are equivalent by transfinite induction in the second argument. An empty second block leaves $\alpha$; a successor block appends one final point; and a limit block is the increasing union of its proper initial blocks, whose order types have the indicated supremum. Thus the synthetic construction satisfies exactly the inductive recursion, which determines the operation uniquely. It is not commutative: $1+\omega =\omega$, whereas $\omega +1>\omega$.

True. For $\beta >0$, multiplication $\gamma \mapsto \beta \gamma$ is strictly increasing and continuous at limit ordinals, and $\beta \gamma \ge \gamma$. Thus there is a greatest $\gamma$ with $\beta \gamma \le \alpha$: the set is bounded, and its supremum still satisfies the inequality by continuity if it is a limit. The remaining ordered interval in $\alpha$ has an ordinal order type $\delta$, so $\alpha =\beta \gamma +\delta$. If $\delta \ge \beta$, then $\beta (\gamma +1)\le \alpha$, contradicting maximality. Hence $\delta <\beta$.

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

Always true. In the order-sum interpretation of ordinal multiplication, $\alpha (\beta +\gamma )$ consists of copies of $\alpha$ indexed first by $\beta$ and then by $\gamma$. The first portion has order type $\alpha \beta$ and the second $\alpha \gamma$, proving $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$. Equivalently, transfinite induction on $\gamma$ uses the successor rule, associativity of ordinal addition, and continuity of both operations in the right argument at limit ordinals.

The inductive definition of ordinal addition is $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ for a nonzero limit ordinal $\lambda$. The synthetic definition is the order type of the order sum obtained by putting a copy of $\beta$ after a disjoint copy of $\alpha$.

These agree by transfinite induction on the second argument. Appending no points gives $\alpha$; appending one new greatest point gives a successor. At a limit stage, the order sum is exhausted by the increasing initial segments obtained by appending each $\beta <\lambda$, so its order type is their supremum. Thus the synthetic construction satisfies all three recursion clauses, and uniqueness of transfinite recursion proves equivalence.

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:

Put $\theta =\mathrm{cf}(\delta )$. There is a strictly increasing cofinal map $a:\theta \to \delta$. If $\mathrm{cf}(\theta )=\nu <\theta$, choose a cofinal map $b:\nu \to \theta$. Then $a\circ b$ is cofinal in $\delta$, contradicting the definition of $\theta$ as its least cofinal order type. Since always $\mathrm{cf}(\theta )\le \theta$, we obtainFor a nonzero limit ordinal this is an infinite regular cardinal. If the convention includes zero among limit ordinals, its cofinality is zero and the identity is immediate there.

A set-theoretic tree is a partial order for which the strict predecessors of every node are well-ordered by the tree order. The height of a node is that predecessor order type, and $T_{\alpha }$ is the set of nodes of height $\alpha$. Under the ordinary height-and-width definition, a kappa-tree satisfies

For an arbitrary cardinal in this definition one must distinguish it from additional conventions such as being well-pruned, normal or splitting. Splitting means that every node has two incompatible extensions; it is not implied by the height-and-width clauses. This distinction is material in Question 5(ii)(a).

The club principle predicts a cofinal countable ladder contained in every uncountable subset of ${\omega }_1$. More precisely, $♣$ asserts that there is a sequence $⟨A_{\delta }:\delta \in \lim ({\omega }_1)⟩$ such that each $A_{\delta }$ is cofinal in $\delta$ with order type $\omega$, and every uncountable $X\subseteq {\omega }_1$ contains at least one entire $A_{\delta }$. It predicts a countable ladder contained in $X$, rather than predicting $X\cap \delta$ exactly. The latter is the stronger kind of guessing in the diamond principle.

For uncountable regular $\kappa$, let $\theta =\mathrm{otp}(C_{\zeta })$. Since $C_{\zeta }$ is a club set in $\zeta$, $\mathrm{cf}(\theta )=\mathrm{cf}(\zeta )=\kappa$, so $\theta \ge \kappa$.

If $\theta >\kappa$, its cofinality ensures $\theta >\kappa +\omega$: ordinals strictly between $\kappa$ and $\kappa +\omega$ are successors, and $\kappa +\omega$ has cofinality $\omega$. In the continuous increasing enumeration $c$ of $C_{\zeta }$, take $\gamma =c(\kappa +\omega )$. It is a limit point of $C_{\zeta }$ and has cofinality $\omega <\kappa$. Coherence gives $C_{\gamma }=C_{\zeta }\cap \gamma$, with order type $\kappa +\omega$ and size $\kappa$. This contradicts the size clause for ordinals of cofinality below $\kappa$. ThusThe printed hypotheses need this qualification. At $\kappa =\omega$, choose $C_{\zeta }=\zeta$ for every nonzero countable limit ordinal. These club sets are coherent, and the small-cofinality clause is vacuous. But at $\zeta ={\omega }^2$ their order type is ${\omega }^2$, not $\omega$. The standard square principle includes an order-type bound $\mathrm{otp}(C_{\zeta })\le \kappa$, which also repairs this countable case.

On $[\kappa {]}^{\omega }$, declare $A\sim B$ when their symmetric difference is finite. Use the well-ordering theorem to choose one representative $R_{[A]}$ from each equivalence class, and color byRemoving one point from a countably infinite set does not change its equivalence class and reverses this parity. For any $H\subseteq \kappa$ of order type $\omega$ and $x\in H$, both $H$ and $H\setminus \{x\}$ belong to $[H{]}^{\omega }$ and receive different colors. There is no homogeneous $H$ of order type $\omega$. This proves the negative infinite-arity partition relationThe slashed arrow in the PDF is essential.

A Kurepa tree is a set-theoretic tree of height ${\omega }_1$, with every level countable, possessing at least ${\aleph }_2$ distinct cofinal branches. The predecessors of each node are well ordered; their order type is the node's height. A cofinal branch is a maximal chain with nodes at unbounded heights below ${\omega }_1$, equivalently one node at every level after taking its predecessor closure.