무한 논리

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

정의

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

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

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

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

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

${\displaystyle \bigwedge \Phi }$

는

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

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

${\displaystyle \exists X\colon \phi }$

는

${\displaystyle \lnot \forall X\colon \lnot \phi }$

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

${\displaystyle \phi \implies \chi }$

는

${\displaystyle \lnot \phi \lor \chi }$

의 약자이며,

${\displaystyle \phi \iff \chi }$

는

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

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

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

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

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

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

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

성질

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

예

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

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

역사

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

응용

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