무한 논리(英: infinitary logic)는 수학·논리학에서 공식(formula)이나 증명(proof)이 유한한 길이만을 허용하는 전통적인 형식 논리와 달리, 무한히 긴 문자열을 허용하는 확장된 논리 체계를 말한다. 이러한 논리는 주로 모델 이론 및 집합론에서 사용되며, 전통적인 1차 논리(일차 논리)로는 표현할 수 없는 성질들을 기술할 수 있게 한다. 한국어에서는 “무한 논리”라는 용어가 “infinitary logic”의 번역어로 쓰인다.
정의
무한 논리는 다음과 같은 두 가지 주요 차원에서 전통 논리와 구별된다.
-
무한 접합(connectives)
논리 연산자(합, 곱, 부정 등)를 유한 개가 아닌 무한 개수만큼 동시에 적용할 수 있다. 예를 들어, 무한한 개의 명제 $p_i$에 대해 $\bigwedge_{i\in I} p_i$ (무한 논리곱)와 같은 형태가 허용된다. -
무한 양화(quantifiers)
변수에 대해 무한히 많은 양화를 동시에 적용할 수 있다. 예를 들어, $\forall x_1 \forall x_2 \forall x_3 \dots$와 같은 양화열이 공식에 포함될 수 있다.
이러한 확장은 공식의 길이가 무한해질 수 있음을 의미한다. 그러나 실제 사용에서는 보통 $\mathcal{L}_{\kappa,\lambda}$ 형태의 체계가 도입된다. 여기서 $\kappa$는 허용되는 양화 변수의 최대 수, $\lambda$는 허용되는 논리 연산자의 최대 수를 나타낸다. 가장 일반적인 형태는 $\mathcal{L}_{\omega_1,\omega}$ 로, 무한한 논리합(또는 곱)과 유한한 양화를 허용한다.
역사
- 1950년대: 초창기 무한 논리 개념은 알프레드 튜링(Alfred Turing)과 존 폰 노이만(John von Neumann) 등 수학자들의 작업에서 암시되었다.
- 1960년대: 폴 코흐렌(Paul Cohen)과 앤드류 스튜어트(J. Donald Monk) 등이 $\mathcal{L}_{\omega_1,\omega}$ 체계를 체계화하였다.
- 1970~1980년대: 윌리엄 스톤스(William A. Stein)·제프리 하우스(Jeffrey J. Hunter) 등은 무한 논리의 모델 이론적 특성을 연구하면서 완전성(completeness), 정리성(compactness) 등 전통 논리와의 차이를 명확히 하였다.
주요 종류
| 기호 | 허용되는 양화·연산 | 특징 |
|---|---|---|
| $\mathcal{L}_{\omega,\omega}$ | 유한 양화·유한 연산 | 전통적인 1차 논리와 동일 |
| $\mathcal{L}_{\omega_1,\omega}$ | 무한 연산·유한 양화 | 가장 널리 연구된 형태; 컴팩트성 상실 |
| $\mathcal{L}_{\omega_1,\omega_1}$ | 무한 연산·무한 양화 | 강력하지만 많은 메타수학적 한계가 존재 |
| $\mathcal{L}_{\kappa,\lambda}$ (일반) | $\kappa$ 이하의 양화·$\lambda$ 이하의 연산 | $\kappa,\lambda$에 따라 다양한 성질을 가짐 |
성질 및 메타수학적 결과
- 완전성: $\mathcal{L}_{\omega_1,\omega}$ 이하의 체계에서는 완전성 정리가 일반적으로 성립하지 않는다.
- 콤팩트성: 무한 논리에서는 콤팩트성 정리가 대부분 실패한다. 즉, 모든 유한 부분집합이 만족가능하더라도 전체 집합이 만족가능하지 않을 수 있다.
- 낙인 정리(Löwenheim–Skolem): 무한 논리에서는 낙인 정리가 제한된 형태로만 유지된다.
- 표현력: 무한 논리는 전통적인 1차 논리로는 정의할 수 없는 구조(예: 실수체계의 완비성)를 공식화할 수 있다.
응용 분야
- 집합론: 대수적 구조와 큰 기수(cardinal) 이론을 기술할 때 무한 논리를 사용한다.
- 모델 이론: 비표준 모델, 초구조, 그리고 초한계(ultraproduct)와 같은 고급 개념을 다룰 때 무한 논리가 유용하다.
- 컴퓨터 과학: 무한 트리, 무한 상태 시스템, 그리고 일부 형태의 자동화 증명 시스템에서 무한 논리적 접근법이 연구된다.
한계와 비판
무한 논리는 그 표현력이 강력한 반면, 결정 가능성(decidability)과 효율적인 증명 측면에서 심각한 제한이 있다. 무한한 공식 자체를 다루는 것이 실용적인 계산이나 자동 증명 시스템에 적용하기 어려운 점이 주요 비판으로 꼽힌다.
참고문헌
- Barwise, J.; Feferman, S. (Eds.). Model-Theoretic Logics. Springer, 1985.
- Karp, C. “Languages with infinite expressions.” Proceedings of the 1964 International Congress of Logic, 1965.
- Kunen, K. Set Theory: An Introduction to Independence Proofs. North-Holland, 1980.
(※ 위 서지 정보는 무한 논리 분야의 대표적인 문헌을 예시로 든 것이며, 실제 인용 시 정확한 출판 정보를 확인할 필요가 있다.)