0
$\begingroup$

I was wandering how to define an equvalence relation using predicate logic, and suddently I realized that I was probably messing with somenthing relating open and closed formulas...

$\bf{Exercise \;}$: formalize in the language $\mathcal{L}=\{R\}\,$ where $R$ is the only symbol of relation "$R$ is an equivalence relation with at least two classes"

I'm confused about these two formulas:

$${\bf{(1)}}\;\; R(x,y)= R(x,x)\wedge (R(x,y)\longleftrightarrow R(y,x)) \,\wedge \,\forall z\,((R(x,y)\,\wedge\,R(y,z))\longrightarrow\,R(x,z))\;\wedge\;\;\;\;\;\;\;\;\;\; \exists \,v \,\exists \,w\,(R(w,v)\,\wedge \neg (R(w,x)\vee R(v,x)) $$

It's an open formula, what does it say? it's Probably identifying a set of $(x,y)$ that has those properties.

$${\bf{(2)}}\;\; R= \forall x\,\forall y\,R(x,x)\wedge (R(x,y)\longleftrightarrow R(y,x)) \,\wedge \,\forall z\,((R(x,y)\,\wedge\,R(y,z))\longrightarrow\,R(x,z))\;\wedge\;\;\;\;\;\;\;\;\;\; \exists \,v \,\exists \,w\,(R(w,v)\,\wedge \neg (R(w,x)\vee R(v,x)) $$

What's the difference?

Why the formula has to be closed?

$\endgroup$
2
$\begingroup$

1) is indeed an open formula with two free variables, $x$ and $y$. This, however, can only be used to express what it takes for $x$ and $y$ to stand in some relationship $R$ ... it cannot be used to express that R is an equivalence relationship, because that requires you to make a general claim about all pairs of objects in the domain.

So yes, 2) is the way to go. I would recommend a few minor changes though:

  • remove the $R=..$ at the beginning, since that is not part of the logic expression

  • either recycle the quantifiers for each of the reflexivity, symmetry, and transivity part, or have just one set of quantifiers ... you are somewhere in between. Personally, I would recycle the quantifiers so the whole expression becomes one big conjunction ... that way, you can immediately do a conjunction simplification to get the separate parts if needed for a formal proof

  • you can greatly simplify the part about there being at least two classes. All you need is: $\exists x \exists y \, \neg R(x,y)$

So, in sum:

$$\forall x R(x,x) \; \land $$ $$\forall x \forall y (R(x,y)\leftrightarrow R(y,x)) \; \land$$ $$\forall x \forall y \forall z\,((R(x,y)\,\land\,R(y,z))\rightarrow\,R(x,z))\;\land$$ $$ \exists x \exists y \; \neg R(x,y) $$

$\endgroup$

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.