[proofplan] We argue by contradiction. Completeness of $T$ means that for every sentence $p$, either $T \vdash p$ or $T \vdash \neg p$. Suppose $T$ is not complete: then some sentence $p$ is independent of $T$, so both $T \cup \{p\}$ and $T \cup \{\neg p\}$ are consistent. We use the Löwenheim–Skolem theorems to produce models of these two theories of the **same** infinite cardinality $\kappa$. Because one model satisfies $p$ and the other satisfies $\neg p$, they disagree on a sentence, so they cannot be isomorphic. This contradicts $\kappa$-categoricity, which asserts that any two models of $T$ of cardinality $\kappa$ are isomorphic. The hypothesis that $T$ has no finite models is used to guarantee that the models produced have genuinely infinite cardinality (so that the Löwenheim–Skolem machinery applies to adjust their size to $\kappa$). [/proofplan] [step:Assume for contradiction that $T$ is not complete and extract an independent sentence $p$] Suppose $T$ is not complete. Then there exists a sentence $p$ in the language of $T$ such that \begin{align*} T \not\vdash p \quad \text{and} \quad T \not\vdash \neg p. \end{align*} By the standard equivalence between non-derivability and consistency of the negation, the theories \begin{align*} T_1 := T \cup \{p\}, \qquad T_2 := T \cup \{\neg p\} \end{align*} are both consistent. By the [Completeness Theorem](/theorems/1457) (Gödel), each consistent theory has a model: fix \begin{align*} A_1 \models T_1, \qquad A_2 \models T_2. \end{align*} [guided] Completeness of $T$, by definition, is the statement: for every sentence $p$ in the language of $T$, either $T \vdash p$ or $T \vdash \neg p$. So **not complete** means there is some sentence $p$ with neither $T \vdash p$ nor $T \vdash \neg p$ — such a $p$ is called **independent** of $T$. Why does this translate into consistency of $T \cup \{p\}$ and $T \cup \{\neg p\}$? By contraposition of the deduction theorem: if $T \cup \{p\}$ were **in**consistent, then $T \cup \{p\} \vdash \bot$, and hence $T \vdash \neg p$ (discharging the assumption $p$), contradicting our assumption $T \not\vdash \neg p$. Similarly $T \cup \{\neg p\}$ must be consistent. So both theories are consistent. By Gödel's Completeness Theorem, every consistent first-order theory has a model. We therefore obtain structures $A_1$ and $A_2$ for the language of $T$ with $A_1 \models T \cup \{p\}$ and $A_2 \models T \cup \{\neg p\}$. These exist unconditionally on cardinality — the models may be very large or very small. Step 2 handles the cardinality. [/guided] [/step] [step:Use the no-finite-models hypothesis to conclude $A_1$ and $A_2$ are infinite] Since $A_i \models T$ for each $i \in \{1, 2\}$ and $T$ has no finite models by hypothesis, the structures $A_1$ and $A_2$ have infinite underlying sets. In particular, $|A_i| \ge \aleph_0$. [/step] [step:Resize both models to cardinality $\kappa$ using Löwenheim–Skolem] We now produce models $B_1 \models T_1$ and $B_2 \models T_2$ with $|B_1| = |B_2| = \kappa$. **Case $|A_i| \le \kappa$.** Since $|A_i|$ is infinite and $\kappa$ is an infinite cardinal with $|A_i| \le \kappa$, the [Upward Löwenheim–Skolem Theorem](/theorems/1489) applied to $T_i$ (which has the infinite model $A_i$) yields a model $B_i \models T_i$ of cardinality exactly $\kappa$. **Case $|A_i| > \kappa$.** Since $T_i$ is consistent in a language of cardinality at most $\kappa$ (the language of $T$, which is countable in the standard setting, or in any case of cardinality $\le \kappa$ by the implicit convention that $\kappa \ge |L|$), the [Downward Löwenheim–Skolem Theorem](/theorems/1490) applied to $A_i \models T_i$ yields an elementary substructure $B_i \preceq A_i$ with $B_i \models T_i$ and $|B_i| = \kappa$. In either case we obtain $B_1 \models T_1$ and $B_2 \models T_2$ with \begin{align*} |B_1| = |B_2| = \kappa. \end{align*} [guided] The goal of this step is subtle: we need not just some models of $T_1$ and $T_2$, but models of the **same cardinality $\kappa$** — because $\kappa$-categoricity only constrains models of size exactly $\kappa$. The two Löwenheim–Skolem theorems together act as a "size-adjustment" toolkit that can shrink or grow an infinite model to any target infinite cardinality at least as large as the language. **Upward direction.** If our starting model $A_i$ is too small (at most $\kappa$ in size), the Upward Löwenheim–Skolem Theorem provides, for any infinite cardinal $\lambda \ge |A_i|$, an elementary extension $B_i \succeq A_i$ of cardinality $\lambda$. Take $\lambda = \kappa$. The theorem requires an infinite starting model — this is exactly where we consume the hypothesis that $A_i$ is infinite, which came from "no finite models" in Step 2. **Downward direction.** If $A_i$ is too large, the Downward Löwenheim–Skolem Theorem provides, for any infinite cardinal $\lambda$ with $|L| \le \lambda \le |A_i|$, an elementary substructure $B_i \preceq A_i$ of cardinality $\lambda$. Take $\lambda = \kappa$; we need $\kappa \ge |L|$, which is the standard tacit convention in statements of categoricity (and is automatically satisfied for countable languages since $\kappa$ is infinite). Because $B_i \preceq A_i$ (elementary substructure) or $A_i \preceq B_i$ (elementary extension), the models $B_i$ satisfy exactly the same first-order sentences as $A_i$, in particular $B_i \models T_i$. So we have delivered $B_1 \models T_1$ with $|B_1| = \kappa$ and $B_2 \models T_2$ with $|B_2| = \kappa$. [/guided] [/step] [step:Observe that $B_1$ and $B_2$ are not isomorphic, because they disagree on $p$] Since $B_1 \models T_1 = T \cup \{p\}$ we have $B_1 \models p$, and since $B_2 \models T_2 = T \cup \{\neg p\}$ we have $B_2 \models \neg p$, i.e., $B_2 \not\models p$. First-order satisfaction is preserved under isomorphism: if $B_1 \cong B_2$ then for every sentence $q$ in the language, \begin{align*} B_1 \models q \iff B_2 \models q. \end{align*} Taking $q = p$ gives a contradiction (the LHS holds, the RHS fails). Therefore $B_1 \not\cong B_2$. [guided] This is the classical use of **elementary equivalence**: isomorphic structures are elementarily equivalent, i.e., they satisfy exactly the same first-order sentences. The proof is a straightforward induction on formula complexity — if $\pi: B_1 \to B_2$ is an isomorphism, then atomic formulas are preserved by the homomorphism property, and the logical connectives and quantifiers are preserved by bijectivity. In our setting, $B_1$ and $B_2$ satisfy contradictory sentences: $B_1 \models p$ and $B_2 \models \neg p$. If they were isomorphic, they would share the truth value of every sentence, including $p$. But the truth value of $p$ on $B_1$ is T and on $B_2$ is F. Contradiction with isomorphy. Conclude $B_1 \not\cong B_2$. [/guided] [/step] [step:Derive a contradiction with $\kappa$-categoricity of $T$] Both $B_1$ and $B_2$ satisfy $T$ (since $T \subseteq T_i$ and $B_i \models T_i$), and both have cardinality $\kappa$. By hypothesis, $T$ is $\kappa$-categorical, meaning any two models of $T$ of cardinality $\kappa$ are isomorphic. Therefore $B_1 \cong B_2$, contradicting the previous step. This contradiction shows the assumption "$T$ not complete" is untenable. Hence $T$ is complete. $\square$ [guided] We now collect everything. We have two structures: - $B_1$ is a model of $T$ (since $T \subseteq T_1$) and $|B_1| = \kappa$. - $B_2$ is a model of $T$ (since $T \subseteq T_2$) and $|B_2| = \kappa$. By the hypothesis of $\kappa$-categoricity — which states that any two models of $T$ of cardinality $\kappa$ are isomorphic — we must have $B_1 \cong B_2$. But Step 4 showed $B_1 \not\cong B_2$. This is a contradiction, and it was derived from the assumption that $T$ is not complete. Therefore $T$ **is** complete: for every sentence $p$ in the language of $T$, either $T \vdash p$ or $T \vdash \neg p$. **Where each hypothesis entered.** The hypothesis "no finite models" was used in Step 2 to ensure $A_1, A_2$ are infinite, enabling Löwenheim–Skolem in Step 3. If $T$ permitted finite models, $A_1$ might be a finite model of $T \cup \{p\}$ whose size we cannot adjust by Löwenheim–Skolem (which requires infinite cardinalities). The hypothesis of $\kappa$-categoricity was used in the final step to force $B_1 \cong B_2$, delivering the contradiction. Without $\kappa$-categoricity, $B_1$ and $B_2$ could simply be two non-isomorphic models of $T$ of size $\kappa$, and no contradiction would arise. [/guided] [/step]