무한 논리

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

정의

$\kappa$가 무한 정칙 기수이며, $\lambda \leq \kappa$ 역시 무한 기수라고 하자. 무한 논리 $L_{\kappa \lambda }$의 항(영어: term)들은 다음과 같다.

• 임의의 순서수 $\alpha \leq \lambda$에 대하여, 변수 $x_{\alpha }$는 항이다.
• 자연수 $n\in \mathbb {N}$에 대하여, 만약 $n$항 연산 $f$ 및 항 $t_{1},t_{2},\dots ,t_{n}$이 존재한다면, $f(t_{1},\dots ,t_{n})$은 항이다.

$L_{\kappa \lambda }$의 공식(영어: formula)들은 다음과 같다.

• 자연수 $n\in \mathbb {N}$에 대하여, 만약 $n$항 관계 $R$ 및 항 $t_{1},t_{2},\dots ,t_{n}$이 존재한다면, $R(t_{1},t_{2},\dots ,t_{n})$은 공식이다.
• (등식) 임의의 항 $s$, $t$에 대하여, $s=t$는 공식이다.
• (부정) 임의의 공식 $\phi$에 대하여, $\lnot \phi$는 공식이다.
• (무한 논리합) 크기가 $\kappa$ 미만인, 공식들의 집합 $\Phi$에 대하여, $\bigvee \Phi$
• (무한 전칭 기호) 크기가 $\lambda$ 미만인 변수들의 집합 $X$ 및 공식 $\phi$에 대하여, 만약 $X$의 어느 원소도 $\phi$에서 속박 변수가 아니라면, $\forall X\colon \phi$는 공식이다.

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

$\bigwedge \Phi$

는

$\lnot \bigvee \{\lnot \phi \colon \phi \in \Phi \}$

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

$\exists X\colon \phi$

는

$\lnot \forall X\colon \lnot \phi$

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

$\phi \implies \chi$

는

$\lnot \phi \lor \chi$

의 약자이며,

$\phi \iff \chi$

는

$\bigwedge \{\phi \implies \chi ,\chi \implies \phi \}$

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

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

• 어떤 문장 $\phi \in L_{\kappa ,\lambda }$이 모든 모형 $M$에서 성립한다면, $\phi$의 증명이 존재한다.

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

• 임의의 이론 ${\mathcal {T}}$ 및 문장 $\phi$에 대하여, 만약 ${\mathcal {T}}\models \phi$라면 ${\mathcal {T}}\vdash \phi$이다. 여기서 ${\mathcal {T}}\models \phi$는 임의의 모형 $M$에 대하여, 만약 $M\models {\mathcal {T}}$라면 $M\models \phi$라는 뜻이다.

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

성질

만약 $L_{\kappa \kappa }$가 강완전 논리라면, $\kappa$는 강콤팩트 기수이다.

예

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

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

역사

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

응용

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

외부 링크

• Bell, John L. (2012년 2월 22일). “Infinitary logic”. 《Stanford Encyclopedia of Philosophy》 (영어). 스탠퍼드 대학교. 
• Marker, David (2007). “Infinitary logic” (PDF) (영어). 

같이 보기

• 약콤팩트 기수
• 강콤팩트 기수