등호가 있는 1차 술어 논리를 전제로 한다.
공리 체계라는 것은,
단순히 모든 명제들의 집합의 부분집합을 의미한다. 종종 여기에 consistentcy 조건(해당 명제를 모두 참이 되는 예시가 존재할 것.)이 붙기도 하지만, 일단은 무시하자.
임의의 2 이상의 정수 n에 대해, Pn=∃x_1,∃x_2, ∃x_3, ... , ∃x_n (~x_1=x_2)&(~x_1=x_3)&...(~x_1=x_n)& (~x_2=x_3)&....& (~x_(n-1)=x_n) 이라는 명제라고 하자. 즉, Pn은 x1, x2, x3, ..., xn이 있어서 이들이 모두 서로 다르다는 것을 의미한다.
예를 들어, P2= ∃x_1,∃x_2 (~x_1=x_2) 를 의미한다. 참고로, ~은 부정하는 의미로, x_1≠x_2와 같은 의미이다.
그러면, A={Pn | n은 양의 정수}에 대해서 살펴보자.
A를 만족하는 예시(모델)가 되는 집합 S가 있다고 하면, S는 모든 2 이상의 정수 n에 대해, Pn을 만족, S에서 서로 다른 n개의 원소가 존재해야 한다.
따라서, S의 원소의 개수는 n 이상이다. 따라서, S는 유한 집합이 아니므로 무한 집합이다.
즉, A를 만족하는 모델은 모두 무한집합이다.
반대로 S를 무한 집합이라고 해 보자. 그러면, 모든 2 이상의 정수 n에 대해, S에 서로 다른 n개의 원소가 존재하므로, S는 Pn을 만족한다.
따라서 S는 A의 모든 명제들을 만족한다.
따라서 집합 A는 무한 집합에 대한 공리 체계라고 할 수 있다.
질문 : 그러면 유한 집합에 대한 공리 체계는 어떻게 될까?
