자연수를 말하는 이론이 왜 여러 모습을 갖나요?

우리가 익숙한 표준 자연수 구조를 ℕ이라고 부르겠습니다. 영역은 보통의 자연수들이고, 0·후속 함수 S·덧셈 +·곱셈 ×·크기 비교 <가 통상적인 뜻을 갖습니다. 이 구조는 산술 언어의 수많은 일차논리 문장을 참으로 만듭니다. 그런데 ‘그 문장을 만족한다’는 것과 ‘구조가 정확히 ℕ과 동형이다’는 것은 별도 조건입니다.

놀랍게도 표준 자연수에서 참인 모든 일차논리 문장을 모아도 비표준 모형이 생깁니다. 콤팩트성 정리로 직접 따라가 보겠습니다. 자연수 구조의 실제 원소와 문장을 만족하는 다른 모형의 원소를 구별해야 합니다.

산술 언어에서 표준 ℕ이 참으로 만드는 닫힌 일차논리 문장 전체를 Th(ℕ)이라고 부릅니다. 이 집합은 모든 문장 A에 대해 A와 ¬A 중 하나를 포함하므로 의미론적으로 완전한 이론입니다. 그러나 여기에서 모든 모형이 ℕ과 동형이라는 결론은 나오지 않습니다.

아닙니다. PA는 효과적으로 열거할 수 있는 공리들과 귀납 공리 도식을 갖는 특정한 형식 이론입니다. Th(ℕ)은 표준 ℕ에서 참인 문장을 모두 모은 집합으로 훨씬 강하며, 일반적으로 효과적인 공리 열거로 제시할 수 없습니다. 이번 비표준 모형의 구성은 Th(ℕ)을 사용하면 더욱 선명해집니다.

원래 산술 언어에 없던 상수 c를 더하고 c>0, c>S(0), c>S(S(0)), … 을 모두 요구합니다. 여기서 Sⁿ(0)은 0에 후속 함수를 n번 적용하여 얻는 수를 가리키는 닫힌 항입니다. n은 바깥에서 세는 표준 자연수입니다. 모든 표준 수보다 큰 해석값을 요구하는 무한한 문장 집합을 만들었습니다.

맞습니다. 자연수 n 하나를 고르면 그 값은 자기 자신보다 크지 않습니다. c를 어떤 표준 자연수로 잡아도 c>Sⁿ(0) 조건 중 하나에 걸립니다. 그래서 전체 집합은 ℕ을 c까지 해석한 구조에서는 만족되지 않습니다.

예를 들어 c>0, c>1, c>2, c>10만 요구하면 표준 자연수 c=11로 모두 만족합니다. 일반적으로 유한한 부등식들의 최대 오른쪽 수가 N이면 c=N+1로 두면 됩니다. 표준 ℕ은 Th(ℕ)의 모든 문장을 동시에 만족하므로, Th(ℕ)과 새 부등식들의 어떤 유한 부분도 이 확장된 표준 구조에서 만족 가능합니다.

바로 그 차이가 콤팩트성을 적용할 자리입니다. 모든 유한 부분을 만족하는 모형은 찾을 수 있지만, 부분에 따라 c에 부여하는 값이 달라집니다. 그 값들을 한 고정된 표준 수로 잡아야 한다는 요구는 없습니다.

문장 집합 T*=Th(ℕ)∪{c>Sⁿ(0): n∈ℕ}의 모든 유한 부분이 만족 가능하므로 일차논리 콤팩트성 정리에 의해 T* 전체를 만족하는 모형 M이 있습니다. M에서는 c가 모든 표준 숫자 항 Sⁿ(0)보다 큽니다. 동시에 M은 원래 Th(ℕ)의 모든 문장을 만족합니다.

M의 전체 영역 안에서 산술 언어의 한 대상입니다. M의 내부에서는 자연수의 원소로 취급되지만, 바깥의 표준 ℕ에서 그 대상과 같은 표준 자연수를 찾을 수 없습니다. 이런 해석을 비표준 원소라고 부릅니다.

정확하게는 바깥의 각 표준 숫자 항보다 큽니다. M의 모든 원소보다 큰 것은 아닙니다. 예를 들어 M에서 S(c)는 c보다 큰 또 다른 원소입니다. c는 표준 ℕ의 원소로 환원되지 않지만, M 안에서는 덧셈과 후속 함수 등의 연산을 받는 일반 원소입니다.

원래 표준 ℕ의 영역을 바꿔서 같은 구조가 되었다는 뜻은 아닙니다. 우리는 산술 언어의 다른 모형 M을 얻었고, 그 안에 표준 수를 나타내는 항들과 그들로 표시할 수 없는 원소가 공존한다는 사실을 보인 것입니다.

M은 Th(ℕ)의 모든 문장을 만족합니다. 따라서 표준 자연수에서 참인 2+3=5, 덧셈과 곱셈의 기본 성질, 일차논리로 표현되는 귀납 공리의 각 사례도 M에서 참입니다. 비표준 구조가 존재한다는 것은 표준 산술의 모든 일차논리 문장이 구조를 동형까지 유일하게 결정하지 못한다는 사실을 보여 줍니다.

일차논리 귀납 공리 도식은 표준 자연수의 모든 부분집합을 한꺼번에 외부에서 양화하는 형식이 아닙니다. M이 각 일차논리 귀납 공리를 만족해도 바깥에서 바라본 비표준 원소가 존재할 수 있습니다. 일차와 이차 논리의 표현력 차이를 구별해야 합니다.

아닙니다. ∀x는 M의 전체 영역을 훑습니다. x=c를 대입하면 c>c가 거짓이므로 그 보편 문장은 참이 될 수 없습니다. 반면 우리 무한 집합은 바깥의 각 n에 대해 따로 쓴 c>Sⁿ(0)라는 문장들을 요구합니다. 외부에서 순서대로 나열한 무한 문장들과 모형 내부의 하나의 보편 문장은 전혀 다른 조건입니다.

‘모든 표준 수보다 큰 c’가 ‘모형의 모든 원소보다 큰 c’라고 바뀌어 버립니다. 두 양화 범위를 일치시켜 버리는 순간 거짓 결론을 얻게 됩니다.

Th(ℕ)은 실제로 모든 산술 일차논리 문장 A에 대해 A나 ¬A를 포함합니다. 그 뜻은 어떤 문장이 모든 Th(ℕ)-모형에서 참인지 결정되어 있다는 것입니다. 그러나 그 모형들이 서로 동형이라는 뜻은 아닙니다. 표준 ℕ도 Th(ℕ)의 모형이며, 새로 만든 M에서 c의 해석을 잊어 산술 언어만 남긴 구조도 Th(ℕ)의 모형입니다. 둘은 같은 일차논리 문장들을 만족하지만 동형은 아닙니다.

맞습니다. ‘일차논리에서 의미론적으로 귀결되면 증명된다’는 괴델의 완전성 정리, ‘이론 T가 모든 문장 또는 부정을 증명한다’는 구문적 완전성, ‘어떤 이론의 모형이 모두 동형이다’는 범주성을 구별합니다.

비표준 모형을 얻는 데에 Th(ℕ) 전체가 꼭 필요한 것은 아닙니다. 표준 ℕ에서 참인 일차논리 페아노 산술 PA의 공리들에 새 상수 c와 c>n 조건들을 더해도 모든 유한 부분을 표준 ℕ의 확장으로 만족할 수 있습니다. 콤팩트성으로 PA의 비표준 모형을 얻습니다.

PA는 효과적으로 열거 가능한 공리 체계이고, Th(ℕ)은 표준 참 전체입니다. 두 이론에서 비표준 모형이 생긴다는 사실은 같지만, 이론이 결정하는 문장의 범위와 계산 가능성은 다릅니다. 이 차이는 다음의 불완전성 정리와 이어집니다.

그렇습니다. 수학적으로 완전한 Th(ℕ)의 모든 문장은 표준 구조에서 참 또는 거짓 중 하나이지만, 참인 산술 문장을 입력마다 판정하는 일반 알고리즘이 있다는 말은 아닙니다. 15편에서는 유한 시간에 반드시 끝나는 결정 절차와, 답이 ‘예’인 경우에만 언젠가 멈출 수 있는 반결정 절차를 구별합니다.

효과적으로 공리화된 산술 이론이 모든 문장을 증명 또는 반증하도록 만들 수 있는가라는 문제입니다. 지금의 비표준 모형은 의미론적 표현의 한계를 보여 주며, 불완전성은 추가적인 효과성·일관성 가정을 중심으로 읽겠습니다.