Computability and Logic by Boolos and Burgess says that formula $\Gamma_d$ in example 12.12

∀x∀y(∃u(u ≠ x ∧ u ≡ x) ∧ ∃v(v ≠ y ∧ v ≡ y)) → x ≡ y) 

supports models, whose domain is partitioned into equivalence classes of any size, e.g.

enter image description here

is possible. Yet, I do not understand how this is possible. Suppose my x is the first dot. Then, I can find u, which is the second dot. Similarly, let y be the first dot in the second equivalence class and another dot v is in its companion in the eqivalence class. The formula says that x and y must be in the same equivalence class. But they are obviously not!

Are they trying to cheat me?


1 Answer 1


They are not trying to cheat you. You need to read the text of Example 12.12, following the formula. It says:

A denumerable model of $\Gamma_d$ will consist of a denumerable set $X$ with an equivalence relation in which any two elements $a$ and $b$ that are not isolated, that is, that are such that each is equivalent to something other than itself, are equivalent to each other.

Thus $x$ and $y$ in your example must be equivalent in the model, and the picture is not an accurate representation of what $\Gamma_d$ captures.

  • $\begingroup$ The the illustration is indeed inappropriate. My bad. Sorry for the blunder. $\endgroup$
    – Val
    May 12, 2014 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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