Quine, Two Dogmas of Empiricism

26 May 2025

Overview

The distinction between analytic and synthetic propositions, and the verification principle, are the two pillars of logical positivism. However, in Two Dogmas of Empiricism, Quine argues that both the analytic-synthetic distinction and the verification principle are ungrounded. Quine argues that the definition of analyticity is circular. Furthermore, he argues that propositions cannot be verified in isolation, and that only the entire web of beliefs can stand up to verification. The arguments Quine presents in Two Dogmas not only undermine logical positivism but also suggest skepticism about meaning and a radical form of holism. This post also examines some objections to Quine’s arguments.

1. Quine’s Attack on the Analytic-Synthetic Distinction

Quine claims that all previous attempts to define analyticity are unsatisfactory. He examines the definitions provided by Kant and Frege as examples.

1.1. Kant’s Definition of Analyticity

Kant’s first definition of analyticity is as follows:

“All $a$ are $b$” is analytic $\iff$ $a$ is conceptually contained in b

However, not only this definition relies on the metaphorical expression “conceptually contained”, but it is also limited to propositions with a subject-predicate structure. Kant’s second definition of analyticity is as follows:

$P$ is analytic $\iff$ $\lnot P$ implies a contradiction

But this definition requires an explanation of what a contradiction is. If contradiction is defined as “a proposition that is analytically false,” then this is merely a circular definition.

1.2. Frege’s Definition of Analyticity

Frege’s definition of analyticity is as follows:

$P$ is analytic $\iff$ $P$ is a law of logic, or is derivable solely from the definitions of terms involved and the laws of logic

By “law of logic”, Quine understands it to be a sentence that is true regardless of how the non-logical terms are interpreted. For example, $(φ → ψ) → (¬ψ → ¬φ)$ is a law of logic because it is true no matter how $φ$ and $ψ$ are interpreted. Accordingly, “All bachelors are unmarried” is analytic as it can be derived solely from the definition of “bachelor” and laws of logic as follows:

1. Bachelor(x) := ¬Married(x) ∧ Male(x) (definition of bachelor)
2. ∀x [ ¬Married(x) ∧ Male(x) → ¬Married(x) ] (law of logic)
3. ∴ ∀x [ Bachelor(x) → ¬Married(x) ] (from 1 and 2)

1.3. Quine’s Attack on Synonymy

Quine challenges Frege’s definition by questioning how we can determine the definition of a word. That is, he questions under what conditions “$a$ and $b$ are synonymous” holds. Quine examines several possible answers to this question. The first attempt is as follows:

(i) $a$ and $b$ are synonymous $\iff$ $a$ and $b$ are listed as synonyms in the dictionary.

But clearly this approach is flawed, since a dictionary merely records already known synonyms. What we want to know is the criterion by which dictionary compilers list two words as synonyms. The second attempt is as follows:

(ii) $a$ and $b$ are synonymous $\iff$ for any predicate $P$, $P(a)$ and $P(b)$ have the same truth value.

But this too is inadequate. For example, let $a$ = bachelor, $b$ = unmarried man, and $P(x)$: $x$ is a two-syllable word. Although $a$ and $b$ are synonymous, $P(a)$ is true while $P(b)$ is false.

To address this, Quine introduces the notion of cognitive meaning. Cognitive meaning is related only to the referent or concept, and excludes aspects such as word length, poetic mood, etc. Thus, (ii) is revised as follows:

(iii) $a$ and $b$ are synonymous $\iff$ for any predicate $P$ relevant only to cognitive meaning, $P(a)$ and $P(b)$ have the same truth value.

However, this is also inadequate. This is because the extension of “any predicate” is language-relative. (This is partly related to Quine’s skepticism about second-order logic.) For example, let us call creatures with a heart “cordate” ($c$) and those with a kidney “renate” ($r$). All known species either have both a heart and a kidney or neither. Thus in a language $L_1$ that contains only the predicate $\mathrm{HasHeart}(x)$, both $\mathrm{HasHeart}(c)$ and $\mathrm{HasHeart}(r)$ are true, so cordate and renate are synonymous. Yet in a language $L_2$ that contains the predicate $\mathrm{NecessarilyHasHeart}(x)$, $\mathrm{NecessarilyHasHeart}(c)$ is true but $\mathrm{NecessarilyHasHeart}(r)$ is false, so they are no longer synonymous.

Thus, (iii) makes synonymy language-dependent. Indeed, for (iii) to be valid, it seems that the assumed language must include modality. Accordingly, (iii) is revised as follows:

(iv) $a$ and $b$ are synonymous $\iff$ in a language $L$ with modal expressions, for any predicate $P$ relevant only to cognitive meaning, $P(a)$ and $P(b)$ have the same truth value.

However, Quine claims that even this is inadequate. For now the meaning of modality must be explained. That is, he now asks under what conditions “$a$ is necessarily $b$” holds. To define necessity as follows is to give a circular definition:

$a$ is necessarily $b$ $\iff$ “All a are b” is analytically true.

Therefore, Frege’s definition of analyticity is circular unless either a valid definitions of synonymy, or necessity, is provided.

2. Reflections on Quine’s Attack

Quine’s attack targets synonymy, but its implications are much broader.

2.1. Logical Skepticism

First, Quine’s attack also undermines his own definition of laws of logic. For example, according to Quine, $P(x) ∧ Q(x) → P(x)$ is a law of logic because it is true no matter what is substituted for $P, Q, x$. However, for this criterion to be coherent, the terms substituted for x must be synonymous.

For example, let $P(x):$ $x$ is large, $Q(x):$ $x$ is wet, and $x$ = bank. Then, $P(x) ∧ Q(x) → P(x)$ becomes “A large and wet bank is a large bank.” For this sentence to be true, the two “bank”s of the subject and predicate must be synonymous_{A large and wet riverland is a large riverland}. Otherwise, the sentence is false_{A large and wet riverland is a large financial establishment}. Thus, Quine’s definition of law of logic also depends on synonymy.

2.2. Semantic Skepticism

Second, Quine’s attack renders translation between languages fictitious. If someone asks for the translation of “Dieser Apfel ist rot,” we would say “This apple is red.” That this is the correct translation relies upon ‘dieser’, ‘Apfel’, ‘ist’, and ‘rot’ being respectively synonymous with ‘this’, ‘apple’, ‘is’, and ‘red’. Generally, the following seems to hold:

$φ$ is a translation of $ψ$ $\iff$ $φ$ is synonymous with $ψ$.

Hence if the notion in the right side is ambiguous, then that in the left is also ambiguous. Consequently, Quine’s skepticism about synonymy extends to skepticism about translation, and hence to skepticism about meaning. (For an argument connecting skepticism about translation to skepticism about meaning, see forthcoming article.)

3. Objections to Quine’s Attack on the Analytic-Synthetic Distinction

Quine’s attack has the following structure:

If the definition of a concept $C$ is circular, then $C$ is unintelligible.

Let us call this Quine’s Socratic Condition. It may be the case that Quine’s Socratic Condition is too strong of a requirement. For example, “red” or “blue” cannot be defined in a non-circular way — a person born blind cannot “make colors appear before them”, no matter how many utterances involving color words are given to them — but that does not mean that color words are unintelligible. Indeed, Davidson and others have argued that language learning requires some primitive terms — i.e. were there a language all of whose concepts satisfy the Socratic Condition, that language would be unlearnable.

Nevertheless, Quine might argue that although not every concept should satisfy the Socratic Condition, especially those that relate to immediate sense data, certain vaguer concepts—such as analyticity—must. Consider the following sentence:

Everything green has an extension.

Whether this sentence is analytic is ambiguous. Quine claims that this ambiguity arises not because of ambiguity in “green” or “extension,” but of “analytic.” This, he argues, shows that analyticity, unlike color words, cannot be legitimised without a rigorous definition.

In response, Grice and Strawson argue that the ambiguity in whether “Everything green has an extension” is analytic arises not from “analytic,” but from “everything green.” For example, it is unclear whether a “green flash” counts as “everything green,” so the truth value of the sentence remains undetermined. On the other hand, analyticity seems to be used in a consistent way by almost every philosopher and every layman, so there is no reason to think of it so ambiguous as to require the Socratic Condition.

4. Quine’s Critique of Logical Positivism

4.1. Critique of Reductionism

According to logical positivism, every truth is either analytic or synthetic. Analytic truths can be verified through logical analysis, and synthetic truths can be verified through sense data. Thus, the meaning of a sentence is generally taken to be a logical compound of sense data. This is the reductionist thesis of positivism. For example, the meaning of “The cat is on the table or in the box” is analyzed into sense data corresponding to “cat,” “table,” “box,” and logical connectives such as “or” and “is.”

However, Quine argues that semantic reductionists bear the burden of proof to show that it is actually possible to reduce natural language sentences to logical compounds of sense data. He refers to Carnap’s attempt in The Logical Structure of the World to reconstruct natural language solely from sense data and logical connectives, but notes that, as Carnap himself admitted, the project failed.

Quine claims that reductionism cannot be justified unless this burden of proof is met.

4.2. Critique of Verification Principle

According to logical positivism, the meaning of a sentence is its verifiability. Under this verificationist theory of meaning, analyticity can be defined as follows:

P is analytic $\iff$ P is true regardless of the outcome of verification

However, Quine argues that the logical positivist definition of analyticity is also problematic. Quine claims that it is impossible to verify individual propositions in isolation, hence the verificationist theory of meaning cannot account for the meaning of individual sentences.

Consider the following proposition:

(i) Water boils at 100°C

One way to verify this proposition is to put a thermometer in boiling water. But if the thermometer reads 102°C, should we reject (i)? Not necessarily. Instead, we might reject “the thermometer is working,” “the water is pure,” “superheating did not occur,” “I read the thermometer correctly,” and so on.

Thus, Quine argues that what is subject to verification is always the entire web of beliefs. This is his holistic epistemology. In the above case, what is being tested is not the proposition “water boils at 100°C,” but the entire web of beliefs: “this is pure water, the thermometer is working, superheating did not occur, water boils at 100°C, …” and so on.

4.3. Implications of Epistemological Holism

Quine’s holism is radical in that it applies to all propositions. Quine claims that there is no sharp boundary between domains within the web of beliefs. Thus, mathematics does not enjoy a privileged epistemological status over science or philosophy. This leads to Quine’s naturalism.

For Quien, that a proposition $φ$ is certain, does not mean that $φ$ is true in all cases — something which cannot be verified in isolation — but that $φ$ is located deep within the web of beliefs. When evidence contrary to the web of beliefs is presented, we must revise the web so as to minimise the likelihood of future contrary evidence. Hence in a pragmatic spirit, it is preferable to revise beliefs at the periphery rather than those at the core. Thus, beliefs at the core persist almost permanently and acquire the status of certainty. However, if it becomes more practical to abandon a core belief—such as a law of logic—Quine holds that it is appropriate to do so.

4.4. Objections to Epistemological Holism

Crispin Wright argues that Quine’s holism is incoherent because it leads to infinite regress. Consider a web of beliefs consisting of the following two elements:

• A scientific theory of the world $T$
• A logical system $\mathcal{S}$

Suppose that $p → q$ is a law derivable from $T$ and $\mathcal{S}$. For example, if $T$ is Newtonian mechanics and $\mathcal{S}$ is first-order logic, $p$ might be “photons have no mass” and $q$ might be “photons are not affected by gravity.”

Now suppose that, contrary to $T$ and $\mathcal{S}$, an observation is made that supports $p$ and $¬q$—for example, gravitational lensing. According to Quine’s holism, the following four propositions are all candidates for rejection:

1. Reject $p ∧ ¬q$ (the gravitational lensing observation was mistaken)
2. Reject $T$ (Newtonian mechanics is false)
3. Reject $\mathcal{S}$ (first-order logic is false)
4. Reject $T \vdash_\mathcal{S} p → q$ (the derivation of $p → q$ from Newtonian mechanics and first-order logic is mistaken)

Which of these four to reject is determined by pragmatic considerations. Suppose, for example, that pragmatism suggests the following:

5. It is most practical to reject (4).

However, Wright points out that (5) itself is part of the web of beliefs. Thus, instead of rejecting (4), we could choose to reject (5). Conversely, to avoid rejecting (5), the following belief is required:

6. It is practical not to reject (5).

But to avoid rejecting (6), we require the belief that it is practical not to reject (6), and so on, leading to infinite regress. Thus, Wright argues that to avoid infinite regress in epistemology, some beliefs—such as (4)—must be placed outside the scope of pragmatic considerations.

References

Quine, Willard V. O. (1951). Two Dogmas of Empiricism. Philosophical Review 60 (1):20–43.

Miller, Alexander (1998). Philosophy of Language. New York: Routledge.

스톤 공간과 콤팩트성 정리

16 May 2025

다음은 학부 수리논리학의 유명한 정리이다.

콤팩트성 정리. $\mathcal{L}$의 이론 $T$에 대해, $T$의 모든 유한한 부분이론이 모델을 가진다면, $T$는 모델을 가진다.

그런데 왜 이 정리의 이름은 콤팩트성 정리인 것일까? 잘 들여다 보면, 위 정리의 진술은 다음과 같이 적을 수 있다.

임의의 $\mathcal{L}$-문장들의 집합 $T$가 모델을 가지지 않는다면, 어떤 유한한 부분집합 $T’ \subset T$가 존재하여 $T’$이 모델을 가지지 않는다.

확실히 이는 위상수학에서 콤팩트의 정의와 유사하다.

임의의 열린집합들의 모임 $\mathcal{C}$가 전채 공간의 덮개라면, 어떤 유한한 부분집합 $\mathcal{C}’ \subset \mathcal{C}$가 존재하여 $\mathcal{C}’$가 전체 공간을 덮는다.

이 유사성은 단순한 관찰 이상으로 확대될 수 있다. 아이디어는 각각의 완전_complete한 $\mathcal{L}$-이론을 공간의 한 점으로 본 뒤, 이들 모임에 적절한 위상을 부여하였을 때, 콤팩트성 정리가 해당 공간이 콤팩트할 필요충분조건이 되는 것이다. 먼저 다음을 정의한다.

정의. $\mathcal{L}$-구조 $\mathfrak{A}$에 대해, $\mathrm{Th}(\mathfrak{A})$를 $\mathfrak{A}$에서 참인 모든 $\mathcal{L}$-문장들의 집합으로 정의한다.

참고로 위 집합은 이전 글에서 초등적 동등성을 설명하며 정의한 바 있다.

$\mathrm{Th}(\mathfrak{A})$는 무모순적이며 형태론적으로 완전한 이론임이 자명하다. 반대로, 이론 $T$가 무모순적이며 형태론적으로 완전한 이론일 때, 괴델의 완전성 정리에 의해 $T$는 모델 $\mathfrak{A}$를 가지며, $T = \mathrm{Th}(\mathfrak{A})$이다. 따라서 $\mathrm{Th}$는 모든 무모순적이며 형태론적으로 완전한 이론을 생성한다.

이제 위상공간의 배경이 될 공간을 정의해 보자. 먼저 언어 $\mathcal{L}$에 대해, 공간 $\mathcal{S}$를 다음과 같이 정의한다.

\[\mathcal{S} = \{ \mathrm{Th}(\mathfrak{A}) : \mathfrak{A}\text{ is a $\mathcal{L}$-structure } \}\]

앞서 말했듯이 괴델의 완전성 정리에 의해 $\mathcal{S}$는 무모순적이며 형태론적으로 완전한 이론들의 모임과 사실상 같다. 그러나 후술하겠듯이, 완전성 정리를 사용하지 않더라도 $\mathcal{S}$의 위상적 콤팩트성과 1차 논리의 콤팩트성 정리가 동치임을 보이는 것이 목적이기 때문에, 일단은 $\mathcal{S}$를 그저 $\mathrm{Th}(\mathfrak{A})$의 모임으로서 생각하는 것이 낫다.

이제 $\mathcal{S}$의 위상 기저를 정의하자. $\mathcal{L}$-문장 $\phi$에 대해, 다음과 같이 정의한다.

\[U_\phi = \{ T \in \mathcal{S} : \phi \in T \}\]

자명하게, $U_\phi \cap U_\psi = U_{\phi \land \psi}$이다. 즉, $U_\phi$의 모임 $\mathcal{B}$는 유한 교집합에 대해 닫혀 있다. 또한 $\mathcal{B}$는 $\mathcal{S}$를 덮는다. $T \in \mathcal{S}$에 대해, $\phi \in T$라면 $T \in U_\phi$이기 때문이다. 따라서 $\mathcal{B}$는 위상 기저의 조건을 만족하며, 이에 따라 $\mathcal{B}$로 생성되는 위상을 $\mathcal{S}$에 부여하자.

정리. $\mathcal{S}$는 다음의 특징을 가진다.

1. 하우스도르프이다.
2. 완전 비연결 공간_{totally disconnected space}이다. 즉, $\mathcal{S}$에서 연결된 공간은 오직 홑원소 집합뿐이다.

증명.

1. $T_1, T_2 \in \mathcal{S}$에 대해, $T_1 \neq T_2$라면 어떤 문장 $\phi$가 존재하여 $\phi \in T_1, \lnot\phi \in T_2$이다. 따라서 $U_\phi, U_{\lnot \phi}$가 $T_1$과 $T_2$를 각각 분리한다.
2. $T_1$ 공간이 완전 비연결 공간일 충분조건은 모든 원소가 열린닫힌집합_clopen인 기저를 가지는 것이다. $U_\phi^c =U_{\lnot \phi}$에 의해 $\mathcal{B}$는 이 조건을 만족한다. ■

정리. 1차 논리의 콤팩트성 정리는 $\mathcal{S}$가 콤팩트 공간인 것과 동치이다.

증명.

보조정리. $\mathcal{C} \subset \mathcal{B}$가 $\mathcal{S}$를 덮을 필요충분조건은, $\Gamma = \lbrace \lnot \phi : U_\phi \in \mathcal{C} \rbrace $가 모델을 가지지 않는 것이다.

증명. 만약 $\Gamma$가 모델 $\mathfrak{A}$를 가진다면 $T = \mathrm{Th}(\mathfrak{A})$가 $\mathcal{C}$에 의해 덮여지지 않는다. 한편, $\mathcal{C}$가 $\mathcal{S}$를 덮지 못한다면 어떤 구조 $\mathfrak{A}$가 존재하여 $\phi \in \Gamma$에 대해 $\phi \notin \mathfrak{A}$이고, 이는 $\mathfrak{A}$가 $\Gamma$의 모델임을 의미한다. □

이제 본 정리를 증명하자. $\mathcal{S}$가 콤팩트할 필요충분조건은 임의의 기저 원소들로 이루어진 $\mathcal{S}$의 덮개가 유한 부분덮개를 가지는 것이다. $\mathcal{C} \subset \mathcal{B}$에 대해, $\mathcal{C}$가 $\mathcal{S}$를 덮을 필요충분조건은 (보조정리에 의해) $\Gamma$가 모델을 가지지 않는 것이다. 따라서,

$\mathcal{S}$가 콤팩트하다

$\Leftrightarrow$ 임의의 기저 원소들의 모임 $\mathcal{C}$가 덮개라면, 유한 부분덮개가 존재한다.

$\Leftrightarrow$ 임의의 이론 $\Gamma$가 모델을 가지지 않는다면, 모델을 가지지 않는 유한 부분이론이 존재한다.

$\Leftrightarrow$ 콤팩트성 정리 ■

정의. 완전 비연결인 콤팩트 하우스도르프 공간을 스톤 공간_{Stone space}이라고 부른다.

1차 논리의 콤팩트성 정리에 의해, $\mathcal{S}$는 스톤 공간이다. 이와 같이 논리적 구조를 위상적으로 분석하는 접근은 스톤 이중성_{Stone duality}이라고 불리는, 현대수학의 깊은 주제와 연관이 있다.

Stone Spaces and the Compactness Theorem

16 May 2025

This post was machine translated and has not yet been proofread. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

The following is a famous theorem from undergraduate mathematical logic.

Compactness Theorem. For a theory $T$ in language $\mathcal{L}$, if every finite subtheory of $T$ has a model, then $T$ has a model.

But why is this theorem called the compactness theorem? Upon closer examination, the statement of the above theorem can be written as follows:

If an arbitrary set of $\mathcal{L}$-sentences $T$ has no model, then there exists some finite subset $T’ \subset T$ such that $T’$ has no model.

This is certainly similar to the definition of compactness in topology.

If an arbitrary collection of open sets $\mathcal{C}$ covers the entire space, then there exists some finite subset $\mathcal{C}’ \subset \mathcal{C}$ such that $\mathcal{C}’$ covers the entire space.

This similarity can be extended beyond mere observation. The idea is to regard each complete $\mathcal{L}$-theory as a point in a space, and when we endow this collection with an appropriate topology, the compactness theorem becomes a necessary and sufficient condition for the corresponding space to be compact. First, we define the following:

Definition. For an $\mathcal{L}$-structure $\mathfrak{A}$, we define $\mathrm{Th}(\mathfrak{A})$ as the set of all $\mathcal{L}$-sentences that are true in $\mathfrak{A}$.

Incidentally, this set was defined in a previous post when explaining elementary equivalence.

It is clear that $\mathrm{Th}(\mathfrak{A})$ is a consistent and syntactically complete theory. Conversely, when a theory $T$ is consistent and syntactically complete, by Gödel’s completeness theorem, $T$ has a model $\mathfrak{A}$, and $T = \mathrm{Th}(\mathfrak{A})$. Therefore, $\mathrm{Th}$ generates all consistent and syntactically complete theories.

Now let us define the space that will serve as the background for our topological space. First, for a language $\mathcal{L}$, we define the space $\mathcal{S}$ as follows:

\[\mathcal{S} = \{ \mathrm{Th}(\mathfrak{A}) : \mathfrak{A}\text{ is a $\mathcal{L}$-structure } \}\]

As mentioned earlier, by Gödel’s completeness theorem, $\mathcal{S}$ is essentially the same as the collection of consistent and syntactically complete theories. However, as we shall see later, since our goal is to show that the topological compactness of $\mathcal{S}$ is equivalent to the compactness theorem of first-order logic without using the completeness theorem, it is better to think of $\mathcal{S}$ simply as a collection of $\mathrm{Th}(\mathfrak{A})$ for now.

Now let us define a topological basis for $\mathcal{S}$. For an $\mathcal{L}$-sentence $\phi$, we define:

\[U_\phi = \{ T \in \mathcal{S} : \phi \in T \}\]

Trivially, $U_\phi \cap U_\psi = U_{\phi \land \psi}$. That is, the collection $\mathcal{B}$ of $U_\phi$ is closed under finite intersections. Moreover, $\mathcal{B}$ covers $\mathcal{S}$. For $T \in \mathcal{S}$, if $\phi \in T$, then $T \in U_\phi$. Therefore, $\mathcal{B}$ satisfies the conditions for a topological basis, and we endow $\mathcal{S}$ with the topology generated by $\mathcal{B}$.

Theorem. $\mathcal{S}$ has the following properties:

1. It is Hausdorff.
2. It is a totally disconnected space. That is, the only connected subspaces in $\mathcal{S}$ are singleton sets.

Proof.

1. For $T_1, T_2 \in \mathcal{S}$, if $T_1 \neq T_2$, then there exists some sentence $\phi$ such that $\phi \in T_1$ and $\lnot\phi \in T_2$. Therefore, $U_\phi$ and $U_{\lnot \phi}$ separate $T_1$ and $T_2$ respectively.
2. A sufficient condition for a space to be totally disconnected is to have a basis where every element is clopen. Since $U_\phi^c =U_{\lnot \phi}$, $\mathcal{B}$ satisfies this condition. ■

Theorem. The compactness theorem of first-order logic is equivalent to $\mathcal{S}$ being a compact space.

Proof.

Lemma. A necessary and sufficient condition for $\mathcal{C} \subset \mathcal{B}$ to cover $\mathcal{S}$ is that $\Gamma = \lbrace \lnot \phi : U_\phi \in \mathcal{C} \rbrace $ has no model.

Proof. If $\Gamma$ has a model $\mathfrak{A}$, then $T = \mathrm{Th}(\mathfrak{A})$ is not covered by $\mathcal{C}$. On the other hand, if $\mathcal{C}$ does not cover $\mathcal{S}$, then there exists some structure $\mathfrak{A}$ such that for $\phi \in \Gamma$, $\phi \notin \mathfrak{A}$, which means that $\mathfrak{A}$ is a model of $\Gamma$. □

Now we prove the main theorem. A necessary and sufficient condition for $\mathcal{S}$ to be compact is that any cover of $\mathcal{S}$ consisting of basis elements has a finite subcover. For $\mathcal{C} \subset \mathcal{B}$, a necessary and sufficient condition for $\mathcal{C}$ to cover $\mathcal{S}$ is (by the lemma) that $\Gamma$ has no model. Therefore,

$\mathcal{S}$ is compact

$\Leftrightarrow$ If any collection of basis elements $\mathcal{C}$ is a cover, then there exists a finite subcover.

$\Leftrightarrow$ If any theory $\Gamma$ has no model, then there exists a finite subtheory that has no model.

$\Leftrightarrow$ Compactness theorem ■

Definition. A compact Hausdorff space that is totally disconnected is called a Stone space.

By the compactness theorem of first-order logic, $\mathcal{S}$ is a Stone space. This approach of analysing logical structures topologically is connected to a deep topic in modern mathematics called Stone duality.

양화사 제거

15 May 2025

이전 글에서, $\mathcal{L}$-구조 $\mathfrak{A}$에서 정의가능한 집합들이 무엇인지에 관해 알아 보았다. $S \subseteq A$가 $\mathfrak{A}$에서 특정 산술 위계에 속하는 명제 $\phi$로 정의가능할 때, $S$가 그 위계에 속한다고 하자. 예를 들어 $S$가 $\Pi_1$ 문장으로 정의 가능할 때, $S \in \Pi_1$이다.

예를 들어 표준 산술 모형 $\mathfrak{N} = (\mathbb{N}, 0, S, +)$에서 짝수의 집합은 $\Sigma_1$이다.

\[\{ x \in \mathbb{N} : \mathfrak{N} \vDash \exists y (y + y = x) \}\]

집합의 구조는 위계가 높아질수록 까다롭기 때문에, 가장 다루기 이상적인 상황은 모든 정의가능한 집합이 $\Delta_0$으로 환원되는 상황이다. 이같은 특징을 가지는 이론을 양화사 제거 가능한 이론이라고 부른다.

정의. $\mathcal{L}$-이론 $T$가 양화사 제거_{quantifier elimination} 가능하다는 것은 임의의 $\mathcal{L}$-명제 $\phi$에 대해 어떤 $\Delta_0$ $\mathcal{L}$-명제 $\psi$가 존재하여 다음이 성립하는 것이다.

\[T \vdash \phi \leftrightarrow \psi\]

단, $\psi$의 자유변수는 모두 $\phi$의 자유변수이다.

양화사 제거 판별법. $T$가 양화사 제거 가능할 충분조건은, $T$가 $\exists x \psi \; (\psi \in \Delta_0)$ 꼴의 명제에 대해 양화사 제거 가능한 것이다.

증명. 먼저 임의의 $\Delta_0$ 명제 $\psi$에 대해 $\forall x \psi$가 양화사 제거 가능함을 보이자. $\forall x \psi$는 $\lnot\exists x \lnot \psi$와 동치이고, 가정에 의해 $\exists x \lnot \psi$는 어떤 양화사가 없는 명제 $\theta$와 동치이다. 따라서 $\forall x \psi$는 $\lnot \theta$와 동치이며, 양화사 제거 가능하다. 이제 양화사 개수에 대한 귀납법을 적용하면 임의의 명제에 대해 양화사 제거가 가능함이 보여진다. ■

어떤 이론이 양화사 제거 가능할 경우 해당 이론이 완전함을 보일 수 있는 경우가 종종 있다. 일례로 다음을 보자.

정리. 조밀 무계 전순서 이론 $T$는 양화사 제거 가능하다.

증명. 먼저 다음 개념을 정의한다.

정의. 유한한 변수들의 배열_arrangement이란, 변수들의 순서 관계의 무모순적인 논리곱을 의미한다.

예를 들어 다음은 $\lbrace v_1, v_3, v_7, v_8 \rbrace$의 배열이다.

\[(v_1 < v_3) \land (v_8 \land v_7) \land (v_3 = v_8)\]

증명의 핵심은 다음의 보조정리이다.

보조정리. $\mathcal{L} = (<)$의 $\Delta_0$ 명제는 전순서 이론에서 모순과 동치이거나, 어떤 배열들의 논리합과 동치이다.

보조정리를 인정하고 본 정리를 증명해 보자. 양화사 제거 판별법에 의해, $\psi \in \Delta_0$에 대해 $\exists x \psi$가 양화사 제거 가능함을 보이면 된다. 보조정리에 의해 $\psi$는 $\theta_1 \lor \cdots \lor \theta_n$과 동치이며, 각 $\theta_i$는 변수들의 배열이다. $\exists$의 분배법칙에 의해,

\[T \vdash \exists x \psi \leftrightarrow \Big( (\exists x \theta_1) \lor \cdots (\exists x \theta_n) \Big)\]

이다. 그런데 조밀 무계 전순서에서는 배열 $\theta$에 대해, $\exists x \theta$는 $\theta$의 순서 관계를 한줄로 쭉 적은 뒤, $x$를 지운 명제와 동치이다. 예를 들어 $\exists x (v_1 < x) \land (x < v_2)$는 $\exists x (v_1 < x < v_2)$로 적을 수 있고, 이는 조밀성에 의해 $v_1 < v_2$와 동치이다. 한편 $\exists x (v_1 < x)$는 무계성에 의해 항진이며, $v_1 = v_1$과 동치이다. 따라서 위 식의 우항은 양화사 제거 가능하며, 이에 따라 $\exists x \psi$ 또한 양화사 제거 가능하다. ■

따름정리. $T$는 완전하다.

증명. $T$가 양화사 제거 가능하므로, 표준 양화사 제거 형식에 의해, 최대 1개의 자유변수 $x$를 가지는 임의의 $\Delta_0$ 문장 $\psi \in \Delta_0$에 대해 $T \vdash \psi$이거나 $T \vdash \lnot\psi$임을 보이면 된다. 보조정리에 의해 $\psi$는 $x$의 배열과 동치이다. 그런데 가능한 $x$의 배열은 $x < x$와 $x = x$, 두 가지밖에 없다. 전자의 경우 모순이므로 $T \vdash \lnot\psi$이고, 후자의 경우 항진이므로 $T \vdash \psi$이다. ■

$T$가 양화사 제거 가능한 것과 대조적으로, 조밀 유계 전순서 이론 $T_{\mathrm{bd}}$는 양화사 제거 가능하지 않다. $a$가 $<$의 최솟값일 때, $\phi \equiv \exists y (y < x)$가 양화사 제거 가능하지 않기 때문이다. $T_{\mathrm{bd}}$도 전순서 이론이므로, 만약 $\phi$가 양화사 제거 가능했다면 보조정리에 의해 $\phi$는 $x < x$ 또는 $x = x$와 동치여야 하는데, $\phi$는 $x = a$일 때 참이고 그 외의 경우에는 거짓이기 때문에 전자와 후자 모두에 해당하지 않는다.

그러나 이 경우에는 양화사 제거가 가능한 $T_{\mathrm{bd}}$의 확장을 쉽게 찾을 수 있다. 먼저 언어 $\mathcal{L}$에 두 가지 새로운 상수 기호 $a$와 $b$를 추가한다. 그리고 $a$와 $b$가 각각 최솟값과 최댓값이라는 다음의 공리를 $T_{\mathrm{bd}}$에 추가한 것을 $T_{\mathrm{bd}}’$이라고 하자.

\[\lnot \exists (x < a) \quad \lnot \exists (b < x)\]

정리. $T_{\mathrm{bd}}’$는 양화사 제거 가능하다.

증명. 연습문제

따름정리. $T_{\mathrm{bd}}$는 완전하다.

증명. $T_{\mathrm{bd}}$의 보존적 확장_{conservative extension}인 $T_{\mathrm{bd}}’$가 완전하므로, $T_{\mathrm{bd}}$ 또한 완전하다. ■

Quantifier Elimination

15 May 2025

This post was machine translated and has not yet been proofread. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

In the previous article, we examined what sets are definable in an $\mathcal{L}$-structure $\mathfrak{A}$. When $S \subseteq A$ is definable by a formula $\phi$ belonging to a particular arithmetic hierarchy in $\mathfrak{A}$, we say that $S$ belongs to that hierarchy. For instance, when $S$ is definable by a $\Pi_1$ sentence, we have $S \in \Pi_1$.

For example, in the standard arithmetic model $\mathfrak{N} = (\mathbb{N}, 0, S, +)$, the set of even numbers is $\Sigma_1$.

\[\{ x \in \mathbb{N} : \mathfrak{N} \vDash \exists y (y + y = x) \}\]

Since the structure of sets becomes more complex as the hierarchy level increases, the most ideal situation is when all definable sets can be reduced to $\Delta_0$. Theories possessing such a property are called theories admitting quantifier elimination.

Definition. An $\mathcal{L}$-theory $T$ admits quantifier elimination if for any $\mathcal{L}$-formula $\phi$, there exists some $\Delta_0$ $\mathcal{L}$-formula $\psi$ such that the following holds:

\[T \vdash \phi \leftrightarrow \psi\]

where all free variables of $\psi$ are free variables of $\phi$.

Quantifier Elimination Test. A sufficient condition for $T$ to admit quantifier elimination is that $T$ admits quantifier elimination for formulae of the form $\exists x \psi$ where $\psi \in \Delta_0$.

Proof. First, we show that for any $\Delta_0$ formula $\psi$, the formula $\forall x \psi$ admits quantifier elimination. The formula $\forall x \psi$ is equivalent to $\lnot\exists x \lnot \psi$, and by assumption, $\exists x \lnot \psi$ is equivalent to some quantifier-free formula $\theta$. Therefore, $\forall x \psi$ is equivalent to $\lnot \theta$ and admits quantifier elimination. By applying induction on the number of quantifiers, we can show that quantifier elimination is possible for any formula. ■

When a theory admits quantifier elimination, it is often possible to show that the theory is complete. Consider the following example.

Theorem. The theory $T$ of dense unbounded linear orders admits quantifier elimination.

Proof. First, we define the following concept.

Definition. An arrangement of finite variables is a consistent conjunction of order relations amongst the variables.

For instance, the following is an arrangement of $\lbrace v_1, v_3, v_7, v_8 \rbrace$:

\[(v_1 < v_3) \land (v_8 \land v_7) \land (v_3 = v_8)\]

The key to the proof is the following lemma.

Lemma. A $\Delta_0$ formula in $\mathcal{L} = (<)$ is either equivalent to a contradiction in the theory of linear orders, or equivalent to a disjunction of arrangements.

Accepting the lemma, we prove the main theorem. By the quantifier elimination test, it suffices to show that $\exists x \psi$ admits quantifier elimination for $\psi \in \Delta_0$. By the lemma, $\psi$ is equivalent to $\theta_1 \lor \cdots \lor \theta_n$, where each $\theta_i$ is an arrangement of variables. By the distributivity of $\exists$, we have

\[T \vdash \exists x \psi \leftrightarrow \Big( (\exists x \theta_1) \lor \cdots (\exists x \theta_n) \Big)\]

However, in dense unbounded linear orders, for an arrangement $\theta$, the formula $\exists x \theta$ is equivalent to the formula obtained by writing out the order relations of $\theta$ in a single line and then removing $x$. For example, $\exists x (v_1 < x) \land (x < v_2)$ can be written as $\exists x (v_1 < x < v_2)$, which by density is equivalent to $v_1 < v_2$. On the other hand, $\exists x (v_1 < x)$ is a tautology by unboundedness and is equivalent to $v_1 = v_1$. Therefore, the right-hand side of the above equation admits quantifier elimination, and consequently $\exists x \psi$ also admits quantifier elimination. ■

Corollary. $T$ is complete.

Proof. Since $T$ admits quantifier elimination, by the standard quantifier elimination procedure, it suffices to show that for any $\Delta_0$ sentence $\psi \in \Delta_0$ with at most one free variable $x$, either $T \vdash \psi$ or $T \vdash \lnot\psi$. By the lemma, $\psi$ is equivalent to an arrangement of $x$. However, there are only two possible arrangements of $x$: $x < x$ and $x = x$. In the former case, since it is a contradiction, we have $T \vdash \lnot\psi$; in the latter case, since it is a tautology, we have $T \vdash \psi$. ■

In contrast to $T$ admitting quantifier elimination, the theory $T_{\mathrm{bd}}$ of dense bounded linear orders does not admit quantifier elimination. This is because when $a$ is the minimum element of $<$, the formula $\phi \equiv \exists y (y < x)$ does not admit quantifier elimination. Since $T_{\mathrm{bd}}$ is also a theory of linear orders, if $\phi$ admitted quantifier elimination, then by the lemma, $\phi$ would have to be equivalent to either $x < x$ or $x = x$. However, $\phi$ is true when $x = a$ and false otherwise, so it corresponds to neither case.

Nevertheless, in this case we can easily find an extension of $T_{\mathrm{bd}}$ that admits quantifier elimination. First, we add two new constant symbols $a$ and $b$ to the language $\mathcal{L}$. Then we define $T_{\mathrm{bd}}’$ as $T_{\mathrm{bd}}$ with the addition of the following axioms stating that $a$ and $b$ are the minimum and maximum elements, respectively:

\[\lnot \exists (x < a) \quad \lnot \exists (b < x)\]

Theorem. $T_{\mathrm{bd}}’$ admits quantifier elimination.

Proof. Exercise.

Corollary. $T_{\mathrm{bd}}$ is complete.

Proof. Since $T_{\mathrm{bd}}’$, which is a conservative extension of $T_{\mathrm{bd}}$, is complete, $T_{\mathrm{bd}}$ is also complete. ■

포화된 구조와 실수체의 완전성

13 May 2025

$\mathfrak{A}$가 $\mathcal{L}$-구조라고 하자. $A$는 $\mathfrak{A}$의 정의역이다.

정의. $X \subseteq A$가 정의가능_definable하다는 것은, 어떤 $\mathcal{L}$-논리식 $\phi$와 자유변수 할당 $g$가 존재하여 다음이 성립한다는 것이다.

\[X = \{ x \in A : \mathfrak{A} \vDash \phi[g^0_x] \}\]

$\phi$가 $v_0$ 이외의 자유변수를 가지지 않을 때, $X$는 $\emptyset$-정의가능하다고 한다.

Remark. 정의가능성은 괴델의 구성가능성과 같은 의미이다.

예를 들어 $(\mathbb{R}, <)$에서 $(e, 2\pi)$는 다음의 $\phi$와 $g$에 의해 정의가능하다.

• $\phi \equiv (v_1 < v_0 \land v_0 < v_2)$
• $g: v_1 \mapsto e, v_2 \mapsto 2\pi$

그러나 $(e, 2\pi)$는 $\emptyset$-정의가능하지 않다. $(\mathbb{R}, <)$에서 $e$와 $2\pi$를 특정할 방법이 없기 때문이다.

한편 표준 산술 모형 $(\mathbb{N}, 0, +, S)$에서 짝수의 집합 $E$는 다음의 $\phi$에 의해 $\emptyset$-정의가능하다.

• $\phi \equiv \exists y (x = y + y)$

모든 유한집합은 정의가능하다. 예를 들어 $A = \lbrace a_1, a_2, a_3 \rbrace $는 다음과 같이 정의가능하다.

• $\phi \equiv (v_0 = v_1) \lor (v_0 = v_2) \lor (v_0 = v_3)$
• $g: v_1 \mapsto a_1, v_2 \mapsto a_2, v_3 \mapsto a_3$

같은 이유로 모든 쌍대 유한집합_{cofinite set} 또한 정의가능하다.

저번 글에서 탄력적_resilient 집합족에 대해 알아 보았다. 이제 다음을 정의하자.

정의. $\kappa$가 비가산 기수라고 하자. $\mathfrak{A}$가 $\kappa$-포화_{$\kappa$-saturated}되었다는 것은, $\kappa$개보다 적은 $A$의 정의가능한 부분집합들의 모임이 언제나 탄력적이라는 것이다. 특히, $\mathfrak{A}$가 $|A|$-포화되었을 때, $\mathfrak{A}$는 포화_saturated되었다고 한다.

따라서 $\aleph_1$-포화된 구조 $\mathfrak{A}$는, 가산 개의 $\mathfrak{A}$의 정의가능한 부분집합들의 모임이 유한 교집합 속성을 만족할 때, 전체 교집합 또한 공집합이 아닌 구조이다. 한편 구조 $\mathfrak{A}$가 $|A|^+$-포화되는 것은 불가능하다. 다음의 집합족이 유한 교집합 속성을 만족하지만 교집합은 공집합이기 때문이다.

\[\Big\{ A - \{ a \} : a \in A \Big\}\]

포화된 구조의 중요성은 다음 정리에 있다.

정리. 초등적으로 동등하며 기수가 같은 두 포화된 $\mathcal{L}$-구조는 동형이다.

증명. 생략. 기초적인 아이디어는 저번 글에서 본 칸토어의 앞뒤 논법을 일반화한 것이다.

그러나 유감스럽게도 포화된 구조는 구성하기가 까다롭다. 일례로 비가산 기수 $\kappa$와, $|T| \leq \kappa$인 건전한 이론 $T$에 대해, $T$는 $\kappa^+$-포화된, 기수 $2^\kappa$의 모델을 가진다. 따라서 일반화된 연속체 가설을 인정할 시 해당 모델은 포화되어 있다. 그러나 ZFC만으로는 포화된 구조가 존재함을 증명할 수 없음이 알려져 있다.

따라서 다음의 더 약한 조건을 가진 개념을 도입한다.

정의. $\mathfrak{A}$가 특별_special하다는 것은, $\mathfrak{A}$가 방향 유도계 $\lbrace \mathfrak{A}_\kappa \rbrace _{\kappa < |A|}$의 쌍대 극한이라는 것이다. 여기서 $\kappa$는 무한 기수이며, 각 $\mathfrak{A}_\kappa$는 $\kappa^+$-포화되어 있다.

모든 포화된 구조는 특별하다. 각 $\mathfrak{A}_\kappa$를 자기 자신으로 두면 되기 때문이다. 그러나 모든 특별한 구조가 포화된 것은 아니다. 따라서 특별함은 포화보다 엄격히 약한 조건이다. 그럼에도 특별한 구조는 동형성 성질을 만족한다.

정리. 초등적으로 동등하며 기수가 같은 두 특별한 $\mathcal{L}$-구조는 동형이다.

더구나 특별한 구조는 포화된 구조보다 더 구성하기 쉽다. 특히, 다음 뢰벤하임-스콜렘 정리의 특수화가 알려져 있다.

특별 뢰벤하임-스콜렘 정리. $T$가 언어 $\mathcal{L}$의 이론이라고 하자.

1. $T$가 무한 모델을 가진다면, $T$는 임의의 기수보다 큰 기수의 특별한 모델을 가진다.
2. $T$가 무한 모델을 가지고, $\mathcal{L}$이 가산이라면, $T$는 기수가 $\beth_\omega$인 특별한 모델을 가진다.

이 정리의 응용으로서, 다음의 유명한 결과를 보자.

정의. 실수 닫힌 순서체 이론 또는 RCOF란 다음의 공리들로 이루어진 언어 $(0, 1, +, \cdot, <)$의 이론이다. ($x^n$은 $x \underbrace{\cdot \;\cdots\; \cdot}_{n} x$를 줄인 표기법)

1. 순서체 공리
   • $\forall a, b, c : (a < b) \rightarrow (a + c < b + c)$
   • $\forall a, b : (a > 0 \land b > 0) \rightarrow ab > 0$
   • 체 공리
2. 제곱근 공리: $\forall a > 0 \; \exists x : x^2 = a$
3. 닫힘 공리꼴:
   • $\forall a_2, a_1, a_0 \; \exists x :x^3 + a_2x^2 + a_1x + a_0 = 0$
   • $\forall a_4, a_3, a_2, a_1, a_0\; \exists x : x^5 + a_4x^4 + \cdots + a_0 = 0$
   • …

실수 닫힌체 이론 또는 RCF란 다음의 공리들로 이루어진 언어 $(0, 1, +, \cdot)$의 이론이다.

1. 체 공리
2. 형식적 실수 공리: $\forall x : x^2 \neq -1$
3. 제곱근 공리: $\forall a \; \exists x : x^2 = a \lor x^2 = -a$
4. 닫힘 공리꼴

타르스키 정리. RCOF와 RCF는 완전하다.

증명. 핵심은 다음의 보조정리이다.

에르되시-길만-헨릭슨_{Erdös-Gillman-Henriksen} 보조정리. 기수가 같은 두 특별한 실수 닫힌체는 동형이다.

보조정리를 인정하고 타르스키 정리를 증명해 보자. 만약 RCF가 완전하지 않다면, RCF의 확장 $T_1$과 $T_2$가 존재하여 $T_1$의 모델과 $T_2$의 모델은 초등적으로 동등하지 않다. RCF의 모든 모델은 무한 모델이므로 (why?) 특별 뢰벤하임-스콜렘 정리에 의해 $T_1$과 $T_2$는 각각 기수가 $\beth_\omega$인 모델 $\mathfrak{A}_1, \mathfrak{A}_2$를 가진다. 그런데 보조정리에 의해 $\mathfrak{A}_1 \cong \mathfrak{A}_2$인데, 이는 $\mathfrak{A}_1 \not\equiv \mathfrak{A}_2$와 모순이다. ■

Saturated Structures and the Completeness of Real Closed Fields

13 May 2025

This post was machine translated and has not yet been proofread. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Let $\mathfrak{A}$ be an $\mathcal{L}$-structure. Let $A$ be the domain of $\mathfrak{A}$.

Definition. A subset $X \subseteq A$ is said to be definable if there exist some $\mathcal{L}$-formula $\phi$ and free variable assignment $g$ such that the following holds:

\[X = \{ x \in A : \mathfrak{A} \vDash \phi[g^0_x] \}\]

When $\phi$ has no free variables other than $v_0$, we say that $X$ is $\emptyset$-definable.

Remark. Definability has the same meaning as Gödel’s constructibility.

For example, in $(\mathbb{R}, <)$, the interval $(e, 2\pi)$ is definable by the following $\phi$ and $g$:

• $\phi \equiv (v_1 < v_0 \land v_0 < v_2)$
• $g: v_1 \mapsto e, v_2 \mapsto 2\pi$

However, $(e, 2\pi)$ is not $\emptyset$-definable, as there is no way to specify $e$ and $2\pi$ in $(\mathbb{R}, <)$.

On the other hand, in the standard arithmetic model $(\mathbb{N}, 0, +, S)$, the set of even numbers $E$ is $\emptyset$-definable by the following $\phi$:

• $\phi \equiv \exists y (x = y + y)$

All finite sets are definable. For instance, $A = \lbrace a_1, a_2, a_3 \rbrace $ is definable as follows:

• $\phi \equiv (v_0 = v_1) \lor (v_0 = v_2) \lor (v_0 = v_3)$
• $g: v_1 \mapsto a_1, v_2 \mapsto a_2, v_3 \mapsto a_3$

For the same reason, all cofinite sets are also definable.

In the previous post, we examined resilient families of sets. We now define the following:

Definition. Let $\kappa$ be an uncountable cardinal. We say that $\mathfrak{A}$ is $\kappa$-saturated if every collection of fewer than $\kappa$ definable subsets of $A$ is resilient. In particular, when $\mathfrak{A}$ is $|A|$-saturated, we say that $\mathfrak{A}$ is saturated.

Therefore, an $\aleph_1$-saturated structure $\mathfrak{A}$ is one in which, whenever a countable collection of definable subsets of $\mathfrak{A}$ satisfies the finite intersection property, their total intersection is also non-empty. Meanwhile, it is impossible for a structure $\mathfrak{A}$ to be $|A|^+$-saturated, since the following family of sets satisfies the finite intersection property but has empty intersection:

\[\Big\{ A - \{ a \} : a \in A \Big\}\]

The importance of saturated structures lies in the following theorem:

Theorem. Two elementarily equivalent saturated $\mathcal{L}$-structures of the same cardinality are isomorphic.

Proof. Omitted. The basic idea is a generalisation of Cantor’s back-and-forth argument seen in the previous post.

Unfortunately, saturated structures are difficult to construct. For instance, for an uncountable cardinal $\kappa$ and a consistent theory $T$ with $|T| \leq \kappa$, the theory $T$ has a $\kappa^+$-saturated model of cardinality $2^\kappa$. Therefore, under the generalised continuum hypothesis, such a model is saturated. However, it is known that ZFC alone cannot prove the existence of saturated structures.

We therefore introduce the following concept with a weaker condition:

Definition. We say that $\mathfrak{A}$ is special if $\mathfrak{A}$ is the direct limit of a directed system $\lbrace \mathfrak{A}_\kappa \rbrace _{\kappa < |A|}$, where $\kappa$ is an infinite cardinal and each $\mathfrak{A}_\kappa$ is $\kappa^+$-saturated.

Every saturated structure is special, as we can take each $\mathfrak{A}_\kappa$ to be itself. However, not every special structure is saturated. Therefore, being special is a strictly weaker condition than being saturated. Nevertheless, special structures satisfy the isomorphism property:

Theorem. Two elementarily equivalent special $\mathcal{L}$-structures of the same cardinality are isomorphic.

Moreover, special structures are easier to construct than saturated structures. In particular, the following specialisation of the Löwenheim-Skolem theorem is known:

Special Löwenheim-Skolem Theorem. Let $T$ be a theory in language $\mathcal{L}$.

1. If $T$ has an infinite model, then $T$ has a special model of cardinality greater than any given cardinal.
2. If $T$ has an infinite model and $\mathcal{L}$ is countable, then $T$ has a special model of cardinality $\beth_\omega$.

As an application of this theorem, we consider the following famous result:

Definition. The theory of real closed ordered fields or RCOF is a theory in the language $(0, 1, +, \cdot, <)$ consisting of the following axioms: ($x^n$ is an abbreviation for $x \underbrace{\cdot \;\cdots\; \cdot}_{n} x$)

1. Ordered field axioms
   • $\forall a, b, c : (a < b) \rightarrow (a + c < b + c)$
   • $\forall a, b : (a > 0 \land b > 0) \rightarrow ab > 0$
   • Field axioms
2. Square root axiom: $\forall a > 0 \; \exists x : x^2 = a$
3. Closure axiom schemas:
   • $\forall a_2, a_1, a_0 \; \exists x :x^3 + a_2x^2 + a_1x + a_0 = 0$
   • $\forall a_4, a_3, a_2, a_1, a_0\; \exists x : x^5 + a_4x^4 + \cdots + a_0 = 0$
   • …

The theory of real closed fields or RCF is a theory in the language $(0, 1, +, \cdot)$ consisting of the following axioms:

1. Field axioms
2. Formally real axiom: $\forall x : x^2 \neq -1$
3. Square root axiom: $\forall a \; \exists x : x^2 = a \lor x^2 = -a$
4. Closure axiom schemas

Tarski’s Theorem. RCOF and RCF are complete.

Proof. The key is the following lemma:

Erdős-Gillman-Henriksen Lemma. Two special real closed fields of the same cardinality are isomorphic.

Assuming the lemma, we prove Tarski’s theorem. If RCF were not complete, there would exist extensions $T_1$ and $T_2$ of RCF such that models of $T_1$ and models of $T_2$ are not elementarily equivalent. Since all models of RCF are infinite models (why?), by the special Löwenheim-Skolem theorem, $T_1$ and $T_2$ each have models $\mathfrak{A}_1, \mathfrak{A}_2$ of cardinality $\beth_\omega$. However, by the lemma, $\mathfrak{A}_1 \cong \mathfrak{A}_2$, which contradicts $\mathfrak{A}_1 \not\equiv \mathfrak{A}_2$. ■

η 집합

09 May 2025

가산 조밀 무계 전순서_{countable dense unbounded linear order}는 모두 동형임을 보인 칸토어의 앞뒤 논법_{back-and-forth argument}에서 핵심이 되는 원리는 다음이다.

가산 데데킨트 성질. $(L, <)$이 전순서라고 하자. 다음은 동치이다.

1. $(L, <)$은 조밀하고 무계이다.
2. $L$의 유한 부분집합 $C, D$에 대해, $C < D$일 경우 $C < y < D$를 만족하는 $y \in L$이 존재한다.

여기서 $C < D$는 $\forall c \in C, d \in D : c < d$를 줄인 표기이다.

유한 데데킨트 성질로부터 동형성 정리를 다음과 같이 보일 수 있다. $(A, <_A), (B, <_B)$가 두 가산 조밀 무계 전순서라고 하자. 가산이므로 $A, B$의 원소를 자연수로 인덱싱할 수 있다. $f: A \to B$를 다음과 같이 귀납적으로 정의한다.

1. $f(a_0) = b_0$로 두고, $n = 1$로 정한다.
2. $a_n \in \mathrm{dom} f$을 확인한다.
   1. $a_n \in \mathrm{dom} f$라면 3으로 넘어간다.
   2. $a_n \notin \mathrm{dom} f$라면 보조정리에 의해 $C = \lbrace f(a_k) : k < n, a_k <_A a_n \rbrace , D = \lbrace f(a_k) : k < n, a_k >_A a_n \rbrace $에 대해 $C < y < D$인 $y \in B$가 존재한다. $f(a_n) = y$로 정의한다.
3. $b_n \in \mathrm{ran} f$를 확인한다.
   1. $b_n \in \mathrm{ran} f$라면 4로 넘어간다.
   2. $b_n \notin \mathrm{ran} f$라면, 보조정리에 의해 $C = \lbrace f^{-1}(b_k) : k < n, b_k <_B b_n \rbrace , D = \lbrace f^{-1}(b_k) : k < n, b_k >_B b_n \rbrace $에 대해 $C < x < D$인 $x \in A$가 존재한다. $f(x) = b_n$으로 정의한다.
4. $n$을 $n + 1$로 갱신하고 2로 되돌아간다.

위 과정의 귀납적 극한으로서 얻어지는 $f$는 $A$와 $B$의 동형 사상이다.

그런데 위 보조정리의 다음 일반화는 일반적으로 성립하지 않는다.

(틀린 명제) $(L, <)$이 전순서라고 하자. 다음은 동치이다.

1. $(L, <)$은 조밀하고 무계이다.
2. $L$보다 작은 기수인 $L$의 부분집합 $C, D$에 대해, $C < D$일 경우 $C < y < D$를 만족하는 $y \in L$이 존재한다.

예를 들어 $(\mathbb{R} \setminus \lbrace 0 \rbrace , <)$는 조밀하고 무계인 전순서이며, $C = (-\infty, 0) \cap \mathbb{Q}, D = (0, \infty) \cap \mathbb{Q}$일 때 $C < D$이고 $|C|, |D| < |\mathbb{R}|$이지만 $C < y < D$를 만족하는 실수 $y$는 존재하지 않는다.

만약 위 보조정리의 일반화가 성립했다면, 다음과 같이 기수가 $\kappa > \aleph_0$인 조밀 무계 전순서가 유일함을 증명할 수 있었을 것이다. 선택 공리를 가정했을 때, $A$와 $B$는 $\kappa$와 순서 동형이도록 정렬될 수 있다. 이제 서수 $\alpha < \kappa$에 대해 초한귀납적으로 $f$를 정의한다.

1. $f(a_0) = b_0$로 두고, $\alpha = 1$로 정한다.
2. $a_\alpha \in \mathrm{dom} f$을 확인한다.
   1. $a_\alpha \in \mathrm{dom} f$라면 3으로 넘어간다.
   2. $a_\alpha \notin \mathrm{dom} f$라면 일반화된 보조정리에 의해 $C = \lbrace f(a_\beta) : \beta < \alpha, a_\beta <_A a_\alpha \rbrace , D = \lbrace f(a_\beta) : \beta < \alpha, a_\beta >_A a_\alpha \rbrace $에 대해 $C < y < D$인 $y \in B$가 존재한다. $f(a_\alpha) = y$로 정의한다.
3. $b_\alpha \in \mathrm{ran} f$를 확인한다.
   1. $b_\alpha \in \mathrm{ran} f$라면 4로 넘어간다.
   2. $b_\alpha \notin \mathrm{ran} f$라면, 일반화된 보조정리에 의해 $C = \lbrace f^{-1}(b_\beta) : \beta < \alpha, b_\beta <_B b_\alpha \rbrace , D = \lbrace f^{-1}(b_\beta) : \beta < \alpha, b_\beta >_B b_\alpha \rbrace $에 대해 $C < x < D$인 $x \in A$가 존재한다. $f(x) = b_\alpha$로 정의한다.
4. 초한귀납적으로 $f$를 완성한다.

그러나 일반화된 보조정리가 성립하지 않으므로, 칸토어의 앞뒤 논법은 비가산 조밀 무계 전순서가 유일하다는 것을 보이는 데 적용될 수 없다. 실제로 비가산 조밀 무계 전순서는 $\mathbb{R}$ 이외에도 $\lbrace 0\rbrace \times \mathbb{R} \sqcup \lbrace 1\rbrace \times \mathbb{Q}$에 사전식 순서를 준 순서 등 유일하지 않다.

그렇다면 보조정리의 성질은 어느 정도까지 일반화될 수 있을까? 이 물음과 관련된 개념은 다음과 같다.

정의.

1. 집합족 $\mathcal{C}$가 유한 교집합 속성_{finite intersection property}을 가진다는 것은, $\mathcal{C}$의 집합-원소들의 유한한 교집합은 언제나 공집합이 아니라는 것이다.
2. 집합족 $\mathcal{C}$가 탄력적_resilient이라는 것은, $\mathcal{D}$가 유한 교집합 속성을 가지는 $\mathcal{C}$의 부분모임일 때, $\bigcap_{D \in \mathcal{D}} D \neq \varnothing$인 것이다.

위상수학을 공부한 독자라면 이는 친숙한 개념일 것이다.

칸토어 축소구간 정리. $K$가 콤팩트할 필요충분조건은 $K$의 모든 닫힌 집합들의 모임 $\mathcal{F}$가 탄력적인 것이다.

증명. $(\Rightarrow)$ $\mathcal{F}$가 탄력적이지 않다고 하자. 그러면 어떤 닫힌 집합들의 모임 $\mathcal{C}$가 존재하여, $\mathcal{C}$가 유한 교집합 속성을 가지지만 $\bigcap_{C \in \mathcal{C}} C = \varnothing$이다. 드 모르간 법칙에 의해 $\bigcup_{C \in \mathcal{C}} C^c = K$이다. 즉 $\lbrace C^c : C \in \mathcal{C} \rbrace $는 $K$의 열린 덮개이다. $K$가 콤팩트하므로 이는 유한 부분 덮개를 가진다. 그러나 이 경우 다시 드 모르간 법칙에 의해, 어떤 유한한 $\mathcal{C}’ \subset \mathcal{C}$에 대해 $\bigcap_{C \in \mathcal{C}’} C = \varnothing$이다. 이는 $\mathcal{C}$의 유한 교집합 속성에 모순된다.

$(\Leftarrow)$ 거의 비슷한 방식으로 증명한다. ■

이제 다음과 같이 보조정리를 일반화할 수 있다.

비가산 데데킨트 성질. $(L, <)$이 전순서이고, $\kappa$가 비가산 기수라고 하자. 다음은 동치이다.

1. $(L, <)$은 조밀하고 무계이다. 또한, $\kappa$개보다 적은 임의의 열린 구간 및 반직선들의 모임은 탄력적이다.
2. $L$의 부분집합 $C, D$에 대해, $|C|, |D| < \kappa$이고 $C < D$라면 $C < y < D$를 만족하는 $y \in L$이 존재한다.

증명. $(\Rightarrow)$

i. $D = \varnothing$

$\mathcal{C} = \lbrace (c, \infty) : c \in C \rbrace$를 고려하자. $|\mathcal{C}| = |C| < \kappa$이므로 전제에 의해 $\mathcal{C}$는 탄력적이다. $\mathcal{C}$가 유한 교집합 속성을 가지므로 $\bigcap_{c \in C} (c, \infty) = (c’, \infty)$이다. 해당 $c’$이 찾고자 하는 $y$이다.

ii. $C = \varnothing$

i.의 경우와 거의 동일하다.

iii. $C, D \neq \varnothing$

$\mathcal{E} = \lbrace (c, d) : c \in C, d \in D \rbrace $를 고려하자. 기수 관계식 $\lambda \cdot \epsilon = \mathrm{max}(\lambda, \epsilon)$에 의해 $|\mathcal{E}| < \kappa$이며, $\mathcal{E}$는 탄력적이다. $\mathcal{E}$가 유한 교집합 속성을 가지므로 ($\because$ 가산 데데킨트 성질) $\bigcap_{c \in C, d \in D} (c, d) = (c’, d’)$이다. $(c’, d’) \neq \varnothing$이므로 $y \in (c’, d’)$가 존재하며, 이것이 우리가 찾고자 하는 $y$이다.

$(\Leftarrow)$ $(L, <)$이 조밀하고 무계임은 자명하다.

$\mathcal{E}$가 $\kappa$개보다 적은 열린 구간 및 반직선들의 모임이라고 하자. $\mathcal{F} \subseteq \mathcal{E}$가 유한 교집합 속성을 가진다고 하자. 그렇다면 $C = \lbrace c : (c, d) \in \mathcal{F} \text{ or } (c, \infty) \in \mathcal{F} \rbrace $, $D = \lbrace d : (c, d) \in \mathcal{F} \text{ or } (-\infty, d) \in \mathcal{F}\rbrace $에 대하여 $C < D$이다. 그렇지 않다면 어떤 $c’ \in C, d’ \in D$에 대해 $d’ < c’$라는 것인데, 이 경우 $c’$을 왼쪽 끝점으로 가지는 열린 구간 $(c’, d’’) \in \mathcal{F}$와 $d’$을 오른쪽 끝점으로 가지는 열린 구간 $(c’’, d’) \in \mathcal{F}$에 대해 $(c’, d’’) \cap (c’’, d’) = \varnothing$이 되어 $\mathcal{F}$의 유한 교집합 속성에 모순되기 때문이다.

따라서 $C < D$이며, 조건에 의해 $C < y < D$인 $y$가 존재한다. 이로부터 $y \in \bigcap_{I \in \mathcal{F}} I$가 따라 나오며, $\mathcal{E}$가 탄력적임이 보여진다. ■

정의. 비가산 데데킨트 성질을 만족하는 집합을 $\eta$ 집합이라고 한다. 특히, $\kappa = \aleph_\alpha$에 대해 비가산 데데킨트 성질을 만족하는 집합을 $\eta_\alpha$ 집합이라고 한다.

$\eta$ 집합은 하우스도르프에 의해 제시되었다. $\eta$ 집합은 다음 글에서 알아 볼 포화_saturation 개념과 밀접한 관련이 있다.

η Sets

09 May 2025

This post was machine translated and has not yet been proofread. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

The key principle in Cantor’s back-and-forth argument, which demonstrates that all countable dense unbounded linear orders are isomorphic, is the following.

Countable Dedekind Property. Let $(L, <)$ be a linear order. The following are equivalent:

1. $(L, <)$ is dense and unbounded.
2. For finite subsets $C, D$ of $L$, if $C < D$ then there exists $y \in L$ such that $C < y < D$.

Here $C < D$ is shorthand notation for $\forall c \in C, d \in D : c < d$.

From the finite Dedekind property, the isomorphism theorem can be proved as follows. Let $(A, <_A), (B, <_B)$ be two countable dense unbounded linear orders. Since they are countable, the elements of $A, B$ can be indexed by natural numbers. Define $f: A \to B$ inductively as follows:

1. Set $f(a_0) = b_0$ and let $n = 1$.
2. Check whether $a_n \in \mathrm{dom} f$.
   1. If $a_n \in \mathrm{dom} f$, proceed to step 3.
   2. If $a_n \notin \mathrm{dom} f$, by the lemma there exists $y \in B$ such that $C < y < D$ for $C = \lbrace f(a_k) : k < n, a_k <_A a_n \rbrace$ and $D = \lbrace f(a_k) : k < n, a_k >_A a_n \rbrace$. Define $f(a_n) = y$.
3. Check whether $b_n \in \mathrm{ran} f$.
   1. If $b_n \in \mathrm{ran} f$, proceed to step 4.
   2. If $b_n \notin \mathrm{ran} f$, by the lemma there exists $x \in A$ such that $C < x < D$ for $C = \lbrace f^{-1}(b_k) : k < n, b_k <_B b_n \rbrace$ and $D = \lbrace f^{-1}(b_k) : k < n, b_k >_B b_n \rbrace$. Define $f(x) = b_n$.
4. Update $n$ to $n + 1$ and return to step 2.

The function $f$ obtained as the inductive limit of the above process is an isomorphism between $A$ and $B$.

However, the following generalisation of the above lemma does not hold in general.

(False Statement) Let $(L, <)$ be a linear order. The following are equivalent:

1. $(L, <)$ is dense and unbounded.
2. For subsets $C, D$ of $L$ with cardinality less than that of $L$, if $C < D$ then there exists $y \in L$ such that $C < y < D$.

For example, $(\mathbb{R} \setminus \lbrace 0 \rbrace, <)$ is a dense unbounded linear order, and when $C = (-\infty, 0) \cap \mathbb{Q}$ and $D = (0, \infty) \cap \mathbb{Q}$, we have $C < D$ and $|C|, |D| < |\mathbb{R}|$, but there exists no real number $y$ satisfying $C < y < D$.

If the generalisation of the above lemma held, one could prove the uniqueness of dense unbounded linear orders of cardinality $\kappa > \aleph_0$ as follows. Assuming the axiom of choice, $A$ and $B$ can be well-ordered to be order-isomorphic to $\kappa$. Now define $f$ by transfinite induction for ordinals $\alpha < \kappa$.

1. Set $f(a_0) = b_0$ and let $\alpha = 1$.
2. Check whether $a_\alpha \in \mathrm{dom} f$.
   1. If $a_\alpha \in \mathrm{dom} f$, proceed to step 3.
   2. If $a_\alpha \notin \mathrm{dom} f$, by the generalised lemma there exists $y \in B$ such that $C < y < D$ for $C = \lbrace f(a_\beta) : \beta < \alpha, a_\beta <A a\alpha \rbrace$ and $D = \lbrace f(a_\beta) : \beta < \alpha, a_\beta >A a\alpha \rbrace$. Define $f(a_\alpha) = y$.
3. Check whether $b_\alpha \in \mathrm{ran} f$.
   1. If $b_\alpha \in \mathrm{ran} f$, proceed to step 4.
   2. If $b_\alpha \notin \mathrm{ran} f$, by the generalised lemma there exists $x \in A$ such that $C < x < D$ for $C = \lbrace f^{-1}(b_\beta) : \beta < \alpha, b_\beta <B b\alpha \rbrace$ and $D = \lbrace f^{-1}(b_\beta) : \beta < \alpha, b_\beta >B b\alpha \rbrace$. Define $f(x) = b_\alpha$.
4. Complete $f$ by transfinite induction.

However, since the generalised lemma does not hold, Cantor’s back-and-forth argument cannot be applied to show that uncountable dense unbounded linear orders are unique. Indeed, uncountable dense unbounded linear orders are not unique—besides $\mathbb{R}$, there are others such as the lexicographic order on $\lbrace 0\rbrace \times \mathbb{R} \sqcup \lbrace 1\rbrace \times \mathbb{Q}$.

To what extent can the property of the lemma be generalised? The concept related to this question is as follows.

Definition.

1. A family of sets $\mathcal{C}$ has the finite intersection property if the finite intersection of set-elements from $\mathcal{C}$ is always non-empty.
2. A family of sets $\mathcal{C}$ is resilient if, whenever $\mathcal{D}$ is a subfamily of $\mathcal{C}$ with the finite intersection property, we have $\bigcap_{D \in \mathcal{D}} D \neq \varnothing$.

Readers familiar with topology will recognise this as a familiar concept.

Cantor’s Nested Interval Theorem. $K$ is compact if and only if every collection $\mathcal{F}$ of closed subsets of $K$ is resilient.

Proof. $(\Rightarrow)$ Suppose $\mathcal{F}$ is not resilient. Then there exists a collection $\mathcal{C}$ of closed sets such that $\mathcal{C}$ has the finite intersection property but $\bigcap_{C \in \mathcal{C}} C = \varnothing$. By De Morgan’s laws, $\bigcup_{C \in \mathcal{C}} C^c = K$. That is, $\lbrace C^c : C \in \mathcal{C} \rbrace$ is an open cover of $K$. Since $K$ is compact, this has a finite subcover. However, in this case, again by De Morgan’s laws, for some finite $\mathcal{C}’ \subset \mathcal{C}$ we have $\bigcap_{C \in \mathcal{C}’} C = \varnothing$. This contradicts the finite intersection property of $\mathcal{C}$.

$(\Leftarrow)$ The proof follows in almost exactly the same manner. ■

We can now generalise the lemma as follows.

Uncountable Dedekind Property. Let $(L, <)$ be a linear order and let $\kappa$ be an uncountable cardinal. The following are equivalent:

1. $(L, <)$ is dense and unbounded. Moreover, any collection of fewer than $\kappa$ open intervals and half-lines is resilient.
2. For subsets $C, D$ of $L$, if $|C|, |D| < \kappa$ and $C < D$, then there exists $y \in L$ such that $C < y < D$.

Proof. $(\Rightarrow)$

i. $D = \varnothing$

Consider $\mathcal{C} = \lbrace (c, \infty) : c \in C \rbrace$. Since $|\mathcal{C}| = |C| < \kappa$, by the premise $\mathcal{C}$ is resilient. Since $\mathcal{C}$ has the finite intersection property, $\bigcap_{c \in C} (c, \infty) = (c’, \infty)$. This $c’$ is the desired $y$.

ii. $C = \varnothing$

Almost identical to case i.

iii. $C, D \neq \varnothing$

Consider $\mathcal{E} = \lbrace (c, d) : c \in C, d \in D \rbrace$. By the cardinal arithmetic $\lambda \cdot \epsilon = \mathrm{max}(\lambda, \epsilon)$, we have $|\mathcal{E}| < \kappa$, and $\mathcal{E}$ is resilient. Since $\mathcal{E}$ has the finite intersection property ($\because$ countable Dedekind property), $\bigcap_{c \in C, d \in D} (c, d) = (c’, d’)$. Since $(c’, d’) \neq \varnothing$, there exists $y \in (c’, d’)$, which is the desired $y$.

$(\Leftarrow)$ That $(L, <)$ is dense and unbounded is trivial.

Let $\mathcal{E}$ be a collection of fewer than $\kappa$ open intervals and half-lines. Suppose $\mathcal{F} \subseteq \mathcal{E}$ has the finite intersection property. Then for $C = \lbrace c : (c, d) \in \mathcal{F} \text{ or } (c, \infty) \in \mathcal{F} \rbrace$ and $D = \lbrace d : (c, d) \in \mathcal{F} \text{ or } (-\infty, d) \in \mathcal{F}\rbrace$, we have $C < D$. Otherwise, for some $c’ \in C, d’ \in D$ we would have $d’ < c’$, in which case for an open interval $(c’, d’’) \in \mathcal{F}$ with left endpoint $c’$ and an open interval $(c’’, d’) \in \mathcal{F}$ with right endpoint $d’$, we would have $(c’, d’’) \cap (c’’, d’) = \varnothing$, contradicting the finite intersection property of $\mathcal{F}$.

Therefore $C < D$, and by the condition there exists $y$ such that $C < y < D$. From this it follows that $y \in \bigcap_{I \in \mathcal{F}} I$, showing that $\mathcal{E}$ is resilient. ■

Definition. A set satisfying the uncountable Dedekind property is called an $\eta$ set. In particular, a set satisfying the uncountable Dedekind property for $\kappa = \aleph_\alpha$ is called an $\eta_\alpha$ set.

$\eta$ sets were introduced by Hausdorff. $\eta$ sets are closely related to the concept of saturation, which we shall explore in the following article.

로빈슨, 크레이그, 베스의 정리

08 May 2025

초등적 병합 성질_{Elementary amalgamation property}

정리. $\mathcal{L}$-구조 $\mathfrak{A}$와 $\mathcal{L}’$-구조 $\mathfrak{B}$에 대해, $\mathfrak{B}$의 $\mathcal{L}$-퇴화_{$\mathcal{L}$-reduct}가 $\mathfrak{A}$와 초등적으로 동등_{elementarily equivalent}하다고 하자. 이때, $\mathcal{L}’$-구조 $\mathfrak{C}$가 존재하여, $f: \mathfrak{A} \to \mathfrak{C}$가 $\mathcal{L}$의 초등적 임베딩이고 $g: \mathfrak{B} \to \mathfrak{C}$가 $\mathcal{L}’$의 초등적 임베딩이다.

증명. 이 글의 표기법을 따라, 언어 $L_\mathfrak{A}$의 이론 $E(\mathfrak{A})$와 언어 $L’_\mathfrak{B}$의 이론 $E(\mathfrak{B})$를 생각하자. $T = E(\mathfrak{A}) \cup E(\mathfrak{B})$는 언어 $\mathcal{L}’_{\mathfrak{AB}} = \mathcal{L}_\mathfrak{A} \cup \mathcal{L}’_\mathfrak{B}$의 이론이다. $T$가 모델 $\mathfrak{C}$를 가짐을 보이자.

만약 $T$가 모델이 없다면 $T$는 모순적이다. 따라서 콤팩트성 정리에 의해 어떤 $\mathcal{L}$-논리식 $\phi$와 $\mathcal{L}’$-논리식 $\psi$가 존재하여, 적절한 $\lbrace a_i \rbrace \subset \mathcal{L}_\mathfrak{A}$, $\lbrace b_j \rbrace \subset \mathcal{L}_\mathfrak{B}$에 대해,

\[\lbrace \phi(a_1, \dots, a_n), \psi(b_1, \dots, b_m) \rbrace\]

이 모델을 가지지 않는다. $\mathfrak{B} \vDash \psi(b_1, \dots, b_m)$이므로, $\mathfrak{B} \vDash \phi(a_1, \dots, a_n)$를 만족하도록 상수 $a_1, \dots, a_n$을 $\mathfrak{B}$의 정의역에 대응시키는 방법이 존재하지 않아야 한다. 즉,

\[\mathfrak{B} \not\vDash \exists x_1, \dots x_n \; \phi(x_1, \dots, x_n)\]

그런데 $\mathfrak{B}$의 $\mathcal{L}$-퇴화가 $\mathfrak{A}$와 초등적으로 동등하며, 위 식의 우변이 $\mathcal{L}$-문장이고, $\mathfrak{A}$가 해당 문장을 만족하므로 이는 모순이다. 따라서 $T$는 모델 $\mathfrak{C}$를 가진다. 그리고 $\mathfrak{C}$는 $E(\mathfrak{A})$와 $E(\mathfrak{B})$의 모델이므로, $\mathfrak{A}$와 $\mathfrak{B}$는 $\mathfrak{C}$로 자연스럽게 초등적으로 임베딩된다. ■

로빈슨 건전성 정리_{Robinson consistency theorem}

정리. $\mathcal{L} = \mathcal{L}_1 \cap \mathcal{L}_2$라고 하자. $T$가 $\mathcal{L}$의 (의미론적으로) 완전한 이론이고, $T_1$과 $T_2$가 각각 $T$를 확장하는 건전한 $\mathcal{L}_1, \mathcal{L}_2$ 이론일 때, $T_1 \cup T_2$는 $\mathcal{L}_1 \cup \mathcal{L}_2$ 이론으로서 건전하다.

증명. $T_1 \cup T_2$의 모델을 구축하면 정리가 보여진다.

$T_1, T_2$가 각각 건전하므로, 모델 $\mathfrak{A}_0, \mathfrak{B}_0$를 가진다. $T = T_1 \cap T_2$가 완전하므로, $\mathcal{L}$-퇴화로서의 $\mathfrak{A}_0$와 $\mathfrak{B}_0$는 초등적으로 동등하다. 따라서 초등적 병합 성질에 의해, $\mathcal{L}$-초등적 임베딩 $f_0$와 $\mathcal{L}_2$-초등적 임베딩 $h_0$가 존재하여 다음이 성립한다.

이제 $\mathfrak{B}_1$의 $\mathcal{L}$-퇴화를 생각해 보면, 이는 $\mathfrak{A}_0$와 초등적으로 동등하므로, 다시 초등적 병합 성질에 의해 $\mathcal{L}$-초등적 임베딩 $g_0$와 $\mathcal{L}_1$-초등적 임베딩 $k_0$가 존재하여 다음이 성립한다.

이 과정을 반복하여 다음의 구조 유도계_{directed system of structures}를 얻는다.

사상	성질
$f, g$	$\mathcal{L}$-초등적 임베딩
$k$	$\mathcal{L}_1$-초등적 임베딩
$h$	$\mathcal{L}_2$-초등적 임베딩

위 유도계의 모든 모델을 $\mathcal{L}$로 퇴화시키면 $\mathcal{L}$-구조 유도계를 얻는다. 해당 유도계의 쌍대극한_colimit을 $\mathfrak{C}$라고 하자. $\mathfrak{C}$는 다음의 $\lbrace \mathfrak{A}_i \rbrace $로 이루어진 유도계의 쌍대극한이기도 하다. 회색으로 표시된 원 유도계의 일부는 모두 $\lbrace \mathfrak{A}_i \rbrace $ 중 하나로 투사되기 때문이다. 따라서 $\mathfrak{C}$는 $\mathfrak{A}_0$를 초등적으로 임베딩하는 $\mathcal{L}_1$ 구조이다.

같은 이유로 $\mathfrak{C}$는 다음의 $\lbrace \mathfrak{B}_i \rbrace $로 이루어진 유도계의 쌍대극한이기도 하다. 따라서 $\mathfrak{C}$는 $\mathfrak{B}_0$를 초등적으로 임베딩하는 $\mathcal{L}_2$ 구조이다.

즉, $\mathfrak{C}$는 $\mathfrak{A}$와 $\mathfrak{B}$를 모두 임베딩하며, 이로부터 $T_1 \cup T_2$의 모델임이 보여졌다. ■

크레이그 보간 정리_{Craig interpolation theorem}

정리. $\mathcal{L}$-문장 $\phi, \psi$에 대해 $\phi \vDash \psi$라면, 어떤 $\mathcal{L}$-문장 $\theta$가 존재하여 $\phi \vDash \theta, \theta \vDash \psi$이다. 또한, $\theta$에 포함된 비논리 기호(상수, 술어, 함수)는 $\phi$와 $\psi$에 공통적으로 포함된다.

$\theta$를 $\phi$와 $\psi$의 크레이그 보간이라고 부른다.

증명. 귀류법으로 증명한다. 크레이그 보간이 존재하지 않는다고 가정하자. 그러면 $\phi$는 모델을 가진다. 만약 $\phi$가 모델을 가지지 않는다면 $\perp$가 $\phi, \psi$의 크레이그 보간이기 때문이다. 또한 $\lnot \psi$도 모델을 가진다. 그렇지 않다면 $\top$가 크레이그 보간이기 때문이다.

$\mathcal{L}’$을 $\phi$와 $\psi$에 공통적으로 포함되는 비논리 기호들로 이루어진 언어라고 하자. $\Gamma$를, $\phi \vDash \sigma$이거나 $\lnot \psi \vDash \sigma$인 $\mathcal{L}’$-문장 $\sigma$의 집합이라고 하자.

$\Gamma \cup \lbrace \phi \rbrace $는 무모순적임을 보이자. 만약 모순적이라면, 콤팩트성 정리에 의해 어떤 $\mathcal{L}’$-문장 $\sigma_1, \sigma_2$가 존재하여 $\phi \vDash \sigma_1, \lnot\psi \vDash \sigma_2$이고 $\lbrace \sigma_1, \sigma_2, \phi \rbrace $가 모순적이다. 그런데 $\phi \vDash \sigma_1$이므로 $\phi \vDash \lnot\sigma_2$이다. 대우법에 의해 $\lnot\psi\ \vDash \sigma_2$로부터 $\lnot\sigma_2 \vDash \psi$가 따라 나온다. 즉, $\sigma_2$는 $\phi, \psi$의 크레이그 보간이다. 이는 가정에 모순된다.

따라서 $\Gamma \cup \lbrace \phi \rbrace $는 무모순적이며, 같은 이유로 $\Gamma \cup \lbrace \lnot\psi \rbrace $ 또한 무모순적이다. 이제 초른의 보조정리를 적용하여, $\overline{\Gamma}$를 다음 $\mathcal{L}’$-이론들의 순서의 극대로 정의한다.

\[\{ \Gamma' : \Gamma \subseteq \Gamma', \Gamma' \cup \{\phi\} \text{ and } \Gamma' \cup \{\lnot \psi\} \text{ are consistent} \}\]

$\overline{\Gamma}$는 완전함을 보이자. 만약 $\overline{\Gamma}$가 완전하지 않다면, 어떤 $\mathcal{L}’$-문장 $\sigma$가 존재하여 $\sigma \notin \overline{\Gamma}$이고, $\overline{\Gamma} \cup \lbrace \sigma, \phi \rbrace $ 또는 $\overline{\Gamma} \cup \lbrace \sigma, \lnot \psi \rbrace $가 무모순적이다.

전자의 경우, 콤팩트성 정리에 의해 어떤 $\overline{\Gamma}$의 문장 $\theta$가 존재하여 $\phi \vDash \theta \rightarrow \lnot \sigma$이다. $\Gamma$의 정의에 의해 $\theta \rightarrow \lnot \sigma \in \Gamma \subseteq \overline{\Gamma}$이다. 따라서 $\overline{\Gamma} \cup \lbrace \sigma, \phi \rbrace $는 $\lnot\phi$를 증명한다. 이는 모순이다. 후자의 경우에도 마찬가지 모순이 발생한다. 따라서 $\overline{\Gamma}$는 완전하다.

$\overline{\Gamma}$가 완전하고, $\overline{\Gamma} \cup \lbrace \phi \rbrace , \overline{\Gamma} \cup \lbrace \lnot\psi \rbrace $가 건전하므로, 로빈슨 건전성 정리에 의해 $\overline{\Gamma} \cup \lbrace \phi, \lnot \psi \rbrace $가 건전하다. 그런데 이는 $\phi \vDash \psi$에 모순된다. 따라서 귀류법에 의해 $\phi, \psi$는 크레이그 보간을 가진다. ■

베스 정의 가능성 정리_{Beth definability theorem}

언어 $\mathcal{L}$과, $\mathcal{L}$에 포함되어 있지 않은 술어 $P$를 생각하자. $T$가 $\mathcal{L} \cup \lbrace P \rbrace $의 이론이라고 하자. $T$를 만족하는 $\mathcal{L}$의 구조 $\mathfrak{A}$를 $\mathcal{L} \cup \lbrace P \rbrace $로 확장하는 방법이 유일할 때, $T$가 $P$를 암시적으로 정의_{implicitly define}한다고 한다.

이는 다음과 같이 말할 수도 있다. $T(P’)$가 $T$에서 등장하는 모든 $P$를 $P’$으로 바꾼 $\mathcal{L} \cup \lbrace P’ \rbrace $ 이론이라고 하자. $T$가 $P$를 암시적으로 정의한다는 것은 다음이 성립한다는 것이다.

\[T \cup T(P') \vDash \forall x_1, \dots, x_n \; P(x_1, \dots, x_n) \leftrightarrow P'(x_1, \dots, x_n)\]

반면 $T$가 $P$를 명시적으로 정의_{explicitly define}한다는 것은 다음을 만족시키는 $\mathcal{L}$-논리식 $\phi$가 존재한다는 것이다.

\[T \vDash \forall x_1, \dots, x_n \; P(x_1, \dots, x_n) \leftrightarrow \phi(x_1, \dots, x_n)\]

예를 들어 보자. $\mathcal{L} = (0, S, +, \cdot)$의 이론 $\mathsf{PA}$에 술어 $P(x, y)$에 관한 공리를 추가한 다음의 이론을 $T$라고 하자.

\[T = \mathsf{PA} \cup \Big\{ \forall x, y \big[ P(x, y) \rightarrow x + y = S(0) \big] \Big\}\]

$T(P’)$은 다음과 같다.

\[T(P') = \mathsf{PA} \cup \Big\{ \forall x, y \big[ P'(x, y) \rightarrow x + y = S(0) \big] \Big\}\]

$T$가 $P$를 암묵적으로 정의한다는 것은 다음이 성립한다는 것이다.

\[T \cup T(P') \vDash \forall x, y \big[ P(x, y) \leftrightarrow P'(x, y) \big]\]

이는 귀납 공리꼴로부터 자연스럽게 따라 나온다. 그런데 $P$는 다음과 같이 $T$에서 명시적으로 정의될 수도 있다.

\[\begin{gather} T \vDash \forall x, y \big[ P(x, y) \leftrightarrow \phi(x, y) \big] \\\\ \text{where}\\\\ \phi(x, y) : \forall z \big[ x + z = S(0) \rightarrow z = y \big] \end{gather}\]

이는 우연이 아니다.

정리. 언어 $\mathcal{L}$에 대해, $\mathcal{L} \cup \lbrace P \rbrace $의 이론 $T$가 $P$를 암시적으로 정의하면, $T$는 $P$를 명시적으로 정의한다.

증명. $P$가 $n$항 술어라고 하자. $\mathcal{L}$에 새로운 상수 $c_1, \dots, c_n$을 추가한 언어를 $\mathcal{L}’$이라고 하자. $T$가 $P$를 암시적으로 정의하므로,

\[T \cup T(P') \vDash P(c_1, \dots, c_n) \rightarrow P'(c_1, \dots, c_n)\]

이다. 콤팩트성 정리에 의해 어떤 $\mathcal{L} \cup \lbrace P \rbrace $ 문장 $\psi$가 존재하여, $T \vdash \psi$이고 다음이 성립한다.

\[\psi \land \psi(P') \vDash P(c_1, \dots, c_n) \rightarrow P'(c_1, \dots, c_n)\]

함축 원리를 이용하여 이항하면 다음과 같다.

\[\psi \land P(c_1, \dots, c_n) \vDash \psi(P') \rightarrow P'(c_1, \dots, c_n)\]

좌변은 $\mathcal{L}’ \cup \lbrace P \rbrace $의 문장이고, 우변은 $\mathcal{L}’ \cup \lbrace P’ \rbrace $의 문장이다. 따라서 크레이그 보간 정리에 의해 $\mathcal{L}$-논리식 $\theta$가 존재하여 다음이 성립한다.

\[\begin{gather} \psi \land P(c_1, \dots, c_n) \vDash \theta(c_1, \dots, c_n), \\\\ \theta(c_1, \dots, c_n) \vDash \psi(P') \rightarrow P'(c_1, \dots, c_n) \end{gather}\]

다시 이항하고 $P’$을 $P$로 치환하면,

\[\begin{gather} \psi \vDash P(c_1, \dots, c_n) \rightarrow \theta(c_1, \dots, c_n), \\\\ \psi \vDash \theta(c_1, \dots, c_n) \rightarrow P(c_1, \dots, c_n) \end{gather}\]

따라서 $\theta$는 $P$를 명시적으로 정의한다. ■