4
$\begingroup$

The problem is this:

Let $\mathcal{L}$ be the language with a binary relation symbol $\it{R}$. Determine whether the collection $\mathcal{C}_{<\omega}$ of all equivalence relations having equivalence classes of finite size is axiomatizable or finitely axiomatizable.

I have the feeling that this collection is not axiomatizable, but I wasn't able to prove it. I was trying to show that the "complement" of $\mathcal{C}_{<\omega}$, the class of equivalence relations with at least one infinite equivalence class, is not finitely axiomatizable, without success. Can you give me a hint?

EDIT: This is an exercize in the first chapter of an introductory course in mathematical logic, so the solution should be rather simple and not involve advanced concepts.

$\endgroup$
  • $\begingroup$ It’s not closed under ultraproducts. $\endgroup$ – Qiaochu Yuan Sep 14 '19 at 8:24
  • $\begingroup$ thanks for the answer, but we've not introduced ultraproducts and so this problem should be solved without it. $\endgroup$ – Lorenzo Sep 14 '19 at 8:28
  • $\begingroup$ Have you covered the compactness theorem yet? $\endgroup$ – Mark Kamsma Sep 14 '19 at 10:43
  • $\begingroup$ Yes we have. In fact my attempt is using it. $\endgroup$ – Lorenzo Sep 14 '19 at 11:42
5
$\begingroup$

You are right that $\mathcal{C}_{< \omega}$ is not axiomatisable. The usual argument using compactness goes by contradiction. It goes as follows (I'll leave it to you to fill in the details).

  1. Suppose that there is an axiomatisation $T$.
  2. Let $\phi_n$ express "every equivalence class has at least $n$ elements" (exercise: write down such a formula).
  3. Show that $T \cup \{\phi_n : n \in \mathbb{N}\}$ is consistent, using compactness.
  4. Note that $T \cup \{\phi_n : n \in \mathbb{N}\}$ is inconsistent, because any model of it must be in $\mathcal{C}_{< \omega}$, while also satisfying $\phi_n$ for all $n$.
  5. Conclude that we have a contradiction, and so we are done.
$\endgroup$
  • $\begingroup$ I'm not sure I see why it must be inconsistent: satisfying $T \cup \{\phi_{n}: n \in \omega\}$ doesn't simply mean you will have at least one equivalence class for each finite cardinality? $\mathcal{C}_{< \omega}$ poses no bound on the number of equivalence classes. $\endgroup$ – Simone Ramello Sep 14 '19 at 12:45
  • $\begingroup$ @SimoneRamello You are completely right. Luckily it is easily fixed (which I just did in an edit). Thanks for pointing this out, I guess it shows the importance of working out the details. $\endgroup$ – Mark Kamsma Sep 14 '19 at 12:56
  • $\begingroup$ You're welcome! I was also thinking about something along the lines of this. Suppose towards a contradiction that there is an axiomatisation $T$. Expand your language $L$ to $L'$ by adding a unary predicate $C$ and let $\phi$ say that $C$ is a non-empty equivalence class; then consider the formulae $\phi_n$ saying that $C$ has at least $n$ elements, and show $T \cup \{\phi\} \cup \{\phi_n: n \in \omega\}$ is finitely consistent. By compactness, you get a model $M$ that is, in particular, a $L'$-model of $T$. Consider its $L$-reduct $M'$, and you should get a contradiction. $\endgroup$ – Simone Ramello Sep 14 '19 at 12:57
  • $\begingroup$ @SimoneRamello That is also an option, and definitely correct. My first thought was similar: expand the language with an extra constant $c$ and say that the equivalence class of $c$ has $n$ elements for each $n$. The reason I went for the formulation in my answer is because it avoids expanding the language. $\endgroup$ – Mark Kamsma Sep 14 '19 at 13:01
  • $\begingroup$ I always feel a little unsteady when expanding/reducing the language, as if there might be some technical details I'm missing that would break my argument. $\endgroup$ – Simone Ramello Sep 14 '19 at 13:16

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.