1
$\begingroup$

Please help me to study the following simple cases:

Let $P$ be a binary predicate symbol. I am trying to find out, if there exists a satisfiable $T$ having infinite models only, for the following cases:

1) T is under {P} language with "="

2) T is under {P} language with "=" and T is finite

3) T is under {P} language without "="

4) T is under {P} language without "=" and T is finite

Where I am:

1) $\varphi_i \equiv \forall x_1 \forall x_2 ... \forall x_i \exists y \land ^i_{j=1} \lnot( x_j=y)$

$T = \{\varphi_i | i>0 \}$ so there exists a T having only infinite models

2) 4) can probably have use of Löwenheim-Skolem theorem, but I don't see how to apply it properly.

3) No adequate idea so far

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Hint: it is possible to axiomatize that $P$ is the comparison relation for a linear order (i.e., it plays the role of "$\leq$") without endpoints. Think about how those axioms depend on the presence of the equality relation, and how you might modify them to eliminate that dependency while still ensuring your models are infinite.

$\endgroup$
-2
$\begingroup$

To make Mike's answer just a little more explicit:

When $P$ is the inequality symbol of a partial order, it interprets equality in the sense that the definable set $\{m \in M \operatorname{ | } P(m,m)\}$ is exactly the diagonal relation $\{m \in M \operatorname{ | } m = m\}$.

In particular, we know that such a $P$ must satisfy: $$\forall a \forall b, P(a,b) \land P(b,a) \rightarrow P(a,a),$$ $$\forall a \forall b \forall c, P(a,b) \land P(b,c) \rightarrow P(a,c),$$ $$\forall a, P(a,a).$$

After writing these out, can you think of just one more axiom we can add to $T$ such that any chain in our partial order must be infinite? (Hint: given an element $a$ in a partial order $M$, the set of all elements $b$ less than $a$ is $a$-definable.)

$\endgroup$
5
  • $\begingroup$ Do you mean $\forall a \exists b (P(a,b) \land \lnot P(b,a))$ meaning there always exists elem $b$ bigger then whatever $a$ is. I googled for meaning of "a-definable" and haven't found answer:) Seems like T described above answers yes to 2,3,4 $\endgroup$
    – Serg Fillipenko
    Commented Feb 7, 2016 at 18:54
  • $\begingroup$ Yes, that's right. $a$-definable just means "definable if we pretend $a$ is a constant in our language." Generally in model theory, we say that a subset $N \subseteq M$ of a model $M \models T$ is $A$-definable for another subset $A \subseteq M$ if there exists a formula $\varphi(x,x_1, \dots, x_n)$ and parameters $a_1, \dots, a_n \in A$ such that $$N = \{m \in M \operatorname{ | } M \models \varphi[m,a_1, \dots, a_n]\}.$$ $\endgroup$
    – mad_algebraist
    Commented Feb 7, 2016 at 19:30
  • $\begingroup$ How do you force your relation to be antisymetric using axiom 1 without equality sign? It seems like the explanation of this is just in your first sentence, but still I can't get it. $\endgroup$
    – Serg Fillipenko
    Commented Feb 8, 2016 at 18:10
  • $\begingroup$ It won't necessarily be antisymmetric. (In fact, the third axiom makes the first one superfluous. Sorry about the confusion; I was just replacing all instances of "=" with "P(a,a)".) What the third axiom does tell us is that the diagonal relation is contained in $\{m \in M \operatorname{ | } P(m,m)\}$. The containment might not be proper. This doesn't stop us from producing infinite models, though. $\endgroup$
    – mad_algebraist
    Commented Feb 8, 2016 at 19:00
  • $\begingroup$ What my first sentence says is that if you know a priori that P is the inequality of a partial order, the containment mentioned above is an equality. $\endgroup$
    – mad_algebraist
    Commented Feb 8, 2016 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .