수리 논리학

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

수리 논리학은 기호 논리학의 한 분야로, 자연어의 모호성을 피하고 명확한 추론을 위해 기호를 사용한다. 기호와 추론 형식을 활용하여 고전 논리학의 명제를 기호 논리학으로 표현하고 타당성을 검증할 수 있다. 19세기 중반 형식 철학 논리학과 수학의 융합으로 등장했으며, 집합론, 모형 이론, 재귀 이론, 증명론 등 하위 분야를 포함한다. 일차 논리, 고차 논리, 비고전 논리 등 다양한 형식 논리 체계를 사용하며, 컴퓨터 과학, 수학 기초론과도 밀접한 관련을 맺고 있다.

더 읽어볼만한 페이지

논리학 개념 - 추론
추론은 하나 이상의 명제를 전제로 결론을 도출하는 사고 과정으로, 논리학에서는 전제와 결론 간의 관계를 통해 정확성을 판단하며, 연역 추론, 귀납 추론, 가추법 등으로 나뉘고 인공지능 등 다양한 분야에서 활용된다.
논리학 개념 - 마음
마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다.
수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.
수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.

수리 논리학
학문 정보
학문명	수리논리학
영어	mathematical logic
다른 이름	수학 기초론 초수학
연구 분야	논리의 구조 연구 수학의 이론 전개
학문 분야	논리학
주요 개념	괴델의 불완전성 정리 유한의 입장 (형식주의) 무모순성 겐첸 (Gentzen)
파생 분야	컴퓨터 과학
창시자	자료 없음
창시 시기	자료 없음
관련 직업	자료 없음

2. 기호 논리학의 기초

기호 논리학은 자연 언어의 모호성을 피하고 명확한 추론을 위해 기호를 사용하는 논리학의 한 분야이다.

수리 논리학에서 사용되는 기호는 다음과 같다.

언어	기호
그리고	$\cdot , \land$
또는	$\lor$
만일 A 이면 B 이다	$A \subset B ,A \to B$
아니다	$-,\neg$

2. 1. 기호 및 추론 형식

수리 논리학에서 사용되는 기호는 다음과 같다.

언어	기호
그리고	$\cdot , \land$
또는	$\lor$
만일 A 이면 B 이다	$A \subset B ,A \to B$
아니다	$-,\neg$

수리 논리학의 추론 형식은 다음과 같다.

형식	구조	추론
F1	전가언 3단논법(3명제 모두가 가언 명제)	간접추론
F2	혼합가언 전건긍정 3단논법(대전제 가언 ·소전제 정언 명제)	간접추론
F3	혼합가언 후건부정 3단논법(대전제 가언·소전제 정언)	간접추론
F4	혼합선언 부정3단논법(대전제 선언 명제·소전제 정언)	간접추론
F5	드 모르간의 법칙	직접추론
F6	연언 명제	직접추론
F7	연언 명제의 분리(Conjunction Elimination)	직접추론
F8	이중부정	직접추론

2. 2. 고전 논리학과 기호 논리학의 비교

고전 논리학의 명제를 기호 논리학의 기호로 표현하고, 추론 형식을 적용하여 타당성을 검증할 수 있다. 다음은 그 예시이다.

명제	고전 논리학	기호논리학의 기호화
전제 1	만약 A가 B라면 C가 아니거나 D이다.	(A⊂B)⊂(-C∨D)
전제 2	A는 E이거나 또는 C이다.	A⊂(E∨C)
전제 3	A는 B이다.	A⊂B
전제 4	A는 D가 아니다.	A⊂-D
결론1	A는 C가 아니다.	A⊂-C
결론2	A는 E이다.	A⊂E

3. 수리 논리학의 역사

수리 논리학은 19세기 중반, 형식 철학 논리학과 수학이라는 두 전통의 융합을 반영하여 수학의 한 분야로 등장했다. '로지스틱', '기호 논리학', '논리 대수'라고도 불리며, 최근에는 단순히 '형식 논리학'이라고 불리는 수리 논리학은 인공적인 표기법과 엄밀한 연역적 방법을 사용하여 19세기에 걸쳐 정교하게 발전된 논리 이론의 집합이다. 이러한 등장 이전에 논리학은 수사학, ''calculationes''(계산), 삼단 논법, 그리고 철학과 함께 연구되었다. 20세기 전반에는 수학의 기초에 대한 격렬한 논쟁과 함께 근본적인 결과들이 폭발적으로 쏟아져 나왔다.

논리학 이론은 중국, 인도, 그리스 및 이슬람 세계 등 여러 문화권에서 발전했다. 그리스의 방법, 특히 오르가논에서 찾아볼 수 있는 아리스토텔레스 논리 (또는 술어 논리)는 수천 년 동안 서양 과학과 수학에서 널리 적용되고 받아들여졌다. 스토아학파는 특히 크리시푸스를 중심으로 술어 논리의 발전을 시작했다. 18세기 유럽에서는 고트프리트 빌헬름 라이프니츠와 요한 하인리히 람베르트를 비롯한 철학적 수학자들이 형식 논리의 연산을 기호적 또는 대수적으로 다루려는 시도를 했지만, 그들의 노력은 고립된 채 거의 알려지지 않았다.

조지 불과 오거스터스 드 모르간은 논리에 대한 체계적인 수학적 처리를 제시했다. 그들의 연구는 조지 피콕과 같은 대수학자들의 연구를 바탕으로, 전통적인 아리스토텔레스 논리학을 수학의 기초 연구에 충분한 틀로 확장했다. 찰스 샌더스 퍼스는 불의 연구를 바탕으로 관계와 양화자를 위한 논리 시스템을 개발했으며, 1870년부터 1885년까지 여러 논문에서 발표했다.

고틀로프 프레게는 1879년에 출판된 그의 저서 ''개념 표기법''에서 양화자를 포함하는 논리의 독립적인 개발을 제시했으며, 이 저서는 일반적으로 논리학 역사에서 전환점을 나타내는 것으로 간주된다. 그러나 프레게의 연구는 버트런드 러셀이 세기 말 무렵에 그것을 홍보하기 시작할 때까지 알려지지 않았다. 프레게가 개발한 2차원 표기법은 널리 채택되지 않았으며, 현대 텍스트에서는 사용되지 않는다.

1890년부터 1905년까지 에른스트 슈뢰더는 3권으로 구성된 ''논리 대수학 강의''를 출판했다. 이 저서는 불, 드 모르간, 퍼스의 연구를 요약하고 확장했으며, 19세기 말에 이해된 기호 논리학에 대한 포괄적인 참고 자료였다.

수학의 기본 분야에 대한 공리적 시스템의 개발로, 논리학에서 용어 ''산술''은 자연수 이론을 의미한다. 주세페 페아노(Peano, 1889)는 부울과 슈뢰더의 논리 시스템을 변형하여 양자를 추가하여 산술에 대한 일련의 공리들을 발표했는데, 이는 그의 이름(페아노 공리)을 따랐다. 페아노는 당시 프레게의 연구를 알지 못했다. 비슷한 시기에 리하르트 데데킨트는 자연수가 그들의 귀납적 성질에 의해 고유하게 특징지어진다는 것을 보여주었다. 데데킨트는 페아노 공리의 형식적 논리적 특성이 없는 다른 특징을 제안했다. 그러나 데데킨트의 연구는 페아노 시스템에서 접근할 수 없는 정리들을 증명했는데, 여기에는 자연수 집합의 유일성(동형 사상까지)과 다음 함수 및 수학적 귀납법으로부터의 덧셈과 곱셈의 재귀적 정의가 포함되었다.

19세기 중반에 유클리드의 기하학 공리에 결함이 있다는 것이 알려졌다. 니콜라이 로바체프스키가 1826년에 확립한 평행선 공준의 독립성 외에도, 수학자들은 유클리드가 당연하게 여겼던 특정 정리들이 실제로 그의 공리로부터 증명될 수 없다는 것을 발견했다. 힐베르트는 파시의 이전 연구를 기반으로 기하학 공리의 완전한 집합을 개발했다. 기하학의 공리화 성공은 힐베르트가 자연수 및 실수선과 같은 수학의 다른 분야에 대한 완전한 공리화를 모색하게 하는 동기가 되었다.

게오르크 칸토어는 무한 집합론의 기본 개념을 개발했다. 그의 초기 결과는 기수 이론을 개발하고 실수와 자연수가 다른 기수를 갖는다는 것을 증명했다. 다음 20년 동안 칸토어는 일련의 출판물을 통해 초한수 이론을 개발했다. 1891년에 그는 칸토어의 대각선 논법을 도입하고 이 방법을 사용하여 어떤 집합도 그 멱집합과 같은 기수를 가질 수 없다는 칸토어의 정리를 증명하는 실수의 비가산성에 대한 새로운 증명을 발표했다. 칸토어는 모든 집합을 전순서 집합으로 만들 수 있다고 믿었지만, 이 결과에 대한 증명을 제시하지 못했고, 1895년에 미해결 문제로 남겨두었다.

20세기 초, 수리 논리학의 주요 연구 분야는 집합론과 형식 논리였다. 비형식적 집합론에서 여러 역설들이 발견되면서, 수학 자체의 모순 가능성에 대한 의문이 제기되었고, 이는 무모순성 증명의 필요성을 불러일으켰다.

1900년, 다비트 힐베르트는 다음 세기를 위한 23개의 문제 목록 (힐베르트의 문제)을 제시했다. 이 중 첫 번째 두 문제는 각각 연속체 가설 해결과 기본 산술의 일관성 증명이었고, 열 번째 문제는 정수에 대한 다변수 다항식 방정식(디오판토스 방정식)이 해를 갖는지 여부를 결정하는 방법을 제시하는 것이었다. 1928년에 제기된 힐베르트의 ''결정 문제''는 형식화된 수학적 명제가 주어졌을 때, 그 명제가 참인지 거짓인지 결정하는 절차를 묻는 것이었다. 이러한 문제들을 해결하려는 노력은 수리 논리학의 발전에 큰 영향을 미쳤다.

에른스트 체르멜로는 모든 집합이 정렬될 수 있음을 증명했는데, 이는 게오르크 칸토어가 얻지 못했던 결과였다. 이 증명을 위해 체르멜로는 선택 공리를 도입했고, 이는 수학자들과 집합론 개척자들 사이에서 열띤 논쟁과 연구를 불러일으켰다. 체르멜로는 자신의 증명에 대한 비판에 직접적으로 대응하여 자신의 결과에 대한 두 번째 해설을 발표했고, 이는 결국 수학계에서 선택 공리가 일반적으로 수용되도록 만들었다.

선택 공리에 대한 회의론은 순진 집합론에서 발견된 역설들, 즉 체사레 부랄리-포르티의 부랄리-포르티 역설(모든 서수의 모임이 집합을 형성할 수 없음을 보여주는 역설), 버트런드 러셀의 러셀의 역설, 쥘 리샤르의 리샤르의 역설 등에 의해 더욱 강화되었다.

체르멜로는 집합론에 대한 최초의 공리 집합을 제공했다. 이 공리들은 아브라함 프렌켈이 제안한 치환 공리와 함께 현재 체르멜로-프렌켈 집합론(ZF)이라고 불린다. 체르멜로의 공리는 러셀의 역설을 피하기 위해 크기 제한의 원리를 통합했다.

1910년, 러셀과 알프레드 노스 화이트헤드는 ''수학 원리''의 첫 번째 권을 출판했다. 이 기념비적인 작품은 러셀과 화이트헤드가 역설을 피하기 위해 개발한 형식 이론의 완전히 형식적인 틀 내에서 함수와 기수의 이론을 발전시켰다. ''수학 원리''는 20세기의 가장 영향력 있는 작품 중 하나로 여겨지지만, 형식 이론의 틀은 수학의 기초 이론으로서는 널리 받아들여지지 않았다.

프렌켈은 선택 공리가 원소(urelements)를 가진 체르멜로 집합론의 공리들로부터 증명될 수 없음을 증명했다. 이후 폴 코언의 연구는 원소의 추가가 필요하지 않으며, 선택 공리는 ZF에서 증명될 수 없다는 것을 보여주었다.^[4] 코언의 증명은 집합론에서 독립성 결과를 확립하기 위한 중요한 도구인 강제법을 개발했다.^[4]

레오폴트 뢰벤하임과 토랄프 스콜렘은 뢰벤하임-스콜렘 정리(일차 논리가 무한 구조의 기수를 제어할 수 없다는 정리)를 얻었다. 스콜렘은 이 정리가 집합론의 일차 형식화에 적용될 것이며, 따라서 그러한 형식화는 가산 모델을 갖는다는 것을 깨달았다. 이 직관에 어긋나는 사실은 스콜렘의 역설로 알려지게 되었다.

쿠르트 괴델은 박사 학위 논문에서 일차 논리에서 구문론과 의미론 사이의 대응 관계를 확립하는 완전성 정리를 증명했다. 괴델은 완전성 정리를 사용하여 콤팩트성 정리를 증명하여 일차 논리적 귀결의 유한성을 입증했다. 이러한 결과는 일차 논리가 수학자들이 사용하는 지배적인 논리로 자리 잡는 데 기여했다.

1931년 괴델은 ''프린키피아 마테마티카와 관련된 형식적으로 결정 불가능한 명제에 관하여''를 발표하여 충분히 강력하고 효과적인 모든 일차 이론의 불완전성(단어의 다른 의미에서)을 증명했다. 이 결과는 괴델의 불완전성 정리로 알려졌으며, 수학의 공리적 기초에 대한 심각한 제약을 설정하여 힐베르트의 프로그램에 강력한 타격을 가했다. 이는 산술의 형식적 이론 내에서 산술의 무모순성을 증명하는 것이 불가능하다는 것을 보여주었다.

괴델의 정리는 충분히 강력하고 효과적인 모든 공리계의 무모순성 증명이 시스템 자체가 일관성이 있거나, 더 약한 시스템 내에서 얻을 수 없다는 것을 보여준다. 겐첸은 초한 귀납법의 원리와 함께 유한론적 시스템을 사용하여 산술의 무모순성을 증명했다. 겐첸의 결과는 단절 제거와 증명론적 서수의 아이디어를 도입했으며, 이는 증명 이론의 핵심 도구가 되었다. 괴델은 고전 산술의 무모순성을 고차 타입의 직관주의적 산술의 무모순성으로 줄이는 다른 무모순성 증명을 제시했다.

알프레트 타르스키는 모형 이론의 기초를 발전시켰다.

1935년부터 저명한 수학자 그룹이 니콜라 부르바키라는 필명으로 협력하여 백과사전 형식의 수학 텍스트 시리즈인 ''수학 원론''을 출판했다. 이 텍스트는 엄격하고 공리적인 스타일로 작성되었으며 엄밀한 제시와 집합론적 기초를 강조했다. 이 텍스트에서 만들어진 용어, 예를 들어 ''전단사'', ''단사'', ''전사''와 같은 단어, 그리고 텍스트에서 사용된 집합론적 기초는 수학 전반에 걸쳐 널리 채택되었다.

계산 가능성에 대한 연구는 계산 가능성 이론 (혹은 재귀 이론)으로 알려지게 되었다. 초기에는 재귀 함수에 대한 형식화가 괴델과 클리니에 의해 이루어졌고, 이 정의는 튜링 기계를 포함하는 튜링의 형식화와 동등하다는 것이 밝혀졌다. 이를 통해 계산 가능 함수라는 새로운 개념이 발견되었고, 이 정의는 수많은 독립적인 특성을 허용할 정도로 강력하다는 것이 분명해졌다. 괴델은 불완전성 정리에 대한 연구에서 효과적인 형식 시스템에 대한 엄격한 개념이 부족하다는 것을 인식하고, 계산 가능성에 대한 새로운 정의가 이 목적에 사용될 수 있음을 깨달았다.

재귀 이론의 수많은 결과는 1940년대에 스티븐 콜 클리니와 에밀 레온 포스트에 의해 얻어졌다. 클리니는 튜링에 의해 예고된 상대적 계산 가능성의 개념과 산술 위계를 도입했다. 클리니는 나중에 재귀 이론을 고차 함수로 일반화했다. 클리니와 게오르크 크라이젤은 특히 증명 이론의 맥락에서 직관주의 수학의 형식적 버전을 연구했다.

재귀 이론의 중요한 하위 분야는 알고리즘적 해결 불가능성을 연구한다. 결정 문제 또는 함수 문제는 문제에 대한 모든 합법적인 입력에 대해 올바른 답을 반환하는 가능한 계산 가능한 알고리즘이 없을 경우 '''알고리즘적으로 해결 불가능'''하다. 1936년 처치와 튜링에 의해 독립적으로 얻어진 해결 불가능성에 대한 최초의 결과는 결정 문제(Entscheidungsproblem)가 알고리즘적으로 해결 불가능하다는 것을 보여주었다. 튜링은 정지 문제의 해결 불가능성을 확립함으로써 이를 증명했으며, 이는 재귀 이론과 컴퓨터 과학 모두에서 광범위한 영향을 미치는 결과이다.

일반 수학에서 결정 불가능한 문제의 많은 예가 알려져 있다. 군에 대한 단어 문제는 1955년 표트르 노비코프에 의해, 1959년에는 W. 분에 의해 독립적으로 알고리즘적으로 해결 불가능하다는 것이 증명되었다. 1962년 티보르 라도가 개발한 바쁜 비버 문제도 잘 알려진 예이다.

힐베르트의 열 번째 문제는 정수 계수를 갖는 다변수 다항식 방정식이 정수 해를 갖는지 여부를 결정하는 알고리즘을 요구했다. 줄리아 로빈슨, 마틴 데이비스 및 힐러리 푸트남이 부분적인 진전을 이루었고, 이 문제의 알고리즘적 해결 불가능성은 1970년 유리 마티야세비치에 의해 증명되었다.

3. 1. 초기 역사

논리학 이론은 중국, 인도, 그리스 및 이슬람 세계 등 여러 문화권에서 발전했다. 그리스의 방법, 특히 오르가논에서 찾아볼 수 있는 아리스토텔레스 논리 (또는 술어 논리)는 수천 년 동안 서양 과학과 수학에서 널리 적용되고 받아들여졌다. 스토아학파는 특히 크리시푸스를 중심으로 술어 논리의 발전을 시작했다. 18세기 유럽에서는 고트프리트 빌헬름 라이프니츠와 요한 하인리히 람베르트를 비롯한 철학적 수학자들이 형식 논리의 연산을 기호적 또는 대수적으로 다루려는 시도를 했지만, 그들의 노력은 고립된 채 거의 알려지지 않았다.

3. 2. 19세기

조지 불과 오거스터스 드 모르간은 논리에 대한 체계적인 수학적 처리를 제시했다. 그들의 연구는 조지 피콕과 같은 대수학자들의 연구를 바탕으로, 전통적인 아리스토텔레스 논리학을 수학의 기초 연구에 충분한 틀로 확장했다. 찰스 샌더스 퍼스는 불의 연구를 바탕으로 관계와 양화자를 위한 논리 시스템을 개발했으며, 1870년부터 1885년까지 여러 논문에서 발표했다.

고틀로프 프레게는 1879년에 출판된 그의 저서 ''개념 표기법''에서 양화자를 포함하는 논리의 독립적인 개발을 제시했으며, 이 저서는 일반적으로 논리학 역사에서 전환점을 나타내는 것으로 간주된다. 그러나 프레게의 연구는 버트런드 러셀이 세기 말 무렵에 그것을 홍보하기 시작할 때까지 알려지지 않았다. 프레게가 개발한 2차원 표기법은 널리 채택되지 않았으며, 현대 텍스트에서는 사용되지 않는다.

1890년부터 1905년까지 에른스트 슈뢰더는 3권으로 구성된 ''논리 대수학 강의''를 출판했다. 이 저서는 불, 드 모르간, 퍼스의 연구를 요약하고 확장했으며, 19세기 말에 이해된 기호 논리학에 대한 포괄적인 참고 자료였다.

수학의 기본 분야에 대한 공리적 시스템의 개발로, 논리학에서 용어 ''산술''은 자연수 이론을 의미한다. 주세페 페아노(Peano, 1889)는 부울과 슈뢰더의 논리 시스템을 변형하여 양자를 추가하여 산술에 대한 일련의 공리들을 발표했는데, 이는 그의 이름(페아노 공리)을 따랐다. 페아노는 당시 프레게의 연구를 알지 못했다. 비슷한 시기에 리하르트 데데킨트는 자연수가 그들의 귀납적 성질에 의해 고유하게 특징지어진다는 것을 보여주었다. 데데킨트는 페아노 공리의 형식적 논리적 특성이 없는 다른 특징을 제안했다. 그러나 데데킨트의 연구는 페아노 시스템에서 접근할 수 없는 정리들을 증명했는데, 여기에는 자연수 집합의 유일성(동형 사상까지)과 다음 함수 및 수학적 귀납법으로부터의 덧셈과 곱셈의 재귀적 정의가 포함되었다.

19세기 중반에 유클리드의 기하학 공리에 결함이 있다는 것이 알려졌다. 니콜라이 로바체프스키가 1826년에 확립한 평행선 공준의 독립성 외에도, 수학자들은 유클리드가 당연하게 여겼던 특정 정리들이 실제로 그의 공리로부터 증명될 수 없다는 것을 발견했다. 힐베르트는 파시의 이전 연구를 기반으로 기하학 공리의 완전한 집합을 개발했다. 기하학의 공리화 성공은 힐베르트가 자연수 및 실수선과 같은 수학의 다른 분야에 대한 완전한 공리화를 모색하게 하는 동기가 되었다.

게오르크 칸토어는 무한 집합론의 기본 개념을 개발했다. 그의 초기 결과는 기수 이론을 개발하고 실수와 자연수가 다른 기수를 갖는다는 것을 증명했다. 다음 20년 동안 칸토어는 일련의 출판물을 통해 초한수 이론을 개발했다. 1891년에 그는 칸토어의 대각선 논법을 도입하고 이 방법을 사용하여 어떤 집합도 그 멱집합과 같은 기수를 가질 수 없다는 칸토어의 정리를 증명하는 실수의 비가산성에 대한 새로운 증명을 발표했다. 칸토어는 모든 집합을 전순서 집합으로 만들 수 있다고 믿었지만, 이 결과에 대한 증명을 제시하지 못했고, 1895년에 미해결 문제로 남겨두었다.

3. 3. 20세기

20세기 초, 수리 논리학의 주요 연구 분야는 집합론과 형식 논리였다. 비형식적 집합론에서 여러 역설들이 발견되면서, 수학 자체의 모순 가능성에 대한 의문이 제기되었고, 이는 무모순성 증명의 필요성을 불러일으켰다.

1900년, 다비트 힐베르트는 다음 세기를 위한 23개의 문제 목록 (힐베르트의 문제)을 제시했다. 이 중 첫 번째 두 문제는 각각 연속체 가설 해결과 기본 산술의 일관성 증명이었고, 열 번째 문제는 정수에 대한 다변수 다항식 방정식(디오판토스 방정식)이 해를 갖는지 여부를 결정하는 방법을 제시하는 것이었다. 1928년에 제기된 힐베르트의 ''결정 문제''는 형식화된 수학적 명제가 주어졌을 때, 그 명제가 참인지 거짓인지 결정하는 절차를 묻는 것이었다. 이러한 문제들을 해결하려는 노력은 수리 논리학의 발전에 큰 영향을 미쳤다.

에른스트 체르멜로는 모든 집합이 정렬될 수 있음을 증명했는데, 이는 게오르크 칸토어가 얻지 못했던 결과였다. 이 증명을 위해 체르멜로는 선택 공리를 도입했고, 이는 수학자들과 집합론 개척자들 사이에서 열띤 논쟁과 연구를 불러일으켰다. 체르멜로는 자신의 증명에 대한 비판에 직접적으로 대응하여 자신의 결과에 대한 두 번째 해설을 발표했고, 이는 결국 수학계에서 선택 공리가 일반적으로 수용되도록 만들었다.

선택 공리에 대한 회의론은 순진 집합론에서 발견된 역설들, 즉 체사레 부랄리-포르티의 부랄리-포르티 역설(모든 서수의 모임이 집합을 형성할 수 없음을 보여주는 역설), 버트런드 러셀의 러셀의 역설, 쥘 리샤르의 리샤르의 역설 등에 의해 더욱 강화되었다.

체르멜로는 집합론에 대한 최초의 공리 집합을 제공했다. 이 공리들은 아브라함 프렌켈이 제안한 치환 공리와 함께 현재 체르멜로-프렌켈 집합론(ZF)이라고 불린다. 체르멜로의 공리는 러셀의 역설을 피하기 위해 크기 제한의 원리를 통합했다.

1910년, 러셀과 알프레드 노스 화이트헤드는 ''수학 원리''의 첫 번째 권을 출판했다. 이 기념비적인 작품은 러셀과 화이트헤드가 역설을 피하기 위해 개발한 형식 이론의 완전히 형식적인 틀 내에서 함수와 기수의 이론을 발전시켰다. ''수학 원리''는 20세기의 가장 영향력 있는 작품 중 하나로 여겨지지만, 형식 이론의 틀은 수학의 기초 이론으로서는 널리 받아들여지지 않았다.

프렌켈은 선택 공리가 원소(urelements)를 가진 체르멜로 집합론의 공리들로부터 증명될 수 없음을 증명했다. 이후 폴 코언의 연구는 원소의 추가가 필요하지 않으며, 선택 공리는 ZF에서 증명될 수 없다는 것을 보여주었다.^[4] 코언의 증명은 집합론에서 독립성 결과를 확립하기 위한 중요한 도구인 강제법을 개발했다.^[4]

레오폴트 뢰벤하임과 토랄프 스콜렘은 뢰벤하임-스콜렘 정리(일차 논리가 무한 구조의 기수를 제어할 수 없다는 정리)를 얻었다. 스콜렘은 이 정리가 집합론의 일차 형식화에 적용될 것이며, 따라서 그러한 형식화는 가산 모델을 갖는다는 것을 깨달았다. 이 직관에 어긋나는 사실은 스콜렘의 역설로 알려지게 되었다.

쿠르트 괴델은 박사 학위 논문에서 일차 논리에서 구문론과 의미론 사이의 대응 관계를 확립하는 완전성 정리를 증명했다. 괴델은 완전성 정리를 사용하여 콤팩트성 정리를 증명하여 일차 논리적 귀결의 유한성을 입증했다. 이러한 결과는 일차 논리가 수학자들이 사용하는 지배적인 논리로 자리 잡는 데 기여했다.

1931년 괴델은 ''프린키피아 마테마티카와 관련된 형식적으로 결정 불가능한 명제에 관하여''를 발표하여 충분히 강력하고 효과적인 모든 일차 이론의 불완전성(단어의 다른 의미에서)을 증명했다. 이 결과는 괴델의 불완전성 정리로 알려졌으며, 수학의 공리적 기초에 대한 심각한 제약을 설정하여 힐베르트의 프로그램에 강력한 타격을 가했다. 이는 산술의 형식적 이론 내에서 산술의 무모순성을 증명하는 것이 불가능하다는 것을 보여주었다.

괴델의 정리는 충분히 강력하고 효과적인 모든 공리계의 무모순성 증명이 시스템 자체가 일관성이 있거나, 더 약한 시스템 내에서 얻을 수 없다는 것을 보여준다. 겐첸은 초한 귀납법의 원리와 함께 유한론적 시스템을 사용하여 산술의 무모순성을 증명했다. 겐첸의 결과는 단절 제거와 증명론적 서수의 아이디어를 도입했으며, 이는 증명 이론의 핵심 도구가 되었다. 괴델은 고전 산술의 무모순성을 고차 타입의 직관주의적 산술의 무모순성으로 줄이는 다른 무모순성 증명을 제시했다.

알프레트 타르스키는 모형 이론의 기초를 발전시켰다.

1935년부터 저명한 수학자 그룹이 니콜라 부르바키라는 필명으로 협력하여 백과사전 형식의 수학 텍스트 시리즈인 ''수학 원론''을 출판했다. 이 텍스트는 엄격하고 공리적인 스타일로 작성되었으며 엄밀한 제시와 집합론적 기초를 강조했다. 이 텍스트에서 만들어진 용어, 예를 들어 ''전단사'', ''단사'', ''전사''와 같은 단어, 그리고 텍스트에서 사용된 집합론적 기초는 수학 전반에 걸쳐 널리 채택되었다.

계산 가능성에 대한 연구는 계산 가능성 이론 (혹은 재귀 이론)으로 알려지게 되었다. 초기에는 재귀 함수에 대한 형식화가 괴델과 클리니에 의해 이루어졌고, 이 정의는 튜링 기계를 포함하는 튜링의 형식화와 동등하다는 것이 밝혀졌다. 이를 통해 계산 가능 함수라는 새로운 개념이 발견되었고, 이 정의는 수많은 독립적인 특성을 허용할 정도로 강력하다는 것이 분명해졌다. 괴델은 불완전성 정리에 대한 연구에서 효과적인 형식 시스템에 대한 엄격한 개념이 부족하다는 것을 인식하고, 계산 가능성에 대한 새로운 정의가 이 목적에 사용될 수 있음을 깨달았다.

재귀 이론의 수많은 결과는 1940년대에 스티븐 콜 클리니와 에밀 레온 포스트에 의해 얻어졌다. 클리니는 튜링에 의해 예고된 상대적 계산 가능성의 개념과 산술 위계를 도입했다. 클리니는 나중에 재귀 이론을 고차 함수로 일반화했다. 클리니와 게오르크 크라이젤은 특히 증명 이론의 맥락에서 직관주의 수학의 형식적 버전을 연구했다.

재귀 이론의 중요한 하위 분야는 알고리즘적 해결 불가능성을 연구한다. 결정 문제 또는 함수 문제는 문제에 대한 모든 합법적인 입력에 대해 올바른 답을 반환하는 가능한 계산 가능한 알고리즘이 없을 경우 '''알고리즘적으로 해결 불가능'''하다. 1936년 처치와 튜링에 의해 독립적으로 얻어진 해결 불가능성에 대한 최초의 결과는 결정 문제(Entscheidungsproblem)가 알고리즘적으로 해결 불가능하다는 것을 보여주었다. 튜링은 정지 문제의 해결 불가능성을 확립함으로써 이를 증명했으며, 이는 재귀 이론과 컴퓨터 과학 모두에서 광범위한 영향을 미치는 결과이다.

일반 수학에서 결정 불가능한 문제의 많은 예가 알려져 있다. 군에 대한 단어 문제는 1955년 표트르 노비코프에 의해, 1959년에는 W. 분에 의해 독립적으로 알고리즘적으로 해결 불가능하다는 것이 증명되었다. 1962년 티보르 라도가 개발한 바쁜 비버 문제도 잘 알려진 예이다.

힐베르트의 열 번째 문제는 정수 계수를 갖는 다변수 다항식 방정식이 정수 해를 갖는지 여부를 결정하는 알고리즘을 요구했다. 줄리아 로빈슨, 마틴 데이비스 및 힐러리 푸트남이 부분적인 진전을 이루었고, 이 문제의 알고리즘적 해결 불가능성은 1970년 유리 마티야세비치에 의해 증명되었다.

3. 4. 21세기 (현대)

4. 수리 논리학의 하위 분야

1977년에 출판된 ''수학 논리 핸드북''은 현대 수리 논리학을 대략 4개의 영역으로 나누고 있다.

# 집합론

# 모형 이론

# 재귀 이론

# 증명론과 구성적 수학 (하나의 영역의 일부로 간주됨).

각 영역은 뚜렷한 초점을 가지고 있지만, 많은 기술과 결과가 여러 영역에서 공유된다. 이러한 분야 사이의 경계선과 수리 논리학과 다른 수학 분야를 구분하는 선은 항상 명확하지 않다. 괴델의 불완전성 정리는 재귀 이론과 증명론의 이정표일 뿐만 아니라 양상 논리에서의 뢰브의 정리/Löb's theorem^영어를 이끌어냈다. 강제법은 집합론, 모형 이론, 재귀 이론에서 사용되며, 직관주의 수학 연구에서도 사용된다.

범주론의 수학 분야는 많은 형식적인 공리적 방법을 사용하며, 범주적 논리 연구를 포함하지만, 범주론은 일반적으로 수리 논리학의 하위 분야로 간주되지 않는다. 다양한 수학 분야에 적용할 수 있기 때문에, 손더스 매클레인을 포함한 수학자들은 범주론을 집합론과 독립적인 수학의 기초 시스템으로 제안했다. 이러한 기초는 토포스를 사용하며, 토포스는 고전 논리 또는 비고전 논리를 사용할 수 있는 일반화된 집합론 모형과 유사하다.

4. 1. 집합론

'''집합론'''은 대상의 추상적인 모임인 집합에 대한 연구이다. 서수와 기수와 같은 많은 기본적인 개념들은 집합론의 공식적인 공리화가 개발되기 전에 칸토어에 의해 비공식적으로 개발되었다. 최초의 이러한 공리화는 체르멜로에 의한 것이며, 약간 확장되어 현재 수학의 가장 널리 사용되는 기초 이론인 체르멜로-프렝켈 집합론(ZF)이 되었다.

폰 노이만-괴델-베르나이스 집합론(NBG), 모스-켈리 집합론(MK), 새로운 기초(NF)를 포함하여 집합론의 다른 공식화가 제안되었다. 이 중에서 ZF, NBG, MK는 집합의 누적 계층을 설명하는 데 유사하다. 새로운 기초는 다른 접근 방식을 취하는데, 집합 생성 공리에 대한 제한을 대가로 모든 집합의 집합과 같은 대상을 허용한다. 크립키-플라텍 집합론의 시스템은 일반화된 재귀 이론과 밀접한 관련이 있다.

집합론의 두 가지 유명한 명제는 선택 공리와 연속체 가설이다. 체르멜로가 처음 제시한 선택 공리는 비어 있지 않은 집합들의 모임이 주어지면, 그 모임의 각 집합에서 정확히 하나의 원소를 포함하는 단일 집합 ''C''가 있다는 것을 명시한다. 집합 ''C''는 모임의 각 집합에서 하나의 원소를 "선택"한다고 한다. 슈테판 바나흐와 알프레드 타르스키는 선택 공리를 사용하여 고체 공을 유한한 수의 조각으로 분해한 다음 크기 조정 없이 재배열하여 원래 크기의 두 개의 고체 공을 만들 수 있음을 보여주었다. 이 정리는 바나흐-타르스키 역설로 알려져 있다.

연속체 가설은 다비트 힐베르트에 의해 1900년에 그의 23가지 문제 중 하나로 나열되었다. 쿠르트 괴델은 연속체 가설이 연속체 가설이 성립해야 하는 집합론의 구성 가능 우주를 개발함으로써 선택 공리 유무에 관계없이 체르멜로-프렝켈 집합론의 공리로부터 반증될 수 없음을 보여주었다. 1963년에 폴 코언은 연속체 가설이 체르멜로-프렝켈 집합론의 공리로부터 증명될 수 없음을 보여주었다.

집합론의 현대 연구에는 거대 기수와 결정성에 대한 연구가 포함된다. 거대 기수는 ZFC에서 그러한 기수의 존재를 증명할 수 없을 정도로 강한 특정 속성을 가진 기수이다.

4. 2. 모형 이론

'''모형 이론'''은 다양한 형식적 이론의 모형을 연구한다. 여기서 이론은 특정 형식 논리 및 시그니처의 공식 집합이며, 모형은 이론을 구체적으로 해석하는 구조이다. 모형 이론은 보편 대수 및 대수 기하학과 밀접한 관련이 있지만, 모형 이론의 방법은 이러한 분야보다 논리적 고려 사항에 더 중점을 둔다.

특정 이론의 모든 모형 집합을 기본적인 클래스라고 한다. 고전적인 모형 이론은 특정 기본적인 클래스에서 모형의 속성을 결정하거나, 특정 구조 클래스가 기본적인 클래스를 형성하는지 여부를 결정하려고 한다.

양화사 제거 방법은 특정 이론에서 정의 가능한 집합이 너무 복잡할 수 없음을 보여주는 데 사용할 수 있다. 타르스키는 실수 닫힌 체에 대한 양화사 제거를 확립했으며, 이 결과는 실수 체의 이론이 결정 가능함을 보여준다. 그는 또한 자신의 방법이 임의의 표수를 갖는 대수적으로 닫힌 체에도 똑같이 적용될 수 있음을 언급했다. 여기서 발전된 현대의 하위 분야는 o-최소 구조에 관한 것이다.

마이클 D. 몰리가 증명한 몰리의 범주 정리에 따르면, 가산 언어의 일차 이론이 어떤 비가산 기수에서 범주적, 즉 이 기수의 모든 모형이 동형이라면 모든 비가산 기수에서 범주적이다.

연속체 가설의 사소한 결과는 연속체보다 적은 수의 비동형 가산 모형을 가진 완전한 이론은 가산 개수만 가질 수 있다는 것이다. 로버트 로슨 보트의 이름을 딴 보트 추측은 연속체 가설과 무관하게도 이것이 사실이라고 말한다. 이 추측의 많은 특수한 경우가 확립되었다.

4. 3. 재귀 이론

재귀 이론(계산 가능성 이론이라고도 불림)은 계산 가능 함수와 튜링 차수(계산 불가능 함수를 같은 수준의 계산 불가능성을 가진 집합으로 나눔)의 성질을 연구한다. 또한 일반 계산 가능성과 정의 가능성의 연구를 포함한다. 재귀 이론은 1930년대 뢰저 페터, 앨론조 처치, 앨런 튜링의 연구에서 시작되었으며, 1940년대 스티븐 콜 클린과 에밀 레온 포스트에 의해 크게 확장되었다.

고전적 재귀 이론은 자연수에서 자연수로의 함수의 계산 가능성에 주목한다. 기본적인 결과는 튜링 기계, 람다 대수 등 다수의 독립적이지만 동치인 특징을 가진 강력하고 표준적인 계산 가능 함수의 클래스를 확립한 것이다. 보다 고도적인 결과는 튜링 차수의 구조나 재귀적 열거 집합이 이루는 격자에 관한 것이다.

일반화된 재귀 이론은 재귀 이론의 여러 개념을 더 이상 유한하지 않은 계산으로 확장한다. 여기에는 고차 타입의 계산 가능성 연구나 초산술 이론 및 알파 재귀 이론 등의 분야를 포함한다.

현대 재귀 이론 연구에는 순수 재귀 이론의 새로운 결과와 마찬가지로, 알고리즘적 무작위성, 계산 가능한 모형 이론, 역수학 등의 응용 연구가 포함된다.

재귀 이론의 중요한 부분 영역에서는 알고리즘적으로 비가해적인 문제를 연구한다. 결정 문제 또는 함수 문제가 '''알고리즘적으로 해결 불가능'''하다는 것은, 임의의 합법적인 입력에 대해 올바른 해를 반환하는 계산 가능한 알고리즘이 존재하지 않는다는 것을 의미한다. 1936년에 앨론조 처치와 앨런 튜링에 의해 독립적으로 얻어진 최초의 결과는 결정 문제가 알고리즘적으로 해결 불가능하다는 것이다. 튜링은 정지 문제의 해결 불가능성을 증명함으로써 이를 증명했다.

일반적인 수학에서도 많은 결정 불가능 문제의 예가 알려져 있다. 군에 대한 단어 문제는 1955년 표트르 노비코프와 1959년 W. 분에 의해 독립적으로 증명되었다. 바쁜 비버 문제는 1962년 티보르 라도에 의해 제시된 또 다른 잘 알려진 예이다.

힐베르트의 열 번째 문제는 다변수 정수 계수 대수 방정식(디오판토스 방정식)이 정수 해를 갖는지 여부를 결정하는 알고리즘의 존재를 묻는 것이다. 부분적인 해답은 줄리아 로빈슨, 마틴 데이비스, 힐러리 퍼트넘 등에 의해 제시되었다. 이 문제의 알고리즘적 비가해성은 유리 마티야세비치에 의해 1970년에 증명되었다.

4. 4. 증명론 및 구성적 수학

증명 이론은 다양한 논리적 추론 시스템에서의 형식적 증명에 대한 연구이다. 이러한 증명은 형식적인 수학적 객체로 표현되어 수학적 기법을 통해 분석이 용이하다. 힐베르트식 추론 시스템, 자연 연역 시스템, 겐첸이 개발한 시퀀트 미적분을 포함한 여러 추론 시스템이 일반적으로 고려된다.

수리 논리의 맥락에서 '''구성적 수학''' 연구는 직관주의 논리와 같은 비고전 논리 시스템에 대한 연구와 예측 가능 시스템에 대한 연구를 포함한다. 예측주의의 초기 지지자 중 한 명은 헤르만 바일이었으며, 그는 예측적 방법만을 사용하여 실해석학의 상당 부분을 개발하는 것이 가능함을 보여주었다.

증명은 완전히 유한한 반면, 구조 내의 진실은 그렇지 않기 때문에 구성적 수학 연구에서는 증명 가능성을 강조하는 것이 일반적이다. 고전적(또는 비구성적) 시스템에서의 증명 가능성과 직관주의적(또는 구성적) 시스템에서의 증명 가능성의 관계는 특히 중요하다. 괴델-겐첸 음의 변환과 같은 결과는 고전 논리를 직관주의 논리에 임베딩(또는 ''논리 변환'')하는 것이 가능하여 직관주의적 증명에 대한 일부 속성을 고전적 증명으로 다시 전송할 수 있음을 보여준다.

최근 증명 이론의 발전에는 울리히 콜렌바흐의 증명 마이닝 연구와 마이클 라트젠의 증명론적 서수 연구가 포함된다.

5. 형식 논리 체계

수학적 논리는 본질적으로 형식 논리 체계를 사용하여 표현된 수학적 개념을 다룬다. 이러한 체계들은 세부 사항에서 많이 다르지만, 고정된 형식 언어로 된 표현만 고려한다는 공통된 속성을 공유한다. 명제 논리 및 술어 논리 체계는 수학의 기초에 대한 적용 가능성, 바람직한 증명론적 속성 때문에 오늘날 가장 널리 연구되고 있다. 2차 논리 또는 무한 논리와 같은 강력한 고전 논리와 비고전 논리와 직관 논리와 같은 논리도 연구된다.

5. 1. 일차 논리

일차 논리는 특정 형식 논리 체계이다. 그 구문론은 잘 정의된 공식으로 유한한 표현만을 포함하며, 의미론은 모든 양화사를 고정된 담론 영역으로 제한함으로써 특징지어진다.

레오폴트 뢰벤하임(Leopold Löwenheim)과 토랄프 스콜렘(Thoralf Skolem)은 뢰벤하임-스콜렘 정리를 얻었는데, 이 정리는 일차 논리가 무한 구조의 기수를 제어할 수 없다고 말한다. 스콜렘은 이 정리가 집합론의 일차 형식화에 적용될 것이며, 따라서 그러한 형식화는 가산 모델을 갖는다는 것을 깨달았다. 이 직관에 어긋나는 사실은 스콜렘의 역설로 알려지게 되었다. 뢰벤하임-스콜렘 정리에 따르면 가산 일차 언어의 문장 집합이 무한 모델을 가지고 있다면, 각 무한 기수의 모델을 적어도 하나 가지고 있다. 이는 일차 공리 집합이 자연수, 실수 또는 다른 무한 구조를 동형사상까지 특징지을 수 없음을 보여준다.

쿠르트 괴델은 박사 학위 논문에서 일차 논리에서 구문론과 의미론 사이의 대응 관계를 확립하는 완전성 정리를 증명했다. 괴델은 완전성 정리를 사용하여 콤팩트성 정리를 증명하여 일차 논리적 귀결의 유한성을 입증했다. 이러한 결과는 일차 논리가 수학자들이 사용하는 지배적인 논리로 자리 잡는 데 기여했다. 괴델의 완전성 정리는 일차 논리에서 논리적 결과의 의미론적 및 구문론적 정의 사이의 동등성을 확립한다. 특정 문장이 특정 공리 집합을 만족하는 모든 모델에서 참이라면, 공리에서 문장에 대한 유한한 추론이 있어야 함을 보여준다. 콤팩트성 정리는 괴델의 완전성 정리 증명의 보조 정리로 처음 등장했으며, 논리학자들이 그 중요성을 파악하고 일상적으로 적용하기 시작하기까지 많은 시간이 걸렸다. 이는 문장 집합이 모델을 갖는 것은 모든 유한 부분 집합이 모델을 갖는 경우와 같고, 즉 모순된 공식 집합은 유한한 모순된 부분 집합을 가져야 함을 의미한다.

1931년 괴델은 ''프린키피아 마테마티카와 관련된 형식적으로 결정 불가능한 명제에 관하여''(On Formally Undecidable Propositions of Principia Mathematica and Related Systems)를 발표하여 충분히 강력하고 효과적인 모든 일차 이론의 불완전성(단어의 다른 의미에서)을 증명했다. 이 결과는 괴델의 불완전성 정리로 알려졌으며, 수학의 공리적 기초에 대한 심각한 제약을 설정하여 힐베르트의 프로그램에 강력한 타격을 가했다. 이는 산술의 형식적 이론 내에서 산술의 무모순성을 증명하는 것이 불가능하다는 것을 보여주었다. 괴델의 불완전성 정리는 일차 공리화에 대한 추가적인 한계를 설정한다. '''제1 불완전성 정리'''는 산술을 해석할 수 있는 일관적이고 효과적으로 주어진 (아래 정의됨) 논리 체계의 경우, 참이지만 (자연수에 대해 유효하다는 의미에서) 해당 논리 체계 내에서 증명할 수 없는 명제가 존재하며 (실제로, 논리 체계와 일치할 수 있는 일부 비표준 산술 모형에서 실패할 수 있음)라고 명시한다. 예를 들어, 페아노 공리를 표현할 수 있는 모든 논리 체계에서 괴델 문장은 자연수에 대해 유효하지만 증명할 수 없다. '''제2 불완전성 정리'''는 산술에 대한 충분히 강력하고, 일관적이며, 효과적인 공리 체계는 자체 일관성을 증명할 수 없으며, 이는 힐베르트 프로그램을 달성할 수 없음을 보여주는 것으로 해석되었다.

괴델의 정리는 충분히 강력하고 효과적인 모든 공리계의 무모순성 증명이 시스템 자체가 일관성이 있거나, 더 약한 시스템 내에서 얻을 수 없다는 것을 보여준다. 이것은 그들이 고려하는 시스템 내에서 형식화될 수 없는 무모순성 증명의 가능성을 열어둔다. 겐첸은 초한 귀납법의 원리와 함께 유한론적 시스템을 사용하여 산술의 무모순성을 증명했다. 겐첸의 결과는 단절 제거와 증명론적 서수의 아이디어를 도입했으며, 이는 증명 이론의 핵심 도구가 되었다. 괴델은 고전 산술의 무모순성을 고차 타입의 직관주의적 산술의 무모순성으로 줄이는 다른 무모순성 증명을 제시했다.

5. 2. 고차 논리 및 기타 논리

고차 논리(고계 술어 논리)는 담론 영역의 원소뿐만 아니라 담론 영역의 부분 집합, 그러한 부분 집합의 집합 및 더 높은 유형의 다른 객체에 대한 양화도 허용한다. 의미론은 각 고차 유형의 양화자가 범위를 갖도록 별도의 영역을 갖는 대신, 양화자가 적절한 유형의 모든 객체를 범위로 갖도록 정의된다. 프레게의 논리와 같이 일차 논리가 개발되기 전에 연구된 논리는 유사한 집합론적 측면을 가지고 있었다. 고차 논리는 더 표현력이 뛰어나 자연수와 같은 구조의 완전한 공리화를 허용하지만, 일차 논리의 완전성 정리 및 콤팩트성 정리와 유사한 정리를 만족하지 않으며, 따라서 증명론적 분석에 덜 적합하다.

일차 논리 외에도 많은 논리가 연구되고 있다. 여기에는 무한한 양의 정보를 제공하는 공식을 허용하는 무한 논리와, 귀납적 정의를 허용하는 고정점 논리가 포함된다. 가장 잘 연구된 무한 논리는

L_{\omega_1,\omega}

이며, 이 논리에서 양화자는 일차 논리와 같이 유한 깊이까지만 중첩될 수 있지만, 공식은 유한 또는 가산 무한 결합과 분리를 포함할 수 있다. 예를 들어

L_{\omega_1,\omega}

공식을 사용하여 객체가 정수임을 표현할 수 있다.

린드스트룀 정리는 축약 정리와 하향 뢰벤하임-스콜렘 정리를 모두 만족하는 일차 논리의 유일한 확장이 일차 논리임을 의미한다.

5. 3. 비고전 논리 및 양상 논리

비고전 논리는 고전 논리와 다른 공리 체계를 갖는 논리 체계를 말한다. 직관주의 논리와 다치 논리 등이 비고전 논리에 속한다.

직관주의 논리는 브라우어의 직관주의 프로그램을 연구하기 위해 하이팅에 의해 개발되었다. 직관주의 논리는 각 문장이 참이거나 그 부정문이 참이라는 배중률을 포함하지 않는다. 클리니의 연구에 따르면, 직관적 증명에서 구성적인 정보를 얻을 수 있으며, 직관적 산술에서 증명 가능한 모든 전역 함수는 계산 가능하다. 이는 페아노 산술과 같은 고전 산술 이론에서는 사실이 아니다.

양상 논리는 특정 공식이 참일 뿐만 아니라 필연적으로 참임을 나타내는 연산자와 같은 추가적인 양상 연산자를 포함하는 논리 체계이다. 양상 논리는 일차 술어 증명 가능성과 집합론적 강제의 속성을 연구하는 데 사용되어 왔다.

6. 컴퓨터 과학과의 관계

컴퓨터 과학에서의 계산 가능성 이론 연구는 수학적 논리학에서의 계산 가능성 연구와 밀접한 관련이 있다. 하지만 강조점에는 차이가 있다. 컴퓨터 과학자들은 종종 구체적인 프로그래밍 언어와 실현 가능한 계산 가능성에 집중하는 반면, 수학적 논리학 연구자들은 종종 계산 가능성을 이론적 개념으로, 그리고 비계산 가능성에 집중한다.

프로그래밍 언어 의미론 이론은 모형 이론과 관련이 있으며, 프로그램 검증 (특히, 모형 검증)도 마찬가지다. 증명과 프로그램 사이의 커리-하워드 대응은 증명 이론, 특히 직관주의 논리와 관련이 있다. 람다 계산 및 조합 논리와 같은 형식적 계산법은 현재 이상화된 프로그래밍 언어로 연구되고 있다.

컴퓨터 과학은 또한 자동 정리 증명 및 논리 프로그래밍과 같은 증명의 자동 검사 또는 발견 기술을 개발하여 수학에 기여한다.

기술 복잡성 이론은 논리를 계산 복잡성과 관련시킨다. 이 분야의 첫 번째 중요한 결과인 페이긴의 정리 (1974)는 NP가 정확히 존재적 2차 논리의 문장으로 표현 가능한 언어의 집합임을 확립했다.

7. 수학 기초론

19세기에 수학자들은 여러 수학 분야에서 논리적 허점과 모순을 발견하였다. 오랫동안 공리적 방법의 본보기로 여겨졌던 유클리드의 기하학 공리가 불완전하다는 것이 밝혀졌다. 무한소 개념과 함수 정의 자체에 대한 문제 제기가 이루어졌고, 바이어슈트라스의 미분 불가능한 연속 함수와 같은 예외적인 사례들이 발견되었다.

칸토어의 무한 집합 연구는 비판에 직면했다. 레오폴트 크로네커는 "신이 정수를 만들었고, 그 외의 모든 것은 인간의 작품이다"라고 주장하며, 유한하고 구체적인 수학적 대상에 대한 연구로 돌아갈 것을 주장했다. 크로네커의 관점은 20세기에 구성주의자들에 의해 계승되었지만, 수학계 전반적으로는 받아들여지지 않았다. 다비트 힐베르트는 무한에 대한 연구를 옹호하며 "칸토어가 창조한 낙원에서 우리를 몰아낼 자는 아무도 없다"라고 말했다.

수학자들은 수학의 광범위한 부분을 형식화할 수 있는 공리 체계를 찾기 시작했다. 함수와 같이 이전에 모호했던 용어의 모호성을 제거하는 것 외에도, 이러한 공리화는 일관성 증명을 가능하게 할 것으로 기대되었다. 19세기에 공리 집합의 일관성을 증명하는 주된 방법은 모델을 제공하는 것이었다. 예를 들어, 비유클리드 기하학은 '점'을 고정된 구면 위의 점으로, '선'을 구면 위의 대원으로 정의함으로써 일관성을 증명할 수 있었다. 그 결과 구조인 타원 기하학 모델은 평행선 공리를 제외한 평면 기하학의 공리를 만족한다.

형식 논리의 발전과 함께, 힐베르트는 공리 체계의 구조를 분석하고, 그 분석을 통해 모순을 증명하는 것이 불가능하다는 것을 보여줌으로써 공리 체계의 일관성을 증명할 수 있는지 질문했다. 이러한 아이디어는 증명론 연구로 이어졌다. 힐베르트는 이 분석이 완전히 구체적이어야 하며, 허용할 방법을 지칭하기 위해 '유한적'이라는 용어를 사용했지만 정확하게 정의하지는 않았다. 힐베르트 프로그램으로 알려진 이 프로젝트는 괴델의 불완전성 정리에 의해 큰 영향을 받았는데, 괴델의 불완전성 정리는 산술의 형식 이론의 일관성이 해당 이론에서 형식화할 수 있는 방법을 사용하여 확립될 수 없음을 보여준다. 겐첸은 초한 귀납법 공리를 추가한 유한적 시스템에서 산술의 일관성을 증명할 수 있음을 보였고, 그가 개발한 기술은 증명론에서 중요한 역할을 했다.

수학 기초의 역사에서 또 다른 흐름은 비고전 논리 및 구성적 수학과 관련이 있다. 구성적 수학 연구는 '구성적'의 다양한 정의를 가진 여러 프로그램을 포함한다. 가장 포괄적인 범위에서, 선택 공리를 사용하지 않는 ZF 집합론의 증명은 많은 수학자들에 의해 구성적인 것으로 간주된다. 구성주의의 더 제한적인 버전은 자연수, 수론적 함수, 자연수 집합(실수를 나타내는 데 사용되어 수학적 분석 연구를 용이하게 함)으로 제한된다. 일반적인 아이디어는 함수 자체가 존재한다고 말하기 전에 함수의 값을 계산하는 구체적인 방법이 알려져 있어야 한다는 것이다.

20세기 초 레이첸 에버르투스 얀 브라우어는 수학 철학의 일부로서 직관주의를 창시했다. 처음에는 제대로 이해되지 않았던 이 철학은 수학 명제가 수학자에게 참이 되기 위해서는 그 사람이 명제를 '직관'할 수 있어야 하며, 그 진실을 믿을 뿐만 아니라 그 진실의 이유를 이해해야 한다고 말했다. 이러한 진실 정의의 결과는 배중률의 거부였는데, 브라우어에 따르면 그들의 부정을 참이라고 주장할 수 없는 명제들이 있었기 때문이다. 브라우어의 철학은 영향력이 있었고, 저명한 수학자들 사이에서 격렬한 논쟁을 일으켰다. 클린과 크라이젤은 나중에 직관주의 논리의 형식화된 버전을 연구했다(브라우어는 형식화를 거부하고, 비형식화된 자연어로 그의 작업을 제시했다). BHK 해석과 크립키 모형의 등장으로 직관주의는 고전 수학과 더 쉽게 조화될 수 있게 되었다.

8. 한국의 수리 논리학

9. 결론

참조

_[1] 웹사이트 "Logic and Computational Complexity {{!}} Department of Mathematics" https://math.ucsd.ed[...] 2024-12-05
_[2] 웹사이트 Computability Theory and Foundations of Mathematics / February, 17th – 20th, 2014 / Tokyo Institute of Technology, Tokyo, Japan http://www.jaist.ac.[...]
_[3] 웹사이트 "Bertić, Vatroslav {{!}} Hrvatska enciklopedija" https://www.enciklop[...] 2023-05-01
_[4] 서적 Cohen 2008
_[5] 서적 SYMBOLIC LOGIC Part I Elementary https://archive.org/[...] Macmillan 1896
_[6] 간행물 日本大百科全書 https://kotobank.jp/[...]
_[7] 간행물 世界大百科事典第２版 https://kotobank.jp/[...]
_[8] 뉴스 美 수리논리학 개척자 코헨 사망 https://news.naver.c[...] 서울신문 2007-04-03
_[9] 뉴스 '시리'가 아직까지 말귀를 못 알아듣는 까닭 https://news.naver.c[...] 블로터 2015-05-14
_[10] 뉴스 '벤 다이어그램'의 창시자 수학자 존 벤 탄생 180주년 http://www.daejonilb[...] 대전일보 2014-08-05
_[11] 뉴스 (김대수의 수학 어드벤처)디지털의 출발점은 논리학자 아리스토텔레스 https://news.naver.c[...] 중앙SUNDAY 2014-11-09
_[12] 뉴스 (김대수의 수학 어드벤처)19세기에 디지털 시대 터 닦은 불멸의 수학자들 https://news.naver.c[...] 중앙SUNDAY 2015-03-01

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com