다이아코네스쿠의 정리 ( Diaconescu's Theorem )

다이아코네스쿠의 정리(Diaconescu's Theorem)는 선택공리가 배중률($\forall P(P\lor\neg P)$)을 함의한다는 정리이다. 고전논리의 가장 기본이 되는 명제인 배중률을 증명할 수 있다고 하면 이상하게 들리겠지만, 이는 엄연한 사실이다. 증명은 생각보다 간단한데, 그 과정은 다음과 같다.

 

Proof:

임의의 술어명제 $P$에 대해 다음과 같은 두 모임을 정의할 수 있다.

$$U=\{x\in\{0,1\}\;|\;x=0\lor P\}\\V=\{x\in\{0,1\}\;|\;x=1\lor P\}$$

위와 같이 정의된 두 모임 $U$와 $V$는 분류 공리꼴에 의해 ZF 공리계 아래에서 집합임이 보장된다.

선택공리를 가정하면, 다음이 성립하는 집합 $\{U,V\}$의 선택함수 $f$가 존재한다.

$$(f(U)\in U)\land(f(V)\in V)$$

따라서 두 집합 $U$, $V$의 정의에 의해 $(f(U)=0\lor P)\land(f(V)=1\lor P)$가 성립하며, 이는 $f(U)\neq f(V)\lor P$를 함의한다.

하지만, $P$가 $U=V$임을 함의하므로 $P$는 $f(U)=f(V)$를 함의하며, 따라서 $f(U)\neq f(V)$는 $\neg P$를 함의한다.

따라서 $P\lor\neg P$가 성립한다.

$\blacksquare$

 

여담이지만, 위 증명 과정에서 정의한 두 집합 $U$와 $V$가 유한집합임은 배중률을 가정해야만 보장되므로 배중률을 증명하는 과정에서는 사용할 수 없다. 그렇기 때문에 ZF 공리계로부터 증명 가능한 유한 선택공리를 사용할 수 없고, 선택공리의 가정이 필요했던 것이다. 심지어는 ZF 공리계가 유한 선택공리를 함의하는 것의 증명 또한 배중률을 사용하기 때문에 $U$와 $V$가 유한집합이라 가정하더라도 선택공리를 가정해야만 한다.