Wk04:보다 정도높은 예비사항들 II.pdf

기호논리학

문장형식

문장형식(sentence form)은 문장이거나 문장으로부터 그 문장 속에 직접적으로 나타난 이름들 일부 혹은 모두를 변항들로 대치해서 얻어낼 수 있는 표현이다. 예를 들어 x 는 총을 가지고 있었다， 스미스는 총을 가지고 있었다， x 는 y 다， 스미스는 y 다. 는 모두 문장형식이다.

문장형식과 대체예

x + 6 < 8 과 같은 문장형식을 살펴보자. 이 표현으로부터 문장이 얻어내지는 방식에는 두 가지가 있다. 우선 수의 이름 혹은 기술구로 ‘x’를 대치하여， 1 + 6 < 8 2 + 6 < 8 3 + 6 < 8 과 같은 문장틀을 얻어낼 수 있다.

문장형식과 양화문

또 하나의 방식으로서 우리는 소위 양화사 (quantifier)를 사용할 수 있다. 양화사는

보편양화사(universal quantifier): 모든 x에 대해 . . . (For every x . . . )

와

존재양화사(existential quantifier): . . . 한 x가 있다 (There is an x such that . . . ) 같은어구들이다. 이 방법을 사용하면 우리는 앞의 문장형식으로부터 거짓 문장 모든 x에 대해_{，x + 6 < 8} 과 참 문장 x + 6 < 8인 x 가 있다. 를얻을 수 있다.

구속변항과 자유변항

문장형식 x < y 인 x 가 있다. 로부터 문장을 얻으려면 y 를 숫자 또는 수를 지시하는 기술구로 대치하거나 혹은 양화시켜야 한다. 그 경우 모든 y 에 대해서도 x < y 인 x가 있다. 라는 문장이 얻어진다. 위 문장형식에서 알 수 있듯이, 일반적으로 변항은 두 가지 방식으로 나타난다: 1. 문장을 얻기 위해 대입이나 양화를 필요로 하는 것과 2. 그렇지 않은 것. 전자를 변항이 자유롭게(free) 나타났다고 하고 후자를 변항이 속박되어(bound) 나타났다고 한다.

만

족(satisfaction)

I 단지 한 가지의 변항—이를테면 ‘x’—만이 문장형식에서 나타난다고 하자. 그때 그 자유변항에 어떤 대상을 할당한 결과가 참이라면 그 대상은 그 문장형식을 만족시킨다(satisfy) 고 말한다. 따라서 문장형식 “4 < x이고 x < 9이다”를 5, 6, 7, 또는 8은 만족하지만 3이나 10은 만족하지 않는다. I 정확히 두 가지의 변항이 나타나는 형식의 경우, 우리는 대상의 순서쌍(ordered pair)이 그 형식을 만족하거 만족하지 않는다고 말한다. 이때 변항들은 알파뱃 순서로 다루어진다. 예를 들어, h3, 6i—3과 6으로 이루어진 순서쌍—은 “x < y ”를 만족시키는 반면, h6, 3i은 그렇지 않다. 뒤의 쌍은 대신 형식 “y < x”를 만족한다.

만

족(satisfaction) (계속)

I 세 변항이 자유롭게 나타날 때엔 대상들의 순서 삼중체

(ordered triple)를 고려해야 한다. h3, 5, 7i은 “x < y 이고 y < z”를 만족한다. 이것은 3 < 5이고 5 < 7이기 때문이다; 그러나 h3, 5, 3i은 그렇지 않다. 왜냐하면 3 < 5이고 5 < 3인 경우가 아니기 때문이다. I 일반적으로 n개의 변항이 자유롭게 나타나는 문장형식은 n-중체(n-tuple)에 의해서 만족되거나 만족되지 않는다고 말한다. 이 경우에도 —n = 1이 아닌 이상— 순서가 중요하다.

원소관계 그리고

집합의 외연성

I 집합을 구성하는 대상들은 그 집합의 원소들(elements)이다.

이때 ‘ ... 의 원소이다 (is a member of)’를 ‘∈’으로 줄여쓴다. 예를 들어 ’P’가 소수들(prime numbers)의 집합을 지시하는 문자라면 ’7 ∈ P’는 7이 소수의 집합의 원소라는 것을, 다시 말하자면, 7이 솟수라는 것을 말한다. I 각 집합은 그 원소들에 의해 단일하게 결정된다. 즉 같은 원소들을 가지는 집합은 동일하다. 예를 들어 {2, 3, 5, 7} = {x|0 < x < 10이고 x는 소수이다}.

집합과 문장형식

I 방금전 예—{x|0 < x < 10이고 x는 소수이다}—에서 보듯이, 집합은 자유변항이 하나인 문장형식과 밀접한 관련을 가지고 있다. 아주 특수한 경우를 제외하고는, 자유변항이 하나인 각 문장형식에 대해 그 형식을 만족시키는 대상들을 원소들로 가지는 집합이 존재한다고 말할 수 있다. I 일반적으로, “φv ”가 “v ”를 유일한 자유변항으로 가지는 문장형식일 때, {v |φv }는 “φv ”를 만족하는 모든 대상들의 집합이다. I 반면, {v1, . . . , vn}은 v1, . . . , vn를, 그리고 그것들만을 원소로 가지는 집합이다.

공집합 (null set)과 전체집합(universal set)

I 공집합은 이렇게 표기되고 정의된다: ∧ = {x|x 6= x} 주의: 공집합을 가리키는 현재의 표준 기호는 “∅”이다. I 전체집합은 이렇게 표기되고 정의된다: ∨ = {x|x = x} 주의: "U"가 전체집합을 가리키는 현재의 표준 기호에 가깝다.

부분집합(subset)

집합 A의 모든 원소가 집합 B의 원소라면—즉, A 의 어떠한 원소도 B의 원소가 아닌 것이 없다면—집합 A는 집합 B에

포함된다(be included in), 혹은 A는 B의 부분집합(a subset)이라고 말한다. 기호로는: A ⊂ B 라고 쓴다. 주의: 현재 표기법으로는 “A ⊂ B”는 A가 B의 진부분집합, 즉 A가 B의 부분집합이지만 그 역은 성립하지 않는다는 뜻으로 쓰인다. 단순히 A가 B의 부분집합이라는 것을 나타내려면, 현재 표기법으로는 “A ⊆ B”라고 쓴다.

몇 가지 정리들

만일 A, B, C 가 각각 어떤 집합이라면, 다음과 같은 정리들이 도출된다: (1) ∧ ⊂ A (2) A ⊂ A (3) A ⊂ ∨ (4) 만일 A ⊂ B이고 B ⊂ A이면 A = B이다. (5) 만일 A ⊂ B이고 B ⊂ C 이면 A ⊂ C 이다.

합집합, 교집합, 여집합

만일 A, B, C 가 각각 어떤 집합이라면, A ∪ B =df {x|x ∈ A 또는 x ∈ B}, A ∩ B =df {x|x ∈ A 그리고 x ∈ B}, A0 =df {x|x /∈ A}

와 같이 합집합(union), 교집합(ntersection), 여집합(complement) 을 정의할 수 있다.

또 다른 정리들

역시 A, B, C 가 각각 어떤 집합이라면, 다음 정리들도 도출된다: (6) A ∪ B = B ∪ A. (7) A ∪ B = B ∪ A. (8) A ⊂ A ∪ B. (9) A ⊃ A ∩ B. (21) A ∪ (B ∪ C ) = (A ∪ B) ∪ C . (22) A ∩ (B ∩ C ) = (A ∩ B) ∩ C . 그밖의 흥미로운 정리들은 교과서 70-71쪽 참조.

순서쌍(ordered pair)과 순서 n중체(n-tuple)

이 책에서 우리는 I 첫째 항이 x이고 둘째 항이 y 인 순서쌍(ordered pair)을 나타내기 위해 hx, y i , I 첫째 항이 x, 둘째 항이 y , 셋째 항이 z인 순서삼중체(ordered triple)를 나타내기 위해 hx, y , zi , I 첫째 항이 x, 둘째 항이 y , 셋째 항이 z, 넷째 항이 w 인 순서사중체(ordered quadruple)를 나타내기 위해 hx, y , z, w i , I 그리고 일반적으로 첫째 항이 x1,. . . n째항이 xn인 순서 n 중체(ordered n-tuple)를 나타내기 위해 hx_n, . . . , xni 를 사용할 것이다.

관계 (relation)

관계 (relation) 의 개념은 집합의 개념과 유사하게 다루어진다. 사실, 관계는 특수한 종류의 집합으로 여겨진다.

I 대상들의 순서쌍들(ordered pairs)의 집합은 모두 이항(binary)

관계이다; I 대상들의 순서삼중체들(ordered triples)의 집합은 모두 삼항 (ternary)관계이다; I 대상들의 순서사중체들 (ordered quadruples) 의 집합은 모두 사항 (quaternary) 관계이다; I 일반적으로 대상들의 순서 n중체들(ordered n-tuples)의 집합은 모두 n항(n-ary) 관계이다.

관계 (relation) (계속)

문장형식 x 와 y 는 정수이고 x < y 이다. 를 살펴보자. 이 형식을 만족시키는 순서쌍들의 집합은 ‘보다-작음 (less-than)’이라고 불리는 이항 관계를 구성한다. 그리고 다음 사실이성립한다: 모든 대상 x, y 에 대해 순서쌍 hx, y i가 이 ‘보다-작음’ 관계의 원소일 경우, 오직 그 경우에만, x와 y 는 정수이고 x < y 이다. 다음 순서쌍들은 이 관계에 속한다: h1, 2i, h2, 10i, h5, 8329i, h6 + 4, 11i. 반면 다음 순서쌍들은 그렇지 않다:

이항관계

어떤 이항관계 R이 있다고 하자. 어떤 순서쌍 hx, y i가 R의 원소라면, 물론 우리는 이 사실을 hx, y i ∈ R 로 표기할 수 있다. 그러나 이 표기법은 번거롭고 부자연스럽기 때문에, 이항관계의 경우에는 xRy 형태의 표기를 특별히 채택할 것이다. 사실 ‘<’를 보다-작음 관계의 다른 이름으로 생각할 수 있다. 즉 0 < 1, 2100< 3100 등은 h0, 1i ∈<,2100_{, 3}100_∈< 등의 간편한표기로 생각될 수 있다.

이항관계 (계속)

I 이항관계 R의 정의역(domain) 은 어떤 y 에 대해 xRy 인 모든

x 의 집합이다.

I 이항관계 R의 치역(converse domain)은 어떤 x에 대해 xRy 인 모든 대상 y 의 집합이다. I 이항관계 R의 전체역(field) 은 그 정의역과 치역의 합집합이다. I 이항관계 S는 정확히 다음 경우 이항관계 R의 역(converse) 이다: S = ˘R =df {hy , xi |xRy }. I 이항관계 R은 정확히 다음 경우에 함수(function)이다: 모든 대상 x, y , z에 대해 xRy 이고 xRz이면_{，y = z이다.} I 이항관계 R은 정확히 다음 경우 1-1관계(1-1 relation)이다: R 과 그 역이 모두 함수다.

함수

이항관계들 가운데서 함수는 앞으로 논의에서 특히 중요하므로, 추가적인논의가 필요하다. I 함수F 가 집합 D를 정의역으로 가지고 C 를 치역으로 가진다고 하자. 즉 어떤 x ∈ D와 y ∈ C 에 대해서 xFy 이다. I 이때 임의의 x ∈ D가 주어지면, xFy 인 y ∈ C 는 하나 밖에 없다. (왜 그런가?) 앞으로 우리는 그런 y 를 ‘F (x)’라고 표기할 것이다. I 물론 함수는 언제나 이항관계이다. 하지만 위의 F 같은 함수는 하나의 대상 x를 입력값으로 받는다는 의미에서, 단항함수(unary function)라고도 한다. I 예를 들어 다음 함수를 생각해 보자: s =df {hx, y i |x, y ∈ N이고 y = x + 1}. (N은 자연수들, 즉 0 또는 양의 정수인 수들의 집합이다.) s가 이렇게 정의되었을 때, s (1) = 2, s (2) = 3, . . . s (1000) = 1001,. . . 여기서 s는 단항함수이지만 이항관계이기도 하다.

n-항 연산

I (n + 1)항 관계 F 이 집합 D에 관해서 n항 연산 (n-ary operation) 일 경우 오직 그 경우에만 D의 대상들의 각 n중체 hx1, x2, . . . , xni에 대해 hx1, x2, . . . , xn, y i ∈ F 인 y ∈ D가 정확히 하나 존재한다. n항 함수(n-ary function)라는 용어도 같은 뜻으로 자주 사용되는데, 이 경우 이항관계인 함수는 단항함수라고 구별하여 부른다. I 편의상 다음 표기법을 채택할 것이다: F 를 D의 대상들에 대해 정의된 n-항 함수라고 하자. 이때 임의의 x1∈ D, x1 ∈ D, . . . x1 ∈ D가 주어지면 hx1, x2, . . . , xn, y i ∈ F 인 y 를 ‘F (x₁, x2, . . . , xn)’이라고 표기할 것이다. I 예를 들어 F 를 다음과 같이 정의해 보자: F =df {hx, y , zi |x, y , z ∈ N이고 z = x + y } 사실 우리는 ‘F (·, ·)’를 ‘· + ·’의 다른 표기법으로 생각할 수 있다.

대상언어와 메타언어

I 우리는 한 언어에 관해서 다른 언어를 사용해 이야기할 때마다, 전자를 대상언어(object-language)라 하고 후자를 메타언어(metalanguage)라고 부를 것이 다. 따라서 한국말로 쓰여진 영어 문법책의 경우 영어는 대상언어이고 한국어는 메타언어이다. I 이미 논했지만, 대상언어의 표현들을 값으로 가지는 변항을 메타언어적 변항(metalinguistic variables)이라 부른다. 메타언어적 변항들을 대상언어들의 변항들과 혼동해서는 안된다. 예를 들어, (φ ∨ ψ) 에서“φ”와 “ψ”는 메타언어적 변항들이지만, (Fx ∨ Gy ) 에서 “x”와 “y ”는 대상언어에 속하는 변항들이다.

메타함수

I 일전에 우리는 대상언어의 표현들을 입력값으로 받아 역시 대상언어의 표현을 출력값으로 돌려주는 이항함수(또는 이항연산)를 하나 배웠다. 즉 우리는 접합함수 (concatenation function) _을 배웠다. I (대상언어의 표현을 값으로 가지지만 메타언어에 속하는 변항인 메타변항인 것처럼) 대상언어의 표현들을 입력값 그리고/또는 출력값으로 가지는 함수는 메타함수 (metafunction)이다.

수학적 귀납법

수학적 귀납법은 몇 가지 형태로 나타난 다. 소위 약한 귀납법은 다음 두 가지를 보임으로써 모든 양의 정수들이 어떤 주어진 속성 P를 가지고 있음을 입증하기 위해 사용된다. (a) 1이 속성 P를 가졌다. (b) 모든 양의 정수 k에 대해，만일 k가 속성 P를 갖는다연，k + 1도 속 성 P를 갖는다. 강한 귀납법도 모든 양의 정수들이 어떤 주어진 속성 P를 가지고 있음을 입증하기 위해 사용된다. I 각 양의 정수 k에 대해，만일 k보다 작은 모든 양의 정수틀이 속성 P를 가졌다면 k도 속성 P를 갖는다. * 위 내용은 교과서 273페이지에 있으니 참조하라. 수학적 귀납법은 양의 정수들의집합(= N+_{) 이 아니라 자연수들의 집합} (= N0) 을 대상으로 할 수도 있는데, 위의 논의에서 ‘양의 정수’를 ‘자연수’로, ‘1’을 ‘0’으로 대치하기만 하면 된다.

수학적 귀납법 (계속)

쉬운 예: 어떤 양의 정수 n도 그 자체로 짝수거나 n + 1이 짝수이다. 먼저 다음 정의를 살펴보자: I 양의 정수 n이 짝수라는 것은 n = 2 · k인 양의 정수 k가 존재한다는 것이다. 이 정의와 약한 귀납법을 사용하여 위의 주장을 증명할 수 있다. (a) 1은 그 자체로 짝수는 아니지만 1 + 1이 짝수이다. 왜냐하면 1 + 1 = 2 · 1이기 때문이다. (b) (C_k) k가 짝수거나 k + 1이 짝수라고 가정하고, (Ck+1) k + 1이 그 자체로 짝수거나 (k + 1) + 1이 짝수임을 보이자. k + 1이 짝수인 경우는 당연히 (C_k+1)가 성립하므로, k가 짝수일 경우 (C_k+1)이 성립함을 보이면 충분하다. 그러므로 k가 짝수라고 가정하자. 즉 어떤 양의 정수 l에 대하여 k = 2 · l 이다. 이때 (k + 1) + 1 = 2 · l + 2 = 2 · (l + 1)이므로 (k + 1) + 1이 짝수이다. *강한 귀납법을 사용하면 더 간단히 증명된다.