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

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$.