무한 논리

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

수리논리학에서, 무한 논리(無限論理, 영어: infinitary logic)는 무한한 논리합·논리곱·전칭 기호·존재 기호를 나타낼 수 있는 논리 체계이며, 유한 1차 논리를 일반화한다.

정의[편집]

가 무한 정칙 기수이며, 역시 무한 기수라고 하자. 무한 논리 (영어: term)들은 다음과 같다.

  • 임의의 순서수 에 대하여, 변수 는 항이다.
  • 자연수 에 대하여, 만약 항 연산 및 항 이 존재한다면, 은 항이다.

공식(영어: formula)들은 다음과 같다.

  • 자연수 에 대하여, 만약 항 관계 및 항 이 존재한다면, 은 공식이다.
  • (등식) 임의의 항 , 에 대하여, 는 공식이다.
  • (부정) 임의의 공식 에 대하여, 는 공식이다.
  • (무한 논리합) 크기가 미만인, 공식들의 집합 에 대하여,
  • (무한 전칭 기호) 크기가 미만인 변수들의 집합 및 공식 에 대하여, 만약 의 어느 원소도 에서 속박 변수가 아니라면, 는 공식이다.

크기가 미만인 공식들의 집합 에 대하여,

의 약자이다. 마찬가지로, 크기가 미만인 변수들의 집합 가 속박 변수로 등장하지 않는 공식 에 대하여,

의 약자이다. 마찬가지로,

의 약자이며,

의 약자이다. 문장(영어: sentence)은 자유 변수가 없는 공식이다. 이론(영어: theory)은 문장들의 집합이다.

무한 논리는 (유한) 1차 논리와 마찬가지로 증명 이론모형 이론을 정의할 수 있다. 논리 가 다음 조건을 만족시키면, 완전 논리(영어: complete logic)라고 한다.

  • 어떤 문장 이 모든 모형 에서 성립한다면, 의 증명이 존재한다.

논리 가 다음 조건을 만족시키면, 강완전 논리(영어: strongly complete logic)라고 한다.

  • 임의의 이론 및 문장 에 대하여, 만약 라면 이다. 여기서 는 임의의 모형 에 대하여, 만약 라면 라는 뜻이다.

강완전성은 완전성보다 더 강한 조건이다. 즉, 모든 강완전 논리는 완전 논리이나, 그 역은 일반적으로 성립하지 않는다.

성질[편집]

만약 가 강완전 논리라면, 강콤팩트 기수이다.

[편집]

대표적인 무한 논리로는 다음을 들 수 있다.

  • . 이는 (유한) 1차 논리이며, 또한 강완전 논리이다 (괴델의 완전성 정리).
  • . 이는 완전 논리이지만 강완전 논리가 아니다.

역사[편집]

데이나 스콧알프레트 타르스키가 1958년에 도입하였다.[1][2]

응용[편집]

무한 논리는 집합론에서 약콤팩트 기수·강콤팩트 기수 등의 큰 기수들을 정의할 때 쓰인다.

참고 문헌[편집]

  1. Scott, D.; Tarski, A. (1958). “The sentential calculus with infinitely long expressions” (PDF). 《Colloquium Mathematicum》 (영어) 6: 165–170. ISSN 0010-1354. 
  2. Tarski, A. (1958). “Remarks on predicate logic with infinitely long expressions” (PDF). 《Colloquium Mathematicum》 (영어) 6: 171–176. ISSN 0010-1354. 

외부 링크[편집]

같이 보기[편집]