Can the Mind Be Reduced to a Machine: Gödel's Disjunction and the Penrose-Lucas Argument

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

This article is a summary of Peter Koellner, On the question of whether the mind can be mechanized (2018).

Abstract. The Church-Turing thesis and Gödel’s incompleteness theorems suggest the existence of mathematical truths that cannot be proved mechanically. However, if an ideal human mind can prove all mathematical truths, then the conclusion follows that the ideal human mind is not equivalent to a machine. This article examines the arguments of Lucas and Penrose, who attempt to establish anti-mechanism in such a manner, and introduces formal proofs that refute these arguments.

Introduction

The following are well-known results in logic:

• Church-Turing Thesis. To be computable by an ideal machine is to be implementable by a Turing machine.

• Gödel’s Incompleteness Theorem. If $F$ is a formal system satisfying certain conditions, then there exists a sentence that is true but unprovable in $F$.

• Formal System-Turing Machine Correspondence. If $F$ is a formal system satisfying certain conditions, then there exists a Turing machine that enumerates the propositions provable in $F$.

Combining these three theses with the fact that we humans appear to be capable of grasping mathematical truths not captured by formal systems—such as the consistency of arithmetic—the incompleteness theorem appears to suggest that the extension of mathematical results derivable by an ideal human mind exceeds the extension of results derivable by an ideal finite machine. That is, the incompleteness theorem appears to suggest anti-mechanism: that the mind cannot be reduced to a machine.

In this article, we examine how far this suggestion can be justified. As a result, we shall show that while the incompleteness theorem suggests anti-mechanism or Platonism, it does not directly suggest anti-mechanism.

1. Gödel’s Disjunction

Gödel argued that from the incompleteness theorem, it follows that at least one of the following two positions is true. We shall call this Gödel’s Disjunction.

1. Anti-mechanism: The mathematical results derivable by an ideal human mind always exceed the mathematical results derivable by an ideal finite machine. Therefore, the human mind cannot be reduced to a machine.

2. Platonism: There exist mathematical truths that cannot be grasped by an ideal human mind. Therefore, mathematical truth exists independently of the human mind.

It is noteworthy that both positions are contrary to materialist philosophy. while Gödel was generally reserved about philosophical arguments, he argued strongly that this particular argument was a “mathematically established fact”. Our first task is to verify whether this argument is indeed a “mathematically established fact”.

1.1. Gödel’s Three Claims

Let us introduce some notation.

1. $F$ is the set of all sentences that the formal system $F$ can prove.

2. $K$ is the set of all sentences that an ideal human mind can prove.

3. $T$ is the set of true sentences.

Throughout this article, we shall assume $K \subseteq T$. We also presuppose that $F$ is a formal system to which Gödel’s incompleteness theorem applies—that is, a consistent system containing Peano arithmetic (in fact, this condition can be weakened to Robinson arithmetic).

Before proceeding to the main discussion, let us review Gödel’s incompleteness theorem.

Gödel’s Incompleteness Theorem. When $F$ is a consistent mathematical system containing arithmetic, the following holds:

• First Theorem. There exists a proposition that is true but unprovable in $F$.
• Second Theorem. The consistency of $F$ is an instance of the First Theorem.

Incidentally, while the incompleteness theorem traditionally targets Peano arithmetic, the incompleteness theorem also holds for weaker arithmetic systems, including Robinson arithmetic.

1.1.1. First Claim

Gödel first claims the following:

Claim 1. $F \subseteq T \implies F \subsetneq T$

The proof is as follows. If $F \subseteq T$, then $\mathrm{Con}(F) \in T$. However, by the Second Incompleteness Theorem, $\mathrm{Con}(F) \notin F$. Therefore, $F \subsetneq T$.

1.1.2. Second Claim

Gödel’s second claim is as follows:

Claim 2. $K(F \subseteq T) \implies F \subsetneq K$

The proof is as follows. If $K(F \subseteq T)$, then $\mathrm{Con}(F) \in K$. However, as we have seen, $F \subseteq T \implies \mathrm{Con}(F) \notin F$, so $F \subsetneq K$.

But if $F \subsetneq K$ is true, how should we understand this? One approach is to consider a hierarchy of formal systems.

Gödel emphasises that the unprovable sentences suggested by the incompleteness theorem need not be absolutely unprovable. This is because sentences unprovable in formal system $F$ may become provable in systems of higher order than $F$. For example, if $\mathsf{PA}$ is consistent, then while $\mathsf{PA}$ cannot prove $\mathrm{Con}(\mathsf{PA})$, it is known that second-order Peano arithmetic $\mathsf{PA}_2$ can prove $\mathrm{Con}(\mathsf{PA})$. Of course, $\mathsf{PA}_2$ cannot prove $\mathrm{Con}(\mathsf{PA}_2)$, but this is provable in third-order Peano arithmetic, and such a hierarchy continues.

This entire hierarchy appears to be subsumed under $K$. From this perspective, each formal system is like a set, and $K$ is like the collection of all sets. And just as the collection of all sets cannot be a set, an analogy holds that $K$ cannot be a formal system.

1.1.3. Third Claim

However, one might wonder: instead of writing “Claim 2” as a conditional, could we not claim $F \subsetneq K$ by asserting that $K(F \subsetneq T)$ is true?

Gödel points out that the incompleteness theorem alone cannot lead to such a claim. This is because the possibility of the existence of a formal system $F^*$ that coincides with $K$ cannot be completely ruled out (note that the previous discussion regarding higher-order Peano arithmetic was merely an analogy).

Regarding this, Gödel says:

[If such a formal system exists] human reason—at least in its mathematical aspect—is equivalent to a finite machine. However, that machine cannot completely understand its own operation [in the sense that it cannot prove its own consistency]. This inability would be mistaken by humans as the infinite extensibility of the mind.

Instead, Gödel’s third claim is as follows. This claim is Gödel’s disjunction.

Claim 3. $\forall F (F \subsetneq K) \; \lor \; K \subsetneq T$

The proof is as follows. Suppose there is a formal system $F^$ such that $F^ = K$. Since we have assumed $K \subset T$, we have $F^* \subset T$, and by Claim 1, $F^* \subsetneq T$.

The former signifies anti-mechanism, while the latter signifies Platonism.

1.2. Formalisation of Gödel’s Disjunction

So far, we have presented Gödel’s three claims and introduced brief proofs thereof. However, these proofs were not actually precise. This is because we did not introduce rigorous definitions of $F, K, T$, nor did we distinguish between what content can be proved within a formal system and what content can only be proved outside a formal system. To overcome this limitation, let us rigorously formalise $F, K, T$ and the proofs of Gödel’s three claims.

1.2.1. $F$

$F$ is the easiest concept to formalise. In particular, the following facts are known:

Formal System-Turing Machine Correspondence. When $F$ is a recursively axiomatisable formal system, there exists a Turing machine that recursively enumerates the propositions provable from $F$.

Additionally, the formal systems of interest to us are recursively axiomatisable.

Recursiveness of Kleene Predicates. The operation of Turing machines can be formalised within Peano arithmetic. Specifically, there exists a first-order logical predicate $K(x, y, z)$ that determines whether a Turing machine with Gödel number $x$, when given natural number $y$ as input, terminates with a computation record with Gödel number $z$.

As a corollary of the above two theorems, we obtain:

Corollary. Formal systems are recursively enumerable. That is, the “$e$-th formal system” $F_e$ can be defined in Peano arithmetic.

For example, $F_{123}$ might be Robinson arithmetic, $F_{456}$ might be ZFC, and so forth. $F_{123}(\ulcorner 1 + 1 = 2 \urcorner)$ means that $1 + 1 = 2$ is provable in Robinson arithmetic. And $\mathsf{PA} \vdash F_{123}(\ulcorner 1 + 1 = 2 \urcorner)$.

1.2.2. $T$

The most promising formal definition of $T$ is Tarski’s typed truth definition. while Tarski’s typed truth definition is a syntactic rather than semantic definition, it is suitable for the purposes of the present discussion. Tarski’s definition consists of axioms including the following:

• $\forall x : \mathrm{Sent}(x) \rightarrow (T(\hat{\lnot} x) \leftrightarrow \lnot T(x))$

• $\forall x, y : [\mathrm{Sent}(x) \land \mathrm{Sent}(y)] \rightarrow [T(x\; \hat{\lor} \;y) \leftrightarrow T(x) \lor T(y)]$

Here, $\mathrm{Sent}$ determines whether a given sentence (or its Gödel number) is well-formed. Meanwhile, $\hat{\quad}$ is introduced to distinguish between language and meta-language; a detailed explanation is not particularly important, so we shall leave it at this.

1.2.3. $K$

$K$ is the most challenging of the three concepts. Not only can we not provide a complete semantic definition, but there are also questionable aspects to providing a syntactic definition. However, since the goal of this article is to demonstrate that $F \subsetneq K$ cannot be directly shown from the incompleteness theorem, according to the principle of charity, we shall present the following syntactic definition that maximally guarantees the extension of $K$.

Syntactic Definition of $K$.

1. When $\phi$ is logically true, $K\phi$.
2. For arbitrary sentences $\phi, \psi$: $(K(\phi \rightarrow \psi) \land K\phi) \rightarrow K\psi$.
3. For arbitrary sentence $\phi$: $K\phi \rightarrow \phi$.
4. For arbitrary sentence $\phi$: $K\phi \rightarrow KK\phi$.

Here, $K$ is a logical operator. Therefore, we write $K\phi$ rather than $K(\phi)$ or $K(\ulcorner \phi \urcorner)$. For the reason why $K$ should be regarded as a logical operator rather than a predicate, see footnote 29 of the original paper.

1.2.4. $\mathsf{EA}$ and $\mathsf{EA}_T$

Let us construct a formal system capable of reasoning about $F, K, T$. Firstly, as we saw in 1.2.1, $F$ is already formalisable in $\mathsf{PA}$, so no special measures are required.

Let $L_{\mathsf{EA}}$ be defined as $\mathsf{PA}$ with the function $K$ added. Let $\Sigma$ be the collection of axioms of $\mathsf{PA}$ and the axioms of the syntactic definition of $K$ (where the induction schema of $\mathsf{PA}$ is taken over sentences of $L_{\mathsf{EA}}$ rather than $L_{\mathsf{PA}}$). The axioms of $\mathsf{EA}$ are $\Sigma \cup K\Sigma$.

Let $L_{\mathsf{EA}T}$ be defined as $\mathsf{EA}$ with the predicate $T$ added. Let $\Sigma^*$ be the collection of $\Sigma$ and the axioms of the syntactic definition of $T$ (where the induction schema of $\mathsf{PA}$ is taken over sentences of $L{\mathsf{EA}_T}$). The axioms of $\mathsf{EA}_T$ are $\Sigma^* \cup K\Sigma^*$.

1.3. Formal Proof of Gödel’s Disjunction

We show that Gödel’s three claims are formally provable in $\mathsf{EA}_T$.

1.3.1. First Claim

Claim 1. $F \subseteq T \implies F \subsetneq T$

This claim is easily provable in $\mathsf{EA}_T$. This is because it is a direct consequence of Gödel’s incompleteness theorem.

1.3.2. Second Claim

Claim 2. $K(F \subseteq T) \implies F \subsetneq K$

This claim is also provable in $\mathsf{EA}_T$. In fact, the following stronger result is provable:

Reinhardt’s First Theorem. For arbitrary sentence $\phi$, if

\[\mathsf{EA} \vdash K(F(\ulcorner \phi \urcorner) \rightarrow \phi)\]

then there exists some sentence $\psi$ such that

\[\mathsf{EA} \vdash K\psi \land K\lnot F(\ulcorner \psi \urcorner)\]

(that is, $\mathsf{EA} \vdash F \subsetneq K$).

1.3.3. Third Claim

Claim 3. $\forall F (F \subsetneq K) \; \lor \; K \subsetneq T$

Expanding $F \subsetneq K$ in the above claim gives:

And expanding $K \subsetneq T$ gives:

However, there is a problem here. As mentioned earlier, since $K$ is a logical operator rather than a predicate, it cannot be placed within a quantified context. Just as $\exists \phi : \lnot\phi$ is not grammatically correct. To circumvent this problem, instead of writing $\exists x \; K(x)$, we write $\exists x\; T(\hat{K}x)$. Therefore, the correct formalisation of Claim 3 is as follows:

Let us call the above formula $\mathrm{GD}$. The following theorem is known:

Reinhardt’s Second Theorem. $\mathsf{EA}_T \vdash \mathrm{GD}$.

Therefore, Gödel’s disjunction is provable under an appropriate formal system.

2. Lucas and Penrose

2.1. The Consistency Decision Problem

Lucas and Penrose attempt to directly show $F \subsetneq K$ by claiming $K(F \subseteq T)$. That is, Lucas and Penrose argue that the ideal human mind has the ability to determine whether any given formal system is consistent or not, and accordingly claim $\forall F \subseteq T: F \subsetneq K$.

However, it is highly questionable whether the ideal human mind has the ability to determine the consistency of arbitrary formal systems. For instance, let $R$ be the Riemann hypothesis. $R$ can be formalised as a $\Pi_1$ proposition in Peano arithmetic. And as mentioned earlier, since $\mathsf{PA}$ is $\Sigma_1$-complete, the consistency of $\mathsf{PA} + R$ is equivalent to $R$. This example shows that there are cases where the consistency decision problem for formal systems is at least as difficult as the Riemann hypothesis.

2.2. Relative Consistency of Mechanism

This fact alone would put Lucas and Penrose’s project in difficulty, but we can go further and show a more powerful fact. That fact is that $K(F\subseteq T)$ is formally unprovable. This is because mechanistic theses are consistent with $\mathsf{EA}_T$.

Before showing this, it is useful to classify mechanistic theses according to their strength. Reinhardt’s classification adopted in this article is as follows:

• Weak Mechanical Thesis (WMT): $\exists e \; ( K = F_e )$
• Strong Mechanical Thesis (SMT): $K\exists e\; (K = F_e)$
• Super Strong Mechanical Thesis (SSMT): $\exists e \; K(K = F_e)$

To explain each:

• WMT: The ideal human mind is equivalent to some Turing machine.
• SMT: The ideal human mind knows that it is equivalent to some Turing machine.
• SSMT: The ideal human mind knows that it is equivalent to a specific Turing machine.

The following is known:

Reinhardt’s Third Theorem. $\mathsf{EA}_T + \mathsf{SSMT}$ is inconsistent.

Therefore, assuming the axioms of $\mathsf{EA}T$, the super strong mechanical thesis is false. In short, even if a computer equivalent to the ideal human mind were given, we could not know whether it is _truly equivalent to the human mind.

However, this fact alone is insufficient to support Lucas and Penrose. This is because the core thesis of mechanism is not the method of identifying machines with capabilities equivalent to ours, but the existence of machines with capabilities equivalent to ours. Regarding this, the following is known:

Reinhardt’s Fourth Theorem. $\mathsf{EA}_T + \mathsf{WMT}$ is consistent.

Furthermore, the following is known:

Carlson’s Theorem. $\mathsf{EA}_T + \mathsf{SMT}$ is consistent.

That is, $\mathsf{EA}_T$ not only leaves open the possibility of the existence of a machine equivalent to the ideal human mind, but also leaves open the possibility that the human mind can prove this fact itself. These facts show that attempts to establish anti-mechanism solely through the incompleteness theorem are bound to fail.

2.3. Gödel’s Insight

Remarkably, Gödel appears to have understood all of this discussion from the beginning. According to Wang’s recollections of conversations with Gödel:

The incompleteness theorem does not rule out the possibility of a computer that produces results equivalent to human mathematical intuition [$\exists e\; (F_e = K)$]. However, it does suggest the following: if that possibility—though the probability is extremely low due to other considerations—is true, then either we cannot know the design of such a computer [$\lnot K (F_e = K)$], or we cannot know that the computer operates correctly [$\lnot K (F_e \subseteq T)$].

3. Conclusion

The discussion thus far should be sufficient to prevent further attempts to directly derive anti-mechanism from Gödel’s disjunction. However, there is another approach to arguing for anti-mechanism from logical results. This argument, commonly called Penrose’s new argument, is an argument that puts forward type-free truth, as distinguished from Tarski’s typed truth. The formalisation of this argument and its implications will be addressed in Part 2 of this paper.

산술 위계

주의. 이 글은 뇌피셜로 쓰였기 때문에 엄밀하지 않고, 심지어 틀린 내용이 있을 수 있습니다.

산술 위계(arithmetical hierarchy)는 산술 — 엄밀히는 1차 페아노 산술 — 의 명제들을 양화사의 복잡도에 따라 분류한 것이다. 산술 위계는 증명 이론 및 계산 복잡도 이론의 핵심 개념이며, 기술적 집합론과도 연관이 있다.

1. $\Delta_0$ 명제

1.1. 정의

정의. $\Sigma_0 = \Pi_0 = \Delta_0$는 상한이 있는 양화사만을 가지는 명제들의 집합이다.

왜 같은 부류의 명제를 세 개의 이름으로 부르는지는 곧 명확해질 것이다. 이 글에서는 특별한 이유가 없을 때에는 세 이름 중 $\Delta_0$라는 이름을 대표로 사용하겠다.

예를 들어 다음 네 명제들은 모두 $\Delta_0$ 명제들이다.

$\phi_1$은 거짓인 문장이다. $\phi_2$는 $x$가 짝수일 때, $\phi_3$는 $x$가 $y$의 약수일 때 참인 명제이다.

$\Delta_0$ 명제들은 양화사에 상한이 걸려 있기 때문에, 임의의 $x$가 주어졌을 때 $x$가 해당 명제에 부합하는지를 튜링 기계로 판단할 수 있다. 예를 들어 $x$가 $\phi_2$를 만족하는지 판단하는 튜링 기계는 다음과 같다.

for y < x:
   if y + y == x:
      return true;

return false;

위 튜링 기계는 $x$번의 반복 이내에 정지한다. 따라서 $\Delta_0$는 또는 튜링 기계 등의 기계 장치로 결정 가능(decidable)한, 또는 재귀적인(recursive), 또는 계산 가능(computable)한 명제들이다(세 표현은 동의어이다). 그러나 뒤에서 자세히 설명하듯이, 모든 결정 가능한 명제들이 $\Delta_0$인 것은 아니다.

괴델의 표현가능성 정리에 따라 결정 가능한 참인 명제는 증명 가능하다. 그리고 이 글에서 $\phi$가 ‘참’이라 함은, $\mathsf{PA} \vDash \phi$가 아니라, 표준 자연수 모형 $\mathcal{N}$에 대해 $\mathcal{N} \vDash \phi$라는 의미이다. 다시 말해, 다음이 성립한다.

정리. 참인 $\Delta_0$ 문장들의 집합은 완전하다. (즉, $\phi$가 참인 $\Delta_0$ 문장이라면 $\mathsf{PA} \vdash \phi$이다.)

1.2. 계산 이론에서의 $\Delta_0$

프로그래밍 언어의 관점에서 보았을 때 $\Delta_0$ 문장들은 다음만을 허용하는 코드의 집합과 대응된다.

• 조건문
• 상한이 있는 반복문
• 덧셈과 곱셈

주의할 점은, 상한이 없는 반복문과 변수 재지정은 허용되지 않는다는 것이다. 예를 들어 다음의 코드는 소수 판별이 $\Delta_0$임을 입증한다.

for y < x:
  for z <= y:
    if yz == x:
      return false;

return true;

그러나 $x^y$를 계산하는 다음의 코드는 $\Delta_0$에 해당되지 않는다.

let a = 1
for 1<= z <= y:
   a = a * x

return a

그렇다면 지수 연산은 $\Delta_0$가 아닌 것일까? 그렇지는 않다. 복잡하긴 하지만, $\Delta_0$ 명제로 지수를 표현하는 방법이 있다. 이 사례는 주어진 연산 또는 술어가 $\Delta_0$인지 판단하는 일이 까다로울 수 있음을 방증한다. 일례로 다음이 알려져 있다.

정리. 팩토리얼은 $\Delta_0$이지만 테트레이션은 $\Delta_0$가 아니다.

그러나 테트레이션은 결정 가능하다. 따라서 모든 결정 가능한 명제들이 $\Delta_0$인 것은 아니다.

2. 한 단계 올라가기

정의.

\[\begin{gather} \Sigma_1 := \{ \exists x_1 \cdots \exists x_n \;\phi : \phi \in \Pi_0 \}\\ \Pi_1 := \{ \forall x_1 \cdots \forall x_n \;\phi : \phi \in \Sigma_0 \}\\ \Delta_1 := \Sigma_1 \cap \Pi_1 \end{gather}\]

2.1. $\Sigma_1$ 명제

다음 명제들은 $\Sigma_1$이다.

$\phi_1$은 집합 $\lbrace 1, 3, 7, 13, \dots \rbrace$에서 참이다. $\phi_2$는 골드바흐의 추측으로, 모든 $x$가 이를 만족하는지는 알려져 있지 않다.

$\Sigma_1$은 재귀적으로 열거 가능(recursively enumerable)한 집합들의 모임이다. 즉, $\phi \in \Sigma_1$이라면 다음의 튜링 기계 $M$이 존재한다.

• $\phi(c)$가 참이라면 $M$이 $\phi(c)$를 결정함이 보장된다.
• $\phi(c)$가 거짓이라면 $M$이 $\phi(c)$를 결정함이 보장되지 않는다.

예를 들어 다음의 튜링 기계는 $\phi_2$가 재귀적으로 열거 가능함을 보여준다.

for y > 1:
   for z > 1:
      if isPrime(y) & isPrime(z) & x = y + z & isEven(x):
         return true;

return false;

return false 문이 있기는 하지만, 반복문에서 빠져나올 break 문이 없으므로 return false는 도달 불가능하다. 즉, $\phi_2(c)$가 참이라면 위의 튜링 기계는 참을 반환하지만 거짓이라면 무한 루프에 빠진다.

$\phi \in \Sigma_1$이 표준 자연수 모형에서 참인 문장이라면 $\mathsf{PA} \vdash \phi$이다. $\phi : \exists x \; \psi(x)$ 꼴의 명제가 표준 자연수 모형에서 참이라는 것은 어떤 $c \in \mathbb{N}$에 대해 $\psi(c)$가 참이라는 의미이며, $\psi(c)$는 참인 $\Pi_0$ 문장이므로 증명 가능하기 때문이다. 따라서 다음이 성립한다.

정리. 참인 $\Sigma_1$ 문장들의 집합은 완전하다.

2.2. $\Sigma_1 \setminus \Delta_0$ 명제

그런데 사실 지금까지 필자는 독자를 오도했다. 앞서 $\Sigma_1$의 예시로 나열한 명제들은 사실 $\Delta_0$로 쓸 수 있기 때문이다.

그렇다면 $\Delta_0$에 속하지 않는 $\Sigma_1$ 명제는 어떻게 생겼을까? 한 가지 답은 정지 문제에서 찾을 수 있다.

먼저 $\mathrm{HaltsIn}(x, n)$를, “괴델 수가 $x$인 튜링 기계”가 $n$회의 연산 이내에 출력값을 내놓는지를 판별하는 술어라고 하자. 이 술어는 클레이니 술어로부터 쉽게 정의할 수 있으며, 클레이니 술어는 $\Sigma_0$임이 알려져 있다. 예를 들어 3의 제곱을 2회의 연산으로 계산하는 튜링 기계의 괴델 수가 $123$이라면 $\mathrm{HaltsIn}(123, 3)$은 참이지만 $\mathrm{HaltsIn}(123, 1)$는 거짓이다.

이제 다음 명제를 고려하자.

위 명제가 말하는 바는, 괴델 수가 $x$인 튜링 기계가 언젠가 정지한다는 것이다. 즉, 위 명제는 정지 문제와 동치이다. 그런데 정지 문제는 결정 불가능하다. 앞서 $\Delta_0$ 명제는 모두 결정 가능함을 보았으므로, $\phi$는 $\Delta_0$에 속하지 않는 $\Sigma_1$ 명제이다.

다른 예시로, 다음 명제를 고려하자.

여기서 $\mathrm{Proves}(x, y)$는 “괴델 수가 $x$인 문장의 증명”의 괴델 수가 $y$일 때 참인 술어이다. 즉, $\phi_2(x)$는 괴델 수가 $x$인 문장이 증명 가능하다는 술어이다. 그런데 이 술어는 결정 가능하지 않다. 만약 $\phi_2$가 결정 가능하다면 (PA가 무모순적이라는 가정 하에) $\phi_2(\ulcorner 0 = 1 \urcorner)$이 거짓이라는 증명이 PA에 존재하게 되어 괴델의 불완전성 정리와 상충하기 때문이다.

2.3. $\Pi_1$ 명제

$\Sigma_1$ 명제가 재귀적으로 열거 가능한 명제들의 모임이라면, $\Pi_1$ 명제는 쌍대-재귀적으로 열거 가능한(co-recursively enumerable) 명제들의 모임이다. 즉 $\Pi_1$의 문장은 거짓이라면 결정 가능하지만 참이라면 결정 가능성이 보장되지 않는다. 예를 들어 다음 두 명제는 $\Delta_0$가 아닌 $\Pi_1$ 문장이다.

$\Sigma_1$의 경우와 달리, $\Pi_1$은 완전하지 않다. $\Sigma_1$ 문장의 부정이 $\Pi_1$이기 때문에, $\Pi_1$ 또한 완전하다면 $\Sigma_1 = \Pi_1=$ (결정 가능한 명제들의 모임)이 되기 때문이다.

정리. 참인 $\Pi_1$ 문장들의 집합은 완전하지 않다.

2.4. $\Delta_1$ 명제

$\Delta_1$ 명제는 $\Sigma_1$과 $\Pi_1$에 모두 속한다. 따라서 $\Delta_1$은 결정 가능한 명제들의 모임이다. 앞서 본 테트레이션은 $\Delta_0$가 아닌 $\Delta_1$ 명제이다.

3. 한 단계 더 올라가기

정의.

\[\begin{gather} \Sigma_2 := \{ \exists x_1 \cdots \exists x_n \;\phi : \phi \in \Pi_1 \}\\ \Pi_2 := \{ \forall x_1 \cdots \forall x_n \;\phi : \phi \in \Sigma_1 \}\\ \Delta_2 := \Sigma_2 \cap \Pi_2 \end{gather}\]

이제 패턴이 보일 거라 생각한다. $\Sigma_2$ 명제의 예시로, 다음을 보자.

여기서 $\mathrm{DoesNotHaltOn}(x, y)$는, “괴델 수가 $x$인 튜링 기계”에 $y$를 입력했을 때 정지하지 않으면 참인 술어이다. 앞선 논의로부터 $\mathrm{DoesNotHaltOn}$이 $\Pi_1$임을 어렵지 않게 알 수 있다.

정리. $\phi_5 \notin \Pi_1$

증명. $\phi_5 \in \Pi_1$이라고 가정하자. 우리의 목표는 이 가정이 “참인 $\Pi_1$ 문장들의 집합은 완전하다”를 시사함을 보이는 것이다.

$\psi(x)$가 임의의 $\Delta_0$ 명제라고 하자. $\theta : \forall x \;\psi(x)$는 $\Pi_1$ 문장이다. 다음의 튜링 기계 $M$을 생각하자.

if ψ(x):
   return 1;

while True:

이 튜링 기계는 값 $x$에 대해 $\psi(x)$가 참이면 정지하고 거짓이면 정지하지 않는다. 따라서 $\theta$가 참이라는 것은 모든 $x$에 대해 $M$이 정지한다는 것과 동치이며, 이것은 $\phi_5(\ulcorner M \urcorner)$이 거짓임과 동치이다. 그리고 가정에 의해 $\phi_5 \in \Pi_1$이므로, $\phi_5(\ulcorner M \urcorner)$이 거짓이라면 $\mathsf{PA} \vdash \lnot \phi(\ulcorner M \urcorner)$이다. 즉, $\mathsf{PA} \vdash \theta$가 되어 모든 참인 $\Pi_1$ 문장은 증명 가능하게 된다. 이것은 모순이다. ■

Remark. 엄밀히는 위의 증명이 PA 내에서 표현 가능함을 보여야 한다.

앞서 $\Sigma_1$ 명제는 참일 때 결정 가능하고, $\Pi_1$ 명제는 거짓일 때 결정 가능하다고 했다. 그런데 $\Sigma_2$ 문장은 $\forall$과 $\exists$가 섞여 있기 때문에, 참일 때에도, 거짓일 때에도 결정이 불가능한 문장이 있을 수 있다.

3.1. 오라클

정의. $\mathcal{O}$가 단 한 번의 연산으로 문제 $P$의 결과를 구할 수 있을 때 $\mathcal{O}$을 $P$의 오라클이라고 한다.

예를 들어 정지 문제의 오라클은 주어진 튜링 기계의 정지 연부를 단 한 번의 연산으로 알아낼 수 있는, 그야말로 신적인 존재다.

산술 위계를 오르는 것은 점점 더 강한 오라클이 주어지는 것과 같다. 앞서 $\Sigma_1$ 명제의 예시로 다음을 보았다.

그런데 만약 정지 문제 오라클 $\mathcal{O}$가 주어졌다면, $\phi_1$은 $\Delta_0$ 명제로 단순하게 표현 가능하다.

또한 앞서 $\Sigma_2$ 명제의 예시로 다음을 보았다.

정지 문제 오라클 $\mathcal{O}$가 주어졌다면, $\phi_5$는 $\Sigma_1$ 명제로 표현 가능하다.

여기서 $x|_y$는 괴델 수가 $x$인 튜링 기계에 $y$를 입력한 상태의 괴델 수이다. 즉, $\Sigma_2$ 명제는 정지 문제의 오라클이 주어졌을 때 $\Sigma_1$ 명제로 환원된다. 비슷한 원리로, $\Pi_2$ 명제와 $\Delta_2$ 명제는 각각 정지 문제의 오라클이 주어졌을 때 $\Pi_1$ 명제와 $\Delta_1$ 명제로 환원된다.

나아가 2차 오라클을 정의할 수 있다. 2차 정지 문제 오라클은, 정지 문제 오라클을 사용하는 튜링 기계들에 대한 정지 문제 오라클이다. 예를 들어 $\mathcal{O}$가 다음 코드의 정지 여부를 판단하는 데 그치는 데 반해,

for x > 0:
   for y > 0:
      for z > 0:
         for n > 2:
            if x^n + y^n == z^n:
               return True;
return False;

$\mathcal{O}^2$은 다음 코드의 정지 여부를 판단할 수도 있다. 다음의 코드는 NP 튜링 기계의 괴델 수 $x$를 입력받았을 때, $x$와 출력이 일치하는 P 튜링 기계가 존재하면 정지하고 존재하지 않으면 정지하지 않는다.

let x ∈ NP;
for y ∈ P:
   if !Halts(
      let z = 0
      while x(z) == y(z):
         z = z + 1
   ):
      return 1; // x가 P에 속하는 NP일 때 정지

일반적으로 다음이 성립한다.

정리. $\Pi_n, \Sigma_n, \Delta_n$의 명제들은 $k$차 오라클이 주어졌을 때 각각 $\Pi_{n - k}, \Sigma_{n - k}, \Delta_{n - k}$의 명제들이 된다.

Arithmetic Hierarchy

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Warning. This article was written informally and may therefore lack rigour or even contain incorrect content.

The arithmetic hierarchy is a classification of propositions in arithmetic — more precisely, first-order Peano arithmetic — according to the complexity of their quantifiers. The arithmetic hierarchy is a central concept in proof theory and computational complexity theory, and is also related to descriptive set theory.

1. $\Delta_0$ Propositions

1.1. Definition

Definition. $\Sigma_0 = \Pi_0 = \Delta_0$ is the set of propositions containing only bounded quantifiers.

Why the same class of propositions is referred to by three names will become clear shortly. In this article, unless there is a specific reason otherwise, we shall use $\Delta_0$ as the representative name among the three.

For example, the following four propositions are all $\Delta_0$.

$\phi_1$ is a false statement. $\phi_2$ is true when $x$ is even, and $\phi_3$ is true when $x$ is a divisor of $y$.

Since $\Delta_0$ propositions have bounded quantifiers, it is possible to determine whether an arbitrary $x$ satisfies the corresponding proposition using a Turing machine. For instance, a Turing machine that determines whether $x$ satisfies $\phi_2$ is as follows:

for y < x:
   if y + y == x:
      return true;

return false;

The above Turing machine halts within $x$ iterations. Therefore, $\Delta_0$ propositions are decidable, recursive, or computable (the three expressions are synonymous). However, as we shall explain in detail later, not all decidable propositions are $\Delta_0$.

According to Gödel’s representability theorem, decidable true propositions are provable. In this article, when we say that $\phi$ is ‘true’, we mean $\mathcal{N} \vDash \phi$ for the standard model of arithmetics $\mathcal{N}$, rather than $\mathsf{PA} \vDash \phi$.

The following holds:

Theorem. The set of true $\Delta_0$ sentences is complete. (That is, if $\phi$ is a true $\Delta_0$ sentence, then $\mathsf{PA} \vdash \phi$.)

1.2. $\Delta_0$ in Computational Theory

From a programming language perspective, $\Delta_0$ sentences correspond to the set of code that permits only the following:

• Conditional statements
• Bounded loops
• Addition and multiplication

It should be noted that unbounded loops and variable reassignment are not permitted. For example, the following code demonstrates that primality testing is $\Delta_0$:

for y < x:
  for z <= y:
    if yz == x:
      return false;

return true;

However, the following code that computes $x^y$ does not correspond to $\Delta_0$:

let a = 1
for 1<= z <= y:
   a = a * x

return a

So is exponentiation not $\Delta_0$? Not necessarily. Although complex, there are methods to express exponentiation with a $\Delta_0$ proposition. This case demonstrates that determining whether a given operation or predicate is $\Delta_0$ can be intricate. For instance, the following is known:

Theorem. Factorial is $\Delta_0$, but tetration is not $\Delta_0$.

However, tetration is decidable. Therefore, not all decidable propositions are $\Delta_0$.

2. Moving Up One Level

Definition.

\[\begin{gather} \Sigma_1 := \{ \exists x_1 \cdots \exists x_n \;\phi : \phi \in \Pi_0 \}\\ \Pi_1 := \{ \forall x_1 \cdots \forall x_n \;\phi : \phi \in \Sigma_0 \}\\ \Delta_1 := \Sigma_1 \cap \Pi_1 \end{gather}\]

2.1. $\Sigma_1$ Propositions

The following propositions are $\Sigma_1$:

$\phi_1$ is true in the set $\lbrace 1, 3, 7, 13, \ldots\rbrace $. $\phi_2$ is Goldbach’s conjecture; it is not known whether all $x$ satisfy this.

$\Sigma_1$ is the collection of recursively enumerable sets. That is, if $\phi \in \Sigma_1$, then there exists a Turing machine $M$ such that:

• If $\phi(c)$ is true, then $M$ is guaranteed to decide $\phi(c)$.
• If $\phi(c)$ is false, then $M$ is not guaranteed to decide $\phi(c)$.

For example, the following Turing machine shows that $\phi_2$ is recursively enumerable:

for y > 1:
   for z > 1:
      if isPrime(y) & isPrime(z) & x = y + z & isEven(x):
         return true;

return false;

Although there is a return false statement, since there is no break statement to exit the loop, return false is unreachable. That is, if $\phi_2(c)$ is true, the above Turing machine returns true, but if it is false, it falls into an infinite loop.

If $\phi \in \Sigma_1$ is a sentence that is true in the standard model of arithmetics, then $\mathsf{PA} \vdash \phi$. A proposition of the form $\phi : \exists x \; \psi(x)$ being true in the standard model of arithmetics means that $\psi(c)$ is true for some $c \in \mathbb{N}$, and since $\psi(c)$ is a true $\Pi_0$ sentence, it is provable. Therefore, the following holds:

Theorem. The set of true $\Sigma_1$ sentences is complete.

2.2. $\Sigma_1 \setminus \Delta_0$ Propositions

However, I have in fact been misleading the reader thus far. The propositions I listed earlier as examples of $\Sigma_1$ can actually be written as $\Delta_0$:

So what do propositions that strictly belong to $\Sigma_1$ look like? One answer can be found in the halting problem.

First, let $\mathrm{HaltsIn}(x, n)$ be a predicate that determines whether “the Turing machine with Gödel number $x$” produces an output within $n$ operations. This predicate can be easily defined from the Kleene predicate, and the Kleene predicate is known to be $\Sigma_0$. For example, if the Gödel number of a Turing machine that computes the square of 3 in 2 operations is $123$, then $\mathrm{HaltsIn}(123, 3)$ is true but $\mathrm{HaltsIn}(123, 1)$ is false.

Now consider the following proposition:

What this proposition states is that the Turing machine with Gödel number $x$ eventually halts. That is, the above proposition is equivalent to the halting problem. However, the halting problem is undecidable. Since we showed earlier that all $\Delta_0$ propositions are decidable, $\phi$ is a $\Sigma_1$ proposition that does not belong to $\Delta_0$.

As another example, consider the following proposition:

Here, $\mathrm{Proves}(x, y)$ is a predicate that is true when the Gödel number of “a proof of the sentence with Gödel number $x$” is $y$. That is, $\phi_2(x)$ is a predicate stating that the sentence with Gödel number $x$ is provable. However, this predicate is not decidable. If $\phi_2$ were decidable, then (under the assumption that PA is consistent) there would exist a proof in PA that $\phi_2(\ulcorner 0 = 1 \urcorner)$ is false, which would conflict with Gödel’s incompleteness theorem.

2.3. $\Pi_1$ Propositions

If $\Sigma_1$ propositions are the collection of recursively enumerable propositions, then $\Pi_1$ propositions are the collection of co-recursively enumerable propositions. That is, a $\Pi_1$ sentence is decidable if false, but not necessarily decidable if true. For example, the following two propositions are $\Pi_1$ sentences that are not $\Delta_0$:

Unlike the case of $\Sigma_1$, $\Pi_1$ is not complete. Since the negation of a $\Sigma_1$ sentence is $\Pi_1$, if $\Pi_1$ were also complete, then $\Sigma_1 = \Pi_1 =$ (collection of decidable propositions).

Theorem. The set of true $\Pi_1$ sentences is not complete.

2.4. $\Delta_1$ Propositions

$\Delta_1$ propositions belong to both $\Sigma_1$ and $\Pi_1$. Therefore, $\Delta_1$ is the collection of decidable propositions. The tetration we saw earlier is a $\Delta_1$ proposition that is not $\Delta_0$.

3. Moving Up Another Level

Definition.

\[\begin{gather} \Sigma_2 := \{ \exists x_1 \cdots \exists x_n \;\phi : \phi \in \Pi_1 \}\\ \Pi_2 := \{ \forall x_1 \cdots \forall x_n \;\phi : \phi \in \Sigma_1 \}\\ \Delta_2 := \Sigma_2 \cap \Pi_2 \end{gather}\]

I believe the pattern should now be clear. As an example of a $\Sigma_2$ proposition, consider the following:

Here, $\mathrm{DoesNotHaltOn}(x, y)$ is a predicate that is true if “the Turing machine with Gödel number $x$” does not halt when given input $y$. From the preceding discussion, it is not difficult to see that $\mathrm{DoesNotHaltOn}$ is $\Pi_1$.

Theorem. $\phi_5 \notin \Pi_1$

Proof. Suppose $\phi_5 \in \Pi_1$. Our goal is to show that this assumption implies “the set of true $\Pi_1$ sentences is complete”.

Let $\psi(x)$ be an arbitrary $\Delta_0$ proposition. Then $\theta : \forall x \;\psi(x)$ is a $\Pi_1$ sentence. Consider the following Turing machine $M$:

if ψ(x):
   return 1;

while True:

This Turing machine halts for value $x$ if $\psi(x)$ is true and does not halt if it is false. Therefore, $\theta$ being true is equivalent to $M$ halting for all $x$, which is equivalent to $\phi_5(\ulcorner M \urcorner)$ being false. By assumption, $\phi_5 \in \Pi_1$, so if $\phi_5(\ulcorner M \urcorner)$ is false, then $\mathsf{PA} \vdash \lnot \phi(\ulcorner M \urcorner)$. That is, $\mathsf{PA} \vdash \theta$, making all true $\Pi_1$ sentences provable. This is a contradiction. ■

Remark. Strictly speaking, one should show that the above proof is expressible within PA.

We said earlier that $\Sigma_1$ propositions are decidable when true, and $\Pi_1$ propositions are decidable when false. However, since $\Sigma_2$ sentences have mixed $\forall$ and $\exists$ quantifiers, there may be sentences that are undecidable both when true and when false.

3.1. Oracles

Definition. When $\mathcal{O}$ can obtain the result of problem $P$ in a single operation, we call $\mathcal{O}$ an oracle for $P$.

For example, an oracle for the halting problem is a truly divine entity that can determine whether a given Turing machine halts in a single operation.

Ascending the arithmetic hierarchy is equivalent to being given increasingly powerful oracles. We saw earlier the following as an example of a $\Sigma_1$ proposition:

However, if a halting problem oracle $\mathcal{O}$ were given, $\phi_1$ could be expressed simply as a $\Delta_0$ proposition:

Also, we saw earlier the following as an example of a $\Sigma_2$ proposition:

If a halting problem oracle $\mathcal{O}$ were given, $\phi_5$ could be expressed as a $\Sigma_1$ proposition:

Here, $x|_y$ is the Gödel number of the state where input $y$ is given to the Turing machine with Gödel number $x$. That is, $\Sigma_2$ propositions reduce to $\Sigma_1$ propositions when given an oracle for the halting problem. By similar principles, $\Pi_2$ and $\Delta_2$ propositions reduce to $\Pi_1$ and $\Delta_1$ propositions, respectively, when given an oracle for the halting problem.

Furthermore, we can define second-order oracles. A second-order halting problem oracle is a halting problem oracle for Turing machines that use halting problem oracles. For example, while $\mathcal{O}$ is limited to determining whether the following code halts:

for x > 0:
   for y > 0:
      for z > 0:
         for n > 2:
            if x^n + y^n == z^n:
               return True;
return False;

$\mathcal{O}^2$ can also determine whether the following code halts. The following code takes as input the Gödel number $x$ of an NP Turing machine, halts if there exists a P Turing machine whose output matches $x$, and does not halt if no such machine exists:

let x ∈ NP;
for y ∈ P:
   if !Halts(
      let z = 0
      while x(z) == y(z):
         z = z + 1
   ):
      return 1; // halts when x is an NP that belongs to P

In general, the following holds:

Theorem. Propositions in $\Pi_n$, $\Sigma_n$, $\Delta_n$ become propositions in $\Pi_{n-k}$, $\Sigma_{n-k}$, $\Delta_{n-k}$, respectively, when given a $k$-th order oracle.

곱군과 위수에 관한 노트: 페르마 소수 정리와 윌슨의 정리

Remarks

• 소수 $p$에 대해 $p - 1$에 대한 정보가 주어졌다면 위수가 $p - 1$인 곱군 $(\mathbb{Z}/p\mathbb{Z})^\times$을 생각해 보자.
• 유한체의 곱군은 순환군이다.
• 순환적 곱군 $G$에 대해 $nm \mid |G|$는, $x^{nm} = 1$이지만 $x^n, x^m \neq 1$인 원소 $x$의 존재성과 동치이다.
• 위수는 주기와 다르다. 일반적으로 (주기) = (위수) + 1이다.

페르마 소수 정리

정리. 소수 $p$가 두 정수 $a, b$에 대해 $p = a^2 + b^2$ 꼴로 나타내어질 필요충분조건은 $p \bmod 1 = 4$인 것이다.

증명.

(⇒) 자명

(⇐) $G = (\mathbb{Z}/p\mathbb{Z})^\times$라고 하자. 조건에 의해 $4 \mid |G|$이다. 따라서 $n^4 = 1$이지만 $n^2 \neq 1$인 원소 $n$이 존재한다. 즉, $n^2 = -1$이다. 따라서 $p \mid n^2 + 1$이다. 이제 $\mathbb{Z}[i]$에서 생각해 보면 $p \mid (n + i)(n - i)$이다. 만약 $p$가 $\mathbb{Z}[i]$에서 기약이었다면 $p \mid n + i$ 또는 $p \mid n - i$인데 둘 다 불가능하다. 따라서 $p$는 기약이 아니며, 켤레성에 의해

이다. ■

윌슨의 정리

정리. $p$가 소수일 필요충분조건은 $(p - 1)! \equiv -1 \mod p$인 것이다.

증명.

(⇒) $G = (\mathbb{Z}/p\mathbb{Z})^\times$라고 하자. $G$의 원소를 모두 곱한 값은 $(p - 1)!$이다. $x^2 = 1$의 근인 $\pm 1$을 제외한 $G$의 모든 원소는 자기 자신을 역원으로 가지지 않는다. 따라서 $(p - 1)! \equiv -1$이다.

(⇐) $N = (p - 1)! + 1$이라고 하자. 조건에 의해 $p \mid N$이다. 만약 $p$가 소수가 아니라면 어떤 소수 $q < p$에 대해 $q \mid N$이다. 그러나 $N \bmod q = 1$이므로 모순이다. ■

Notes on Multiplicative Groups and Order: Fermat's Theorem on Primes and Wilson's Theorem

Remarks

• For a prime $p$, if information about $p - 1$ is given, consider the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p - 1$.
• The multiplicative group of a finite field is cyclic.
• For a cyclic multiplicative group $G$, $nm \mid |G|$ is equivalent to the existence of an element $x$ such that $x^{nm} = 1$ but $x^n, x^m \neq 1$.
• Order is different from period. In general, (period) = (order) + 1.

Fermat’s Theorem on Primes

Theorem. A prime $p$ can be expressed in the form $p = a^2 + b^2$ for two integers $a, b$ if and only if $p \equiv 1 \pmod{4}$.

Proof.

(⇒) Trivial.

(⇐) Let $G = (\mathbb{Z}/p\mathbb{Z})^\times$. By the condition, $4 \mid |G|$. Therefore, there exists an element $n$ such that $n^4 = 1$ but $n^2 \neq 1$. That is, $n^2 = -1$. Hence, $p \mid n^2 + 1$. Now, considering in $\mathbb{Z}[i]$, we have $p \mid (n + i)(n - i)$. If $p$ were irreducible in $\mathbb{Z}[i]$, then $p \mid n + i$ or $p \mid n - i$ (note that the fact that $\mathbb{Z}[i]$ is UFD is used here) but both are impossible. Therefore, $p$ is not irreducible, and by conjugacy,

■

Wilson’s Theorem

Theorem. $p$ is prime if and only if $(p - 1)! \equiv -1 \pmod{p}$.

Proof.

(⇒) Let $G = (\mathbb{Z}/p\mathbb{Z})^\times$. The product of all elements of $G$ is $(p - 1)!$. Except for $\pm 1$, which are the roots of $x^2 = 1$, all other elements of $G$ do not have themselves as their inverse. Therefore, $(p - 1)! \equiv -1$.

(⇐) Let $N = (p - 1)! + 1$. By the condition, $p \mid N$. If $p$ were not prime, then for some prime $q < p$, we would have $q \mid N$. However, $N \equiv 1 \pmod{q}$, which is a contradiction. ■

베타 함수를 통한 페아노 산술에서의 괴델 수 정의

요약. 1차 페아노 산술은 술어에 대한 양화를 허용하지 않기 때문에 덧셈과 곱셈 공리를 별도로 요구한다. 그러나 지수나 계승 등의 추가적인 연산은 — 튜플을 페아노 산술에서 정의할 수 있는 한 — 별도의 공리 없이 정의 가능하다. 그리고 튜플은 베타 암호화를 통해 페아노 산술에서 정의 가능하기 때문에, 페아노 산술은 지수, 계승, 소인수분해, 나아가 괴델 수까지 형식화할 수 있다.

1. 서론

정의. 페아노 산술(Peano arithmetics, PA)은 $(0, S, +, \cdot)$를 부호수(signature)로 가지는 이론으로, 공리는 다음과 같다.

1. $\forall x : S(x) \neq 0$
2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
3. $\forall x : x + 0 = x$
4. $\forall x, y : x + S(y) = S(x + y)$
5. $\forall x, y : x \cdot 0 = 0$
6. $\forall x, y : x \cdot S(y) = (x \cdot y) + x$

추가로 다음의 귀납 공리꼴(axiom schema)을 가진다. 임의의 1차 논리식 $\phi(x)$에 대해,

 7. $\big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)$

추가적으로 편의를 위해 $<, -, \bmod$를 다음과 같이 정의한다.

역사적으로 데데킨트가 처음 제시한 페아노 산술은 2차 논리 이론이었기 때문에 귀납 공리꼴 대신 귀납 공리가 있었다. 또한 3번부터 7번 공리가 없었다.

정의. 2차 논리 페아노 산술은 $(0, S)$를 부호수(signature)로 가지는 이론으로, 공리는 다음과 같다.

1. $\forall x : S(x) \neq 0$
2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
3. $\forall \phi \bigg[ \big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)\bigg]$

나머지 공리가 불필요한 이유는, 2차 논리는 술어에 대한 양화를 허용하기 때문에 2차 논리식만으로 덧셈과 곱셈을 정의할 수 있기 때문이다. 예를 들어 $w = u + v$는 다음 논리식과 동치이다.

그러나 2차 논리는 수많은 수학적 · 철학적 허점을 가지는 것으로 드러났기 때문에 서두에서 소개한 1차 논리 페아노 산술이 표준으로 선택되었다. 이 선택의 함의는 첫째로 귀납 공리가 귀납 공리꼴이 된다는 것이고, 둘째는 덧셈과 곱셈을 별도의 공리를 통해 정의해야 한다는 것이다.

그런데 이런 의문이 남는다. 덧셈과 곱셈 말고 다른 연산은 따로 정의할 필요가 없는 것일까? 예를 들어 지수, 소인수분해, 계승과 같은 연산은 별도의 공리 없이 정의 가능할까? 나아가, 임의의 논리식을 자연수에 대응시키는 괴델 수 기법은 페아노 산술만으로 정의 가능할까?

2. 튜플

이 의문에 답하는 혜안은, 튜플을 페아노 산술에서 정의할 수 있다면 기타 수많은 연산이 정의 가능해진다는 사실이다. 여기서 튜플이란 $(1, 4, 2)$와 같은 유한한 자연수의 나열을 말한다.

일례로 다음과 같은 술어와 함수들이 정의되어 있다고 가정하자.

• $\mathrm{Tup}(\tau):$ $\tau$가 튜플이다.
• $\mathrm{At}(\tau, i):$ $\tau$가 튜플일 때, $\tau$의 $i$번째 자연수를 반환한다.
• $\mathrm{Len}(\tau):$ $\tau$의 길이를 반환한다.

편의를 위해 $\mathrm{At}(\tau, i)$를 $\tau[i]$로 쓰도록 하자. 예를 들어 $\tau = (1, 4, 2)$라면 다음이 성립한다. (인덱스는 0부터 시작하는 것으로 생각한다)

튜플을 사용하면 다음과 같이 $z = x^y$를 정의할 수 있다.

3. 베타 암호화

그렇다면 튜플을 덧셈과 곱셈, 그리고 1차 논리식만으로 정의할 수 있을까? 이에 대한 답은 “가능하다”이다. 아니나다를까역시나적시나 이 결과를 처음 증명한 사람은 괴델이다. 먼저 다음의 정리를 상기하자.

중국인의 나머지 정리. $(n_1, \dots, n_k)$가 켤레서로소(pairwise coprime)라고 하자. $0 \leq r_i < n_i$인 임의의 $(r_1, \dots, r_k)$에 대해 다음을 만족하는 수 $x$가 언제나 존재한다.

\[x \bmod n_i = r_i\]

괴델의 아이디어는 중국인의 나머지 정리에서 $x$에 해당하는 수를 튜플 $(r_1, \dots, r_k)$의 코드로 생각하는 것이다. 그런데 여기에는 문제가 있다. $x$로부터 $(r_1, \dots, r_k)$를 복호화하기 위해서는 $(n_1, \dots, n_k)$가 주어져야 하는데, 이는 또다시 튜플을 요구하기 때문이다.

이 문제를 해결하기 위해 괴델은 다음의 보조정리를 꺼내든다.

보조정리. $n!+ 1, 2n! + 1, \dots, n \cdot n! + 1$은 켤레서로소이다.

증명. $1 \leq a < b \leq n$에 대해 $u = an! + 1, v = bn! + 1$이라고 하자. 유클리드 호제법에 의해,

이다. $(b - a)n!$의 모든 약수의 집합은 $\lbrace 1, 2, \dots, n\rbrace $이다. 그런데 이중 어느 원소도 $an! + 1$의 약수가 아니므로 $\mathrm{gcd}(an! + 1, (b - a)n!) = \mathrm{gcd}(u, v) = 1$이다. □

이제 우리는 튜플을 순서쌍으로서 정의할 수 있다.

정의. 튜플 $(r_1, \dots, r_k)$를 다음과 같이 순서쌍 $\langle a, b \rangle$로 표현한다.

• $b = n! \quad \text{where} \quad n = \max(r_1, \dots, r_k, k)$
• $a \bmod (kb + 1) = r_k$

단, $a$는 2번 조건을 만족하는 자연수 중 가장 작은 자연수로 선택한다.

한편 튜플은 칸토어 대응을 통해 자연수로 표현이 가능하다.

정의.

\[\langle a, b \rangle = \frac{(a + b)(a + b + 1)}{2} + b\]

이로써 우리는 튜플 $\tau$를 자연수 $n$으로 암호화(coding)할 수 있다. 그리고 역으로 $n$이 주어지면 덧셈, 곱셈, 그리고 나머지 연산만을 사용하여 $\tau$를 복호화해낼 수 있다. 그리고 나머지 연산은 덧셈, 곱셈, 그리고 1차 논리로부터 쉽게 정의가 가능하므로, 목표가 달성되었다.

역사적으로 괴델이 증명한 정리는 다음과 같다.

$\beta$-함수 보조정리. 임의의 자연수열 $(n_1, \dots, n_k)$에 대해, 어떤 자연수 $a, b$가 존재하여 $1 \leq i \leq k$에 대해 $\beta(a, b, i) = n_i$이다. 여기서 $\beta$는 다음과 같이 정의된 함수이다.

\[\beta(x, y, i) = x \bmod (iy + 1)\]

이런 이유로 지금까지의 과정을 베타 암호화(Beta coding)라고 부른다. 괴델은 베타 암호화를 이용하여 지수 연산과 소인수분해를 PA에서 성공적으로 정의했으며, 이로부터 괴델 수와 비롯된 여러 술어를 PA에서 형식화할 수 있었다. 제목에서 드러나다시피 원래 이 글의 목표는 이 과정을 모두 개괄하는 것이었으나 때늦게 찾아온 필자의 귀찮음 이슈와, 글을 여기까지 읽은 독자라면 이후 내용은 어렵지 않게 유추 가능하리라는 생각으로 이만 줄인다.

Defining Gödel Numbers in Peano Arithmetic via the Beta Function

Summary. First-order Peano arithmetic does not permit quantification over predicates, hence it requires separate axioms to define addition and multiplication. However, further operations such as exponentiation and factorial are definable without separate axioms, provided that tuples can be defined in Peano arithmetic. And since tuples are definable in Peano arithmetic through beta encoding, Peano arithmetic can formalise exponentiation, factorial, prime factorisation, and ultimately Gödel numbering.

1. Introduction

Definition. Peano arithmetic (PA) is a theory with signature $(0, S, +, \cdot)$, where the axioms are as follows:

1. $\forall x : S(x) \neq 0$
2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
3. $\forall x : x + 0 = x$
4. $\forall x, y : x + S(y) = S(x + y)$
5. $\forall x, y : x \cdot 0 = 0$
6. $\forall x, y : x \cdot S(y) = (x \cdot y) + x$

Additionally, it has the following induction axiom schema. For any first-order formula $\phi(x)$:

 7. $\big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)$

For convenience, we define $<, -, \bmod$ as follows:

Historically, the Peano arithmetic first presented by Dedekind was a second-order logic theory, hence it had an induction axiom rather than induction axiom schema.

Definition. Second-order Peano arithmetic is a theory with signature $(0, S)$, where the axioms are as follows:

1. $\forall x : S(x) \neq 0$
2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
3. $\forall \phi \bigg[ \big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)\bigg]$

Note that second-order formalisation omits axioms 3-6. The reason they are unnecessary is that second-order logic permits quantification over predicates, enabling addition and multiplication to be defined using second-order formulae alone. For instance, $w = u + v$ is equivalent to the following formula:

However, since second-order logic was found to have numerous mathematical and philosophical shortcomings, the first-order Peano arithmetic introduced at the beginning became the standard norm. The implications of the transition from second to first are, firstly, that the induction axiom becomes an axiom schema, and secondly, that addition and multiplication must be defined through separate axioms.

This raises the question: are there no other operations besides addition and multiplication that need separate definition? For example, can operations such as exponentiation, prime factorisation, and factorial be defined without additional axioms? Furthermore, can Gödel numbering, which maps formulae to natural numbers one-to-one, be defined using Peano arithmetic alone?

2. Tuples

The insight that answers this question is that if tuples can be defined in Peano arithmetic, then numerous other operations become definable. Here, a tuple refers to a finite sequence of natural numbers such as $(1, 4, 2)$.

For instance, suppose the following predicates and functions are defined:

• $\mathrm{Tup}(\tau):$ $\tau$ is a tuple.
• $\mathrm{At}(\tau, i):$ When $\tau$ is a tuple, returns the $i$-th index of $\tau$.
• $\mathrm{Len}(\tau):$ Returns the length of $\tau$.

For convenience, let us write $\mathrm{At}(\tau, i)$ as $\tau[i]$. For example, if $\tau = (1, 4, 2)$, then the following holds (assuming the index starts from 0):

Using tuples, we can define $z = x^y$ as follows:

3. Beta Encoding

Can tuples be defined using only addition, multiplication, and first-order formulae? The answer is yes. As might be expected, it was Gödel who first proved this result. Let us first recall the following theorem:

Chinese Remainder Theorem. Let $(n_1, \dots, n_k)$ be pairwise coprime. For any $(r_1, \dots, r_k)$ with $0 \leq r_i < n_i$, there always exists a number $x$ satisfying:

\[x \bmod n_i = r_i\]

Gödel’s idea was to think of the number $x$ from the Chinese Remainder Theorem as a code for the tuple $(r_1, \dots, r_k)$. However, there is a problem here. To decode $(r_1, \dots, r_k)$ from $x$, we need $(n_1, \dots, n_k)$ to be given, which itself is a tuple.

To solve this problem, Gödel produced the following lemma:

Lemma. $n!+ 1, 2n! + 1, \dots, n \cdot n! + 1$ are pairwise coprime.

Proof. For $1 \leq a < b \leq n$, let $u = an! + 1, v = bn! + 1$. By the Euclidean algorithm,

The set of all divisors of $(b - a)n!$ is $\lbrace 1, 2, \dots, n\rbrace $. Since none of these elements divides $an! + 1$, we have $\mathrm{gcd}(an! + 1, (b - a)n!) = \mathrm{gcd}(u, v) = 1$. □

With this lemma, instead of individually specifying $n$ pairwise coprime numbers, we can simply let $n$ be an arbitrary number, and from it, $n$ pairwise coprime numbers $n! + 1, 2n! + 1, \dots, n \cdot n! + 1$ can be chosen canonically. We can now define tuples as an ordered pair.

Definition. We represent the tuple $(r_1, \dots, r_k)$ as an ordered pair $\langle a, b \rangle$ as follows:

• $b = n! \quad \text{where} \quad n = \max(r_1, \dots, r_k, k)$
• $a \bmod (kb + 1) = r_k$

where $a$ is chosen to be the smallest natural number satisfying the second condition.

Meanwhile, tuples can be represented as natural numbers through a well-defined injection from $\mathbb{N}^2$ to $\mathbb{N}$. The following is an example:

Check that $b$ is injective. Hence we can define as follows:

Definition.

\[\langle a, b \rangle = \frac{(a + b)(a + b + 1)}{2} + b\]

This establishes that we can encode a tuple $\tau$ as a natural number $n$. Conversely, given $n$, we can decode $\tau$ using only addition, multiplication, and the modulo operation. Since the modulo operation is easily definable from addition, multiplication, and first-order logic, our goal is achieved.

Historically, Gödel’s theorem was as follows:

$\beta$-function Lemma. For any sequence of natural numbers $(n_1, \dots, n_k)$, there exist natural numbers $a, b$ such that $\beta(a, b, i) = n_i$ for $1 \leq i \leq k$, where $\beta$ is the function defined as follows:

\[\beta(x, y, i) = x \bmod (iy + 1)\]

For this reason, the entire process is called beta encoding. Gödel used beta encoding to successfully define exponentiation and prime factorisation in PA, enabling the formalisation of Gödel numbers and various related predicates in PA. As indicated by the title, the original goal of this article was to provide an overview of this entire process. However, due to the author’s tardily arising laziness and the belief that readers who have come this far can easily infer the subsequent content, let me finish off here.

워시의 정리

이전 글에서 이어지는 내용이다.

5. 초자연수의 비표준적 특징

지금까지 우리가 살펴본 초자연수는 $[0], [1], [2], \dots$와 같이 표준 자연수와 상응하는 것들이었다. 이제 표준 자연수와는 괴리가 있는 초자연수들을 살펴 보자.

다음의 초자연수 $\mathfrak{n}$을 보자.

초자연수의 정의가 동치류이기 때문에 등호가 아닌 포함 관계로 표현함에 유의하라. 초자연수에서 부등호의 정의를 상기하면, 자연수 $n$에 대해 $[n] < \mathfrak{n}$임을 알 수 있다. 즉, $\mathfrak{n}$은 모든 자연수보다 큰 초자연수이다. 따라서 초자연수에서는 다음이 성립한다.

위 명제는 자연수에서는 성립하지 않는다.

이번에는 다음의 초자연수 $\mathfrak{m}$을 보자.

표준 자연수 $n$에 대해 $\mathfrak{m}$은 $[n]$으로 나누어떨어진다. 즉, $\mathfrak{m}$은 모든 자연수를 약수로 가진다. 따라서 초자연수에서는 다음이 성립한다.

위 명제 또한 자연수에서는 성립하지 않는다.

그런데 이상한 점이 있다. 저번 글의 서론에서 필자는 자연수와 초자연수가 논리적으로 구분 불가능하다고 했다. 그러나 $\phi_1$과 $\phi_2$는 $\mathbb{N}^*$에서는 참이지만 $\mathbb{N}$에서는 거짓이므로, 둘은 논리적으로 구분 가능한 것으로 보인다. 필자가 거짓말을 한 것일까?

그렇지 않다. 이 표면적인 역설을 해결하는 실마리는, $\phi_1$과 $\phi_2$가 1차 논리로 표현 불가능한 문장이라는 사실이다. 콤팩트성 정리에 의해 “…가 유한하다”는 1차 논리로 표현 불가능하기 때문이다.

$\mathbb{N}^*$과 $\mathbb{N}$이 논리적으로 구분 불가능하다는 말의 엄밀한 의미는 다음과 같다.

정의. 언어 $\mathcal{L}$의 모형 $\mathcal{M}_1$과 $\mathcal{M}_2$가 초등적으로 동등(elementarily equivalent)하다는 것은 임의의 (1차 논리) 문장 $\phi$에 대해

\[\mathcal{M_1} \vDash \phi \iff \mathcal{M}_2 \vDash \phi\]

가 성립하는 것이다.

정리. $\mathbb{N}$과 $\mathbb{N}^*$은 초등적으로 동등하다.

위 정리는 워시의 정리의 특수한 결과이다. 워시의 정리를 소개하기 앞서, 일반화된 초곱의 개념을 먼저 살펴보자.

6. 초곱

집합 $I$와, $I$ 위의 자유 초필터 $\mathcal{U}$가 주어졌다고 하자. 또한, 언어 $\mathcal{L}$의 모형 $\lbrace \mathcal{M}_i \rbrace_{i \in I}$가 주어졌다고 하자. 이때, 초곱(ultraproduct) $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$를 다음과 같이 정의한다.

초곱의 원소

$\mathcal{M}^*$의 원소는 $\lbrace (a_i)_{i\in I} : a_i \in \mathcal{M}_i \rbrace$가 $\sim$에 대해 이루는 동치류이다. 여기서 $\sim$은 다음과 같이 정의된다.

\[(a_i)_{i\in I} \sim (b_i)_{i \in I} \iff \lbrace i \in I : a_i = b_i \rbrace \in \mathcal{U}\]

초곱 위의 연산

$f(x)$가 $\mathcal{L}$의 함수라고 하자. $\mathcal{M}^*$의 원소 $\mathfrak{a} = [(a_i)_{i\in I}]$에 대해 다음과 같이 정의한다.

\[f(\mathfrak{a}) = [(f(a_i))_{i \in I}]\]

위 정의는 자연스러운 방식으로 $n$항 함수로 일반화된다.

초곱 위의 술어

$P(x, y)$가 $\mathcal{L}$의 술어라고 하자. $\mathcal{M}^*$의 두 원소 $\mathfrak{a} = [(a_i)_{i\in I}]$와 $\mathfrak{b} = [(b_i)_{i\in I}]$에 대해 다음과 같이 정의한다.

\[\mathcal{M}^* \vDash P(\mathfrak{a}, \mathfrak{b}) \iff \lbrace i \in I : \mathcal{M}_i \vDash P(a_i, b_i) \rbrace \in \mathcal{U}\]

위 정의는 자연스러운 방식으로 $n$항 술어로 일반화된다.

초곱 위의 연산과 술어를 정의할 때, 연산과 술어의 결과가 동치류에서 어떤 원소를 대표자로 선택하든 상관없이 같음을 보여야 한다. 이것은 $\mathcal{U}$의 교집합 속성으로부터 어렵지 않게 얻어진다.

연습문제. 주 초필터로 취한 초곱은 원소가 유한함을 보이시오. (이것은 우리가 초자연수를 정의할 때 프레셰 필터와 같은 자유 초필터를 사용해야 하는 이유이다)

이로써 우리는 초자연수를, $I, \mathcal{U}, \mathcal{L}, \mathcal{M}_i$가 각각 다음과 같을 때 도출되는 초곱으로 재정의할 수 있다.

• $I = \mathbb{N}$
• $\mathcal{U} =$ 프레셰 초필터
• $\mathcal{L} = (0, S, <)$
• $\mathcal{M}_i = \mathbb{N}$

비슷한 방식으로 초실수_hyperreals를 정의할 수 있다.

• $I = \mathbb{N}$
• $\mathcal{U} =$ 프레셰 초필터
• $\mathcal{L} = (0, 1, +, ⋅, <)$
• $\mathcal{M}_i = \mathbb{R}$

7. 워시의 정리

워시_Łoś의 정리. 초곱 $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$가 주어졌을 때, 임의의 $\mathcal{L}$-문장 $\phi$에 대해 다음이 성립한다.

\[\mathcal{M}^* \vDash \phi \iff \lbrace i \in I : \mathcal{M}_i \vDash \phi \rbrace \in \mathcal{U}\]

Proof. $\phi$에 대한 구조적 귀납법으로 증명한다.

1. $\phi$가 원자 명제이다

“초곱 위의 술어” 정의에 의해 자명하게 성립한다.

2. $\phi := \psi \land \theta$

$(*)$는 귀납 가정에 의해 성립하고, $(**)$는 $\mathcal{U}$의 교집합 닫힘 속성으로 성립한다.

3. $\phi := \lnot \psi$

2와 비슷한 방법으로 하면 된다. 단, 귀납 가정과 $\mathcal{U}$의 초필터 속성($A \in \mathcal{U} \lor A^c \in \mathcal{U}$)를 사용한다.

4. $\phi := \exists x\; \psi$

2와 비슷한 방법으로 하면 된다. 단, 귀납 가정만 사용해도 충분하다.

모든 명제는 1, 2, 3, 4로 구성할 수 있으므로 귀납법에 의해 정리가 증명되었다. ■

따름정리. $\mathbb{N}$과 $\mathbb{N}^*$은 초등적으로 동등하다.

Proof. 워시의 정리에 의해 $\mathbb{N}^* \vDash \phi$일 필요충분조건은 $\lbrace i \in \mathbb{N} : \mathbb{N}^\ast_i \vDash \phi \rbrace \in \mathcal{U}$인 것이다. 그런데 $\mathbb{N}^*_i = \mathbb{N}$이므로, 필요충분조건은 $\mathbb{N} \vDash \phi$로 환원된다. ■

Łoś's Theorem

This post continues from the previous post.

5. Nonstandard Characteristics of Hypernatural Numbers

The hypernatural numbers we have examined so far — $[0], [1], [2], \dots$ — correspond to standard natural numbers. We shall now examine some bizarre hypernatural numbers.

Consider the following hypernatural number $\mathfrak{n}$:

Recalling how binary relation is defined for hypernaturals, for any natural number $n$, we have $[n] < \mathfrak{n}$. That is, $\mathfrak{n}$ is a hypernatural number greater than all natural numbers. That is, the following holds for hypernaturals:

This sentence does not hold in the natural numbers.

Now consider the following hypernatural number $\mathfrak{m}$:

For any standard natural number $n$, $\mathfrak{m}$ is divisible by $[n]$. That is, $\mathfrak{m}$ has every natural number as a divisor. Therefore, the following holds for hypernaturals:

Again, this sentence does not hold in the natural numbers.

This may seem to contradict the promise delivered in the previous essay. There, I stated that the natural numbers and hypernatural numbers are logically indistinguishable. Yet $\phi_1$ and $\phi_2$, both of which seem to be a cogent logical formula, are true in $\mathbb{N}^*$ but false in $\mathbb{N}$. Have I been misleading?

Of course not. The key to this apparent paradox lies in the fact that $\phi_1$ and $\phi_2$ cannot be expressed in first-order logic. By the compactness theorem, “… is finite” is inexpressible in first-order logic.

For a more precise statement, let us define the following:

Definition. Two $\mathcal{L}$-models $\mathcal{M}_1$ and $\mathcal{M}_2$ of a language $\mathcal{L}$ are elementarily equivalent if for any $\mathcal{L}$-sentence $\phi$,

\[\mathcal{M_1} \vDash \phi \iff \mathcal{M}_2 \vDash \phi\]

Theorem. $\mathbb{N}$ and $\mathbb{N}^*$ are elementarily equivalent.

This theorem is a special case of Łoś’s theorem. But before we state Łoś’s theorem, let us first rigorously define ultraproducts.

6. Ultraproducts

Let a set $I$ and a free ultrafilter $\mathcal{U}$ on $I$ be given. Furthermore, let models $\lbrace \mathcal{M}_i \rbrace_{i \in I}$ of a language $\mathcal{L}$ be given. We define the ultraproduct $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$ as follows:

Elements of the Ultraproduct

The elements of $\mathcal{M}^*$ are equivalence classes of $\lbrace (a_i)_{i\in I} : a_i \in \mathcal{M}_i \rbrace$ under the relation $\sim$, where $\sim$ is defined as:

\[(a_i)_{i\in I} \sim (b_i)_{i \in I} \iff \lbrace i \in I : a_i = b_i \rbrace \in \mathcal{U}\]

Operations on the Ultraproduct

Let $f(x)$ be a function in $\mathcal{L}$. For an element $\mathfrak{a} = [(a_i)_{i\in I}]$ of $\mathcal{M}^*$, we define:

\[f(\mathfrak{a}) = [(f(a_i))_{i \in I}]\]

This definition generalises naturally to $n$-ary functions.

Relations on the Ultraproduct

Let $P(x, y)$ be a relation in $\mathcal{L}$. For two elements $\mathfrak{a} = [(a_i)_{i\in I}]$ and $\mathfrak{b} = [(b_i)_{i\in I}]$ of $\mathcal{M}^*$, we define:

\[\mathcal{M}^* \vDash P(\mathfrak{a}, \mathfrak{b}) \iff \lbrace i \in I : \mathcal{M}_i \vDash P(a_i, b_i) \rbrace \in \mathcal{U}\]

This definition generalises naturally to $n$-ary predicates.

When defining operations and relation on the ultraproduct, one needs to show that the definition is irrelevant to which element is chosen as a representative for each equivalence class. This follows readily from the intersection property of $\mathcal{U}$, so we leave it as an exercise.

We can now redefine the hypernatural numbers as the ultraproduct arising when $I, \mathcal{U}, \mathcal{L}, \mathcal{M}_i$ are respectively:

• $I = \mathbb{N}$
• $\mathcal{U} =$ Fréchet ultrafilter
• $\mathcal{L} = (0, S, <)$
• $\mathcal{M}_i = \mathbb{N}$

Similarly, we can define the hyperreal numbers:

• $I = \mathbb{N}$
• $\mathcal{U} =$ Fréchet ultrafilter
• $\mathcal{L} = (0, 1, +, ⋅, <)$
• $\mathcal{M}_i = \mathbb{R}$

7. Łoś’s Theorem

Łoś’s Theorem. Given an ultraproduct $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$, for any $\mathcal{L}$-sentence $\phi$, the following holds:

\[\mathcal{M}^* \vDash \phi \iff \lbrace i \in I : \mathcal{M}_i \vDash \phi \rbrace \in \mathcal{U}\]

Proof. We prove this by structural induction on $\phi$.

1. $\phi$ is an atomic proposition

This follows trivially from the definition of predicates on ultraproducts.

2. $\phi := \psi \land \theta$

$(*)$ holds by the inductive hypothesis, and $(**)$ holds by the intersection closure property of $\mathcal{U}$.

3. $\phi := \lnot \psi$

This can be proved by a similar method to case 2, using the inductive hypothesis and the ultrafilter property of $\mathcal{U}$ ($A \in \mathcal{U} \lor A^c \in \mathcal{U}$).

4. $\phi := \exists x\; \psi$

This can be proved by a similar method to case 2, though the inductive hypothesis alone suffices.

Since every proposition can be constructed from cases 1, 2, 3, and 4, the theorem is proved by induction. ■

Corollary. $\mathbb{N}$ and $\mathbb{N}^*$ are elementarily equivalent.

Proof. By Łoś’s theorem, the necessary and sufficient condition for $\mathbb{N}^* \vDash \phi$ is that $\lbrace i \in \mathbb{N} : \mathbb{N}^\ast_i \vDash \phi \rbrace \in \mathcal{U}$. However, since $\mathbb{N}^*_i = \mathbb{N}$, the necessary and sufficient condition reduces to $\mathbb{N} \vDash \phi$. ■

프레셰 필터와 비표준 자연수

뢰벤하임-스콜렘 정리에 따르면 표준 산술 모형과 초등적으로 동등_{elementarily equivalent}하지만 구조적으로 상이_{nonisomorphic}한 모형이 존재한다. 달리 말해, 자연수가 만족하는 모든 1차 논리 명제를 만족하지만 자연수가 아닌 수 체계가 존재한다.

이 글에서는 초곱_ultraproduct을 이용하여 대표적인 산술의 비표준적 모형인 초자연수_{hypernaturals}를 구성하고, 이것이 표준 산술 모형과 초등적으로 동등함을 보증하는 워시의 정리_{Łoś’s theorem}를 증명한다.

1. 개괄

콤팩트성 정리에 의해 우리는 1차 논리가 유한과 무한을 구별하지 못함을 안다. 따라서 무한을 적절히 사용함으로써 자연수와 1차 논리적으로 구분 불가능한 모델을 정의할 수 있으리라 기대해봄직하다.

이에 따라 다음과 같이 초자연수 $[0], [1], [2], \dots$를 정의하자.

그런데 생각해 보면 모든 항이 0으로 차 있어야 $[0]$으로 간주하는 것은 지나치게 엄격하다. 예를 들어 처음 두 개의 항만 1이고 나머지 항은 모두 0인 튜플 $(1, 1, 0, 0, 0, \dots)$ 또한 $[0]$으로 보는 것이 자연스럽다. 따라서 유한 개의 항을 제외한 모든 항이 $n$이라면 그 튜플 또한 $[n]$으로 간주하도록 하자. 즉,

하지만 이제 다음의 문제가 생긴다. 다음 튜플은 $[0]$으로 간주해야 하는가, $[1]$로 간주해야 하는가?

이 모호함을 제거하기 위해 우리는 짝수 집합과 홀수 집합 중 하나를 임의로 채택할 것이다. 만약 짝수 집합을 채택했다면 위 튜플은 $[0]$이 되고(인덱스는 0부터 시작하는 것으로 전제한다) 홀수 집합을 채택했다면 $[1]$이 될 것이다.

하지만 이 채택의 과정에는 주의가 필요하다. 만약 6의 배수의 집합이 채택되었다면, 3의 배수의 집합 또한 채택되어야 논리적으로 일관된다. 후자를 만족하는 튜플은 자명하게 전자를 만족하기 때문이다. 그리고 3의 배수의 집합이 채택되었으므로, 3의 배수가 아닌 수의 집합은 기각되어야 한다. 자연수의 모든 부분집합에 대해 이같은 채택과 기각의 과정을 거친 결과물은 초필터_ultrafilter라고 불리는 구조와 상응될 것이다. 적절한 초필터가 주어지면 그것을 토대로 임의의 튜플을 초자연수에 대응시킬 수 있으며, 이 전체적인 과정을 초곱_ultraproduct이라고 부른다.

2. 초필터의 정의

정의. $X$가 집합이라고 하자. $X$의 부분집합들로 이루어진 집합 $\mathcal{F}$가 다음을 만족할 때, $X$의 필터라고 부른다.

1. $X \in \mathcal{F}$
2. $\varnothing \not\in \mathcal{F}$
3. 상위집합 닫힘: $A \in \mathcal{F}, A \subset B \implies B \in \mathcal{F}$
4. 유한 교집합 닫힘: $A, B \in \mathcal{F} \implies A \cap B \in \mathcal{F}$

직관적으로 필터는 “큰 집합들의 모임”이다. 이 관점에서 보면 1번과 2번 공리는 전체집합은 크고 공집합은 작다는 자명한 원리를 진술한다. 3번 공리는 큰 집합을 포함하는 집합은 크다는 원리를, 4번 공리는 큰 집합끼리 유한 번 교집합을 해도 여전히 크다는 원리를 진술한다.

여담으로 필터는 초곱뿐 아니라 퍼지 논리의 모형을 고전 논리의 모형으로 변환하는 데도 쓰인다. 이때 필터는 “큰 집합들의 모임”이 아닌 “참인 문장들의 모임”이 된다. 그리고 퍼지 논리에서 고전 논리로의 변환은 코헨의 강제법을 이해하는 한 가지 방식이기도 하다.

하세 다이어그램_{Hasse diagram}을 통해 필터를 더 직관적으로 이해할 수 있다. 색칠된 영역은 $X = \lbrace 0, 1, 2 \rbrace$의 필터이다. 하세 다이어그램을 $\varnothing$에서 $X$로 가는 물줄기의 흐름으로 이해하면, 특정 지점에 잉크를 떨어뜨렸을 때 그 잉크가 퍼져 나가는 영역은 필터를 이룬다.

2번 공리와 4번 공리에 의해, $A \in \mathcal{F}$라면 $A^c := X \setminus A \notin \mathcal{F}$이다. 이 사실을 강화하여, $X$의 모든 부분집합에 대해 그 집합 또는 여집합이 필터에 있을 것을 요구하면 초필터의 정의를 얻는다.

정의. $X$의 필터 $\mathcal{F}$가 다음을 만족할 때 $\mathcal{F}$는 초필터이다.

\[\forall A \in \mathcal{P}(X) : A \in \mathcal{F} \lor A^c \in \mathcal{F}\]

앞선 그림의 필터는 초필터이다. 초필터는 하세 다이어그램의 정확히 절반을 차지한다는 사실에 주목하라.

3. 무한집합에서의 초필터

최소 원소를 가지는 필터를 주 필터_{principal filter}라고 하며, 주 필터가 아닌 필터를 자유 필터_{free filter}라고 한다. 지금까지 우리가 본 모든 필터는 주 필터로, “특정 지점에 떨어뜨린 잉크가 퍼져 나가는 영역”의 이미지와 완전히 부합한다.

연습문제. 모든 주 초필터는 홑원소 집합을 원소로 가짐을 보이시오.

주 필터와 달리 자유 필터는 직관적으로 포착하기 힘들다. 다음의 정리 때문이다.

정리. 유한집합 위의 필터는 모두 주 필터이다.

Proof. $A_0 \in \mathcal{F}$가 최소 원소가 아니라고 하자. 그러면 어떤 $B \in \mathcal{F}$가 존재하여 $A_1 = A_0 \cap B \subsetneq A$이다. 즉, $|A_1| < |A_0 |$이다. $A_1$이 최소 원소라면 증명이 끝나고, 아니라면 똑같은 과정을 반복한다. 주어진 집합의 크기가 유한하므로 이 과정은 계속 반복될 수 없으며, 최소 원소에 종착하게 된다. ■

위 정리는 이렇게 이해할 수도 있다. 자유 필터는 그 내부에 무한히 이어지지만 (따라서 유한 교집합만으로 최소 원소에 도달할 수 없다) 공집합에 도달하지는 않는 부분집합의 체인을 가지는 필터이다. 이에 따라 무한집합 위의 필터만이 자유 필터가 될 수 있다.

그 실례를 살펴보자.

정의. $X$가 무한집합이라고 하자. $A \subset X$가 여유한_cofinite하다는 것은 $X \setminus A$가 유한집합인 것이다.

정리. $\mathbb{N}$의 모든 여유한 부분집합의 모임을 $\mathcal{F}$라고 하자. $\mathcal{F}$는 자유 필터이다.

증명은 연습문제로 남긴다. 위 정리의 $\mathcal{F}$를 프레셰 필터_{Fréchet filter}라고 부른다. 일례로 10보다 큰 수들의 집합 $\lbrace 11, 12, 13, 14, \dots \rbrace$은 $\mathcal{F}$의 원소이지만, 짝수의 집합은 $\mathcal{F}$의 원소가 아니다.

프레셰 필터는 초필터가 아니다. 하지만 다음 정리에 의해 초필터로 확장할 수 있다.

정리. 모든 필터는 초필터로 확장될 수 있다.

Proof. $X$의 모든 필터들의 모임 $\Omega$에 포함 관계로 정의되는 순서를 주자. 이 순서 하에서 체인을 이루는 필터들의 합집합은 필터임을 어렵지 않게 보일 수 있다. 따라서 초른의 보조정리에 의해 $\Omega$는 극대 원소 $\mathcal{U}$를 가진다. 만약 $\mathcal{U}$가 초필터가 아니라면, 어떤 $A_0 \subset X$가 존재하여 $A_0, A_0^c \notin U$이다. 이제 다음과 같이 $\mathcal{V}$를 정의한다.

$\mathcal{V}$는 필터임을 확인할 수 있다. 이것은 $\mathcal{U}$의 극대성에 위배된다. 따라서 $\mathcal{U}$는 초필터이다. ■

따라서 자연수 집합은 프레셰 필터로부터 확장되는 자유 초필터를 가진다. 이 필터를 프레셰 초필터라고 부르자.

4. 초자연수

지금까지의 논의를 정리하자면, 프레셰 초필터를 비롯한 자유 초필터는 다음의 성질을 가진다.

1. 모든 여유한 집합을 원소로 가진다.
2. 유한집합은 원소로 가지지 않는다.
3. $A \subset \mathbb{N}$일 때 $A$가 필터의 원소이거나 $A^c$가 필터의 원소이다.

위 세 성질 덕분에 프레셰 초필터는 서론에서 초곱의 기초적인 아이디어를 개괄했을 때 맞닥뜨렸던 모호성의 문제를 해결하는 데 안성맞춤이다. 이제 우리는 다음과 같이 초자연수를 정의할 수 있다.

$\mathcal{U}$가 자유 초필터라고 하자. $\mathbb{N}^\omega$ 위에 다음의 동치 관계를 정의한다.

이것이 동치 관계임은 어렵지 않게 확인할 수 있다. 따라서 다음과 같이 동치류를 취할 수 있다.

$\mathbb{N}^*$을 초자연수라고 한다. 초자연수의 정의가 동치류인 것은 서론에서 초자연수를 $[n]$으로 적은 이유이다. 이제 남은 것은 초자연수의 연산과 술어 관계를 정의하는 것이다.

초자연수의 덧셈은 다음과 같이 자연스럽게 정의한다.

여기에는 한 가지 미묘한 문제가 있다. 초자연수의 정의가 동치류이기 때문에, 동치류의 어떤 원소를 택하더라도 위 덧셈의 결과에 영향을 주지 않음을 보여야 한다. 즉,

에 대해,

임을 보여야 한다. 다행히 이는 어렵지 않다.

곱셈과 역원 또한 비슷하게 정의하면 된다. 한편 $<$와 같은 이항 관계는 다음과 같이 정의한다.

이 정의는 자연스럽게 삼항, 사항 관계로 일반화할 수 있다.

이로써 우리는 초자연수를 정의했다. 다음 글에서는 초자연수의 여러 비표준적인 특징과, 그런 비표준성에도 불구하고 초자연수와 자연수를 1차 논리로 구분할 수 없음을 보이는 워시의 정리를 살펴볼 것이다.