The compactness theorem says that a set $T$ of first-order sentences has a first-order model if and only if every finite subset of $T$ has a first-order model. One direction follows by using the same first-order model for each subset.

For the nontrivial direction suppose every finite subset has a first-order model, but $T$ has none. Semantically $T\models \perp$, so completeness gives a formal logical derivation $T⊢\perp$. A formal logical derivation is finite and uses only finitely many assumptions, say $T_0\subseteq T$. Thus $T_0⊢\perp$. Soundness would make $T_0$ unsatisfiable, contradicting the hypothesis. Here $\perp$ can be any fixed contradictory first-order sentence, such as $\exists x(x\ne x)$, if it is not a primitive logical symbol. Therefore finite satisfiability implies satisfiability.

Soundness states that formal derivability implies semantic entailment:For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.

Strong completeness states the converse:Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.

For independence, construct four first-order structures, each satisfying exactly the three required remaining axioms and failing the chosen one.

To fail associativity, use the carrier $\{0,1,2\}$, interpret $c$ as $0$, and define the commutative operation by its table:The first row and column give a two-sided identity, and every element is its own inverse because the diagonal entries are $0$. Symmetry gives commutativity. Butso associativity fails.

To fail the identity axiom, take $\{0,1\}$, $c=0$, and the constant operation $F(x,y)=0$. It is associative and commutative, and every element has a two-sided partner producing $c$; but $F(1,c)=0\ne 1$.

To fail the inverse axiom, use natural numbers under addition with $c=0$. Addition is associative and commutative and has the required identity, but $1$ has no additive inverse in this carrier.

To fail commutativity, use the symmetric group $S_3$ under permutation composition with $c$ its identity. Associativity, identity and inverses are group properties, while $(12)(23)\ne (23)(12)$. Each countermodel witnesses the failure of semantic entailment from the other three to the failed first-order sentence. Hence the four source axioms are independent.

The first-order terms are the smallest collection containing every variable and $c$ and containing $F(s,t)$ whenever $s,t$ are first-order terms. The atomic formulas are exactly $s\approx t$ for first-order terms $s,t$. Logical formulas are then obtained from atomic formulas by the logical connectives and quantifiers: if $\theta ,\psi$ are logical formulas and $x$ a variable, then $\neg \theta$, $(\theta \wedge \psi )$, $(\theta \vee \psi )$, $(\theta \to \psi )$, $\forall x\theta$ and $\exists x\theta$ are logical formulas. These closure rules, with no additional strings admitted, define the syntax; a presentation using fewer primitive connectives treats the others as abbreviations.

Semantic entailment is the conditionThe same first-order variable assignment is used for all premises and the conclusion. This matters when free variables occur; for first-order sentences the truth value is independent of the first-order variable assignment.

Suppose both extensions were inconsistent. By the explosion argument in (i), the extension by $\varphi$ proves $\neg \varphi$, and the extension by $\neg \varphi$ proves $\varphi$. The deduction theorem for propositional logic therefore yieldsThe identity theorem gives $⊢\neg \varphi \to \neg \varphi$ and $⊢\varphi \to \varphi$. Apply E to the first displayed logical implication and the identity logical implication with antecedent $\neg \varphi$ to obtain $\Gamma ⊢\neg \varphi$. Apply E to the identity logical implication with antecedent $\varphi$ and the second displayed logical implication to obtain $\Gamma ⊢\varphi$. This contradicts propositional consistency of $\Gamma$.

Consequently at least one of the two one-formula extensions is propositionally consistent. The formal proof uses the source's own calculus, including its rule E, rather than assuming an unproved completeness theorem for this presentation.

For this calculus the deduction theorem for propositional logic isFor the reverse logical implication, retain the logical derivation from $\Gamma$, add the assumption $\alpha$, and use modus ponens rule.

For the forward logical implication, induct on a logical derivation from $\Gamma \cup \{\alpha \}$. For each line $\delta$ we construct a logical derivation of $\alpha \to \delta$ from $\Gamma$. If $\delta =\alpha$, use (ii). If $\delta$ is an axiom instance or belongs to $\Gamma$, it is already derivable from $\Gamma$; L1 gives $\delta \to (\alpha \to \delta )$, and modus ponens rule finishes that case.

If $\delta$ comes from $\eta$ and $\eta \to \delta$ by modus ponens rule, the induction hypothesis suppliesPart (iii) supplies $\Gamma ⊢\alpha \to \delta$.

If $\delta$ comes by the elimination rule E from $\eta \to \delta$ and $\neg \eta \to \delta$, the induction hypothesis suppliesThe L2 instance with $(\alpha ,\beta ,\gamma )=(\alpha ,\eta ,\delta )$ combines these by two applications of modus ponens rule. Thus the rule E also survives the discharge construction. These are all possible lines, proving the theorem for the final line $\beta$.

An instance of L3 isUsing the first assumed logical derivation and modus ponens rule gives $\Gamma ⊢\alpha \to (\neg \beta \to \gamma )$. The L2 instance for these same three propositional formulas isUse the other assumed logical derivation and then the newly obtained logical derivation in two applications of modus ponens rule. ThereforeThis conditional modus ponens construction is the step needed to discharge assumptions from a modus ponens rule line in part (iv).

Choose an auxiliary propositional formula $\beta$. The two instances of L1 areThe instance of L2 with $\gamma =\alpha$ isApply modus ponens rule first with the first L1 instance and then with the second. This is an assumption-free logical derivation, soIn particular no semantic completeness theorem or deduction theorem for propositional logic has been assumed to obtain this identity theorem.

A logical derivation from $\Gamma$ is a finite sequence of propositional formulas, each either a member of $\Gamma$, an instance of one of the three axioms, or obtained from earlier lines by one of the two displayed inference rules. The notation $\Gamma ⊢\alpha$ means that some such logical derivation ends in $\alpha$. Writing $⊢\alpha$ means derivability with no assumptions.

Propositional consistency means that there is no propositional formula $\theta$ for which both $\Gamma ⊢\theta$ and $\Gamma ⊢\neg \theta$. Equivalently not every propositional formula is derivable. To check the equivalence directly for this calculus, use the identity theorem proved in (ii): from $\theta \to \theta$ and L3 obtain $\theta \to (\neg \theta \to \eta )$; two uses of modus ponens rule give arbitrary $\eta$. Thus a contradictory theory proves everything. Conversely a theory proving everything proves a propositional formula and its negation.

Assume first that $\varphi$ is false on the all-true and all-false Boolean valuations. Use the truth-table normal form from part (ii). Every satisfying Boolean valuation on the finitely many propositional variables must have at least one true propositional variable and at least one false propositional variable. Its minterm therefore has the formwhere $C_s$ conjoins its true propositional variables and $D_s$ disjoins its false propositional variables; both lists are nonempty. This is equivalent to $\neg (C_s\to D_s)$. If the satisfying Boolean valuations are indexed by $1,\dots ,N$, De Morgan's laws givesIf there are no satisfying Boolean valuations, take $N=1$ and $C_1=D_1=p$: the result is $\neg (p\to p)$, again always false.

Conversely, on the all-true Boolean valuation every nonempty $D_i$ is true, so every $C_i\to D_i$ is true. On the all-false Boolean valuation every nonempty $C_i$ is false, so every logical implication is again true. Negating their logical conjunction gives false on both Boolean valuations. Logical equivalence transfers these values to $\varphi$. The usual nonempty meaning of logical conjunction and logical disjunction of propositional variables is used here; allowing empty $C_i$ or $D_i$ without qualification would destroy this converse.

Two propositional formulas are logically equivalent if every Boolean valuation gives them the same truth value. A disjunctive normal form is a logical disjunction of logical conjunctions of literals, with a literal being a propositional variable or its negation.

Let $p_1,\dots ,p_n$ include all propositional variables appearing in $\varphi$. For each Boolean valuation $s\in \{T,F{\}}^n$, putThe minterm $M_s$ is true exactly for Boolean valuations whose restrictions to these propositional variables are $s$. ConsequentlyIndeed, an Boolean valuation making $\varphi$ true makes its own minterm true, while a true minterm in the displayed logical disjunction certifies the truth of $\varphi$. There are only finitely many Boolean valuations, so this is a finite disjunctive normal form. If there are no satisfying Boolean valuations, use $p\wedge \neg p$ for any propositional variable $p$; this is a disjunctive normal form for falsity without needing an empty logical disjunction convention.

A Boolean valuation is an arbitrary function $v$ assigning one of the two truth values to each propositional variable. It extends uniquely to all propositional formulas by following the construction of the propositional formula:For logical implication, $\tilde{v}(A\to B)$ is false exactly when $\tilde{v}(A)$ is true and $\tilde{v}(B)$ is false; otherwise it is true. Here the operations on the right are Boolean operations on truth values. Structural recursion gives existence, and structural induction gives uniqueness: once the immediate subformulas have their values, the outer connective fixes the resulting value.

Construct compatible choices in the nested spaces, rather than choosing unrelated orthonormal bases for different $V_n$. Set $V_{-1}=\{0\}$ and defineThe orthogonal complement is taken for the inner product from part (i). Since $\dim V_n=n+1$ and $\dim V_{n-1}=n$, the space $L_n$ has dimension one and $V_n=V_{n-1}\oplus L_n$.

It is an invariant subspace. Indeed, if $v\in L_n$ and $u\in V_{n-1}$, part (ii) givesbecause $Tu\in V_{n-1}$. Also $Tv\in V_n$. Hence $Tv\in L_n$. Any nonzero vector in this one-dimensional space is consequently an eigenvector. Choose a unit vector $g_n\in L_n$. It has polynomial degree exactly $n$: membership in $V_{n-1}$ would make it orthogonal to itself and thus zero. Part (iii) now supplies its eigenvalue.

For $m<n$, $g_m\in V_{n-1}$ and $g_n\perp V_{n-1}$, so the choices are pairwise orthogonal. We have provedAn explicit compatible construction is the Gram-Schmidt process on $1,x,x^2,\dots$:The leading term of $r_n$ is $x^n$, so it is never zero. This fixes the positive real leading coefficient and yields the normalized Hermite polynomials. For example, the Gaussian integral givesEvery polynomial is a finite linear combination of these eigenvectors, since $g_0,\dots ,g_n$ form an orthonormal basis of $V_n$ for each $n$.

If $f\in V_n\setminus V_{n-1}$, write $f(x)=a_n{x}^n+\cdots$ with $a_n\ne 0$. In the expression $Tf=f^{\prime \prime }-2x{f}^{\prime }-2f$, the first term has polynomial degree at most $n-2$, while the other two contributeThus, if $Tf=\lambda f$, comparison of the leading coefficients givesFor $n=0$ take $V_{-1}=\{0\}$; the same result follows from $T1=-2$. This identifies the eigenvalue conditional on the existence of the eigenvector; existence is established next.

Differentiate the expression from the source before applying any finite-dimensional result. The exponential factors cancel:This is a polynomial whenever $f$ is a polynomial, and its polynomial degree is at most that of $f$. Differentiation and multiplication are linear, so $T$ is a linear transformation $V\to V$, and every $V_n$ is an invariant subspace.

For self-adjointness, put $w(x)=e^{-x^2}$. Then $w^{\prime }=-2xw$ and $wTf=(w{f}^{\prime }{)}^{\prime }-2wf$. Integration by parts therefore givesThe discarded endpoint terms are $w\overline{f^{\prime }}g$ and $w\overline{f}{g}^{\prime }$. They vanish at both infinities because exponential decay dominates every polynomial. The same decay justifies the intermediate integrals. ConsequentlyHere the question's self-adjointness is in the sense of an adjoint on an inner product space: $T$ itself represents the adjoint on the polynomial space. Each finite-dimensional restriction $T{|}_{V_n}$ is a self-adjoint operator. No choice of operator domain in a completed Hilbert space is needed for this argument. The resulting Gaussian polynomial operator will produce Hermite polynomials in part (iv).

The integral is conjugate-linear in $f$, linear in $g$, and conjugate-symmetric, by the corresponding properties of the integral and of complex conjugation. Also,If a polynomial $f$ is not zero, there is a real point $x_0$ with $f(x_0)\ne 0$: a nonzero polynomial cannot vanish at every real point. By continuity, $|f|$ has a positive lower bound on a sufficiently small closed interval about $x_0$. The continuous function $e^{-x^2}$ also has a positive lower bound there. The integral over this interval is strictly positive. HenceTogether with the finiteness allowed in the question, these properties prove that the formula defines an inner product on $V=\mathbb{C}[x]$.

Let $e_1,\dots ,e_d$ be the given orthonormal basis, with $T{e}_j={\lambda }_j{e}_j$. From the defining identity of the adjoint operator,These coordinates prove $T^{\ast }{e}_j={\overline{\lambda }}_j{e}_j$ without assuming a matrix formula. Thereforefor every basis vector. Thus $T$ is a normal operator, andThe condition of possessing an orthonormal basis of eigenvectors is already part of the hypothesis; real eigenvalues alone would not imply self-adjointness for an arbitrary linear transformation.

Proceed by induction on $\dim V$. The result is immediate for dimension zero. In positive dimension, the characteristic polynomial has a root over the complex numbers, so there is a nonzero eigenvector $v$ with eigenvalue $\lambda$. Normalize it to have norm one. Self-adjointness givesso $\lambda$ is real.

The orthogonal complement $v^{\perp }$ is an invariant subspace: if $w\perp v$, thenThe restriction of $T$ to $v^{\perp }$ is again self-adjoint, since the same inner product identity holds on that subspace. By induction it has an orthonormal basis of eigenvectors. Adjoining $v$ givesThe existence of the first eigenvector is the essential use of the complex numbers in this proof of the finite-dimensional spectral theorem.

Use the convention that the inner product is conjugate-linear in its first argument and linear in its second, as in part (b). The adjoint operator is characterized byExistence and uniqueness follow from the finite-dimensional representation of linear functionals by the inner product. More concretely, choose an orthonormal basis $e_i$ and let $a_{ij}=⟨e_i,T{e}_j⟩$. Thenwhich defines $T^{\ast }$ uniquely and verifies the required identity by expansion in that basis. Thus its matrix is the conjugate transpose, proved here rather than assumed. A self-adjoint operator satisfies $T^{\ast }=T$, equivalently $⟨Tv,w⟩=⟨v,Tw⟩$ for every pair of vectors.

If $\varphi =T^{\prime }\psi$ and $v\in \ker T$, then $\varphi (v)=\psi (Tv)=0$. Thus $\mathrm{im}{T}^{\prime }\subseteq (\ker T{)}^{\circ }$, using the annihilator of a vector subspace.

Conversely, let $\varphi$ vanish on the kernel of a linear map $\ker T$. Define a linear functional on $\mathrm{im}T$ by ${\psi }_0(Tv)=\varphi (v)$. This is well-defined: $Tv=Tw$ implies $v-w\in \ker T$, so $\varphi (v)=\varphi (w)$. Extend ${\psi }_0$ to a linear functional $\psi$ on $W$, using the extension argument from part (i). Then $T^{\prime }\psi =\varphi$, provingThe dimension formula from part (i) and the rank-nullity theorem now giveTo deduce the eigenvalue statement, apply this equality of rank of a linear map to $T-\lambda I$. Its dual map is $T^{\prime }-\lambda I$, so their kernel of a linear map dimensions agree. Thus the same $\lambda$ are eigenvalues, with the same geometric multiplicities.

For algebraic multiplicities as well, part (a)(iii) givesso equality of rank applies to every power. HenceAfter extending to a field where the characteristic polynomials split, take $r\ge \dim V$. These kernel of a linear map spaces are the generalized eigenspaces; the primary decomposition theorem for linear maps identifies their dimensions with the algebraic multiplicities. The same proof works over the original field for every eigenvalue in it. We obtainIn fact the argument also includes the zero eigenvalue.