무한 논리

틀:위키데이터 속성 추적 수리논리학에서 무한 논리(無限論理, 틀:Llang)는 무한한 논리합·논리곱·전칭 기호·존재 기호를 나타낼 수 있는 논리 체계이며, 유한 1차 논리를 일반화한다.

정의

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

• 임의의 순서수 $\alpha \le \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 }$의 공식(틀:Llang)들은 다음과 같다.

• 자연수 $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$는 공식이다.
• (부정) 임의의 공식 $\varphi$에 대하여, $\mathrm{\neg }\varphi$는 공식이다.
• (무한 논리합) 크기가 $\kappa$ 미만인, 공식들의 집합 $\mathrm{\Phi }$에 대하여, $\bigvee \mathrm{\Phi }$
• (무한 전칭 기호) 크기가 $\lambda$ 미만인 변수들의 집합 $X$ 및 공식 $\varphi$에 대하여, 만약 $X$의 어느 원소도 $\varphi$에서 속박 변수가 아니라면, $\mathrm{\forall }X:\varphi$는 공식이다.

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

$\bigwedge \mathrm{\Phi }$

는

$\mathrm{\neg }\bigvee \{\mathrm{\neg }\varphi :\varphi \in \mathrm{\Phi }\}$

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

$\mathrm{\exists }X:\varphi$

는

$\mathrm{\neg }\mathrm{\forall }X:\mathrm{\neg }\varphi$

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

$\varphi ⟹\chi$

는

$\mathrm{\neg }\varphi \vee \chi$

의 약자이며,

$\varphi ⟺\chi$

는

$\bigwedge \{\varphi ⟹\chi ,\chi ⟹\varphi \}$

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

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

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

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

• 임의의 이론 $𝒯$ 및 문장 $\varphi$에 대하여, 만약 $𝒯\models \varphi$라면 $𝒯⊢\varphi$이다. 여기서 $𝒯\models \varphi$는 임의의 모형 $M$에 대하여, 만약 $M\models 𝒯$라면 $M\models \varphi$라는 뜻이다.

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

성질

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

예

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

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

역사

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

응용

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

외부 링크

• 틀:웹 인용
• 틀:웹 인용

같이 보기

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