공리 집합론 (Axiomatic Set Theory) 칸토어(G. Cantor) 집합론 (원시적인 형태) 공집합 { }, {1, 2777771}, {{}, {1}} … x A: x는 A의 원소이다. A B: A는 B의 부분집합이다. AB, AB A = {x: x는 소크라테스를 읽은 한국인} A = {x: P(x)}는 집합이다.

러셀의 모순(Rusell’s Paradox) N  N C = {x: x는 x x를 만족하는 집합} C가 집합이라면 C  C 이라면 C C C C 이라면 C  C 즉 모순이다.

체르멜로 프랜켈 (Zermelo-Fraenkel) 공리집합론 클래스 도입, 집합은 클래스의 원소가 되어야 한다. A ∋ A_1 ∋ A_2 ∋ A_3 ∋ A_4 ∋…. 는 존재하지 않는다. 공리들

수학의 기초로서의 집합론 모든 수학적 관계는 집합들의 관계로 이해해야 한다. A, B 집합, A와 B의 관계란 AxB의 부분집합을 말한다. 함수, 순서등이 이렇게 표현된다. 정수, 실수, 더하기, 곱하기 군,환,모듈,체, 유클리드공간, 비유클리드공간…..

칸토어의 수 (Ordinal) 0 = {}, 1={{}}, 2={{},{{}}}, …. A+1 = A {A} 내부에 순서가 정해져 있다.  = {0,1,2,3,4, ….} 더하기 곱하기를 정할 수는 있다. (문제가 많음) +1 = {0,1,2,3,4,…..,} 2= {0,1,2,3,…., , +1, +2, …} 2 = {0,1,2,3, …, , +1, +2, …, 2, …, 3, …, …., n,…}

Cardinal Card(R) > Card(Q) = Card(Z) 1, ½, 1/3, ¼, 1/5, …… 2, 2/2,2/3,2/4,2/5,….. 3, 3/2, 3/3,3/4,3/5,….. R A1=0.0011245… A2=1.2341567… A3=0.5746000… ……… 대각수에서 각 digit을 한 개씩 바꾼 수는 리스트에 없다.

초한수 aleph0, aleph1, aleph2, ….. aleph0 + aleph1 = alph1,…. 2aleph0 = aleph1? …..(연속체가설) P(A) = 2A 로 정의됨 칸토어 (p. 82 II) Card A < Card P(A)

Card A < Card P(A) A의 원소 -> P(A)의 원소 y -> A(y)={a, c, d} ⊂ A z -> A(z)={a, c, d, e} ⊂ A t -> A(t) = {a, b, c, d} ⊂ A …. U = {x| x ∉ A(x)} w -> U w가 U의 원소라면 w ∉ A(w)=U w가 U의 원소가 아니라면 w ∊ A(w) = U 즉 모순이다.

힐베르트 계획(Hilbert Program) 힐베르트(1862-1943) 수학의 공리화 공리체계의 완전성을 주장: 즉 수학적으로 제대로 만들어진 질문은 답이 있다. 예: 삼각형의 각의 합은 180도이다. Godel에 의해서 충분히 복잡한 공리체계는 항상 결정불가능인 명제가 존재한다는 것이 보여졌다.

괴델정리 정수와 덧셈, 곱하기등이 있는 어떠한 공리체계도 결정이 불가능한 명제가 있다. (2nd order logic) Godel, Escher, Bach 저자 D. Hofstadter (Pulitzer Prize)

Epimenides paradox The following sentence is false. The preceding sentence is true.

Richard Paradox 자연수가 가질수 있는 모든 성질들의 정의를 나열한다. 즉 성질 1개 <-> 자연수 어떤자연수가 그자연수가 가르치는 성질을 가지지 않는 경우 리차드수라한다. N을 리차드 성질에 해당하는 자연수라하자. 그러면 N이 리차드 <-> N은 리차드가 아니다. 모순이다 이것은 잘못되었다. 왜냐하면 리차드성질은 리스트에 없기때문이다.(meta-mathematical) 괴델정리는 이러한 어려움이 없다.

(*) 이쪽에서 별표를 부친 명제는 증명 불가능이다. (*) 이쪽에서 별표를 부친 명제는 증명 불가능이다. 이 명제는 참또는 거짓이다. 거짓이라면 이 명제는 증명가능이고 즉 참이다. 즉 이 명제는 참이다. 이 명제가 참이라면 이명제는 증명불가능이다. 즉 참이지만 증명이 불가능이 명제가 존재한다.

괴델정리 Godels proof (New York Univ. Press 2001) 모든 명제는 산술의 문제로 바꿀수 있으며 명제의 증명도 산술화 된다. (괴델산술화) 만약 모든 명제가 참 또는 거짓이며 그에 대한 증명이 항상존재한다고 하자. 모든 명제와 증명을 나열하자. (y의 괴델수 17) ∃x Dem(x, z) 괴델수 z인 명제의 괴델수 x증명 sub(y, 17, y) y가 괴델수인 공식의 17변수를 y의 괴델수로 치환 ~(∃x) Dem(x, sub(y, 17, y)) 괴델수를 n ~(∃x) Dem(x, sub(n, 17, n)) 은 증명불가능 (sub(n, 17, n)은 이 공식의 괴델수)

현대 논리학의 탄생 Proof theory, Model theory Tarski, Robinson, Cohen (연속체 가설의 결정 불가능성) Computability theory Church, Turing, Kleene

언어와 문법 (languages, grammar) 과거의 문법: 법률처럼 조직되어 해서 안될일들의 망라 Syntactic structure, grammar 언어의 역사, 진화연구 (과학적 접근) Saussure, Boas, Bloomfield Chomsky의 생성문법 정규 문법 <-> finite state automata (computer 의 일종)

언어와 문법 (languages, grammar) 과거의 문법: 법률처럼 조직되어 해서 안될일들의 망라 Syntactic structure, grammar 언어의 역사, 진화연구 (과학적 접근) Saussure, Boas, Bloomfield Chomsky의 생성문법 정규 문법 <-> finite state automata (computer 의 일종)

언어와 문법 (languages, grammar) 과거의 문법: 법률처럼 조직되어 해서 안될일들의 망라 Syntactic structure, grammar 언어의 역사, 진화연구 (과학적 접근) Saussure, Boas, Bloomfield Chomsky의 생성문법 정규 문법 <-> finite state automata (computer 의 일종)

생성(영)문법 <sentence> -> <subject><predicate> <subject> -> <noun phrase> <noun phrase> -> <noun> <noun phrase> -> <noun><conjunction><noun> <conjunction> -> and <noun>-> Jack <noun> -> Jill

<predicate> -> <verb><prepositional phrase> <propositional phrase> -> <proposition><article><noun> <preposition> -> up <article> -> the <noun> -> hill Jack and Jill ran up the hill

S(sentence) -> DNP(noun phrase) VP (verb phrase) VP -> V(verb) DNP PP (prepositional phrase) -> P(preposition) DNP DNP -> DET NP DNP -> DNP PP NP -> A(adjective) NP N -> NP The womans runs to the big car

Formal grammar G=(N,T,P,S) N finite set of nonterminal symbols T terminal symbols (N, T disjoint) P productions 생성자 S sentence symbol 문장기호 P의 원소 aAb -> awb (A = S or nonterminal symbol, w ∊ (N∪T)*

언어(language) L(G) = {w∈T*: S =>* w} G N={A}, T={a,b} S -> A, A -> aAb, A-> ab S => A => aAb => aaAbb => aaabbb L(G) = {akbk: 모든 k ≧1} G1 N={A, B, C}, T={a, b,c} P: S -> A, A -> aABC, A-> abC, CB -> BC, bB-> bb, bC -> bc, cC->cc L(G1) = {akbkck: 모든 k ≧1}