Mathematical Logic

읽기자료

계획

강의 목표

수리논리학이란 수학을 형식적으로 표현하기 위해 만들어진 수학기초론의 분과로서, 철학, 수학, 컴퓨터공학 등 관련된 분야에 영향을 미치었다. 우리가 사용하고 있는 자연언어의 경우 모호함이 존재하고 있어 사람마다 다르게 적용이 되는 한계점을 지니고 있다. 수리논리학은 이러한 한계를 극복하고자 수학적 대상들을 추상화 하여 정의하고, 그 정의를 통해 얻어진 수학적 명제를 올바르게 추론하는 방식에 대해 논의한다. "예를 들어, 우리가 생각하는 숫자, 군, 기하 등의 머리 속의 개념을 어떻게 정의를 내릴 수 있을까?" "이러한 수학적 대상과 공리로 부터 얻어낸 정리들은 우리는 어떻게 이것이 '올바른 결론' 혹은 '증명 과정이 올바르다'를 보일 수 있을까?" 와 같은 수학의 뿌리에 이르게 되는 질문을 해결하고자 한다. 19세기 초 이러한 수학을 공리화 할려는 Hilbert의 시도가 있었지만 이는 실패하였다. 이 스터디를 마치면 우리는 수학의 공리화의 한계점이 어떻게 발생되는지 이해하고 설명할 수 있기를 기대한다.

계산 가능성이론이란 계산이 가능한 함수의 집합을 정의내리고 있다. 우리는 어렴풋이 계산할 수 있는 함수를 알고 있고, 이들을 계산하는 계산기(컴퓨터)-지금 이 페이지를 보고 있는 기계도 컴퓨터-또한 가지고 있다. 그렇지만 이러한 계산 가능한 함수에 대해서 엄밀히 정의를 내리는 고찰은 20세기 초에 이르러서야 이루어졌다. 우리가 알고 있는 사실은 Church's Thesis를 통해 계산 가능한 집합을 Turing machine 혹은 lambda calculus를 통해 정의내리고 있다는 사실을 알고 있지만, 이들의 정의를 살펴보면 지금의 컴퓨터와 연결짓기는 어렵다. 우리는 계산 가능한 집합을 Unlimited Register Machine을 통해 기초적인 공리가 되는 연산을 정의하고, 이를 합쳐 쌓아올림으로써 계산 가능한 함수를 정의한다. 다른 한 편, 우리가 알고 있는 사실은 Halting problem과 같이 모든 문제가 계산이 가능하지는 않다. 우리는 이러한 계산 가능한 집합의 정의를 내림으로써 계산이 불가능한 문제에 대해 생각해 볼 수 있고, 그 한계와 계산 가능함 사이를 고찰하게 될 것이다. 이 스터디를 마치면 우리는 계산 가능한 함수의 집합이 어떻게 정의되는지 이해하고 설명할 수 있기를 기대한다.

1. Mathematical Logic
1. Introduction to Mathematical Logic
2. Syntax of First-Order-Logic
3. Semantics of First-Order Logic
4. Sequent Calculus
5. Completeness theorem
6. The Löwenheim-Skolem and the Compactness Theorem
2. Computability Theory
1. Introduction to Computable Functions (Unlimited Register Machine, Computable, Decidable)
2. Build on Computable Functions (Join, Recursion, Minimalisation)
3. Turing Machine and Church's thesis (other apporaches to computability)
4. Numbering computable functions (Gödel number), Diagonal method, s-m-n theorem, Universal programs
5. Decidability and its applications
6. Gödel's incompleteness theorem

일정표

유용한 자료들

FAQ

Q. 계산이론 수업을 수강중입니다. 도움이 될까요?

A. 아니요. 본 수업의 내용은 2023년 가을학기 계산이론 수업내용과 크게 다릅니다. 아래 책을 참고하시는게 도움이 더 됩니다.

• Michael Sipser, "Introduction to the Theory of Computation"
• Sanjeev Arora and Boaz Barak, "Computational Complexity"
• Christopher Moore and Stephan Mertens, "The Nature of Computation"

Q. 수업을 듣는데 있어서 필요한 선수과목이 있나요?

A. 이산수학을 이수하였으며, 수학적 귀납법에 익숙하다고 가정할 것입니다. 그 이외, 프로그래밍 언어, 알고리듬을 이수하신 경우 도움이 될 것입니다. 첫 강의 슬라이드를 참고해주세요.