2
$\begingroup$

Let $\mathcal{L}$ be a language (with equality) containing a binary relation symbol $R$.

Assume $R$ is interpreted as an equivalence relation (so it is reflexive, symmetric, and transitive)

I see that the sentence $\sigma_1$: $\exists! x \forall y(xRy \to x=y)$ says that there is a unique equivalence class of size $1$. Similarly, we can define $\sigma_2$ by $\exists^{=2}x \exists!y(x \neq y \wedge \forall z(zRx \to z=x \vee z=y)$, which says there is a unique equivalence class of size $2$. (Here, the notation $\exists^{=2}$ is an abbreviation for "there exist exactly two" in the obvious sense.)

Similarly, I see that, in principle, one could define $\sigma_k$ be the sentence saying that there is a unique equivalence class of size $k$.

Q: How can we express that there is a unique equivalence class of size $k$ for each $k$?

If infinite conjunctions were allowed, I would just write $\bigwedge_{i=1}^ \infty \sigma_i$ and call it a day. However, they are not.

I was thinking perhaps of adding a sentence $\sigma$ which says "for each equivalence class, there exists a unique equivalence class of size $1$ larger." Then I would write down $\sigma_1 \wedge \sigma$ and call it a day. The only problem is that I don't know how to express $\sigma$ formally. (Is it even possible to express it formally?)

Please let me know if there are any typos in the above.

$\endgroup$

1 Answer 1

7
$\begingroup$

There no such formula.

Let $T=\{\sigma_k:k\in\omega\}$.

Suppose there is a formula $\sigma$ equivalent to $T$. In partucular $T\vdash\sigma$. By compactness a finite subset $T_0\subseteq T$ implies $\sigma$, a contradiction.

$\endgroup$

You must log in to answer this question.

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