Past exam of the logic and set theory course of the University of Oxford / 2008 (B1, DMAB 2640, DMCN 2640, DMPB 2640, DMST 2640)

This University of Oxford Part B paper is cross-listed for Mathematics, Mathematics and Computer Science, Mathematics and Philosophy, and Mathematics and Statistics. It contains mathematical logic in section A and set theory in section B. ^[ref] The archive contains the full editable five-page transcription. Bounded official-source searches found no advertised answers for this exact 2008 paper. All source leaves are solved below, including all five optional arguments in A1(e) and the unnumbered preliminary tasks in B5, B6 and B7.

Start with the propositional variables as atomic symbols and close under the two formation operationsThe set of propositional formulas is the smallest set satisfying these conditions: every logical formula has a finite construction from logical variables by negation and logical implication, and no other strings qualify. In particular, parentheses belong to the binary logical implication formation rule; they cannot be added or removed arbitrarily. Each symbol $p_i$ is one token, regardless of how its index is printed.

Use structural induction on the formation of a propositional formula. A propositional variable has no parentheses. Applying negation to a logical formula adds no parentheses, so preserves equality of the two counts. If $\psi$ and $\chi$ each have equally many opening and closing parentheses, the formation of $(\psi \to \chi )$ adds one of each to their combined counts. Thus every propositional formula satisfiesThis is a necessary condition for being a logical formula; it is not sufficient, since the logical connectives and the placement of symbols must also follow the formation rules.

Not a logical formula. The string has one opening parenthesis and no closing parenthesis, contradicting the parentheses count established above. It also fails the binary logical implication formation rule, whose final symbol must be a closing parenthesis.

Not a logical formula of this language. Logical disjunction is not one of its permitted logical connectives. Even though the displayed expression has an ordinary interpretation in a larger propositional language, membership in the specified formal language is a syntactic question. A logically equivalent logical formula using only negation and logical implication would have to be written with those symbols instead.

A logical formula. Both $p_1$ and $p_2$ are propositional variables, so $(p_1\to p_2)$ and $(p_2\to p_1)$ are logical formulas. Applying the binary logical implication formation rule to this ordered pair of logical formulas gives the displayed whole expression. This supplies a construction of its formula syntax tree rather than merely checking that its parentheses balance.

The unique readability theorem says that every propositional formula has exactly one of the following forms: a unique propositional variable; $\neg \psi$ for a unique logical formula $\psi$; or $(\psi \to \chi )$ for a unique ordered pair of logical formulas $(\psi ,\chi )$. These three alternatives are disjoint. Consequently each logical formula has a unique formula syntax tree and a uniquely determined principal logical connective whenever it is not a logical variable.

A propositional variable $p_i$ is a single symbol of the alphabet. Its only nonempty substring is that symbol itself. Every propositional formula is nonempty, so the only substring that is a logical formula is $p_i$. ThereforeThe subscript is part of the name of an atomic token; it does not introduce additional symbol positions inside the logical variable.

A useful consequence of the formation rules is that logical formulas form a prefix-free set of strings. To see this, describe a deterministic parser that reads one logical formula from its starting position. On a logical variable it consumes that one symbol. On a negation symbol it recursively reads one following logical formula. On an opening parenthesis it recursively reads a left logical formula, requires a logical implication symbol, recursively reads a right logical formula, and requires the closing parenthesis. Induction on formation proves that, if a valid logical formula begins at the current position, this procedure consumes exactly that logical formula and stops at its end.

Suppose now that both $\alpha$ and $\varphi$ are logical formulas and $\varphi =\alpha ϵ$. The same parser, started at their common first symbol, must stop both at the end of $\alpha$ and at the end of $\varphi$. Its deterministic stopping position cannot differ, so $ϵ$ is empty. HenceThis argument applies to symbol strings; it does not use truth values or logical equivalence.

First note that a substring which is itself a logical formula must coincide with a subtree of the formula syntax tree of the surrounding logical formula. Indeed, a logical formula can begin only at a logical variable, a negation symbol or an opening parenthesis. Every such position in a valid logical formula is the start of one of its parsed subtrees. If $\beta$ is the logical formula at that subtree and $\alpha$ is another logical formula starting at the same position, one is an initial segment of the other; prefix-freeness of fully parenthesized formulas from the preceding part forces $\alpha =\beta$.

Now consider a final subformula. For a logical variable, it can only be the whole logical formula. For a binary logical implication $(\psi \to \chi )$, every proper subtree is contained in $\psi$ or $\chi$ and finishes before the final closing parenthesis of the whole expression. It therefore cannot be a final substring of the whole. The only remaining possible outer formation is negation. ThusThe second alternative is a necessary possibility, not a claim that every negated logical formula has every one of its subformulas as a suffix.

The whole logical formula $\neg \psi$ is a subformula of itself, and any subformula of $\psi$ remains a contiguous substring after placing a negation symbol in front of $\psi$.

Conversely, a subformula occurrence starting at the first symbol of $\neg \psi$ is an initial subformula, so equals the whole logical formula by prefix-freeness of fully parenthesized formulas. An occurrence starting later lies wholly inside the following string $\psi$, and is therefore a subformula of $\psi$. ConsequentlyHere $\mathrm{Sub}$ records distinct logical formulas; multiple occurrences of the same logical formula do not create different elements of this set.

A subformula beginning at the first opening parenthesis equals the whole logical formula by prefix-freeness of fully parenthesized formulas. Every other subformula is the logical formula of a proper syntax subtree, by the parsing argument in part (iii). The two children of the root are precisely $\psi$ and $\chi$, so such a subtree lies entirely inside one of those children. In particular no logical formula substring can begin in $\psi$ and cross the principal logical implication symbol into $\chi$.

Conversely, each subformula of either child is visibly a substring of the whole expression, as is the whole expression itself. ThusTogether these cases identify the substring definition of a subformula with its usual syntax-tree definition.

Fix the particular occurrence of $\alpha$ that is being replaced. The subformula analysis above makes it a node of the formula syntax tree of $\varphi$. Proceed by structural induction on the surrounding logical formula.

If this node is the root, the subformula replacement gives $\beta$, already a logical formula. Otherwise, if $\varphi =\neg \psi$, the chosen occurrence lies inside $\psi$. The induction hypothesis gives a logical formula ${\psi }^{\prime }$ after the subformula replacement there, and the whole result is the logical formula $\neg {\psi }^{\prime }$. If $\varphi =(\psi \to \chi )$, a proper chosen occurrence lies in exactly one of the two children. Replacing inside that child gives either $({\psi }^{\prime }\to \chi )$ or $(\psi \to {\chi }^{\prime })$, each a logical formula by the formation rule. A logical variable has no proper subformula, so there is no additional base case.

Therefore replacing the designated subformula occurrence by any logical formula preserves well-formedness. The argument concerns one chosen occurrence; it does not require simultaneous subformula replacement of every occurrence of the same string.

Fix any Boolean valuation $v$. Logical equivalence of $\alpha$ and $\beta$ means $v(\alpha )=v(\beta )$ for this Boolean valuation and every other one. Follow the unique path from the replaced node to the root of the formula syntax tree. At a negation node, equal input truth values have equal negations. At a logical implication node, the unaffected child has the same truth value before and after subformula replacement, while the affected child has the same truth value by induction; the resulting logical implications therefore agree as well.

Induction along that finite path yields $v(\varphi )=v({\varphi }^{\prime })$. Since $v$ was arbitrary,This is the replacement theorem for logical equivalence: the semantics of each logical connective depends only on the truth values of its immediate inputs.

A collection of logical connectives is functionally complete, or adequate, if every Boolean function of finitely many propositional variables is represented by a logical formula using only those logical connectives. More explicitly, for every $n\ge 1$ and every $F:\{0,1{\}}^n\to \{0,1\}$ there is a logical formula $\theta (p_1,\dots ,p_n)$ whose truth value under each Boolean valuation is $F(v(p_1),\dots ,v(p_n))$. Constant functions with Boolean values may use an otherwise irrelevant logical variable, for example $p\to p$ for truth and $\neg (p\to p)$ for falsity.

Translate logical formulas recursively, leaving propositional variables unchanged and translating negation by applying negation to the translation. For the other two logical connectives setThe first logical implication is false exactly when both original inputs are false; the second displayed logical formula is true exactly when both inputs are true. Hence each clause preserves truth values. Structural induction gives $v(T(\theta ))=v(\theta )$ for every Boolean valuation and every logical formula $\theta$ in the larger language.

By the assumed functional completeness of negation, logical conjunction and logical disjunction, any finite Boolean function has such a logical formula $\theta$. Its translation $T(\theta )$ uses only negation and logical implication and represents the same function. Thus $\{\neg ,\to \}$ is adequate.

Under any Boolean valuation there are two possibilities. If $\neg (\psi \to \chi )$ is false, the outer logical implication is true by vacuous truth. If it is true, then $\psi \to \chi$ is false, which forces $\psi$ true and $\chi$ false. In that case $\neg \chi$ is true, so the outer logical implication is again true. These possibilities exhaust the truth values of its antecedent; therefore

There is a three-line Hilbert formal proof. Use A1 with $\alpha =\chi$, $\beta =\psi$; then use A3 with $\alpha =\chi$, $\beta =(\psi \to \chi )$:This is a direct logical derivation in the displayed Hilbert proof system. Neither the deduction theorem for propositional logic nor a completeness theorem for propositional logic is needed: the desired logical implication is just the contrapositive, supplied by A3, of the particular A1 instance on line 1.

Yes, for soundness and completeness of theoremhood. An axiom-only complete propositional calculus is obtained as follows. Declare every propositional tautology, and only such a tautology, to be an axiom; supply no inference rules. A formal proof then consists of a single axiom. Every proved logical formula is valid, giving soundness, and every valid logical formula is already an axiom, giving completeness.

This is not merely an unspecified collection: whether a finite propositional formula is a tautology is decidable by its finite truth table, so the axiom set can be recognized effectively. It is a deliberately uninformative Hilbert proof system, since all the work has been put into axiom recognition. If one instead asked for strong completeness of derivations from arbitrary additional assumptions, a system whose only formal proof lines are axioms or assumptions would not suffice; the affirmative construction here concerns $⊢\varphi$ versus $\models \varphi$.

An $L$-structure consists of a nonempty domain $A$, an element $c^{\mathcal{A}}\in A$ for each constant symbol, a function $f^{\mathcal{A}}:A^n\to A$ for each $n$-ary function symbol, and a relation $R^{\mathcal{A}}\subseteq A^n$ for each $n$-ary predicate symbol. When equality is part of the logic it is interpreted as actual identity on $A$.

An assignment in a first-order structure is a function $s$ from logical variables to $A$. It induces a term valuation of first-order terms recursively:For an atomic formula, substitute these first-order term values into the interpreted relation, or compare them for equality. Extend satisfaction for a set structure through the truth tables of the logical connectives, and through the quantifier clausesThus the first-order structure and assignment in a first-order structure together determine truth values for all logical formulas. A first-order sentence has no free variables, so its truth does not depend on the assignment in a first-order structure.

The assertion that $\mathcal{A}$ is a first-order model of $\Gamma$ means that every first-order sentence belonging to $\Gamma$ is true in the first-order structure:Equivalently each first-order sentence is true under every assignment in a first-order structure, since first-order sentences have no free variables. The first-order sentences must all hold in the same interpretation of the language; one cannot select a different first-order structure for each member of $\Gamma$.

Use the following group axioms in the given language:Commutativity supplies the other identity and inverse equations. These first-order sentences therefore specify precisely an abelian group with the named identity $0$; an inverse function symbol is unnecessary because inverses are asserted to exist by a quantified formula.

For each positive integer $n$, let $t_n(x)$ be the first-order term recursively defined by $t_1(x)=x$ and $t_{n+1}(x)=t_n(x)+x$. Add the torsion-free abelian group axiom schemeEvery first-order model of these first-order sentences is an abelian group with no nonidentity element of finite order. Conversely every torsion-free abelian group satisfies each of the displayed first-order sentences. This is a countably infinite first-order axiomatization of exactly the required class.

No finite axiomatization exists. Write $\Gamma$ for the axioms just constructed and suppose a finite set $\Delta$ of first-order sentences had exactly the same first-order models. Its logical conjunction $\delta$ is a single first-order sentence, and $\Gamma \models \delta$. By the compactness theorem there is a finite subset ${\Gamma }_0\subseteq \Gamma$ with ${\Gamma }_0\models \delta$: otherwise $\Gamma \cup \{\neg \delta \}$ would be finitely satisfiable and hence satisfiable, a contradiction.

Only finitely many of the integers $n$ in the torsion-free scheme occur in ${\Gamma }_0$. Choose a prime number $p$ larger than all of them. The cyclic group $\mathbb{Z}/p\mathbb{Z}$ satisfies all the group axioms and each of these finitely many conditions from the torsion-free abelian group axiom scheme: multiplication by an integer $1\le n<p$ is invertible modulo $p$, so $nx=0$ implies $x=0$. It consequently satisfies ${\Gamma }_0$, then $\delta$, and therefore $\Delta$.

But its nonzero elements have finite order $p$, so it is not a torsion-free group, contradicting the assumed description of the first-order models of $\Delta$. This establishes the nonfinite axiomatizability of torsion-free abelian groups, ruling out every finite set of defining first-order sentences, not just finite subsets of the particular scheme in part (c).

For a standard classical propositional calculus, strong completeness statesTogether with soundness, this identifies semantic consequence with formal derivability. One proves the contrapositive by the maximal consistent set in propositional logic construction. If $\Gamma ⊬\varphi$, the set $\Gamma \cup \{\neg \varphi \}$ is propositionally consistent, by the deduction theorem for propositional logic and classical propositional reasoning. Extend it to a maximal consistent set in propositional logic $M$, deciding each logical formula in turn. At each stage at least one selection of $\theta$ or $\neg \theta$ preserves propositional consistency; a contradiction in the union would use only finitely many assumptions and hence already occur at a stage.

Define a Boolean valuation by $v(p_i)=1$ exactly when $p_i\in M$. Maximal consistency in propositional logic gives $\neg \theta \in M$ exactly when $\theta \notin M$, and $(\theta \to \eta )\in M$ exactly when either $\theta \notin M$ or $\eta \in M$. Structural induction on logical formulas therefore proves the maximal consistent set truth lemma $v(\theta )=1⟺\theta \in M$. Thus $v$ satisfies $\Gamma$ but falsifies $\varphi$, contradicting semantic entailment. The countable language here permits an enumeration of logical formulas; the corresponding general-language argument uses a well-ordering or a principle of maximality in a partially ordered set.

Gödel's completeness theorem for first-order sentences says that, in a standard sound first-order Hilbert calculus,Equivalently every first-order consistent set of first-order sentences has a first-order model: apply this existence statement to $T\cup \{\neg \sigma \}$ for the consequence formulation.

For the first-order model existence formal proof use a Henkin construction. Enlarge the language by fresh constant symbols and adjoin Henkin witness axiomsFreshness of $c_{\theta }$ preserves first-order consistency. In detail, if a contradiction followed after adjoining one witness axiom, the deduction theorem for first-order logic would yield its negation, from which one obtains both $\exists x\theta (x)$ and $\neg \theta (c_{\theta })$ over the old theory. Since the new constant symbol does not occur in that theory or in $\theta$, replace it by a fresh logical variable and generalize to derive $\forall x\neg \theta (x)$, a contradiction. Finitely many witness additions preserve first-order consistency successively, and unions preserve first-order consistency because formal proofs are finite. Iterate the enlargement so that logical formulas involving newly introduced constant symbols also receive witnesses. Include at least one constant symbol to guarantee closed terms.

Extend the resulting first-order consistent witnessed first-order theory to a maximal consistent set of first-order sentences $H$. In the equality-free case make the domain the set of closed terms. Interpret constant symbols and function symbols by their formal first-order term constructions; interpret an atomic formula byThe truth lemma for a Henkin term model follows by induction on logical formulas with closed terms substituted for their free variables. The logical connective steps use maximal consistency of a first-order theory. In the existential step, membership of $\exists x\theta$ supplies a witness constant and hence a first-order term satisfying $\theta$; conversely a satisfying closed term gives the existential sentence by an inference of the calculus. The term model consequently satisfies $H$ and the original theory. Equality is absent here, so distinct closed terms may remain distinct domain elements without further identifications.

In the presence of equality, two syntactically different closed terms can be asserted equal by the Henkin theory, so the raw first-order term domain from part (b) must be replaced by a quotient set. DefineThe equality axioms give reflexivity, symmetry and transitivity, so this is an equivalence relation. Their substitution consequences make it a congruence relation on a first-order structure: replacing an input by an equivalent first-order term preserves equivalence of function values and preserves membership of atomic formulas in $H$.

Take domain $\{[t]:t\text{ is a closed term}\}$. Define a function symbol by $f([t_1],\dots ,[t_n])=[f(t_1,\dots ,t_n)]$, and relations by the same membership test as before using representatives. The congruence relation on a first-order structure makes these definitions independent of representatives. Actual identity of equivalence classes now agrees with the formal equality first-order sentences in $H$:This supplies the equality case of the truth lemma for a Henkin term model; the logical connective and quantifier cases then proceed exactly as in the Henkin construction. Thus the term model built from the quotient set is a genuine first-order model with equality interpreted as identity.

For a countable first-order language, the Henkin construction introduces only countably many constant symbols: each round needs at most one for each logical formula, there are countably many finite strings in a countable alphabet, and countably many rounds suffice. There are therefore at most countably many closed terms. The term model, and also its quotient set by equality, has at most countably many elements.

It follows that every satisfiable theory in a countable first-order language has an at most countable first-order model. If the theory has no finite first-order model, the constructed first-order model is countably infinite. More generally the same counting argument gives a first-order model of cardinality at most $\max (|L|,{\aleph }_0)$ for any satisfiable theory in language $L$.

For the elementary-substructure version of the downward Löwenheim-Skolem theorem, begin with a first-order structure $M$ and a set $S$ of designated elements. Close $S$, the named constant symbols and one initial element under the language's functions and under chosen witnesses in $M$ for existential formulas with parameters already chosen. Iterate countably often. The resulting set has cardinality at most $\max (|L|,|S|,{\aleph }_0)$, and its induced substructure $N$ is elementary: induction on logical formulas proves the truth equivalence, with the existential case supplied by the chosen witnesses. This is the same witness mechanism as the Henkin formal proof, now keeping witnesses inside a given first-order model.

Let $T=\mathrm{Th}(\mathbb{C})$ in the finite language of rings: it is the set of all first-order sentences true in the field of complex numbers. It is satisfiable, with first-order model $\mathbb{C}$, so the countable-language Löwenheim-Skolem theorem gives an at most countable first-order model $K$ of $T$.

All field axioms belong to $T$, hence $K$ is a field. For every positive integer $n$, the first-order sentence saying that there are at least $n$ distinct elements is also true in $\mathbb{C}$ and belongs to $T$. Thus $K$ cannot be finite, and is countably infinite.

Finally, for each first-order sentence $\sigma$, either $\sigma \in T$ or $\neg \sigma \in T$. Since $K$ satisfies all of $T$, it satisfies $\sigma$ exactly when $\mathbb{C}$ does. ThereforeElementary equivalence concerns first-order first-order sentences and does not imply an isomorphism; the two fields have different cardinalities. The stronger downward form may even choose $K$ as a countable elementary subfield of $\mathbb{C}$.

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.