Find $\Gamma$ such that any model of $\Gamma$ has an infinite domain.

147 Views Asked by At

As part of a homework assignment for a logic class, I'm supposed to find a finite set $\Gamma$ (I believe of wffs) such that any model of $\Gamma$ has an infinite domain. This is for the predicate calculus, and I'm really not sure how to get started. Every solution I can think of seems to depend on the interpretation of a predicate relation. For example, since infinite sets have no minimal or maximal element I could do something like

$$(\forall x_1) \neg A^{2}_{1}(x_1, f^{2}_{1}(x_1))$$

where $A^{2}_{1}$ is equality and $f^{2}_{1}$ is the successor function. However, this involves a specific interpretation and my understanding is that the set $\Gamma$ should not have any associated interpretation. I could really just use a hint to get me started.

1

There are 1 best solutions below

5
On BEST ANSWER

HINT: You can actually use basically the same idea. All you need is a binary relation symbol $R$ and axioms saying that the relation is a strict linear order, together with $\forall x\,\exists y\,R(x,y)$.