0
$\begingroup$

Let $L=\left\{R\right\}$ be a language with only one relation symbol.
Consider these formulas:
$\Psi _1\:=\:\forall x\left(R\left(x,x\right)\right)$
$\Psi _2\:=\:\forall x\forall y\left(R\left(x,y\right)\rightarrow R\left(y,x\right)\right)\:$
$\Psi _3\:=\:\forall x\forall y\forall z\left(R\left(x,y\right)\wedge R\left(y,z\right)\rightarrow R\left(x,z\right)\right)\:$
I need to show $Mod\left\{\Psi _1,\Psi _2,\Psi _3\right\}\ne Mod\left\{\Psi \:_2,\Psi \:_3\right\}$.

So far, i understand the meaning of each formula, but i wonder which relation on any domain, can show that $R$ is symmetric and transitive but not reflexive. Any ideas?

EDITED: Well, i looked at If a relation is symmetric and transitive, will it be reflexive? and it really helpfull! but i want to find other examples just from curiosity ..

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ How about the empty relation? $\endgroup$ – Slade Feb 1 '15 at 22:22
  • $\begingroup$ @Slade, can you elaborate me about empty relation? what does it mean? $\endgroup$ – user2637293 Feb 1 '15 at 22:25
0
$\begingroup$

The empty relation on a nonempty domain is vacuously symmetric and transitive, but not reflexive.

|cite|improve this answer
$\endgroup$
-1
$\begingroup$

Quite generally, if the relation $R(x,y)$ holds, then from symmetry you have $R(y,x)$ and then from transitivity you have $R(x,x)$. So on the face of it symmetry+transitivity indeed imply reflexivity. However, note that we implicitly assumed that there exists such $y$.

So to conclude your question:

Theorem: For a relation that's symmetric and transitive, and that for every $x$ there's a $y$ such that $R(x,y)$, then indeed $R$ is also reflexive.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The implicit assumption isn't that $x\neq y$, it is that $y$ exists at all. $\endgroup$ – James Feb 1 '15 at 22:30
  • $\begingroup$ That's a matter of taste. If you assume that $y$ exists and that $y=x$ then it's like assuming reflexivity in the first place, which is kind of cheating. $\endgroup$ – yohBS Feb 1 '15 at 22:34
  • $\begingroup$ It would be "cheating" if you didn't do both cases, $x= y$ and $x\neq y$. However, your argument, at no point, relies on any implicit assumption that $x\neq y$, it assumed there was a $y$ so that $R(x,y)$. $\endgroup$ – James Feb 1 '15 at 22:38
  • $\begingroup$ OK. I still think it's a matter of taste, but I'll edit my answer. $\endgroup$ – yohBS Feb 1 '15 at 22:47

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