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.

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.

Irrationality of $\sqrt{2}$ makes the expression $q+r\sqrt{2}$ unique for rational $q,r$: equality of two such expressions with different $r$ would express $\sqrt{2}$ as a rational number. Therefore the rule selecting the coefficient $r$ defines a function on $A$. Its domain is a vector subspace over $\mathbb{Q}$, and direct coefficient addition and rational scaling show it is $\mathbb{Q}$-linear, hence weakly linear. In particularUse Zorn's lemma on the nonempty family of weakly linear extensions of this particular function. Chain unions remain extensions by (a); hence there is a maximal extension $h$. Any further extension in $\mathcal{F}$ would also contain the original function, so this $h$ is maximal in $\mathcal{F}$. Part (b) therefore gives $\mathrm{dom}h=\mathbb{R}$.

A real-linear map $\mathbb{R}\to \mathbb{R}$ is multiplication by its value at $1$. Were $h$ real-linear, it would satisfycontradicting the inherited value $h(\sqrt{2})=1$. Thus a weakly linear function on all of $\mathbb{R}$ need not be real-linear. Its rational homogeneity of an additive function is insufficient for real homogeneity. This particular extension is also discontinuous: rational numbers approaching $\sqrt{2}$ have value zero, while the value at their limit is one.

A nonempty weakly linear function has a domain $D$ closed under rational scalars and addition, hence a vector subspace of $\mathbb{R}$ over $\mathbb{Q}$. Additivity first gives $f(0)=0$ and $f(-x)=-f(x)$, then $f(nx)=nf(x)$ for integers $n$. If $q=m/n$ with $n>0$, rational closure puts $qx$ in $D$ andThus $f(qx)=qf(x)$: it is a $\mathbb{Q}$-linear map. The empty function is not maximal because it extends to the function on $\{0\}$ with value zero.

Suppose a maximal $f$ had proper domain $D\ne \mathbb{R}$. Choose $t\notin D$ and any prescribed real value $a$, for instance $a=0$. Every element of $D+\mathbb{Q}t$ has a unique expression $d+qt$: if two expressions coincide and the coefficients differ, then $t$ would belong to $D$. DefineUniqueness makes this well-defined. The displayed logical formula and the $\mathbb{Q}$-linearity of $f$ show directly that $h$ is additive and has a domain closed under rational scalars. Hence it is a weakly linear function and extends $f$. It is a proper extension because $t$ is now in its domain, contradicting maximality. ThereforePart (a) and Zorn's lemma guarantee the existence of maximal extensions as well as this description of their domains.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound contains a maximal element. Here a chain means a subset totally ordered by the inherited order; it need not have a greatest member.

View every partial function as its graph, a subset of $\mathbb{R}\times \mathbb{R}$. The family $\mathcal{F}$ is a set by axiom of separation from the power set of this product. Let $\mathcal{C}\subseteq \mathcal{F}$ be a chain and put $h=\bigcup \mathcal{C}$. If two members of the union assign values to the same input, the chain property makes one graph contain the other, so those values agree. Thus $h$ is a partial function.

If $x\in \mathrm{dom}h$ and $q\in \mathbb{Q}$, choose a chain member containing $x$ in its domain. Its rational-scalar closure gives $qx\in \mathrm{dom}h$. If $x,y\in \mathrm{dom}h$, choose two chain members containing them; the larger one contains both, and therefore contains $x+y$ with value $h(x)+h(y)$. Hence $h$ satisfies the required additive identity and domain closure. Consequentlyand it is an upper bound for the chain. For the empty chain its union is the empty function, which satisfies the defining logical implications vacuously, so this case is covered too.

Inclusion gives $|\mathbb{R}\setminus \mathbb{Q}|\le \mathfrak{c}$. If $\kappa =|\mathbb{R}\setminus \mathbb{Q}|$, the disjoint decomposition of $\mathbb{R}$ givesThe irrational numbers are infinite, for instance $n+\sqrt{2}$ are pairwise distinct irrationals. Standard infinite cardinal addition gives ${\aleph }_0+\kappa =\max ({\aleph }_0,\kappa )$. Since Cantor's theorem gives $\mathfrak{c}>{\aleph }_0$, the equality forces $\kappa =\mathfrak{c}$. ThereforeThis is the permitted cardinal-arithmetic formal proof; it does not subtract infinite cardinals as though they were finite numbers.

The family is a subset of all complex sequences, so its cardinality is at mostFor each $z\in \mathbb{C}$, the sequence $(z,0,0,\dots )$ belongs to the family because its displayed series has just one nonzero first-order term. These sequences are distinct as $z$ varies, giving a lower bound $\mathfrak{c}$. ThusThe source condition is convergence of ${\sum }_j{a}_j^2$, without absolute-value bars. The argument uses exactly that printed condition and makes no assertion that it is equivalent to square summability of complex sequences. The same upper and lower bounds would also work for the stronger absolute-square condition, but no alteration of the source is needed.

Every strictly increasing sequence is in ${\mathbb{N}}^{\mathbb{N}}$, whose cardinality is ${\aleph }_0^{{\aleph }_0}=\mathfrak{c}$. This gives the upper bound.

For each binary sequence $ϵ=({ϵ}_n{)}_{n\in \mathbb{N}}$, defineThen $a_{n+1}-a_n=2+{ϵ}_{n+1}-{ϵ}_n\ge 1$, so the sequence is strictly increasing. Distinct binary sequences give distinct increasing sequences. This injects a set of size $2^{{\aleph }_0}$ into the desired family, giving the matching lower bound. HenceOne may also identify an increasing sequence with its infinite range subset of $\mathbb{N}$; the explicit binary coding establishes the lower bound without discarding finite subsets by cardinal subtraction.

The set $D=\mathbb{Q}+i\mathbb{Q}$ is countable and dense in $\mathbb{C}$. Restriction to $D$ is injective on continuous functions $\mathbb{C}\to \mathbb{R}$: if two such functions agree there, their equality set is closed and contains a dense set, so is all of $\mathbb{C}$. Equivalently a sequence of points of $D$ converging to any chosen point and continuity determine its value uniquely.

Thus the family has cardinality at mostFor the lower bound, every real number determines a different constant continuous function. Cantor-Schröder-Bernstein yieldsThe reduction to countably many values is the feature that separates this answer from unrestricted functions.

The set of all functions from a set of size $\mathfrak{c}$ to another set of size $\mathfrak{c}$ has size ${\mathfrak{c}}^{\mathfrak{c}}$. Cardinal exponentiation and the law $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \mu }$ giveThereforeThe lower bound can also be seen by taking characteristic functions of all subsets of $\mathbb{C}$. Cantor's theorem makes this strictly larger than $\mathfrak{c}$, unlike the continuous-function space in the next part.

The Cantor-Schröder-Bernstein theorem says that injections $X\to Y$ and $Y\to X$ imply a bijection $X\to Y$. Thus mutual cardinal inequalities imply equal cardinalities, without a choice assumption.

Write $\mathfrak{c}=2^{{\aleph }_0}=|\mathbb{R}|$. Standard cardinal arithmetic gives $\mathfrak{c}\cdot \mathfrak{c}=\mathfrak{c}$ and ${\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$. The correspondence $x+iy\leftrightarrow (x,y)$ is a bijection $\mathbb{C}\leftrightarrow {\mathbb{R}}^2$. HenceEquivalently, the real axis supplies the lower inequality and a coding of two real coordinates supplies the upper one; Cantor-Schröder-Bernstein then gives the equality.

Fix $m$ and induct on $n$. The initial equality $m+0=0+m$ follows from the defining zero clause and (ii). Assuming $m+n=n+m$, the successor clause and (iii) giveThis provesThe extension to arbitrary ordinals is false. By the limit clause for ordinal addition,whereas $\omega +1$ is the successor ordinal of $\omega$ and is strictly greater than it. ThereforeFinite addition is commutative; ordinal addition records the order of concatenated well-orders and need not be commutative.

Fix $m,n$ and induct on $k$. For $k=0$,For the induction step, use the multiplication recursion, the induction hypothesis, and addition associativity from (i):ThusThis establishes the indicated distributive law without assuming multiplication is commutative.

Fix $m$ and induct on $n$. At $n=0$,If $m^{+}+n=m+n^{+}$, thenThe last expression is the right-hand side required at the successor $n^{+}$. ThereforeIn particular both sides also equal $(m+n{)}^{+}$ by the recursion equation for the second argument.

Induct on $n$. The initial equation is $0+0=0$ by the zero clause. If $0+n=n$, the successor clause givesConsequentlyThis proves the left-identity property independently of the right-identity equation built into the recursive definition.

The axiom of infinity asserts that an inductive set exists: some set $I$ contains $0=\varnothing$ and contains $x^{+}=x\cup \{x\}$ whenever it contains $x$. Inside one such $I$, axiom of separation definesThis intersection is itself inductive and is contained in every inductive set, by intersecting that set with $I$. It is therefore the set of natural numbers. If a property holds at $0$ and passes from $n$ to $n^{+}$, axiom of separation forms the subset of $\omega$ on which it holds. That subset is inductive, so must equal $\omega$. This proves mathematical induction, including properties with set parameters.

Recursion on $\omega$ defines the arithmetic operations byExistence and uniqueness follow from the recursion theorem on the natural numbers.

For associativity of addition fix $m,n$ and induct on $k$. At $k=0$ both sides equal $m+n$. If the equality holds at $k$, thenThusEvery step after the induction hypothesis is a defining successor equation, so commutativity has not been used prematurely.

Suppose such a first-order theory $S$ existed. Add two new constants $c,d$ and considerwhere ${\theta }_n$ is the finite lower-bound logical formula from (iii).

Every finite subset of $T$ has a first-order model. Choose a first-order structure with exactly two equivalence classes: one countably infinite, and one finite of size at least the largest bound appearing in that subset. Interpret $c$ in the infinite class and $d$ in the finite class. The first-order structure satisfies all of $S$, by its assumed characterization, and meets the finite demands on both named classes.

Compactness theorem in the language with the two new constants gives a first-order model of all of $T$. Its classes of $c$ and $d$ are distinct and both infinite. Its reduct still satisfies $S$, which is impossible if $S$ characterizes exactly one infinite class. HenceThe finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.

Take $S_1$ to consist of the three usual first-order sentencesThese assert reflexivity, symmetry and transitivity and therefore define exactly the equivalence relations.

For $S_2$, adjoin to $S_1$ the single first-order sentenceIts witness $y$ gives a second member of each class, while its final universal clause excludes all others. Hence every class has exactly two members, and conversely such a relation satisfies it. This remains a finite set of first-order sentences.

For each positive integer $n$, writeThenEvery class in a first-order model has at least $n$ elements for every $n$, so cannot be finite. Conversely every infinite equivalence class supplies each finite collection of distinct witnesses. The displayed infinite scheme therefore has exactly the requested first-order models.