Wk13:형식화된 이론들.pdf

(1)

기호논리학

(2)

연역적 이론

I 어떤 주제에 관한 문장들의 집합은 다음 조건을 만족하면 연역적 이론(deductive theory)의 주장들 혹은 입론들을 구성한다: 그 집합에 포함된 입론들의 모든 귀결은 만일 그것이 관련된 주제에 관한 것이라면 또한 입론이다. (여기서 입론이란 주어진 연역적 이론의 공리들과 정리들을 합쳐 부르는 이름이다.) I 이 정의를 형식적으로 가다듬으면 다음과 같이 된다: T 가 (동일성과 항을 포함한) 일차 술어논리(the rst order predicate calculus with identity)에 의해 형식화된 연역적 이론일 경우 오직 그 경우에만 T = h∆, Γi이되, 단 ∆는 L0 의 비논리상항들의 집합이고, Γ는 다음 조건들을 만족하는 L0_{의 문장집합이다}_: 1. Γ의 원소들 속에 나타나는 모든 비논리상항들은 ∆의 원소들이다. 2. Γ의 귀결인T 의 모든 문장들은 Γ의 원소들이다. (그리고 T 의 문장(혹은 식)이란 그 속의 모든 비논리상항들이 ∆에 속하는 문장(혹은 식)이다.)

(3)

연역적 이론의 특성들

I 이론T 는 T 의 어떠한 문장 φ에 대해서도 φ와 −φ이 동시에 T 에 의해 주장되지 않을 경우 오직 그 경우에만 일관적(consistent) 이다. I 이론T 는 T 의 어떠한 문장 φ에 대해서도 φ와 −φ 가운데 최소한 하나가T 에 의해 주장될 경우 오직 그 경우에만 완전(complete)하다. 따라서 모든 비일관적 이론은 자동적으로 완전하다. (왜 그런가?) I 문장집합 Γ는 Γ의 어떠한 원소 φ도 Γ ∩ {φ}0의 귀결이 아닐 경우 오직 그 경우독립적(independent)이다. 흔히 우리는 어떤 선택된 공리도 다른 공리들로부터 연역되지 않는 방식으로 공리들을 고르려고 한다. 그렇게 하는데 실패하면 어떤 공리들은 어떤 정리들을 쉽게 연역해내는데 실용적으로는 도움이 될지라도 이론적으로는 잉여적이 될 것이다. (왜 그런가?)

(4)

공리적 이론

I 어떤L0의 표현 φ에 대해서도 φ가 Γ에 속하는지 않는지를 유한한 수의 단계들을 통해서 결정할 수 있는 절차가 있을 때 문장집합 Γ는 결정가능(decidable)하다고 말한다. 예를 들어, L0의 모든 문장들의 집합은 결정가능하지만, L0의 모든 타당한 문장들의 집합은 그렇지 않다. I 이론T 의 주장들 가운데 다른 모든 것들이 그 귀결인 그러한 결정가능한 부분집합이 존재한다면, T 는 공리화가능(axiomatizable) 하다. I 그 경우 문제의 그 부분집합은 T 의 공리집합(set of axioms)이다. 그리고 T 는 공리화된 이론 혹은 공리적 이론(axiomatized or axiomatic theory) 이라고 불려진다.

(5)

공리적 이론의 의의와 평가잣대

I 역사적으로 자연언어에 있어 공리적 이론에 해당하는 것들은 수학과 물리학에서 꽤 중요한 역할을 했기 때문에, 공리적 이론은 특별한 관심의 대상이 되어왔다. I 대부분의 학생들은 공리적으로 발전된 유클리드 기하학에 어느 정도는 익숙할 것이다. 그로부터 일반화할 수 있는 아이디어는 특정한 기하학적 원리들이 증명없이 가정되었고 기하학적 문제는 그러한 원리들에 기초해 다른 기하학적 주장을 증명하는 것이라는 점이다. I 사실 공리적 이론은 어떤 주제에 대한 학문적 지식을 조직하기 위해 추구해야 할 이상적 형태로 여겨진다. 이 견해가 아무리 회의를 불러일으킨다고 해도 공리적 방법이 지식을 발달시키고 학생들에게 전달하는 데 상당히 유용한 역할을 해왔다는 것은 의심할 여지가 없다. I 공리체계들은 여러 사항들이 고려됨으로써 평가되는 것이 관례적이다. 일관성, 완전성, 독립성이 바로 그러한 사항들이다.

(6)

페아노 대수

PA

I 수학의 역사에서 기하학의 공리화는 고대부터 이뤄졌다. 기원전 300년 전 이미 유클리드가 쓴 원론(Elements)에서 이미 상당히 엄밀한 공리적 이론을 제시한 바가 있다. I 반면 대수학의 공리화는 19세기에 와서야 이뤄졌다. 1860 년대 그라스만의 작업을 효시로 하여, (여러분도 익히 알고 있는) 미국 철학 찰스 샌더스 퍼스가 자연수의 대수학 이론을 제시한 바가 있다. 그러나 대수학의 모든 주장들을 그로부터 도출할 수있다고 생각되는 공리체계는 이탈리아 수학자 주세페 페아노가 1889년 제안하였다. I (동일성을 포함하는) 일차술어논리에 의해 형식화된 연역적 이론으로서 PA 는 이렇게 정의된다: PA = h∆, Γi 이되, ∆는 (앞으로 설명할) 페아노 대수의 비논리 상항들의 집합, 그리고 Γ는 (역시 앞으로 설명할) 페아노 대수들의 입론들의 집합이다.

(7)

비논리상항들의 집합 ∆

∆는 다음 비논리상항들의 집합이다: 종류 기호 숫자 0 대수기호 + × 계승자 함수 s 숫자0은 수 0을 가리킨다. 대수기호들 가운데서 0, +, ×은 우리가 알고 있는 용법으로 쓰며, α와 β가 각각 자연수를 가리키는 항들일 때 αβ는 보다 친숙한 표기방식에 따라서 αβ 로 쓸 수있다. 또 α가 자연수를 가리키는 항일 때 sα는 그 자연수의 바로 다음 수를 가리키는 표현이다. 그러므로 0, s0, ss0 . . . 은 0, 1, 2, . . . 등을 가리킨다. 예를 들자면, (∃x) (x = s0)은 0의 바로 다음 수가 존재한다는 문장이다.

(8)

입론들의 집합 Γ

Γ는 다음 공리들로부터 도출되는L0의 문장들의 집합이다:

A1. (x) (y) (sx = sy → x = y). (즉 s는 1-1함수이다.)

A2. (x) sx 6= 0. (어떤 수도 0을 계승자로 가지지 않는다.) A3. 어떤1항식 ψx에 대해서도, 다음 형태의 공리가 존재한다: [ψ0& (x) (ψx → ψsx)] → (x) ψx. (즉 만일 0이 ψ라는 속성을 가지고, 어떤 수 x에 대해서도 x가 속성ψ를 가질 때 x의 계승자도 ψ를 가진다면, 모든 수들이 ψ를 가진다.) 이 목록에서A3는 하나의 공리가 아니라 무한히 많은 공리들을 예화로 가지는 공리도식(axiom scheme)이다. A3의 예화들은 귀납공리들(induction axioms)이라고도 불리며, 일반적인 대수적 사실의 증명에서 매우 중요한 역할을 차지한다.

(9)

입론들의 집합 Γ

(계속)

다음 공리들은PA 의 대수기호들에 관한 것들이다:

A4. (x) x + 0 = x. (x 더하기 0은 x이다.)

A5. (x) (y) x + sy = s (x + y). (x와 y의 계승자를 더한 것은x 더하기 y의 계승자이다.)

A6. (x) x · 0 = 0. (x 곱하기 0은 0이다.)

A7. (x) (y) x · sy = x · y + x. (x 곱하기 y의 계승자는 x 곱하기y 더하기 x이다.)

A8. (x) x0 =1. (x의 0제곱은 1이다.)

A9. (x) (y) xsy =xy·x. (x의 y계승자 제곱은 x의 y제곱 곱하기x이다.)

이 공리들만 보고서는+, ·, 로 표현되는 많은 사실들을 그부터 도출해낼 수있다는 것을 믿기 어렵겠지만, 예를 들어, ss0 + sss0 = s (ss0 + ss0) = ss (ss0 + s0) = ss (sss0 + 0) = sssss0 임을(즉 2 + 3 = 5라는 사실을) A4와 A5로부터 도출할 수 있다.

(10)

예

: 0 + x = x

{1} (1) (x) x + 0 = x A4 {1} (2) 0 + 0 = 0 (1) US {3} (3) 0 + a = a P {4} (4) (x) (y) x + sy = s (x + y) A5 {4} (5) (y) 0 + sy = s (0 + y) (4) US {4} (6) 0 + sa = s (0 + a) (5) US {3, 4} (7) 0 + sa = sa (3) (6) I {4} (8) 0 + a = a → 0 + sa = sa (3) (7) C {4} (9) (x) (0 + x = x → 0 + sx = sx) (8) UG {10} (10) (0 + 0 = 0& (x) (0 + x = x → A3 0 + sx = sx)) → (x) 0 + x = x {1, 4, 10} (11) (x) 0 + x = x (2) (9) (10) T 즉A3, A4, 그리고 A5로부터 (x) 0 + x = x이 도출된다. 또 한 가지 예로, (y) ((x) y + x = x + y → (x) sy + x = x + sy)을 증명해 보라. 마지막으로, 이 두 사실을 이용하면 어떤 일반적 사실을 증명할 수 있을까?

(11)

일관성

, 완전성, 독립성

이제 앞에 논했던 공리적 이론의 평가잣대들을PA 에 적용해 보자. 즉, PA 가 일관적인지, 완전한지, 그리고 그 공리들의 집합이 독립적인지 따져보자. I PA 에는 자연수들을 가지고 해석을 줄 수 있을 것으로 보이기 때문에, 해석일관적일 것이다. 만일 그렇다면, PA 를 위해서 우리는 이미 그 건전성이 증명된L_I의 추론규칙들을 채택했기 때문에, PA 는 도출일관적이기도 할 것이다. I 불행히도, PA 는 불완전하다. 즉 φ도 −φ도 PA 의 공리들로부터 도출이 안 되는 그런 어떤 φ ∈ Γ가 있다. 더구나, PA 에 새로운 공리들을 아무리 더 많이 덧붙여도, 언제나 ψ도 −ψ도 증명이 안 되는 그런 ψ가 남게 된다는 것이 알려져 있다. I PA 의 공리들이 독립적인지 여기서 엄밀하게 따져볼 수는 없지만, 최소한 A4-A9의 공리들 각각은 다른 공리들로부터 도출되지 않을 것이라는 것이 명백해 보인다.

(12)

두 가지 유형의 정의들

형식이론이 주어졌을 때, 우리는 원래 이론의 어휘에는 속하지 않으면서 식들을 읽기 쉽게 만들고 그 내용을 더 명료하게 해주는 표기법을 도입하기 위해 정의들을 종종 사용한다. 그러한 정의는 다음 두 가지 형식 중 어느 하나로 나타난다: (a) 주어진 대상언어의 기호가 어떤 다른 대상언어 표현과 같은 의미라는 것(다른 대상언어 표현을 줄여 쓴 말이라는 것, 혹은 다른 대상언어 표현으로 항상 치환될 수 있다는 것)을 주장하는 메타언어적 문장. 예: α ≥ β는 (z) α = β + z를 줄여쓴 말이다. (b) 어떤 형식(대개 동일성이나 쌍조건문, 혹은 양화된 동일성이나 쌍조건문으로서 그 좌변에 새로운 기호가 홀로 나타나는 형식)의 대상언어적 문장. 예: (x) (y) (z) (x ≥ y ↔ x = y + z). 이 자료에서는 유형(b)에 초점을 맞출 것이다. 왜냐하면, 이 접근법은 여러 위험들을 더욱 명백하게 만들고 그것들을 피하기 위한 비교적 쉬운 규칙들을 정식화하도록 허락하기 때문이다.

(13)

올바른 정의의 요구사항들

I 일관성: 새로운 정의를 첨가하는 것은 이론을 비일관적으로 만들지 말아야 한다. PA 를 위한 다음 정의를 살펴보자: (x) (y) (z)x_y =z ↔ x = yz. 이 정의는 언뜻 무해한 것처럼 보이지만, 문제는 (x) 0₀ =x, 더 나아가서 (x) (y) (x = y)가 그로부터 도출된다는 것이다. 이것은 PA 의 입론들과 정면충돌한다. 덧셈에 의해 유사하게 구성된 뺄셈의 정의는 그러한 문제를 야기하지 않는다: (x) (y) (z) (x − y = z ↔ x = y + z). I 비창조성: 직관적으로, 올바른 정의는 그것을 기존의 이론에 첨가했을 때 정의된 기호를 지니지 않은 어떤 새로운 입론도 생기지 말아야 한다. 왜냐하면 그런 입론이 생긴다면 그것은 원래 이론을 의도하지 않게 확장하거나 심지어는 왜곡하는 것이기 때문이다. 예를 들어, 군이론 (group theory; pp. 313-316)에 이항 연산기호 `g'의 정의로서 이 문장을 덧붙였다고 하자: (x) (y) (z) (gxy ↔ x = y). 이것은 (x) (y) x = y라는 `g'가 포함하지 않은 정리들을 입론의 집합에 첨가시킨다.

(14)

올바른 정의의 요구사항들

(계속)

I 제거가능성: 정의들에 대한 또 하나의 직관적 요구는 정의들을 사용하여 정의된 기호들을 제거할 수 있어야 (eliminable) 한다는 것이다. 정의된 기호의 도움으로 기술될 수 있는 것은 무엇이든지 그 기호 없이도단지 그 기호가 나타나는 모든 경 우에 대해 그 기호를 그 기호가 축약하고 있는 표현으로 대치함으로써기술될 수 있어야 한다. 순환적 정의들은 명백히 이 요구사항을 위배한다. 예: (x) (y) x + y = y + x. 그러나 어떤 정의가 순환적이지는 않더라도 다른 구조적 결함때문에 제거가능성 조건을 위배하게 되기도 한다. 예: (x) (y) (z) Rxyzx ↔ x + yz > z. 이 정의는R의 첫째 항과 네째 항이 같은 경우에만 R을 제거할 수 있도록 허락한다. Rabcd같은 식에 대해 그것은 전혀 적용될 수 없다.

(15)

형식적으로 올바른 정의들

위 세 가지 요구사항들 가운데 최소한 비창조성과 제거가능성은 다음 규칙들을 따름으로서 만족시킬 수 있다: T 가L0에서 형식화된 이론이라고 하자. 그리고 θ가 T 에는 나타나지 않지만 우리가 그것에 형식적으로 올바른 정의를 주고자 하는 비논리상항이라고 하자. 1. 상항 θ가 n항 술어라면, 그 정의를 형식 (α₁) · · · (α_n) (θα₁· · · α_n↔ ω) 의 문장이 되게 하라. 단 ω는 T 의 식이고 오직 α₁, . . . , α_n만이 ω안에서 나타나는 자유변항들이게 하라. 2. 상항 θ가 문장문자라면 그 정의를 문장 θ ↔ ω 가 되게 하라. 단 여기서 ω는 T 의 문장이 되게 하라.

(16)

형식적으로 올바른 정의들

(계속)

3. 상항 θ가 개체상항이라면 그 정의를 문장 (α) (θ = α ↔ ω) 가 되게 하라. 단 여기서 ω는 α를 유일한 자유변항으로 포함한 T 의 식이 되게 하라. 그리고 대응하는 문장 (∃β) (α) (α = β ↔ ω) 가단 β는 α와 다른 변항임T 의 입론이라는 것도 위 정의의 형식적 올바름을 위한 필요조건이다.

(17)

형식적으로 올바른 정의들

(계속)

4. 마지막으로 상항 θ가 n항 연산기호라면, 그 정의는 형식 (γ₁) · · · (γ_n) (α) (θγ₁· · · γ_n= α ↔ ω) 의 문장이 되게 하라. 단, 여기서 α, γ₁, . . . , γ_n은 서로 다르고 ω 속에서 자유롭게 나타나는 변항들 전부이다. 또한 θ는 ω 속에 들어있지 않다. 그리고, 대응하는 유일성 조건 (γ₁) · · · (γ_n) (∃β) (α) (α = β ↔ ω) 이단 β는 α, γ₁, . . . , γ_n과 다름T 의 입론이라는 것도 필요하다.

(18)

형식적으로 올바른 정의들

(계속)

I 기호언어 L0은 오직n항 술어들, 문장문자들, 개체상항들, 그리고 n항 연산기호들만을 비논리상항으로서 허락하기 때문에, 앞의 규칙들은 L0_{의 어떤 비논리상항들을} 정의하는데에도 쓰일 수 있다. I 책에는 이 규칙들은 비창조적이고 제거가능한 정의들만을 허락한다는 일반적 증명이 나오는데, 시간상 우리 수업시간에 이것을 논하지는 않겠다. 하지만 매우 흥미로운 증명이니 일독을 권한다.

(19)

예

: PA 를 읽기 편리하게 만들기

우리는PA 의 비논리상항들에 다음과 같이 정의되는

이항술어들부등호들을 덧붙인다:

DIE1. (x) (y) (x ≥ y ↔ (∃z) x = y + z).

DIE2. (x) (y) (x > y ↔ ((∃z) x = y + z&z 6= 0)).

DIE3. (x) (y) (x ≤ y ↔ (∃z) y = x + z).

DIE4. (x) (y) (x < y ↔ ((∃z) y = x + z&z 6= 0)). 물론DIE1-DIE4는 형식적으로 정확한 정의들이므로 그 부등호들이 나타나는 어떤 문장도PA 의 문장으로 되쓸 수 있고, 또 이렇게 확장된 이론으로부터 그 부등호들을 포함하지 않는 어떤 새로운 정리도 도출할 수 없다. 다음으로 논리적 참을 나타내는 기호>'과 논리적 거짓을 나타내는 기호 ⊥'는 각각 다음과 같이 정의할 수 있다: DT. > ↔0 = 0. DF. ⊥ ↔0 6= 0.

(20)

예

: PA 를 읽기 편리하게 만들기 (계속)

아래의(무한히 많은) 정의들을 도입하는 것이 편리할 것이다: DDN1. (∃x) (1 = x ↔ x = s0). DDN2. (∃x) (2 = x ↔ x = ss0). DDN3. (∃x) (3 = x ↔ x = sss0). ... 일반적으로, α_n이 자연수 n을 가리키는 십진법 숫자(decimal numeral)일 때, DDNn. (∃x) (α_n=x ↔ x = n z }| { ss · · · s0) 형태의 정의를 통해 α_n을 개체상항으로 도입한다.

(21)

예

: PA 를 읽기 편리하게 만들기 (계속)

다음은 뺄셈과 나눗셈을 안전하게 변용하여 정의하는 문장들이다: D-. (x) (y) (∃z) (x − y = z ↔ (x = y + z) ∨ (z = 0& (w) x 6= y + w)). D/. (x) (y) (∃z) (xy =z ↔ ((x = y · z&x 6= 0)∨ (z = 0&(x = 0 ∨ (w) x 6= y · w)))). 대개의 경우D-와 D/에 의해 정의된 −와 /는 통상적인 뺄셈과 나눗셈 기호들처럼 쓰일 수 있지만 만일x − y 혹은 x_y의 값이 자연수가 아닐 때에는0을 값으로 돌려준다. 특히 D/의 경우 이것은 (x) (y) x = y라는 다른 공리들과 충돌하는 결과를 낳지 않는다는 장점이 있다. (그렇지만 이들 정의 하에서 −와 /를 쓸 때에는 조심해야 한다. 왜냐하면 어떤 맥락에서는 그 기호들을 포함한 문장들이 일반적인 덧셈과 뺄심의 문장들과는 다른 진리값을 가질 때가 있기 때문이다).

(22)

그밖에

PA 에 도입할 수 있는 정의들

우리는 친숙성이 아니라 어떤 이론적 편리성 때문에 새로운 비논리상항들을 정의할 수도 있다. 다음 예들을 살펴 보자:

(x) (Prime (x) ↔ − (∃y) (y 6= 1&y 6= x& (∃z) x = y · z)). (x) (∃y)

NextPrime (x) = y ↔

Prime (y) &x < y& − (∃z) (x < z < y&Prime (z)) . (x) (∃y) NthPrime (x) = y ↔ ((x = 0&y = 1)∨ (∃z) (x = sz&y = NextPrime(NthPrime (z)))) . 세번째 정의에 대해서 의아하게 생각할 수 있는데, 왜냐하면 그 정의의 우항(정의항; deniens)에는 우리가 그 뜻을 정의하려고 하는 좌항의 기호(피정의항; deniendum)가 나타나기 때문이다. 그럼에도 불구하고이것은 단순한 순환적 정의는 아니다. 왜냐하면, 표면적으로는 순환적임에도 불구하고 NthPrime을 포함한 모든 입론들에 대해서 그들과 동치인PA 의 입론을 찾아내는 것이 가능하기 때문이다. 이런 정의를 재귀적 정의 (recursive denitions)라고 한다. (사실 공리 A4-A9은 +, ·, 를 각각 정의하는 재귀적 정의들로 생각될 수 있다.)

(23)