How to show "a set which is infinite" can not be finitely axiomatized?

88 Views Asked by At

I met a strange question which gives me a Language L which only has one unary Relation R.(Set R) My concern is how to prove that the theory which axiomatizes "R is infinite" can not be finite.

We know that the theory which axiomatizes "R is infinite" can be something like {R has at least 1 element, R has at least 2 elements... etc} which is infinite. But not sure if it can be done with finite sentences.

So generally how-to, I suppose, use compactness theorem to show that "R is infinite" can not be finitely axiomatized?

A previous relevant question is: The theory which axiomizes infinity.

1

There are 1 best solutions below

4
On BEST ANSWER

We can easily spell out "$|R|\le n$" for any fixed $n$, namely $$\exists x_1\ldots \exists x_n \forall y\colon y\in R\to (y=x_1\lor\cdots \lor y=x_n).$$ Hence we also can formulate $|R|> n$ assume we can spell out some $|R|<\infty$. Then the infinitely many sentences $$ |R|<\infty,|R|> 1, |R|> 2,|R|> 3,\ldots $$ cannot have a model. By compactness, hence some finite subset has no model. But any such finite subset just amounts to $$n<|R|<\infty$$ for some $n$. Now exhibit a model where $R$ is finite but larger than $n$ to arrive at a contradiction.