Is first order logic with an equivalence relation and existence of infinitely many objects, complete?

486 Views Asked by At

Lets work in First order logic without equality extended with a primitive binary relation symbol $\rightleftharpoons$, with the following axioms:

Reflexive: $\forall x: x\rightleftharpoons x$

Symmetric: $\forall x,y: x\rightleftharpoons y \to y\rightleftharpoons x$

Transitive: $\forall x,y,z: x\rightleftharpoons y \land y\rightleftharpoons z \to x\rightleftharpoons z$

Existence: $\text{For }n=1,2,3,...\\ \forall x_1,..,x_n \exists y \ (y \not \rightleftharpoons x_1 \land...\land y \not \rightleftharpoons x_n)$

Is this theory complete?

1

There are 1 best solutions below

10
On BEST ANSWER

Yes, because it is $\aleph_0$-categorical and has no finite models.

Also, in standard first-order logic with equality, your first three axioms are tautologies (they can be proved from no hypotheses), so they don't need to be assumed.


After discussion in the comments, it seems you're actually asking about first-order logic without equality. So a model of your theory looks like a set $M$ equipped with an equivalence relation $=$ with infinitely many classes. Any two such models are elementarily equivalent (in first-order logic without equality), so your theory is indeed complete.