3
$\begingroup$

This is a followup question to Sentence equivalent to $\bigwedge_{i=1}^ \infty \sigma_i$ without using infinite conjunctions. We have a language $\mathcal{L}=\{R\}$ (with equality) where $R$ is a binary relation symbol. Let $\tau$ be the sentence saying $R$ is reflexive, symmetric, and transitive. For each $k \geq 1$, let $\sigma_k$ be the sentence saying there is exactly one equivalence class of size $k$.

I have some questions about this setup:

#1: If $\mathcal{A}, \mathcal{B}$ are $\mathcal{L}$-structures such that $\{\tau, \sigma_1, \sigma_2, \dots\}$ is satisfied by both, and if $\mathcal{A}, \mathcal{B}$ both have no infinite equivalence classes, then does this mean $Th(\mathcal{A})=Th(\mathcal{B})$? [Intuitively, I'm guessing this is true, but I don't understand how to see why formally.]

Assuming the answer to #1 is yes, (say $Th(\mathcal{A})=Th(\mathcal{B})=T$) then I have a further dilemma, or "paradox" if you will, that I'm having trouble resolving.

#2: How many complete 1-types of $T$ are there?

One wants to say there are $\aleph_0$ many, because it seems for each $n$ there should exist some complete 1-type $\Sigma_n(v)$ such that the formula $\theta_i(v)$ saying "$v$ is in the equivalence class of size $i$" belongs to $\Sigma_n(v)$ if and only if $n=i$. Moreover, it seems that an arbitrary complete 1-type $\Sigma(v)$ must be of the form $\Sigma_n(v)$ for some $n$, since there are no infinite equivalence classes.

On the other hand, it seems that each $\Sigma_n(v)$ is a principal complete 1-type, isolated by $\theta_i(u)$. [Correct me if I'm wrong. Once we know which equivalence class $u$ is in we know everything there is to know about $u$, so in particular we should have $T \models \forall v(\theta_n(v) \to \phi(v))$ for any $\phi \in \Sigma_n$, right?]

Now there's a theorem which says that a complete theory $T$ has infinitely many complete 1-types iff there exists at least some non-prinicpal complete 1-type. So the above two paragraphs seem to contradict each other. If there are $\aleph_0$ many complete 1-types, then there should be at least some non-prinicipal one. But if they're all principal, then there can't be $\aleph_0$ many. What have I done wrong?

$\endgroup$

1 Answer 1

5
$\begingroup$

Re: 1, yes - in fact, we have the stronger fact $\mathcal{A}\cong\mathcal{B}$ in that case. (More generally, any two $\{R\}$-structures satisfying $\tau$ with the same number of classes of each cardinality are isomorphic.)

Re: 2, you're missing the fact that "there is no infinite class" is not first-order expressible! The theory $T$ in question has the non-principal $1$-type corresonding to "$x$ is an element of an infinite class," even though this isn't realized in $\mathcal{A}$ or $\mathcal{B}$, and this reflects the fact that a structure with no infinite classes may still be elementarily equivalent to a structure with some infinite classes. So there's no paradox here.

(In fact, it's a good exercise to show that $T=Th(\mathcal{A})=Th(\mathcal{B})$ is simply the deductive closure of $\{\tau\}\cup\{\sigma_k:k\in\mathbb{N}\}$.)


Here's a proof that there is only one non-isolated (= non-principal) type and that the $\Sigma_n$s are the only isolated types over $T$:

Suppose $p,q$ are two types over $T$ which are not among the $\Sigma_n$s. Let $\mathcal{M}\models T$ be a model realizing both $p$ and $q$ via $a$ and $b$ respectively. WLOG (apply dLS if necessary) $\mathcal{M}$ is countable, so a fortiori every class in $\mathcal{M}$ is either finite or countably infinite. By assumption on $p$ and $q$ we know that $[a]_\mathcal{M}$ and $[b]_\mathcal{M}$ must be infinite. But then there must be an automorphism $\alpha\in Aut(\mathcal{M})$ with $\alpha(a)=b$. (More generally, whenever $\mathcal{N}\models T$ then the automorphism orbit relation is just $\{(u,v): \vert[u]_\mathcal{N}\vert=\vert[v]_\mathcal{N}\vert\}$, and this is a good exercise - essentially the same one as in the first paragraph of this answer.)

But this means that $a$ and $b$ realize the same types in $\mathcal{M}$, that is, $p=q$. So there is exactly one $(1-)$type over $T$ besides the $\Sigma_n$s. And we already know that this type must then be non-isolated.

$\endgroup$
10
  • $\begingroup$ So, if I understand correctly, my mistake was where I said "Moreover, it seems that an arbitrary complete 1-type $\Sigma(v)$ must be of the form $\Sigma_n(v)$ for some $n$, since there are no infinite equivalence classes."? Is everything else correct? $\endgroup$ Mar 5, 2022 at 22:02
  • $\begingroup$ @Pascal'sWager Yes, that's right. More broadly, "type realized in $\mathcal{X}$" and "type consistent with $Th(\mathcal{X})$" are in general not the same notion, and that's what we're seeing here. $\endgroup$ Mar 5, 2022 at 22:15
  • $\begingroup$ Ok, thanks. I'm still trying to figure out how many complete types of each type (no pun intended) there are. Are the $\Sigma_n$ ($n \in \mathbb{Z}^+$) the only principal ones, or are there more? And are there multiple non-prinicipal ones or only the single one you mentioned in your answer? $\endgroup$ Mar 5, 2022 at 22:21
  • 2
    $\begingroup$ The $\Sigma_n$s are the only principal ones, and there is only the single non-principal type. I think Lowenheim-Skolem is the easiest way to prove this (show that if $\mathcal{M}\models T$ with $a,b\in\mathcal{M}$ not satisfying any of the $\Sigma_n$s, then there is an elementary substructure $\{a,b\}\subseteq\mathcal{N}\preccurlyeq\mathcal{M}$ with $a$ and $b$ in the same automorphism orbit of $\mathcal{N}$). The $n$-types for $n>1$ are not much more complicated. $\endgroup$ Mar 5, 2022 at 22:32
  • 1
    $\begingroup$ @Pascal'sWager Again, think about automorphisms: show that if $a,b\in\mathcal{M}\models T$ and $\vert[a]_\mathcal{M}\vert=\vert[b]_\mathcal{M}\vert<\aleph_0$ (which happens if they each satisfy the same $\Sigma_n$), then there is an automorphism $\alpha\in Aut(\mathcal{M})$ with $\alpha(a)=b$. Note that this is really just a special case of the second exercise mentioned in my answer, which in turn is basically the same as the first. In general, automorphisms (esp. + elementary submodel/extension arguments) provide a very powerful tool for analyzing types. $\endgroup$ Mar 6, 2022 at 4:47

You must log in to answer this question.

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