I'm looking for an example for a consistent set of sentences $T$ (in first-order logic) that is $\kappa$-categorical (so each two models of $T$ with cardinality $\kappa$ are isomorphic) and that has infinite models (so it's not categorical).

Does anyone know one or how to construct such a set?

  • 2
    $\begingroup$ What about an empty $T$ on the empty language? Its models are the sets, it is $k$-categorical for each cardinal $k$. $\endgroup$ – Berci Jun 8 '15 at 15:27
  • $\begingroup$ Do you want this for arbitrary $k$ or just an example for some $k$. If the latter then unbounded dense linear order works for $k = \omega$. $\endgroup$ – Rob Arthan Jun 8 '15 at 17:09
  • $\begingroup$ From the definition I think it should be arbitrary $k$. $\endgroup$ – xxx Jun 8 '15 at 18:21
  • $\begingroup$ From what definition? $\endgroup$ – Rob Arthan Jun 8 '15 at 20:15

Here's two examples:

Example 1:

Let $L = \{E\}$, where $E$ is a binary relation symbol. Now, we consider the following axioms:

(1) ($E$ is Reflexive) $\psi_1 \equiv (\forall x) (E(x,x))$

(2) ($E$ is Symmetric) $\psi_2 \equiv (\forall x) (\forall y)(E(x,y) \to E(y,x)$

(3) ($E$ is transitive) $\psi_3 \equiv (\forall x) (\forall y) (\forall z) (E(x,y) \wedge E(y,z) \to E(x,z))$

Notice that we now have a theory of $Equivalence$ $classes$

(4) $\varphi_n \equiv $ 'There exists exactly $n$ elements in each each equivalence class'.

(5) (This one is a schema) $\rho_m \equiv$ 'There exists more than $n$ equivalence classes for each $m \in \mathbb{N}$'.

Let $T_n \equiv \psi_1 \cup \psi_2 \cup \psi_3 \cup \varphi_n \bigcup_{i \in \mathbb{N}} \rho_i$. Now, one can easily check that the theory, $T_n$, is complete for any particular $n \in \mathbb{N}$. (Consider two countable models and then demonstrate that they must be isomorphic, hence the theory is complete). Furthermore, it is not difficult to demonstrate that this theory is $\kappa-$categorical for every $\kappa$.

Proof Sketch:

Let $M$, $N$ be two models of $T_n$ of size $\kappa$. Since each model have infinitely many equivalence classes of size $n$ (where $n$ is finite), they must both have $\kappa$ many distinct equivalence classes. Now, just have $F$ be a function which sends each distinct equivalence class in $M$ to a distinct equivalence class in $N$. Since each equivalence class is the same size, we can require $F$ to send the points in $A$ bijectively to the points in $B$. I claim that this map is an isomorphism.

Example 2:

Let $K$ be your favorite finite field. Let $L = \{F_\alpha: \alpha \in K, +, 0 \}$ where each $F_\alpha$ is a unary function symbol for an element of $K$.

Let $T$ be the axiomization of infinite dimensional vector spaces in this language. Now, you can prove that vector spaces over the same field are isomorphic iff they have the same dimension. Finally, the dimension of our vector spaces is identical to it's cardinality. Therefore, this theory is also $\kappa-$categorical for all $\kappa$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.