Prove there is no theory whose models are exactly the interpretations with finite domains

399 Views Asked by At

I'm working through Mendelson's Introduction to Mathematical Logic and I'm having trouble proving the following statement:

'' There is no first-order theory $K$ whose models are exactly the interpretations with finite domains." (ex. 2.57)

I've been trying to argue that any theory $K$ with a model with finite domain also has a model with infinite domain, since we may extend the finite domain into an infinite one. I am however not sure how to go about this formally. I was wondering whether I am on the right track at all an if so, if anyone could help me formalise this idea.

1

There are 1 best solutions below

1
On BEST ANSWER

Claim: "in FOL, there is no theory, $A$, such that ${\cal M}\vDash A\iff |M|<\aleph_0$"

Proof:

Let $$\varphi_n=\exists x_1\cdots\exists x_n\left(\bigwedge_{0<j<i\le n}x_i\ne x_j\right)$$ for all $n\ge2$.

In other words, a model satisfy $\varphi_n$ if it has at least $n$ elements.

Assume for the sake of contradiction that $A$ like above exists, then look at $A\cup\{\varphi_n\}_{n\in\Bbb N_{\ge2}}$, this is finitely satisfiable theory, thus it has a model, but it will have to be an infinite domain model, contradiction.