Does there exist a formula of first-order logic that is satisfiable only on structures with infinite domains?

3.8k Views Asked by At

I am curious to know if there exists a formula of first-order logic without identity =, that is satisfiable only on structures with infinite domain.

Does there exist such a formula, and if so, what is it?

2

There are 2 best solutions below

0
On

Given any sentence with equality which is satisfied only in infinite structures, you can get one without equality by replacing $=$ with an equivalence relation everywhere. That is, replace every instance of $=$ by a new binary relation symbol $R$ and add a subsentence saying $R$ is an equivalence relation to your sentence.

16
On

If the semantics does not allow for the empty structure, you can see :

$\forall x \lnot R(x,x) \land \forall x \forall y \forall z (R(x,y) \land R(y,z) \to R(x,z)) \land \forall x \exists y R(x,y)$.