Skip to content

Posts Gödel, Escher, Bach Chapter II: Meaning and Form in Mathematics #
Find similar titles

Chapter II. Meaning and Form in Mathematics

새로운 Formal systempq-System을 소개하고 의미와 형식의 관계에 대해 고찰.

The pq-System #

알파벳은 p, q, - (hyphen).

MU-system과 달리 공리가 무한개라 공리에 대한 명백한 Decision procedure를 정의하고 시작:

Definition: xp-qx- is an axiom, whenever x is composed of hyphens only.

생성 규칙은 하나:

Rule: Suppose x, y, and z all stand for particular strings containing only hyphens. And suppose that xpyqz is known to be a theorem. Then xpy-qz- is a theorem.

예를 들어 x가 '--', y가 '---', z가 '-'라면:

If --p---q- turns out to be a theorem, then so will --p----q--.

연습: 이 시스템의 Decision procedure를 찾아보자.

The Decision Procedure #

이것저것 해보면 "p와 q로 구분된 세 그룹의 하이픈들"이라는 패턴을 찾을 수 있음.

따라서 --p--p--p--q-------- 같은 형태는 바로 배제할 수 있음. (Well-formed string이 아님)

Decision procedure:

  • 앞의 두 하이픈 그룹을 합친 만큼의 하이픈이 뒤에 나오면 정리
  • --p--q----는 정리
  • --p--q-는 정리 아님

왜 위 규칙이 올바른가? 공리에 대한 정의, 생성 규칙을 합치면 자연수 덧셈의 모든 경우, 또 오로지 자연수 덧셈만을 포괄하므로.

공리들:

-p-q--
-p--q---
-p---q----
...

정리들:

-p-q--
--p-q---
---p-q----
...

사실 길어지는 방향의 생성 규칙만 있는 형식 체계는 항상 결정 절차를 갖는다:

  • 주어진 문자열이 공리인지 판단
  • 공리가 아니면, 생성 규칙에 의거하여 해당 문자열의 직전 단계에 올 수 있는 문자열을 모두 나열
  • 이 각각에 대하여 처음부터 반복

Bottom-up vs. Top-down #

직전에 설명한 절차은 Top-down. Bottom-up도 가능:

  • 가장 간단한(가장 짧은) 공리를 상자(bucket)에 담는다
  • 생성 규칙을 적용하여 정리들을 만들어내고 이걸 몽땅 상자에 담는다
  • 두번째로 간단한 공리를 상자에 담는다
  • 생성 규칙을 적용하여 상자의 모든 아이템에 대해 정리들을 추가로 생성하고 도로 상자에 담는다
  • (반복)
  • (위 절차를 수행하되, 주어진 문자열보다 긴 정리나 공리는 무시)

Isomorphisms Induce Meaning #

왜 우리는 이 시스템을 "더하기"로 해석(즉, 의미 부여) 하나? 저자은 우리가 이 시스템과 더하기 사이에서 Isomorphism을 인식했기 때문이라고 주장.

Gödel, Escher, Bach/Introduction: A Musico-Logical Offering에서의 정의에 따르면 isomorphism이란 "정보를 보존하는 방식의 변환(information-preserving transformation)"

더 부연하자면 두 시스템의 요소간 1:1 대응. 단 대응되는 각 요소가 각자의 시스템에서 유사한(?) 역할을 하는 방식으로 연결될 것.

인간의 마음에서 의미가 생겨나는 시점.

두 수준(tiers)에서의 일치가 존재:

  • 기호 수준에서의 일치. 예를 들어 "q"는 "equals"
  • 정리와 참인 문장의 일치. 예를들어 "-p--q---는 정리이다"는 "1+2=3은 참이다"

처음 접하는 형식 체계에 의미있는 해석을 부과하는 작업은 암호해독 혹은 고문서 해독과 유사.

Meaningless and Meaningful Interpretations #

정리와 참인 문장이 일치하는 해석이 있고 그렇지 않는 해석이 있을 것. 전자를 "의미있는 해석", 후자를 "의미없는 해석"으로 각각 구분.

의미없는 해석의 예:

  • p <==> horse
  • q <==> happy
  • - <==> apple

해석과 의미를 구분하면 유용. pq-system에서 해석은 무한하게 많지만 의미가 있는 해석은 (아직까지는) 하나.

Active vs. Passive Meanings #

실제 언어와 형식 언어의 차이:

  • 실제 언어에서는 의미에 기반하여 새로운 문장을 만들 수 있음. 자연 언어에서 의미는 능동적.
  • 형식 언어에서는 의미에 기반하여 새로운 문장을 만들 수 없음. 예를 들어 "-p-p-q---"는 의미상 맞을 것 같지만 이런 문장을 만들면 안됨(well-formed가 아님). 형식 언어에서 의미는 능동적.

Double-Enterdre! #

또다른 의미있는 해석:

p <==> equals
q <==> taken from

"--p---q-----"는 "2 equals 3 taken from 5"

어느 것이 "올바른" 해석인가? 해석의 의미는 실체와의 isomorphism이 얼마나 정확한가에 따라 정해짐

pq-System에서 우리가 관측한 것들:

  • 의미있는 해석이 주어진 경우, well-formed strings이란 문법적인 문장으로 해석되는 문자열들
  • well-formed strings의 일부만이 정리를 이룸
  • 모든 잘못된 덧셈(2 plus 3 equals 6)은 well-formed 이지만 정리는 아닌 문자열에 대응됨

Formal Systems and Reality #

pq-System은 실체를 완벽하게 흉내내는 것으로 보임. 하지만 실체와 형식 체계는 서로 독립적. 둘 사이의 Isomorphism을 반드시 인식해야할 필요도 없다.

모든 실체가 형식 시스템으로 표현될 수 있을까?

  • 넓은 의미에서는 그럴수도
  • 누군가는 세상이 매우 복잡한 하나의 형식 체계일 뿐이라고 주장할 수도 있을 것
  • 이 경우, 기호는 종이 위에 있는 것이 아니라 3차원 공간 상에 존재 (단, 가장 기본적인 입자가 있을 것이라는 가정이 필요)
  • 기본적으로 우리가 묻고 있는 것은 "세상이 결정론적으로 작동하는가"이다. 이는 아직 열려있는 문제

Mathematics and Symbol Manipulation #

일단 "실체(real world)"를 "수학(mathematics)"으로 제한해서 생각해보자. 심각한 의문:

  • 우리가 수학의 일부를 형식 체계로 담아내고자 했을 때, 이게 올바르게 되었는지 어떻게 알 수 있을까?
  • 특히 우리가 수학의 해당 부분에 대해 완전하게 알고 있지 않은 경우라면?
  • 우리의 목표가 형식 체계를 활용하여 해당 수학 분과의 새로운 지식을 얻어내려는 것이라면?
  • Isomorphism이 완벽하다고 증명하지 않은 상태에서, 모든 정리에 대한 해석이 참이라는 것을 어떻게 확신할 수 있을까?
  • 해당 수학 분과의 모든 부분에 대해 알지 못하는 상태에서 Isomorphism의 완결정은 어떻게 증명할 수 있는가?

이는 자연수를 실체에 대응시키려고 할때 항상 발생하는 문제:

  • 12*12=144가 실체와 맞는지 어떻게 아나? 격자를 그리고 세어본다
  • 987654321*123456789은? 현실적으로 불가능. 곱셈규칙에 따라 기호적으로 연산한 답이 맞을 것이라고 믿을 뿐

The Basic Laws of Arithmetic #

막대기 몇 개가 있다:

/ // // // / /

앞으로 세거나 뒤로 세거나 같은 값. 결합법칙이나 분배법칙은 너무나 직관적이라 증명하려는 시도가 오히려 이상하게 느껴짐. 곱셈도 유사.

하지만 현실의 숫자는 모호. 빗방울 두 개가 합쳐지면 빗방울 한 개 등.

Ideal Numbers #

이상적 수:

  • 현실의 수는 모호하지만 우리에겐 이상적이고 모호하지 않은 수 개념에 대한 내제된 관념이 존재
  • 산술과 수론의 기저에는 이 관점이 깔려있음

수론 전체를 왼벽하게 형식화하는 것이 가능할까? 수론을 형식화한다는 것은 단순히 셈하기만을 의미하지 않음. 예를 들어 소수의 무한성에 대한 증명 같은 것은 단순한 셈으로는 증명이 불가능.

"무한한 소수가 존재한다"는 참이다. 유클리드의 증명은 타당하지만 직관적으로 명백해보이지는 않는다. 그럼에도 불구하고 모든 수학자들은 위 문장이 참이라고 말한다. 왜?

Euclid's Proof #

추론(reasoning)에 의해. 다음은 Euclid의 증명을 변형한 것:

  • 임의의 수 N에 대하여
  • N! + 1 을 구한다. 이 수는 2에서 N 사이의 어떠한 수로도 나누어 떨어지지 않는다
  • N 보다 크고 N! + 1 보다 작은 어떤 수로 N! + 1이 나누어 떨어지면 그 수는 소수, 그런 수가 없으면 N! + 1 자체가 소수

"어떤 수 N을 고르건"이라는 방식의 일반화(generalization) 덕분에, 유한한 단계만으로 무한한 사례에 대해 선언하는 문장을 만들 수 있음

한편 각 단계는 이전 단계로부터 "거부할 수 없는(irresistible)" 방식으로 진행됨. 그렇게 때문에 "쓸만한 근거"가 아니라 "증명"이라고 불림

증명의 각 문장이 이와 같이 연결되어있다는 것은 각 문장을 연결하는 패턴화된 구조(patterned structure)가 있을 수 있다는 점을 시사.

증명을 이루는 문장들은 수론에 대한 문장으로 이해할 수도 있으나, 동시에 어떤 변환 규칙을 따르는 추상적 패턴으로 이해할 수도 있음. (즉, 증명 과정을 충분히 형식화하면 하나의 형식체계로 만들 수 있음)

Getting Around Infinity #

"모든 N에 대하여"와 같은 문장에서의 "모든"이라는 단어 덕분에 무한성을 피할 수 있음.

한편, "모든"이라는 단어를 사용할 때 우리는 그 단어의 의미에 맞춰 쓰고 있다고 생각하지만, 달리 말하자면 "의미에 맞춰 쓴다"는 말은 곧 (암묵적인) 어떤 규칙을 따르고 있다는 것과 같음.

이러한 발상이 수론의 형식화의 시초

다음 장들에서 1) 수론의 모든 문장을 표현할 수 있는 어휘들과, 2) 필요한 모든 추론을 포괄할 수 있는 규칙들을 갖는 Formal system을 소개할 것.

이러한 형식화가 정말 우리의 심적 추론 능력과 동등한 힘을 갖는지, 더 일반적으로는 인간과 같은 수준의 사고 능력을 담아내는 형식 시스템을 (이론적으로는) 만들 수 있을 것인지 등을 물을 것

Incoming Links #

Related Articles #

Related Books #

Suggested Pages #

Other Posts #

0.0.1_20140628_0