0
$\begingroup$

In the signature (R, =), where R is a 2-place predicate symbol, we consider the theory of infinite sets with an equivalence relation for which all classes are 2-element. Prove the completeness of this theory.

I have no idea how to do it. I know, that the quantification elimination method can work here. But I have a little experience of using it, so I don't know how to use it here.

$\endgroup$

closed as off-topic by Andrés E. Caicedo, Shailesh, Leucippus, JonMark Perry, Mark May 28 '18 at 9:17

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, Shailesh, Leucippus, JonMark Perry
If this question can be reworded to fit the rules in the help center, please edit the question.

2
$\begingroup$

Quantifier elimination is overkill. When you're trying to prove that a theory is complete (or really, thinking about a theory at all) you should begin by trying to describe its models (or at least its countable models) up to isomorphism. For example, the easiest proof that DLO (= the theory of dense linear orders without endpoints) is complete is to show that its only countable model (up to isomorphism) is $(\mathbb{Q};<)$ - this is originally due to Cantor, and the simplest application of the generally-quite-useful back-and-forth method - and now simply note that by the Downward Lowenheim-Skolem theorem any $\aleph_0$-categorical (= only one countable model, up to isomorphism) theory with no finite models must be complete.

(And more generally, any theory without finite models which is categorical in some cardinality must be complete.)

With that example in mind, can you see how to describe the countable models of your theory? (HINT: As a first step, if $\mathcal{M}$ is a countable model of your theory, how many equivalence classes must $\mathcal{M}$ have?)

$\endgroup$

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