Relation on X: Symmetry, Reflexivity & Transitivity

  • Thread starter Thread starter sam0617
  • Start date Start date
  • Tags Tags
    Symmetry
AI Thread Summary
The discussion focuses on the properties of relations in set X = {a, b, c}, specifically examining symmetry, reflexivity, and transitivity. The first relation R is symmetric but not reflexive or transitive because it lacks the necessary pairs, such as (b,b), to satisfy transitivity for all elements. The second relation R is both symmetric and transitive, as it holds true for all combinations of elements, demonstrating that aRb and bRa imply aRa. Clarifications were sought regarding why certain conditions do not satisfy transitivity in the first relation, emphasizing that transitivity must hold for all elements, not just some. The conversation concludes with the understanding that adding (b,b) alone would not suffice to make the first relation transitive.
sam0617
Messages
18
Reaction score
1
Let X = { a, b, c }

X x X = { (a,a), (b,b), (c,c) }
{ (a,b), (b,a), (a,c), (c,a) }
{ (b,c), (c,b) }

1. Symmetric but not reflexive or transitive:
R = { (a,b), (b,a), (a,a), (b,c), (c,b) }
How come this is right? Isn't aRb, bRa imply aRa? isn't that transitive? is it because (b,c,), (c,b) is there but not (b,b) the reason why R is not transitive?

I ask because the 2nd question is confusing. Here it is:
2. Symmetric and transitive but not reflexive:
R= { (a,a), (a,b), (b,a), (b,b) }
See how aRb, bRa implies aRa so therefore it's transitive? How come it doesn't hold for the 1st question??

Thank you for any help.
 
Physics news on Phys.org


Transitive means that for ALL x,y,z:

xRy~\text{and}~yRz~\Rightarrow~xRz

It must holds for ALL.

For the first one, it isn't transitive since if you take x=z=a and y=x, then you see that the above is not satisfied. So it doesn't hold for ALL x,y,z. It does hold for some x,y,z. But it does hold for some. But some isn't enough to imply transitivity.

In (2), it does hold for ALL, so it is transitive.
 


micromass said:
Transitive means that for ALL x,y,z:

xRy~\text{and}~yRz~\Rightarrow~xRz

It must holds for ALL.

For the first one, it isn't transitive since if you take x=z=a and y=x, then you see that the above is not satisfied. So it doesn't hold for ALL x,y,z. It does hold for some x,y,z. But it does hold for some. But some isn't enough to imply transitivity.

In (2), it does hold for ALL, so it is transitive.

I'm sorry, I don't understand what the x=z=a and y=x then it wouldn't satisfy above.
Could you explain more?

EDIT: Then to make question 1 transitive, all I would have to add is (b,b) ?
 


Sorry, typo. I meant that if x=z=b and y=c, then it isn't true that bRc and cRb and bRb.

Adding (b,b) would not make it transtive.

Indeed, we also don't have

aRb and bRc => aRc

since (a,c) is not in the relation.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top