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

The ordinal operations are defined by transfinite recursion in the right argument. Addition satisfies $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ at a nonzero limit. Multiplication satisfies $\alpha \cdot 0=0$, $\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha$, and $\alpha \cdot \lambda ={\sup }_{\beta <\lambda }\alpha \cdot \beta$. Exponentiation satisfies ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$ at nonzero limits. These are ordinal operations, not commutative cardinal arithmetic.

For a normal function on an ordinal, prove domination by transfinite induction. At zero, $0\le \Phi (0)$ automatically. If $\alpha \le \Phi (\alpha )$, strict increase at successors gives $\alpha +1\le \Phi (\alpha )+1\le \Phi (\alpha +1)$. At a nonzero limit $\lambda$, continuity and the induction hypotheses giveTherefore $\boxed{\alpha \le \Phi (\alpha )\text{ for every ordinal }\alpha }$. No axiom of choice is needed for this ordinal induction.

For fixed $\beta$, the recursion defining $\beta +\alpha$ makes it continuous in $\alpha$ at every nonzero limit, and $(\beta +\alpha )+1>\beta +\alpha$. Thus $\alpha \mapsto \beta +\alpha$ is normal, including when $\beta =0$.

For $\beta >0$, take $\lambda =\beta \cdot \omega$. If $\alpha <\lambda$, choose a natural number $n$ with $\alpha <\beta n$; then $\alpha +\beta \le \beta (n+1)<\lambda$. Since $\alpha +\beta \ge \alpha$, their supremum as $\alpha \uparrow \lambda$ is $\lambda$. But $\lambda +\beta >\lambda$, soHence right addition by a nonzero fixed ordinal fails continuity and is not normal.

Normality and argument order in ordinal arithmetic also give the multiplication statements: $\alpha \mapsto \beta \cdot \alpha$ is normal for $\beta >0$, while $\alpha \mapsto \alpha \cdot \beta$ is normal exactly when $\beta =1$. At $\beta =0$ it is constant. For fixed $\beta >1$, let $\kappa ={\omega }^{\beta \cdot \omega }$. Cantor normal form shows that $\xi \beta <\kappa$ whenever $\xi <\kappa$: leading exponents below $\beta \omega$ remain below it after adding the leading exponent of $\beta$. Thus ${\sup }_{\xi <\kappa }\xi \beta =\kappa$, but $\kappa \beta >\kappa$, again violating continuity. Left-fixed multiplication is strictly increasing and continuous by its recursion.

For exponentiation, $\alpha \mapsto {\beta }^{\alpha }$ is normal for $\beta \ge 2$; bases zero and one are exceptions. The reverse map $\alpha \mapsto {\alpha }^{\beta }$ is normal exactly when $\beta =1$. Exponent zero gives the constant one. For $\beta >1$, use the same $\kappa$ and put $\lambda ={\omega }^{\kappa }$. For each $\alpha <\lambda$ choose $0<\zeta <\kappa$ with $\alpha \le {\omega }^{\zeta }$. Then ${\alpha }^{\beta }\le {\omega }^{\zeta \beta }<\lambda$, while ${\alpha }^{\beta }\ge \alpha$ for positive $\alpha$. Consequently its left supremum is $\lambda$, but ${\lambda }^{\beta }={\omega }^{\kappa \beta }>\lambda$. The bound by ${\omega }^{\zeta }$ also handles finite bases, where an unqualified leading-exponent multiplication formula would need care. All these are ordinal facts and use no choice.

For a countable fixed point of a normal ordinal function, first show that $\Phi$ maps every countable ordinal to a countable ordinal. Use transfinite induction below ${\omega }_1$. The zero case is assumed, and the successor case is the stated preservation property. If $\lambda$ is a countable limit, normality gives $\Phi (\lambda )={\bigcup }_{\alpha <\lambda }\Phi (\alpha )$, a countable union of countable sets, hence countable. This countable-union step is where axiom of countable choice is used; the assumed axiom of choice supplies it.

Now set ${\alpha }_0=0$, ${\alpha }_{n+1}=\Phi ({\alpha }_n)$. The preceding result makes every term countable, and the domination proved earlier makes the sequence nondecreasing. If it ever stabilizes, it already gives the required fixed point. Otherwise $\alpha ={\sup }_{n<\omega }{\alpha }_n$ is a countable nonzero limit, using axiom of countable choice again for countability of the union. Its defining sequence is cofinal, so monotonicity and continuity giveApply this to $\Phi (\alpha )={\omega }^{\alpha }$. This is normal, begins at $1$, and ${\omega }^{\alpha +1}={\omega }^{\alpha }\cdot \omega$ is countable whenever ${\omega }^{\alpha }$ is countable. Thus a countable $ϵ$ satisfies $\boxed{ϵ={\omega }^{ϵ}}$. Starting at zero gives the familiar tower sequence $0,1,\omega ,{\omega }^{\omega },\dots$, whose supremum is ${ϵ}_0$. The finite recursion, ordinal identities and fixed-point continuity do not require choice; the uses of choice above concern countable unions of countable ordinals.

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 a direct proof, avoiding any appeal to a fixed-point theorem. Let $A_0=A\setminus g(B)$, $A_{n+1}=g(f(A_n))$, and $C={\bigcup }_{n<\omega }{A}_n$. DefineThe second case is defined because $A\setminus C\subseteq g(B)$. On $C$, $f$ is a bijection onto $f(C)$. For $b\in B$, injectivity of $g$ and the construction of $C$ give $g(b)\in C$ if and only if $b\in f(C)$: $g(b)$ cannot be in $A_0$, so membership in $C$ means membership in some $g(f(A_n))$. Hence $g^{-1}$ bijects $A\setminus C$ onto $B\setminus f(C)$. The two pieces have disjoint domains and images and together cover $A,B$, proving $h$ bijective. This proof itself uses no choice.

Write $\mathfrak{c}=|\mathbb{R}|=2^{{\aleph }_0}$. We use the standard infinite-cardinal identities $\kappa \cdot {\aleph }_0=\kappa$, ${\kappa }^n=\kappa$ for positive finite $n$ and infinite $\kappa$, and $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$, under the permitted axiom of choice. The map $z\mapsto (\mathrm{Re}z,\mathrm{Im}z)$ bijects $\mathbb{C}$ with ${\mathbb{R}}^2$. Therefore

For an infinite cardinal $\kappa$, multiplication by a nonzero countable cardinal does not change it. Since $|\mathbb{R}|=\mathfrak{c}\ge {\aleph }_0$,There is also an immediate lower bound from $r\mapsto (r,0)$; the standard product identity supplies the matching upper bound. The discreteness of the second coordinate does not create a new cardinal beyond the continuum.

The notation ${}^{\mathbb{R}}\mathbb{R}$ means all functions from the real numbers to themselves, with no continuity restriction. Its cardinal isThe exponent law follows by viewing a function to a function set as one function on a Cartesian product. Cantor's theorem gives $2^{\mathfrak{c}}>\mathfrak{c}$, so this is strictly larger than the other continuum-sized examples here. Characteristic functions of subsets of $\mathbb{R}$ already supply the lower bound $2^{\mathfrak{c}}$.

Every finitely supported sequence vanishes from some index onward, since a finite subset of the natural numbers has a greatest element. Thus the set is a union over $n<\omega$ of sequences determined by their first $n$ real entries, with zeros afterwards. Each nontrivial piece has cardinal ${\mathfrak{c}}^n=\mathfrak{c}$, so the union has cardinal at most ${\aleph }_0\cdot \mathfrak{c}=\mathfrak{c}$.

Conversely $r\mapsto (r,0,0,\dots )$ is an injection from $\mathbb{R}$. Cantor-Schröder-Bernstein therefore givesNo choice of an arbitrary infinite support is involved; it is the finite support that makes a countable union of finite-dimensional parameter spaces enough.

The common amplitude $a>0$ is uniquely determined by any entry's absolute value. After choosing it, each entry independently has sign $+1$ or $-1$. Thus the correspondenceis a bijection from $(0,\infty )\times \{-1,1{\}}^{\mathbb{N}}$ onto the set. The positive reals have cardinal $\mathfrak{c}$, and binary sign sequences have cardinal $2^{{\aleph }_0}=\mathfrak{c}$. HenceHere “independently” refers to unconstrained deterministic choices of coordinates, not probabilistic independence; no probability distribution is being specified.

The complex plane has a countable basis of disks with positive rational radii and centres with rational real and imaginary coordinates. Each open set is the union of the basic disks it contains, so it is determined by a subset of this countable basis. Therefore the number of open sets is at most $2^{{\aleph }_0}=\mathfrak{c}$.

For the reverse inequality, the distinct disks $\{z:|z|<r\}$ for $r>0$ give $\mathfrak{c}$ different open sets. ThusThe countable-basis restriction is decisive: there are $2^{\mathfrak{c}}$ arbitrary subsets of the plane, but only continuum many open ones.

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.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Order the partial group operations by inclusion of their graphs. The collection is a set, since its members are subsets of $X\times X\times X$. It is nonempty: choose $x_0\in X$ and put the one-element group operation on $\{x_0\}$.

To construct a chain union of partial group operations, for the given nonempty chain, let $m={\bigcup }_{n\in \mathcal{C}}n$ and let $A$ be the union of the corresponding group carriers. Comparability guarantees agreement wherever two operations are both defined, so $m$ is a function. Its domain is $A\times A$: any two elements of $A$ lie together in one carrier, by taking the larger of the two chain members containing them. Their product then lies in that carrier and hence in $A$.

Any three elements similarly lie together in one chain member, where associativity holds; therefore associativity holds for $m$. The identities of nested nonempty groups agree: the smaller identity remains an idempotent under the larger group operation, whose only idempotent is its identity. Hence the whole chain has a common identity. Each element's inverse in a carrier remains its inverse in every larger carrier, so it is an inverse in the union as well. Thus $(A,m)$ satisfies all group axioms andIt is an upper bound for the chain. The empty chain also has an upper bound because $\mathcal{G}$ is nonempty, completing the hypothesis needed for Zorn's lemma.

Apply Zorn's lemma using the chain upper bounds just proved, obtaining a maximal partial group operation $m$ on a nonempty carrier $A\subseteq X$. Suppose $|X\setminus A|\ge |A|$. Then choose a subset $B\subseteq X\setminus A$ and a bijection $b:A\to B$. The set $A\cup B$ can be identified with $A\times C_2$ by sending $(a,0)$ to $a$ and $(a,1)$ to $b(a)$.

Use group extension by a duplicate carrier to transport the direct-product group operation along this bijection. Its restriction to $A\times A$ is exactly the original $m$, because $(a,0)(a^{\prime },0)=(m(a,a^{\prime }),0)$. It therefore gives a strictly larger member of $\mathcal{G}$, contradicting maximality. Thus $|A|\nleqq |X\setminus A|$. Cardinal comparability, allowed as a consequence of Zorn's lemma, leaves the strict opposite inequality:The argument uses choice through Zorn's lemma and cardinal comparability; the extension itself is an explicit transported direct-product operation once the bijection with $B$ is chosen.

If $X$ is finite and nonempty, let $n=|X|\ge 1$, choose a bijection with the cyclic group $\mathbb{Z}/n\mathbb{Z}$, and transport its addition to $X$. This includes the one-element case.

If $X$ is infinite, use the maximal partial group $(A,m)$ from the preceding part. Its carrier must be infinite: otherwise $|X\setminus A|<|A|$ would make the complement finite too, forcing $X$ finite. Since the complement injects into $A$,where the last equality is the permitted infinite-cardinal doubling identity. Cantor-Schröder-Bernstein supplies a bijection $j:X\to A$. DefineAssociativity follows by applying $j$ and using associativity of $m$; the identity is $j^{-1}(e_A)$ and the inverse of $x$ is $j^{-1}(j(x{)}^{-1})$. Hence $(X,\star )$ is a group.

This final transport need not extend the earlier partial operation on its original subset. That stronger claim is neither needed nor generally possible: for example a group of order three cannot occur as a subgroup of a group of order four. The proof establishes exactly the existence of some group structure on every nonempty set, using the allowed choice consequences in the infinite case.