4

Let $T$ be a theory and $\sigma$ a sentence, such that

  • there exists infinite $\mathfrak{A} \models T + \sigma$.
  • there exists finite $\mathfrak{A} \models T + \sigma$.
  • there exists $n \in \mathbb{N}$, such that for all $\mathfrak{A}$ with $|\mathfrak{A}| > n$, $\mathfrak{A} \models T + \neg\sigma$.

Is this possible?

fnimic
  • 436

2 Answers2

7

Certainly.

Consider $\cal L$ to be the language containing one binary relation symbol $<$.

  1. $T$ is the theory stating that $<$ is a linear order (irreflexive, transitive and total).
  2. $\sigma$ is the statement that if there are $n$ different elements in the universe, then $<$ is unbounded. That is:$$\Big(\exists x_1\ldots\exists x_n(\bigvee_{i<n}x_i\neq x_{i+1})\Big)\rightarrow\forall x\exists y(x<y)$$

It's easy to see that $T$ has finite models of any cardinality, as well infinite models. But $\frak A\models\sigma$ then its universe infinite or has less than $n$ different objects.

Asaf Karagila
  • 393,674
1

This question has some good examples of equational theories that only have infinite models as well as the trivial model on one element.

This answer by Alex Kruckman has a Jónsson-Tarski algebra.

$p(x, y)$ is an ordered pair $(x, y)$. $\pi_1$ and $\pi_2$ are the first and second projections respectively. And, furthermore, it's pairs all the way down, so $\pi_1(\pi_1(\pi_1(x)))$ is a valid expression.

  1. $[\forall x y](\pi_1(p(x, y)) = x)$
  2. $[\forall x y](\pi_2(p(x, y)) = y)$
  3. $[\forall z](p(\pi_1(z), \pi_2(z)) = z)$

Call the conjunction of these sentences $T$.

$T$ by itself has infinite models and models of size 1 but no other finite cardinalities (unless you count structures with an empty domain).

We can extend this construction to include a finite number of exceptions that are excused from following the rules to permit models up to size $n$ for some fixed finite $n$.

Let $\varphi_k(x)$ be the well-formed formula $(x \neq c_1 \land x \neq c_2 \land x \neq c_3 \cdots x \neq c_k)$. Let $\varphi_0$ be $\top$.

  1. $[\forall x y](\varphi_{n-1}(x) \land \varphi_{n-1}(y) \to \pi_1(p(x, y) = x)$
  2. $[\forall x y](\varphi_{n-1}(x) \land \varphi_{n-1}(y) \to \pi_2(p(x, y) = y)$
  3. $[\forall z](\varphi_{n-1}(z) \to p(\pi_1(z), \pi_2(z)) = z)$

So, there are now $c_1, c_2, \cdots c_{n-1}$ off to the side, which represent up to $(n-1)$ distinct entities.

The remaining domain without $c_1, c_2, \cdots c_{n-1}$ can have nothing, a single element, or an infinite number of elements in it, giving us at most $n$ elements, or infinitely many, as desired.

Greg Nisbet
  • 11,657
  • 1
    Nice. Of course, if all you want to do is rule out nontrivial finite models, you only need the first two of the three Jónsson-Tarski equations, i.e. an injection $p:A\times A\to A$. – bof Dec 14 '23 at 05:45