Let $\mathcal{L}=\{ \equiv, (c_n)_{n\geq 1},f\}$ and $\Gamma$ a theory. Describe the possible equivalence classes and the number of elements in them.

Question

Let $\mathcal{L}=\{ \equiv, (c_n)_{n\geq 1},f\}$ where $f$ is a unary function symbol, $\equiv$ a binary relation and $c_n$ constant symbols and $\Gamma$ a theory.

Let $\Gamma$ be the theory with the following sentences:

The usual sentence for reflexive, transitive and symmetric for $\equiv$

1. $\forall x,y(x\neq y\to f(x)\neq f(y))$

2. $\forall x(x\equiv f(x))$

3. For each positive integer $n$, the sentence $\underset{0\leq i<n}\wedge c_n\neq c_i$

4. For each odd positive integer $n$, the sentence $f(c_n)=c_{n+2} \wedge \underset{0\leq i\leq n}\wedge c_{n+1}\not\equiv c_i$

5. For each even positive integer $n$ the sentence $f^{(n)}(c_n)=c_n\wedge\underset{1\leq i< n}\wedge f^{i}(c_n)\neq f^{i+1}(c_n)$

For an arbitrary model of $\Gamma$ describe what equivalence classes it could have and how many elements they could have.

So I get from $4.$ that no even constant can be equivalent to any of the constants before it. So for $c_6$ there are at least $5$ constants not equivalent to it.

And I see from $5$ that even constants are cyclic. That from $1$ the function is injective. But in general I'm just not sure how I use sentences in a thoery to start describing equivalence classes.

Answer 1

I state some consequences of the theory:

• the equivalence classes are closed under the function $f$
• the interpretation of constants is injective
• the function over odd constants behaves like a successor function, sending odd constants to their immediate odd successor
• the function over even constants $c_{2n}$ is cyclic order $2n$, but even constants cannot be equivalent to any predecessor constant, as you noticed, therefore these cycles needs to be outside of the subset of interpreted constants: otherwise you'd end up with an even constant being equivalent to a previous even constant or to $c_1$, either case violating axiom 4). In symbols: $$\forall n \quad (\{{f^{(m)}(c_{2n}) : m \in \mathbb{N}}\} \cap \{c_k^M : k \in \mathbb{N}\} = \{c_{2n})\}$$ where $M \models \Gamma$.

A model of this theory is: $$M = \mathbb{N} \sqcup \bigsqcup_{n \ge 1} \mathbb{Z}_{2n}$$ with $f$ interpreted as the successor function and the constants:

\begin{align*} c_{2n-1} &\longmapsto c_{2n-1}^M = n \in \mathbb{N} \\ c_{2n} &\longmapsto c_{2n}^M = \overline{0} \in \mathbb{Z}_{2n} \end{align*}

And also $$M/{\equiv_M} \; = \{\mathbb{N},\mathbb{Z}_{2},\mathbb{Z}_{4},\mathbb{Z}_{6},\ldots\}$$ so the equivalence classes are exactly the different disjoint pieces which compose the model. Moreover $M$ is minimal in the sense that it embeds in every other model of the theory $\Gamma$