formal_system

Formal Language⚑

책 "괴델 에셔 바흐" 를 읽고 정리해두었다.

Formal language 란 Alphabet 으로 구성된 Word 로 구성되고 특정한 규칙에 의해서 지배되는 well-formed 된 언어를 말한다.

MU 의 수수께끼⚑

형식 체계 ( Formal system )⚑

이 책의 핵심개념들 중 하나는 바로 형식체계이다. 이를 위해서 아래 예시를 살펴보자.

1. 당신에게 MI 라는 문자열이 주어지고
2. 문자열을 조작할 수 있는 몇 가지 규칙이 주어진다고 하자

이 때 당신은 주어진 문자열을 특정한 규칙을 통해서 MU 문자열로 만들 수 있는가 ? 적용 가능한 규칙이 여러 개 있을 때, 어떤 규칙을 선택할 것인지 선택하는 당신의 몫이다. 그러나 규칙을 위배하는 조작은 할 수 없다. 우리는 이런 요구를 “형식성 요구” 라고 한다.

자 이제 우리의 형식적 요구를 조금 구체화해보자.

1. MIU-체계에서는 사용하는 알파벳은 세 개 ( M, U, I ) 만을 사용한다.
   • 즉 우리가 만들 수 있는 문자열은 M, U, I 로만 합성이 된다.
   • 우리가 가질 수 있는 문자열은 MIUUIU 같이 세 알파벳으로만 구성된다.

2. 그리고 사용할 수 있는 규칙을 다음과 같이 정의해보자.

   규칙 1 - 마지막 글자가 I 인 경우, 그 끝에 U 를 하나 추가할 수 있다.

   규칙 2 - Mx 를 획득가능하다면 Mxx 를 획득할 수 있다.

   • MIU 를 획득했다면 MIUU 를 획득할 수 있다.
   • MUM 을 획득했다면 MUMM 을 획득할 수 있다.
   • 이 규칙속의 x 는 우리가 획득한 임의의 문자열을 대신할 수 있다. x 는 M, U, I 와는 다른 형태로 형식 체계에 포함되고 있다

   규칙 3 - 우리가 획득한 문자열 중 하나에서 III 가 나타나면 III 대신 U 를 가지는 문자열을 획득할 수 있다.

   • UMIIIMU 를 획득했다면 → UMUMU 를 획득할 수 있다.
   • MIIII 를 획득했다면 → MUI 또는 MIU 를 획득할 수 있다.
   • 그러나 그 역은 성립하지 않는다. 즉, MU 로부터 MIII 를 획득할 수는 없다.

   규칙 4 - 문자열 중 하나에서 UU 가 나타나면 그것을 삭제할 수 있다.

   • UUU 를 획득했다면 U 를 획득할 수 있다.
   • MUUUIII 를 획득했다면 MUIII 를 획득할 수 있다.

이제 MI 라는 문자열이 획득되었다고 ( 주어졌다고 ) 하면 위 규칙들을 적용하여 MU 를 획득할 수 있는가 ?

정리, 공리, 규칙⚑

• MU 를 찾기 위해서 일련의 문자열을 얻게 될 것이다.
  • 예를 들어 다음과 같은 과정을 거칠 수 있을 것이다.
    • MI → 규칙 2 → MII → 규칙 2 → MIII → 규칙 3 → MU
• 이때 규칙에 의해서 획득되는 문자열을 정리 ( theorem ) 이라고 부른다. 정리라는 용어는 우리가 통상 사용하는 것과는 판이한 수학에서 통용되는 의미를 가진다.
  • “정리” 라는 용어는 엄격한 논증을 통해서 참으로 증명된 일상 언어로 표현된 문장을 의미한다.
  • 그러나 형식체계에서는 정리를 문장으로 볼 필요는 없다. 그것은 기호들의 연쇄체 ( =문자열 ) 일 뿐이다.
  • 정리들은 “증명”된다기보다는 그저 “생성”되는 것이다.
• 앞의 수수께끼에서 MI 는 어떤 조건도 없이 주어졌다. 우리는 이것을 “공리 ( axiom )” 이라고 부른다.
• 형식체계는 MIU-체계가 가지는 4개의 규칙처럼, 부호를 변환시키는 규칙을 가진다. 이런 규칙을 생성규칙 ( rules of production ) 또는 추론규칙 ( rules of inference ) 라고 부른다.
• 마지막으로 도입하고자 하는 용어는 생성과정 ( derivation ) 이다. 아래는 정리 MUIIU 의 생성과정이 제시되어 있다.
  • MI ( 공리 )
  • MII ( 규칙 2 )
  • MIIII ( 규칙 2 )
  • MIIIIU ( 규칙 1 )
  • MUIU ( 규칙 4 )
  • MUIUUIU ( 규칙 2 )
  • MUIIU ( 규칙 4 )
• 정리의 생성과정은 규칙에 따라서 그 정리를 생성하는 방식을 단계적으로 구체적으로 보여준다. 생성과정이라는 개념은 증명이라는 개념에 비추어 구상되었지만, 실은 증명의 엄격한 사촌이다. 그래서 MUIIU 를 “증명” 했다고 말하면 이상하게 들리겠지만, MUIIU 를 생성했다고 말하면 그렇게 이상하게 들리지 않는다.

결정 절차⚑

• MI 로 부터 파생될 수 있는 모든 정리들을 전부 뒤진 후 → MU 가 생성된다는 것은 알수 있다.
  • 그러나 생성이 불가능한 문자열의 경우 → 무한한 정리 ( = Search Space ) 를 모두 뒤지더라도 생성 불가능함을 알 수 없다.
  • 모든 정리를 뒤지지 않고 MU 가 생성됨을 알 수 있는 방법이 있는가 ?
  • 즉 일정한 시간 안에 주어진 문자열이 “정리” 인지 판별할 수 있는지 알 수 있는 방벙이 있다면 그 방법은 주어진 형식체계에 대한 결정절차 ( decision procedure ) 라고 불린다.

• 우리가 그런 결정 절차를 가진다면, 우리는 그 체계에 있는 모든 정리들의 속성을 구체적으로 규정하는 것이다. MUI-체계의 추론규칙과 공리들은 MUI 로 구성된 문자열에 대해서 “정리” 와 “비정리”를 규정한다.

• 형식체계에 요구되는 사항은, 공리들의 집합이 결정절차에 의해서 규정된다는 것이다. 이것이 바로 공리의 집합과 정리의 집합 사이의 차이이다. 공리의 집합은 항상 결정절차를 가지지만 정리의 집합은 그럴 필요가 없다.

수학에서의 의미와 형식⚑

pq-체계⚑

• [알파벳] pq- 체계는 다음 세 가지의 alphabet 을 가진다 ( p , q , -(붙임표) )
• [공리] pq- 체계는 수 많은 공리들을 가진다. 그러나 이것을 모두 적을 수 없기 때문에 그것을 기술하는 다른 방법론이 필요하다. 사실 우리가 바라는 것은 공리를 기술하는 것 그 이상이다.
  • 정의 : x 가 오직 -로만 이뤄어질 경우에만, x p - q x - 는 하나의 공리이다.
  • 즉, - - p - q - - - 는 하나의 공리이다. x 를 - - 로 두면 되기 때문이다.
  • x 는 pq- 체계에 속하지 않기 때문에 ( 임의의 기호를 나타내는 기호임 ) x p - q x - 자체는 공리가 아니다.
• [생성규칙] x, y 그리고 z 가 붙임표만을 가지는 특정한 문자열에 대해서만 쓰이며, x p y q z 가 하나의 정리라고 가정해보자. 그렇다면 x p y - q z - 는 하나의 정리이다.
  • 즉, x,y,z 가 - 로만 이뤄진다면 xpyqz 를 얻을 수 있다면 xpy-qz- 를 얻을 수 있다는 말이다.
  • - - p - - - q - 가 정리라면, - - p - - - - q - - 도 정리가 된다.
• pq- 체계의 정리들에 대한 결정 절차를 찾아내는 것은 대단이 유익한 연습이다.

결정 절차⚑

• pq- 체계의 모든 정리는 세 가지 상이한 무리의 붙임표를 가지며, 이 배열에서 그것을 분리하는 요소는 p 와 q 가 된다는 것을 알 수 있을 것이다.
• 그렇다는 것은 - - p - - p - - p - - q - - - - - - - - 와 같은 문자열은 위 공리 및 규칙으로 부터 파생될 수 없다는 것이다.
• 형식체계에서 단순히 공리에 규칙을 적용하여 정리를 얻는 과정은 다분히 형식적이며, “형식” 이외의 것은 보이지 않는다. 하지만 형식체계를 논의하면 “형식”이라는 개념은 더 복잡해지고 추상적이 될 것이다. 따라서 “형식” 이라는 낱말의 의미에 대해서 더욱 숙고해야 할 것이다.

TOP DOWN vs BOTTOME UP⚑

• 공리로부터 → 정리를 유도하거나 ( Top Down )
• 정리로부터 → 역으로 공리르 유도 ( Bottom Up ) 하는 방식으로 정리의 유효성을 결정할 수 있다.

동형 관계 ( = isomorphism ) 가 의미를 유발한다⚑

이제 이 책의 핵심 문제에 도달한다.

어느 순간 위에서 언급된 pq- 정리는 마치 “더하기” 와 같은 형태로 작동한다는 것을 알게되었을 것이다.

- - p - - - q - - - - - 라는 문자열은 마치 2 + 3 = 5 처럼 보이기 때문이다. 마치 2 + 3 = 5이고 그것을 다른 형태로 표현한 것이 - - p - - - q - - - - - 라고 하는 것이 더 자연스러워 보이기도 한다. 그러나 이것이 과연 이 현상을 해석하는 올바른 방식일까 ? 나는 일부러 p 는 PLUS , q 는 EQUAL 을 연상시키기 위해서 p 와 q 라는 문자를 선택했다. 그렇다면 실제로 - - p - - - q - - - - - 는 2 + 3 = 5 를 “의미”하는가?

무엇이 그런 느낌을 주고 있는가 ? 나의 대답은 pq-정리들과 더하기 사이에서 isomorphism 을 발견했다는 다는 것이다. isomorphism 이라는 용어는 한쪽 구조의 각 부분이 다른 구조의 상응하는 부분으로 대응하는 방식으로 두 개의 복합 구조가 사상 ( mapping ) 될 수 있는 경우에 사용된다.

그래서 수학자들은 그들에게서 알려진 두 구조 사이에서 isomorphism 을 찾아낼 때 기뻐한다. 그런 발견은 종종 “섬광” 처럼 나타나 경이로움의 원천이 된다. 알려진 두 구조 사이의 isomorphism 의 인식은 지식의 의미심장한 진보이다. 그래서 인간의 마음에서 “의미”를 창출하는 isomorphism 를 발견할 수 있다고 생각한다. 그러나 동형관계는 다양한 모습과 크기로 나타나기 때문에 우리가 정말 isomorphism를 찾았는지 분명한 것은 아니다. 그래서 isomorphism 는 애매한 단어이다.

“낮은 차원에서” 의 동형관계 관점에서는 pq- 체계에서는 다음과 같은 동형관계를 찾을 수 있다.

p ↔ 더하기

q ↔ 같다

- ↔ 하나

- -↔ 둘

- - -↔ 셋

이러한 기호와 낱말 사이의 대응 관계는 “해석”( interpretation ) 으로 불린다.

한 단계 더 높은 차원에서, 참인 명제와 정리 사이의 대응이 있다. 그러나 이 떄 한 단계 더 높은 층위에서 대응은 기호의 해석이라는 우선적인 선택이 있어야만 확인할 수 있음에 주의하라. 따라서 그것을 참인 명제와 해석된 정리 사이의 대응이라고 기술하는 것이 더 정확할 것이다. 어쨌거나 두 층으로 된 대응 관계를 묘사했는데, 그것은 모든 동형 관계에서 전형적이다.

그러나 우리가 알지 못하는 형식체계를 만날 경우, 그리고 그 안에 숨겨진 의미를 찾기를 바랄 경우, 참인 명제와 정리 사이에 한 단계 높은 층위에서 대응관계가 나타나도록 기호들에게 어떻게 유용한 해석을 할당할 것인가 그것이 관건이다.

수학자들은 형식체계를 다루는 사람들이며, 수학자들은 현실의 일정한 부분을 동형태로 재현해내는 형식체계를 만드려는 것이다. 그런 경우 활자 생성 규칙의 선택과 같은 기호의 선택은 강한 동기를 가지고 있다.

무의미한 해석과 의미 있는 해석⚑

사람마다 다른 해석을 선택할 수 있다. 모든 정리를 다 참으로 만들 필요가 없다. 그렇다고 모든 정리가 다 거짓으로 판명되는 경우에는 해석할 이유가 없을 것이다. 따라서 한 형식 체계에 두 가지 해석유형을 구별해보자.

무의미한 해석, 즉 체계의 정리와 현실 사이에 그 어떠한 동형 관계도 볼 수 없는 해석이 있다.

예를 들면

p ↔ 말

q ↔ 행복한

• ↔ 사과

이제 - p - q - - 는 새로운 해석을 얻는다. 사과 말 사과 행복한 사과 사과 그러나 이런 해석은 거의 무의미하다.

해석의 또 다른 방식은 의미 있는 해석이다. 그런 해석은 정리와 진리 사이의 대응, 즉 정리와 현실의 일정한 부분 사이에 동형 관계가 존재한다. 따라서 “해석”과 “의미”를 구분하는 것이 좋다. 그 어떤 낱말도 p에 대한 해석이 될 수 있지만, “더하기” 라는 말은 “의미있는” “해석”이기 때문이다.