1
$\begingroup$

Let $T$ be any first order theory with a countable set of axioms.

As we know from Löweinheim-Skolem theorem if $T$ has a infinite model, then it has an infinite model of any cardinality.

I am now interested in the question whether any such $T$ has an infinite model, or if there are theories which force a finite model.

All ideas to finding a an example, forcing a finite model would end up with an essential core of the axioms being something like. $$ \forall x,y: x = y $$ This looks sound at the first glimps, but only if you have the default meaning of equality in mind. Even if you add all axioms for a theory of equality (reflexivity, transitivity, symmetry, and functional/predicate consistency), there is still the possibility of using an infinite domain and defining all elements to be equal.

So i'd informally conclude that there is always an infinite model for any theory, as long as it has a model at all, since first order logic cannot model semantic equality. My question is now, whether someone has a proof of that statement or whether there is a theory that forces finite domains.

$\endgroup$
14
  • $\begingroup$ What do you mean by "first order logic cannot model semantic equality"? $\endgroup$
    – Asaf Karagila
    Jan 26, 2018 at 9:35
  • $\begingroup$ I mean that it cannot express the properties of a relation $R$ s.t. $$I(R(x,y)) = true \iff \text{x is the same domain element as y}$$. (Where $I$ is the Model interpreation function.) $\endgroup$
    – joeschman
    Jan 26, 2018 at 9:40
  • 1
    $\begingroup$ @AsafKaragila : some model theorists don't take equality to be part of every first-order language, nor don't they take it to always be interpreted as actual equality in all models. I think that's the point of joeschman $\endgroup$ Jan 26, 2018 at 11:02
  • 2
    $\begingroup$ @AsafKaragila In defense of Cori and Lascar, which I think is a very nice book, their default assumption is that languages have equality with its correct semantics. The section "Models that may not respect equality" begins "Our excursion into this topic will be as brief as possible", and it mostly consists of a proof that we don't really lose any generality by requiring $=$ to have its correct semantics. $\endgroup$ Jan 26, 2018 at 19:22
  • 1
    $\begingroup$ @joeschman The standard semantics for first-order logic does require "$=$" to be interpreted in the usual way. Indeed, it's usually even considered a logical symbol, in the same context as $\wedge,\vee,\neg$, etc. This wasn't always the case, but is definitely a feature of modern first-order logic. That is: the meaning of the term "first-order logic" has changed over time, and the usage you employ here is no longer the standard one (and I'm not sure it was ever the default one). $\endgroup$ Jan 26, 2018 at 19:50

1 Answer 1

5
$\begingroup$

According to the standard semantics first-order logic, if $M$ is an structure and $a$ and $b$ are elements of $M$, then $M\models a = b \iff a = b$. To be totally clear, the right hand side $a = b$ refers to equality of $a$ and $b$ as elements of domain of $M$, which is a set.

The symbol $=$ is a logical primitive, not a relation symbol, and it is handled differently. Relation symbols can have arbitrary interpretations in structures, while $=$ is always interpreted as true equality.

So the sentence $\forall x\, \forall y\, x = y$ is true in a structure $M$ if and only if $M$ has at most one element.

Now you may have in mind a nonstandard semantics for first-order logic, in which $=$ can be interpreted in a structure as an arbitrary equivalence relation which is respected by the other symbols in the language. In that semantics, it's true that any theory with a nonempty model has an infinite model. But it's important to remember that such a semantics is nonstandard. In particular, since you asked about it, the upward Löwenheim-Skolem theorem is completely trivial (and uninteresting) in that semantics. If $T$ has any nonempty model, you can just replace any equivalence class in $T$ by an equivalence class of size $\kappa$ for any infinite cardinal $\kappa$. If you think about this a bit, you'll quickly realize that the only interesting notion of "cardinality of a model" is the number of equivalence classes, i.e. the size of $M/=$, at which point you might as well work with the quotient, in which $=$ has its standard semantics.

$\endgroup$

You must log in to answer this question.

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