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

True in ZF. For a set $A$, the singleton map injects $A$ into its power set. No map $f:A\to \mathcal{P}(A)$ is onto: the diagonal setdiffers from $f(a)$ at the element $a$ for every $a$. Thus there is no bijection between $A$ and its power set. The injection together with this failure proves $\boxed{\kappa <2^{\kappa }}$.

If strict comparison is formulated as injection in one direction but not the other, the Cantor-Schröder-Bernstein theorem, which requires no choice, excludes an injection of the power set back into $A$. This is Cantor's theorem in a choice-free form.

True in ZF. A function from $M$ into the functions $B\to A$ corresponds bijectively to a function from $B\times M$ into $A$:The inverse sends $f$ to the function $m\mapsto (b\mapsto f(b,m))$. These two explicit transformations are inverses, proving the currying law for cardinal exponentiation. Empty domains and codomains cause no exception: the same correspondence still applies, including the unique empty function when its domain is empty. No selection of representatives or choice functions is involved.

True in ZF. Let $i:A\hookrightarrow A^{\prime }$ and $j:B\hookrightarrow B^{\prime }$ witness the two cardinal inequalities. Because $A$ is nonempty, fix one element $a_0\in A$. Send $f:B\to A$ to $\hat{f}:B^{\prime }\to A^{\prime }$ defined byThe first case is well defined by injectivity of $j$. If $f\ne g$, choose a point where their values differ; the images differ at its $j$-image because $i$ is injective. Thus $f\mapsto \hat{f}$ is injective, proving the desired inequality of function-space cardinalities.

Fixing one element of a single known nonempty set does not invoke the axiom of choice. The nonzero-base hypothesis is what permits this constant extension outside the smaller domain.

True in ZF. Suppose $\mathcal{P}(A)$ were countably infinite. The singleton injection would inject $A$ into the natural numbers. The set $A$ cannot be finite, since its power set would then be finite. Its image is therefore an infinite subset of $\mathbb{N}$, which has a canonical increasing enumeration. This gives a bijection $A\cong \mathbb{N}$ without choice.

But then $\mathcal{P}(A)\cong \mathcal{P}(\mathbb{N})$, contradicting Cantor's theorem that the latter is strictly larger than $\mathbb{N}$. HenceThe proof does not assume that an arbitrary infinite set contains a countably infinite subset; here the given injection into the natural numbers supplies its well-ordering.

False. Take $\kappa =2^{{\aleph }_0}$ and $\lambda ={\aleph }_0$, both infinite. The explicit pairing bijection between ${\mathbb{N}}^2$ and $\mathbb{N}$ and the currying law for cardinal exponentiation giveThe power-set cardinal need not be assumed well-orderable. Every bijection used in this calculation is explicitly available in ZF, so the counterexample does not use choice.

False. Take $\kappa ={\aleph }_0$, $\lambda =1$, and ${\lambda }^{\prime }=2$. ThenFor example the Cantor pairing function $⟨m,n⟩=(m+n)(m+n+1)/2+n$ bijects ${\mathbb{N}}^2$ with $\mathbb{N}$. Thus the exponent increases strictly while the cardinal power remains the same. This counterexample is completely choice-free.

True in ZF. Let $A$ be a set that is not finite. For each natural number $n$, formEach $E_n$ is a subset of $\mathcal{P}(A)$ and is nonempty: a nonfinite set has an $n$-element subset for every finite $n$, by finite induction. The sets $E_n$ are pairwise disjoint, hence pairwise distinct. Consequentlyis an injection from $\mathbb{N}$ into $\mathcal{P}(\mathcal{P}(A))$. This is a double-power-set countability bound without choice.

Part (d), applied to the set $\mathcal{P}(A)$, says that its power set is not countably infinite. Combining that result with the displayed injection givesThere is no hidden countable choice: the proof uses the entire definable family of $n$-element subsets, rather than choosing one subset for each $n$.

The recursive definitions of ordinal addition and ordinal multiplication arewhere the limit clauses apply to nonzero limit ordinals. Ordinal exponentiation has ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and for $\alpha >0$, ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$. Complete the zero-base convention by $0^{\beta }=0$ for $\beta >0$, with $0^0=1$. Stating the zero-base exception avoids including the value $0^0$ in a naive supremum at a positive limit.

For finite $n$, induction gives $1+n=n+1$. Now prove commutativity for finite $m,n$ by induction on $m$. The case $m=0$ is immediate. Associativity, the finite identity just obtained, and the induction hypothesis giveThus $\boxed{m+n=n+m\text{ for finite ordinals}}$.

It fails for general ordinals: $\boxed{1+\omega =\omega <\omega +1}$. The equality follows from the limit clause, since the finite sums $1+n$ are cofinal in $\omega$.

For nonzero $\alpha$, consider the exponents $\eta$ with ${\omega }^{\eta }\le \alpha$. The set is nonempty because it contains zero, and bounded because ${\omega }^{\eta }\ge \eta$ by transfinite induction. Let $\delta$ be its supremum. If this supremum is a successor it is attained; if it is a limit, continuity of ordinal exponentiation gives ${\omega }^{\delta }\le \alpha$. The zero case is immediate. Thus $\delta$ itself belongs to the set and is its maximum. Maximality givesPut $\rho ={\omega }^{\delta }>0$. Since ${\omega }^{\delta +1}=\rho \cdot \omega ={\sup }_{N<\omega }\rho N$, there is a least positive natural number $N$ with $\alpha <\rho N$. We have $N\ge 2$ because $\rho \le \alpha$. Set $n=N-1$. ThenFor ordinals $\xi \le \alpha$, the final segment of $\alpha$ after its initial segment $\xi$ has an order type $\zeta$ satisfying $\alpha =\xi +\zeta$. Apply this with $\xi =\rho n$. If $\zeta \ge \rho$, monotonicity would give $\alpha \ge \rho n+\rho =\rho (n+1)$, a contradiction. ThereforeThese intervals also make the leading exponent and coefficient unique. The remainder is unique because addition by a fixed left prefix is strictly increasing in its right operand.

Use transfinite induction on nonzero $\alpha$. Part (b) gives $\alpha ={\omega }^{\delta }n+\zeta$, with $n$ a positive natural number and $\zeta <{\omega }^{\delta }\le \alpha$.

If $\zeta =0$, this is already a one-term Cantor normal form. Otherwise $0<\zeta <\alpha$, so the induction hypothesis supplies a finite Cantor normal form for $\zeta$. Its leading exponent $\eta$ satisfies ${\omega }^{\eta }\le \zeta <{\omega }^{\delta }$, hence $\eta <\delta$. All later exponents are smaller still. Prefixing ${\omega }^{\delta }n$ therefore givesThe number of terms is finite because the inductive representation of the strictly smaller remainder is finite. Equivalently, repeated extraction cannot produce an infinite strictly descending sequence of ordinals. Since $\alpha \ne 0$, the number of terms is positive.

Yes, with the stated strict decrease and positive coefficients. In any displayed Cantor normal form, the first exponent is the unique $\delta$ with ${\omega }^{\delta }\le \alpha <{\omega }^{\delta +1}$. The leading coefficient is the unique positive integer $n$ withThe remaining tail is the unique $\zeta <{\omega }^{\delta }$ satisfying $\alpha ={\omega }^{\delta }n+\zeta$, by strict monotonicity of ordinal addition in the right operand.

Thus any two such representations have the same first exponent and coefficient and the same remainder. Repeat the argument on that remainder. Their finite lists agree term by term and reach zero at the same step, so the lengths agree as well. Allowing zero coefficients or repeated exponents would spoil this normalized uniqueness, which is why those conditions are required.

Hartogs theorem says that for every set $A$ there is a least ordinal $h(A)$ that does not inject into $A$. This theorem requires no axiom of choice.

To prove it, collect all well-orderings of subsets of $A$. They are set-sized data, coded by pairs from $\mathcal{P}(A)$ and $\mathcal{P}(A\times A)$. Each has a unique ordinal order type, so replacement gives a set $H$ of their order types. If $\eta \in H$ and $\xi <\eta$, restricting the corresponding well-order to an initial segment shows $\xi \in H$. Hence $H$ is an ordinal. If this ordinal itself injected into $A$, its transported well-order would put $H$ among its own elements, impossible for an ordinal. Every smaller ordinal does inject by definition. Thus $h(A)=H$ has the asserted property.

The recursion printed in the source needs two boundary restrictions. Its new-row successor clause allows $\beta =\alpha$, which would assign a value at $(\alpha ,\alpha +1)$ outside the declared domain. Also, at $\alpha =0$, its row-start clause gives $g_1(0,0)=0$ while its column-start clause gives $g_1(0,0)=g_1(0,0)+1$. Taken literally, these clauses do not define a function.

The intended extension fills the new row first and the remaining new column second. Restrict the row successor clause to $\beta <\alpha$, and apply the column-start clause only when $\alpha >0$. With these two restrictions the domains are disjoint:All successors here are ordinal successors. Simultaneous transfinite induction proves a stronger result: $g_{\alpha }$ is a bijection of $\alpha \times \alpha$ onto an ordinal ${\gamma }_{\alpha }$, and the functions extend one another.

At zero this is the empty function. Assuming it at $\alpha$, the least missing ordinal is ${\gamma }_{\alpha }$. Recursion down the new row gives values ${\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$; recursion down the remaining column gives ${\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. These enumerate two disjoint consecutive ordinal intervals above the old range, so the extension is well defined and bijective, withAt a limit $\lambda$, take the union of the earlier functions. Compatibility makes it a function, and every pair of coordinates below $\lambda$ is already present at some earlier stage. Its range is the ordinal ${\bigcup }_{\alpha <\lambda }{\gamma }_{\alpha }$, and injectivity is preserved by the compatible union. This completes the construction of the row-and-column enumeration of an ordinal square.

For finite stages ${\gamma }_n=n^2$. For example the table of $g_3$, with the first coordinate indexing rows, isThe remaining parts refer to this domain-consistent construction. The source's literal boundary claims are preserved in the archive, rather than silently asserted as valid.

Let $\kappa =|\alpha |$ be the infinite initial ordinal of the given ordinal. A successor adds only one point, so $|\alpha +1|=\kappa$: one can absorb the additional point by shifting the initial copy of $\omega$ and fixing the rest.

The successor construction from part (a) partitions the new range into the old range, a new row of size $|\alpha +1|$, and a new column of size $|\alpha |$. By hypothesis each part has cardinality at most $\kappa$, and the old range already has cardinality $\kappa$.

A finite disjoint union of copies of a well-orderable infinite cardinal has that same cardinality without invoking the square theorem being proved. Explicitly, write each $\xi <\kappa$ uniquely as $\omega \eta +n$ with $n<\omega$. Interleave three copies byThis stays below $\kappa$ because an infinite initial ordinal is a limit ordinal and is closed under finite successor steps below it. It is injective by uniqueness of the quotient and finite remainder. The reverse injection is immediate, so the Cantor-Schröder-Bernstein theorem proves the finite-union claim.

Applying that bound to the three range pieces yieldsOnly the well-orderability of ordinals, not a choice principle for arbitrary families of sets, was used.

If zero is admitted as a limit case, the assertion there is immediate since ${\gamma }_0=0$. For a nonzero limit, let $\kappa =|\lambda |$, an infinite initial ordinal. There are two cases; separating them avoids choosing an entire family of bijections at earlier stages.

If $\kappa <\lambda$, the hypothesis applies at $\kappa$. Part (a) gives a bijection $g_{\kappa }:{\kappa }^2\to {\gamma }_{\kappa }$, whose range has cardinality $\kappa$ by hypothesis. Fix one bijection $\lambda \to \kappa$; taking its product gives ${\lambda }^2\cong {\kappa }^2$. Since $g_{\lambda }$ is also bijective onto its range, these maps give $\boxed{|{\gamma }_{\lambda }|=\kappa =|\lambda |}$.

If $\lambda =\kappa$ is itself an initial ordinal, suppose ${\gamma }_{\lambda }>\kappa$. Continuity gives ${\gamma }_{\lambda }={\bigcup }_{\alpha <\kappa }{\gamma }_{\alpha }$, so some earlier ${\gamma }_{\alpha }$ contains the ordinal $\kappa$. If $\alpha$ is finite then ${\gamma }_{\alpha }={\alpha }^2$ is finite, impossible. If $\alpha$ is infinite, the hypothesis gives $|{\gamma }_{\alpha }|=|\alpha |<\kappa$, again impossible because its ordinal range contains an initial segment of size $\kappa$.

Thus ${\gamma }_{\lambda }\le \kappa$. Conversely, transfinite induction gives ${\gamma }_{\alpha }\ge \alpha$: each successor appends a nonempty row and limits take unions. In particular ${\gamma }_{\lambda }\ge \lambda =\kappa$. Hence ${\gamma }_{\lambda }=\kappa$ in this case, proving the required cardinal equality as well. The argument includes $\lambda =\omega$, whose earlier stages are finite.

The finite-stage calculation gives ${\gamma }_{\omega }={\sup }_{n<\omega }{n}^2=\omega$, so the desired equality holds at the first infinite ordinal. Apply transfinite induction to all subsequent infinite ordinals. The successor step is part (b), and the limit step is part (c). ThusBy the well-ordering theorem, any infinite cardinal in the question may be represented by an infinite initial ordinal $\kappa$. The corrected recursion supplies a bijection $g_{\kappa }:\kappa \times \kappa \to {\gamma }_{\kappa }$, and the just-proved equality gives $|{\gamma }_{\kappa }|=\kappa$. ThereforeThe proof used only finite-copy interleaving before reaching this conclusion; using the square equality itself to estimate the successor or limit stages would have been circular.