The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model.

For each $n\ge 1$, let ${\chi }_n$ assert that at least $n$ distinct elements exist. Consider $T=\{\varphi \}\cup \{{\chi }_n:n\ge 1\}$. A finite subset requires only some finite lower bound $N$ on the size. Choose an odd integer $m\ge N$; the given property of $\varphi$ supplies a model of that size, satisfying the finite subset. By the compactness theorem, $T$ has a model. Its domain has at least $n$ elements for every $n$, so $\varphi$ has an infinite model. This argument applies to every sentence with the finite-model-size property in (b), irrespective of its behavior on infinite structures.

Use an involution with exactly one fixed point:The first conjunct makes every orbit of the function $f$ have size one or two. The second says precisely one orbit has size one. A finite model therefore has $1+2m$ elements, an odd number.

Conversely, on any set of size $2m+1$, fix one element and partition the remaining $2m$ elements into pairs; let $f$ swap the two members of each pair. This defines a model of $\varphi$. The case $m=0$ gives a one-element model. Thus the finite model sizes are exactly the positive odd integers.

A first-order structure for this language is $\mathcal{A}=(A,f^{\mathcal{A}})$, where $A$ is a nonempty set and $f^{\mathcal{A}}:A\to A$ is a total function. The logical equality symbol is interpreted as actual equality on $A$; there are no other nonlogical symbols to interpret.

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.

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.

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.

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.

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.