Past exam of the logic and set theory course of the University of Oxford / 2008 / B

First give the recursive definitions, keeping the right argument as the recursion variable. For ordinals $\alpha ,\beta$ and nonzero limit ordinals $\lambda$,Here $\xi +1$ is the successor ordinal, and the supremum of a set of ordinals is its union. These are ordinal arithmetic, defined by transfinite recursion, and differ from cardinal sum and ordinal multiplication.

Associativity of ordinal addition is true. Fix $\alpha ,\beta$ and use transfinite induction on $\gamma$. The case $\gamma =0$ is immediate. In the successor step the recursive definitions and the induction hypothesis giveFor a nonzero limit ordinal $\lambda$, the ordinals $\beta +\xi$ for $\xi <\lambda$ form an increasing cofinal subset of the limit ordinal $\beta +\lambda$. The limit clause for ordinal addition, restricted to this cofinal subset, givesCofinal restriction is valid because ordinal addition by a fixed ordinal on the left is increasing and continuous in its right argument, directly from its recursive definition. This completes the induction.

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.

True: ordinal multiplication on the left distributes over ordinal addition. If $\alpha =0$ both sides are zero. Otherwise fix $\alpha >0$ and $\beta$, and induct on $\gamma$. At zero the identity follows from $\alpha 0=0$. At a successor, use the recursive ordinal multiplication rule and the associativity just proved:For a nonzero limit ordinal $\lambda$, the ordinals $\beta +\xi$ are cofinal in $\beta +\lambda$. Continuity of ordinal multiplication in its right argument givesFor the last equality, $\alpha \xi$ is increasing and cofinal in $\alpha \lambda$, which is a limit ordinal because $\alpha >0$, and ordinal addition is continuous in its right argument. This establishes the limit step and the identity for all ordinals.

False. Take $\alpha =\beta =1$ and $\gamma =\omega$. ThenThus ordinal multiplication on the right does not in general distribute over ordinal addition. The side on which ordinal multiplication occurs matters; the left-distributive identity in the previous part does not imply this one.

Use the Kuratowski ordered pairThe axiom of pairing first produces $\{a\}$ by pairing $a$ with itself, then $\{a,b\}$, and then the pair of these two sets. The axiom of extensionality supplies the usual uniqueness of each specified set. In particular, no use of Axiom schema of replacement is needed to construct a single ordered pair from two given sets.

To recover the coordinates from $P=⟨a,b⟩$, observe thatThe first equality recovers $a$. Once $a$ is known, the second recovers $b$: if its union is the singleton $\{a\}$ then $b=a$, and otherwise $b$ is its unique element different from $a$. Hence equality of two encoded pairs forces equality of both coordinates, including the degenerate case $a=b$.

The first ordered triple encoding works. Ifinjectivity of the ordered pair construction first gives $a=a^{\prime }$ and $⟨b,c⟩=⟨b^{\prime },c^{\prime }⟩$, and a second application gives $b=b^{\prime }$ and $c=c^{\prime }$. The construction uses only two successive ordered pair constructions, so is a set as well.

This encoding fails. Choose two distinct sets $0$ and $1$, for example the first two finite von Neumann ordinals. The distinct ordered triples $(0,0,1)$ and $(0,1,1)$ both encode asIndeed the repeated singleton in the first encoding and the repeated two-element set in the second disappear when forming an ordinary set. Thus the middle coordinate cannot always be recovered. The issue is loss of multiplicity, not a failure to construct a set.

This encoding works. Use three distinct tags $0,1,2$ and the ordered pair construction already proved injective. In the setexactly one member has first coordinate $0$, exactly one has first coordinate $1$, and exactly one has first coordinate $2$. Equality of two such sets therefore matches the members carrying each tag. Injectivity of the ordered pair construction then gives equality of $a$, of $b$ and of $c$, respectively.

This is a tagged encoding of a finite tuple. It remains valid when coordinates coincide with one another or with tags: the equality criterion for ordered pairs still distinguishes their first coordinates. Finite set formation using pairing and union makes the encoding a set.

This encoding works, interpreting the outer three-coordinate brackets by the nested ordered pair convention established in item 1. Equality of the outer ordered triples givesFor any fixed set $k$, the map $x\mapsto \{k,x\}$ is injective. If $x=k$, equality $\{k,x\}=\{k,y\}$ makes the right-hand side a singleton and forces $y=k$. If $x\ne k$, membership of $x$ in $\{k,y\}$ forces $x=y$. Applying this argument with $k=0,1,2$ recovers the respective coordinates.

The outer brackets must encode an ordered triple, rather than an unordered set of three doubletons. The source uses three-coordinate angle brackets here; using the successful convention of item 1 makes their meaning explicit and supplies a genuine construction.

The Cantor-Schröder-Bernstein theorem states that injections $f:A\to B$ and $g:B\to A$ imply the existence of a bijection $A\to B$. Here is the injection-chain formal proof, so no fixed-point theorem is needed. Defineand setThe second branch is defined because $a\notin C$ implies $a\notin A_0$, hence $a\in g(B)$, and the inverse there is unique by injectivity of $g$. Each branch is injective. A collision between branches would have $f(c)=g^{-1}(a)$ with $c\in C$ and $a\notin C$, implying $a=g(f(c))\in C$, a contradiction. Thus $h$ is injective.

For surjectivity let $b\in B$. If $g(b)\notin C$, then $h(g(b))=b$. If $g(b)\in C$, it is not in $A_0$, so it belongs to some $A_{n+1}=g(f(A_n))$. There is $a\in A_n$ with $g(b)=g(f(a))$; injectivity of $g$ gives $b=f(a)=h(a)$. This proves that $h$ is a bijection and completes the theorem without the axiom of choice.

For the comparison of cardinalities take the power set of $\omega$ as the reference set. Its cardinality is by definitionThe remaining parts give explicit injections or bijections comparing each requested set with this one.

Map $S\subseteq \omega$ to its indicator function $1_S:\omega \to \{0,1\}$. Its inverse maps a binary sequence $u$ to $\{n\in \omega :u(n)=1\}$. These maps are mutually inverse, soHere the left superscript denotes the set of functions from $\omega$ into $2$. It is a space of binary sequences, not an ordinal square.

There is an injection from the power set of $\omega$ into the real numbers given byIf $S$ and $T$ first differ at $k$, the contribution at $k$ has magnitude $2/3^{k+1}$, while the entire later tail has magnitude at mostTheir real values are therefore different. This proves injectivity directly and avoids any ambiguity of numeral expansions.

Conversely, map a real number $x$ to the set $\{q\in \mathbb{Q}:q<x\}$. Distinct real numbers give distinct sets because the rational numbers are dense in the real line. Fixing a bijection between $\omega$ and the countable set $\mathbb{Q}$ turns this into an injection $\mathbb{R}\to \mathcal{P}(\omega )$. Cantor-Schröder-Bernstein theorem now gives

Constant sequences give an injection $\mathbb{R}\to {}^{\omega }\mathbb{R}$. For the opposite bound fix an enumeration $(q_m{)}_{m\in \omega }$ of the rational numbers and encode a sequence $(x_n)$ byDistinct sequences differ at some coordinate $n$; density of the rational numbers then makes their encoded sets differ at a pair $(n,m)$. Thus $E$ is injective. The Cartesian product $\omega \times \omega$ is countable; for example the Cantor pairing functionis a bijection with $\omega$. Consequently $\mathcal{P}(\omega \times \omega )$ is equinumerous with $\mathcal{P}(\omega )$, already equinumerous with $\mathbb{R}$. Apply Cantor-Schröder-Bernstein theorem to obtain

Write $C(\mathbb{R},\mathbb{R})$ for the set of continuous real-valued functions on the real line. Constant functions give an injection of $\mathbb{R}$ into this set. In the other direction, restriction to the rational numbers is injective. Indeed, if continuous functions $f,g$ agree at every rational and $x$ is real, choose rational numbers $q_n\to x$. Continuity givesThus restriction embeds $C(\mathbb{R},\mathbb{R})$ into ${\mathbb{R}}^{\mathbb{Q}}$, which has the same cardinality as the real-sequence space because $\mathbb{Q}$ is countable. The previous part gives the upper bound $2^{{\aleph }_0}$, while constant functions give the matching lower bound. HenceThis computes the cardinality of continuous real functions. All five sets consequently have the same cardinality. The continuity assumption is decisive for restriction to a dense subset to determine a function.

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.