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

Source release: Oxford examination archive release thread, Part B bundle pages 187–191. The cover cross-lists Mathematics, Mathematics and Computer Science, and Mathematics and Philosophy, all Part B, Friday 11 June 2010, 2.30pm–5.30pm.

Answer availability checked on 28 October 2026: bounded official Oxford searches by exact year, paper label and course title found no advertised exact-paper answers. The official Part B syllabus for the 2010 examination identifies the course. No later-year answer-release policy was assumed applicable.

The alphabet of a first-order language separates logical symbols from nonlogical symbols. In the standard presentation here the logical symbols are the variables $x_0,x_1,\dots$, equality $\dot{=}$, negation $\neg$, logical implication $\to$, the universal quantification $\forall$, and the punctuation symbols parentheses and comma. The nonlogical symbols are constant symbols, function symbols of each specified finite arity, and predicate symbols of each specified finite arity, such as $f_n^{(k)}$ and $P_n^{(k)}$.

Constants can equivalently be treated as zero-ary function symbols. Their arities belong to the language specification. Other logical connectives, and $\exists x\varphi$ as an abbreviation for $\neg \forall x\neg \varphi$, need not be primitive alphabet symbols. This distinction matters in counting literal symbol occurrences.

The first-order terms are the least collection containing every variable and constant and closed under formation of $f(t_1,\dots ,t_k)$ whenever $f$ has arity $k$ and the $t_j$ are terms. A closed term has no variables.

The first-order formulas are the least collection containing the atomic formulas $t_1\dot{=}{t}_2$ and $P(t_1,\dots ,t_k)$ of the appropriate arities, and closed under negation, logical implication, and universal quantification: from formulas $\varphi ,\psi$ one may form $\neg \varphi$, $(\varphi \to \psi )$, and $\forall x_i\varphi$, with the chosen fully parenthesized grammar. Only finite expressions obtained by these rules are formulas. No additional strings belong to either collection.

Terms denote elements under an assignment in a first-order structure; formulas receive truth values in a first-order structure. The two syntactic categories have different formation rules even when they use some of the same punctuation.

False. A ternary atomic predicate gives a counterexample:This string contains one opening parenthesis and two commas. Thus its number of opening parentheses is smaller than its number of commas. A high-arity argument list contributes several commas while requiring only one pair of parentheses.

False. Choose a variable $x_j$ different from $x_i$ and takeThe variable $x_i$ does not occur at all, so in particular it is not free. Yet the formula has one universal-quantifier symbol and zero occurrences of $x_i$. The hypothesis on free occurrences of one variable does not control quantifiers binding other variables.

False. Let $\varphi$ be $x_i\dot{=}{x}_i$ and let $t=x_j$ with $j\ne i$. There is no quantifier that could capture a variable, so $t$ is free for $x_i$ in $\varphi$. Capture-avoiding substitution givesThe number of occurrences of $x_i$ falls from two to zero, contradicting the proposed strict increase. Even capture-avoiding substitution of $x_i$ itself would leave the formula unchanged and refute the strict inequality.

True. In the formation rules, commas occur only between arguments in a function application or an atomic predicate application. Each such argument list includes an opening parenthesis. Subsequent construction of larger terms or formulas retains those symbols.

Equivalently prove by simultaneous structural induction on terms and formulas that an expression containing no opening parenthesis contains no comma. Variables and constants have neither; a comma-bearing function or predicate application already has an opening parenthesis; equality, connectives, and quantifiers cannot introduce a comma outside their constituent expressions. Taking the contrapositive proves the claim.

A collection of logical connectives is adequate, or has functional completeness, if every Boolean function of finitely many propositional variables can be expressed by a formula using those connectives and variables, with the usual convention for nullary truth constants stated if those are included.

An adequate example is $\boxed{\{\neg ,\to \}}$. An inadequate example is $\boxed{\{\to \}}$: formulas using logical implication alone preserve truth when every input is true, so cannot express negation. These examples concern truth functions, rather than mere syntactic formation of formulas.

Use structural induction on formulas. Every term denotes the unique element. Every atomic predicate is true by hypothesis, and every equality is true because its two terms denote that same element.

If both immediate subformulas of an logical implication are true, their logical implication is true. A universal or existential quantification ranges over the singleton domain; its matrix is true for the only possible value by induction, so either quantified formula is true. These are all the formation cases in the reduced language. Hence

No. The full language can express $\neg (x_0\dot{=}{x}_0)$, which is false in the singleton structure from part (i). Every formula of the reduced language is true in that structure under every assignment in a first-order structure. Therefore no formula of the reduced language can be logically equivalent to this negated equality.

This is a singleton truth-preservation obstruction to expressive completeness. Adding both quantifiers to logical implication does not repair the failure: on this particular nonempty singleton model, quantification cannot create a false formula from true atomic formulas.

Let $f=\alpha \to (\beta \to \gamma )$ and $h=\alpha \to \beta$. Temporarily assume $f$, $h$, and $\alpha$. Modus ponens rule first gives $\beta \to \gamma$ from $f$ and $\alpha$, then $\beta$ from $h$ and $\alpha$, and finally $\gamma$.

Apply the deduction theorem for propositional logic successively to discharge $\alpha$, then $h$, then $f$. The result isthe required axiom scheme. This derivation uses only assumptions, modus ponens rule, and the added deduction rule; no negation axiom is involved.

The requested derivation does not follow from the printed axiom set. Use a two-valued matrix interpretation with ordinary material logical implication and designated value $1$, but interpret the unary symbol $\neg$ by the constant function $N(0)=N(1)=0$.

Every instance of the first axiom $\alpha \to (\beta \to \alpha )$ is valid. In the replacement axiom, both $N(\beta )\to \alpha$ and $N(\alpha )\to \beta$ have value $1$, so its whole logical implication is valid as well. Modus ponens rule preserves the designated value. The deduction rule is sound for semantic consequence under this interpretation because logical implication is the ordinary truth-functional logical implication. Induction on derivations, allowing arbitrary sets of assumptions, therefore makes every theorem valid in this matrix.

But the old contraposition axiom has valuewhich is false when $\alpha =1$ and $\beta =0$. ConsequentlyThis is a truth-matrix countermodel for a Hilbert axiom set. A nonstandard interpretation of a primitive symbol is legitimate for proving syntactic nonderivability: only preservation by the displayed axioms and rules is required. The source would need a stronger negation axiom or an extra negation principle to support its requested conclusion.

The old system does derive the replacement axiom. Here is a syntactic proof using only its axioms, modus ponens rule, and the permitted deduction theorem for propositional logic.

First derive explosion. From $U$ and $\neg U$, the first axiom gives $\neg V\to \neg U$. The old third axiom then gives $U\to V$, and modus ponens rule with $U$ gives any desired $V$.

Next derive the classical reductio rule. Suppose $\Gamma ,\neg B$ derives both $C$ and $\neg C$. Let $T$ be the theorem $B\to B$, obtainable by applying the deduction theorem for propositional logic to the identity derivation from assumption $B$. Explosion under $\Gamma ,\neg B$ gives $\neg T$, so the deduction theorem for propositional logic gives $\Gamma ⊢\neg B\to \neg T$. The old third axiom with $\alpha =T$, $\beta =B$ yields $\Gamma ⊢T\to B$. Since $T$ is a theorem, $\Gamma ⊢B$. Thus a contradiction under $\neg B$ permits deriving $B$ with that temporary assumption discharged.

Now assume $h=\neg \beta \to \alpha$ and $\neg \alpha$, and temporarily also assume $\neg \beta$. Modus ponens rule gives $\alpha$, contradicting $\neg \alpha$. The just-proved reductio rule discharges $\neg \beta$ and gives $\beta$. Finally discharge $\neg \alpha$ and $h$ by the deduction theorem for propositional logic:No propositional completeness theorem is needed in this derivation.

Only one logical implication of the printed equivalence is justified:The new system's first axiom is an old axiom, its replacement axiom is derivable in the old system by part (iii), modus ponens rule is shared, and its deduction rule is admissible in the old system by the theorem allowed in the source. Induction on a new-system derivation therefore translates it into an old-system derivation with the same assumptions.

The reverse logical implication is false for the displayed systems. Take $\Gamma =\varnothing$ and let $\varphi$ be an instance of the old contraposition axiom, for example with distinct propositional variables in place of $\alpha ,\beta$. It is an old-system theorem, but the matrix countermodel in part (ii) refutes its derivability in the new system. Thus the requested two-way equivalence cannot be concluded from these printed axioms.

Write $U=\forall x_i\neg \varphi$ and $H=\neg U\to \psi$. All derivations below use the printed replacement axiom, so they do not rely on the false equivalence from part (a).

The identity logical implication $\neg A\to \neg A$ follows by the deduction rule. Substituting $\alpha =\neg A$, $\beta =A$ into the replacement axiom and applying modus ponens rule therefore gives double-negation elimination:Universal instantiation gives $⊢U\to \neg \varphi$. Combine it with $⊢\neg \neg U\to U$ using modus ponens rule under a temporary assumption and then the deduction rule, obtaining $⊢\neg \neg U\to \neg \varphi$.

In the replacement axiom now substitute $\alpha =\neg \varphi$ and $\beta =\neg U$. Its antecedent is precisely the last theorem, and its consequent is $\neg \neg \varphi \to \neg U$. ThusUnder the fixed assumption $H$ and temporary assumption $\neg \neg \varphi$, modus ponens rule gives $\neg U$ and then $\psi$. Discharge the temporary assumption to obtain $H⊢\neg \neg \varphi \to \psi$.

Finally apply universal generalization. The variable $x_i$ is not free in $H$, because it is bound in $U$ and is not free in $\psi$ by hypothesis. Hence the side condition is satisfied andGeneralization is applied after the temporary assumption has been discharged; applying it while that assumption remained open would not be justified.

A consistent set of formulae, restricted here to sentences, does not derive a contradiction in the chosen classical deductive system. Equivalently there is no sentence $\theta$ for which both $\Sigma ⊢\theta$ and $\Sigma ⊢\neg \theta$ hold. By explosion, an inconsistent set derives every sentence; a consistent set does not.

This is a syntactic condition about finite derivations, rather than a definition in terms of models.

A set of sentences is maximal consistent if it is consistent and no proper extension by further sentences remains consistent. Equivalently it is consistent, deductively closed, and decides every sentence: for each $\theta$, exactly one of $\theta$ and $\neg \theta$ belongs to it.

For example, if $\Sigma ⊢\theta$ but $\theta \notin \Sigma$, adding $\theta$ does not create a new contradiction, contrary to maximality. Thus maximality includes deductive closure, not only having as many independent axioms as possible.

A set of sentences is satisfiable if some nonempty first-order structure in its language makes every sentence in the set true. Because the formulas are sentences, their truth is independent of the assignment in a first-order structure.

This is a semantic existence condition. Its equivalence with syntactic consistency is the content of the classical Gödel's completeness theorem, together with soundness.

Order the consistent sets of sentences extending $\Sigma$ by inclusion. This collection is nonempty. The union of a chain is consistent: any derivation of a contradiction uses finitely many assumptions, which all lie in one member of the chain. Zorn's lemma therefore supplies a maximal member, which is a maximal consistent extension of $\Sigma$.

For a countable language one can instead enumerate all sentences and successively add either a sentence or its negation while preserving consistency. At least one choice is consistent, since inconsistency of both extensions, together with the deduction theorem for propositional logic and classical reasoning, would make the previous stage inconsistent. The union of the stages is consistent by finite use of assumptions and decides every sentence, so it is maximal consistent.

The chain proof covers arbitrary set-sized languages; no restriction on the language cardinality was printed here. The later prohibition on choice applies to the cardinal-arithmetic question, not this logic construction.

Suppose a structure satisfies every sentence of $\Sigma$. By the soundness theorem for first-order logic, every sentence derivable from $\Sigma$ is true in this structure. In particular it cannot derive both a sentence and its negation, because they cannot both be true under the usual semantics.

Therefore $\boxed{\Sigma \text{ satisfiable}⟹\Sigma \text{ consistent}}$. This direction uses soundness alone, without constructing a model from a proof-theoretic assumption.

In the Henkin construction, first extend the consistent sentence set to a complete consistent theory with witnesses in an expanded language containing fresh constants. Its term model has closed terms modulo provable equality as elements:Functions are interpreted by applying their symbols to representative terms, and an atomic predicate holds of term classes exactly when the corresponding atomic sentence belongs to $T$. Equality axioms make these definitions independent of representatives. The Henkin witness property handles the existential step in the truth lemma, so the resulting structure satisfies $T$ and hence the original $\Sigma$.

An arbitrary sentence set need not already have enough closed terms or witnesses. Calling this a term model for $\Sigma$ means a term-model construction of a model satisfying $\Sigma$, usually through that witnessed completion; it does not assert that every arbitrary $\Sigma$ itself already supplies the construction.

The downward Löwenheim-Skolem theorem says that a structure in a countable language has a countable elementary substructure containing any specified finite or countable set of its elements. More generally the size bound is $\max (|\mathcal{L}|,|C|,{\aleph }_0)$ for a required parameter set $C$. In particular any satisfiable theory in a countable language has a model of size at most countable.

To see the last assertion directly from the completeness construction, add only countably many witness constants in the Henkin construction. There are then countably many finite closed terms, and taking their quotient cannot increase cardinality. The resulting term model is therefore countable. For the elementary-substructure version, perform the witness construction inside the given structure, choosing actual witnesses and closing under the function symbols. The induced substructure is elementary by the Tarski-Vaught test. This is the same witness mechanism as the completeness construction, with the ambient structure supplying the chosen witnesses.

The upward companion states that a theory with an infinite model has models in every sufficiently large infinite cardinal, at least $|\mathcal{L}|+{\aleph }_0$. Add that many pairwise unequal constants, apply compactness, and then the size-bounded construction. The countable consequence is the part needed below.

Use the axioms for a strict dense linear order without endpoints:The first three give strict linear order; the next gives density; the final two exclude endpoints. Domains are nonempty under the adopted first-order semantics, and these axioms force them to be infinite.

Yes. The usual order on the rational numbers is strict and linear. Between $a<b$ lies the rational midpoint $(a+b)/2$, and $a-1,a+1$ witness absence of endpoints. Thus it is a dense linear order without endpoints.

Yes. The usual order on the real numbers is strict and linear, midpoints witness density, and translation by $\pm 1$ supplies points on either side. It therefore satisfies the same dense linear order without endpoints axioms.

No. With its induced usual order, the closed interval has a least element and a greatest element. At zero there is no smaller domain element, and at one there is no larger domain element. It fails the no-endpoint axioms, although it is densely ordered.

Yes. The induced order is strict and linear and remains dense. For $0<x<1$, the points $x/2$ and $(x+1)/2$ lie in the domain and are strictly below and above $x$. Hence the open interval is a dense linear order without endpoints.

Yes. Removing zero leaves the induced order strict and linear, with no endpoints. For any $a<b$ there are infinitely many points in the real interval between them, so one can choose an intermediate point different from zero. More explicitly, the midpoint works unless it is zero, in which case $(2a+b)/3$ is nonzero and lies strictly between the endpoints. Thus density also survives.

The missing point is a cut, not a pair of adjacent elements; the axioms do not require all cuts to be filled.

Enumerate both countable models. Build an increasing sequence of finite order-preserving partial bijections. At an even stage, take the first unmatched element of the first model. Its position relative to the finitely many already matched points determines an open interval or exterior ray in the second model. Density and absence of endpoints supply an unused point there, so the map extends.

At an odd stage perform the symmetric operation starting from the second model, extending the inverse map. Every required interval has infinitely many points, so avoiding the finitely many used values is possible. The union is a total bijection, by the alternating enumeration requirements, and it preserves and reflects order because every finite stage does. Hence it is an isomorphism of structures.

This is the back-and-forth method, proving countable categoricity of the dense-order theory.

The theory is consistent because the rational order is a model. If some sentence $\theta$ were not decided by the theory, both extensions by $\theta$ and by $\neg \theta$ would be consistent. By Gödel's completeness theorem and the countable-model consequence of Löwenheim-Skolem theorem, each would have a countable model. The two models would disagree on $\theta$, so could not be isomorphic. This contradicts part (iii).

Therefore the theory decides every sentence and is complete. Under the standard convention that a theory includes all its logical consequences, this makes it maximal consistent.

If one takes only the displayed finite list of axioms as a raw set, that list is not literally maximal consistent: one can add further theorems without inconsistency. The conclusion applies to its deductive closure, which is the complete theory of dense linear order without endpoints.

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.