1

This is not homework or a test. I just want to better understand when a relation on a set is reflexive, irreflexive, symmetric, anti-symmetric and transitive. https://i.stack.imgur.com/HkxOk.jpg

AND

  • How can it be antisymmetric and symmetric? Why is it not just symmetric since the off main-diagonal 0 is mirrored by 0?
  • Why Transitive?

OR

  • Why is it transitive?

IF THEN

  • Again why transitive?

IF AND ONLY IF

  • Why antisymmetric?

  • Why transitive?

Thank you in advance!

1 Answers1

0

You seem to be struggling with anti0symmetry and Transitivity.

OK, first anti-symmetry.

Anti-symmetric is that for any $a \neq b$: if $aRb$, then not $bRa$

This is vacuously satisfied for both the AND and the IF AND ONLY IF, since in both cases you simply don't have any $aRb$ with $a$ and $b$ distinct in the first place. So, both are anti-symmetric.

But, they are also symmetric. Like you say: it's mirrored by the diagonal

And yes, it's confusing that something can be symmetrical as well as anti-symmetrical ... but this is what the definitions are, and they are both symmetric and anti-symmetric.

OK, then transitivity:

For transitivity we need:

For any $a,b,c$:L if $aRb$ and $bRc$, then $aRc$

OK, I'll just do the AND, and I'll let you do the others.

Now, for AND, the only time we have $aRb$ and $bRc$ is when $a=b=c=1$. And, we do have $1R1$, i.e. we do have $aRc$ in that case. So, we're good, and the AND is therefore indeed transitive.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • So because T=T and F=F in if-and-only-if it is anti-symmetric and symmetric? While in if-then it is antisymmetric because they are not all equal and the main diagonal is not symmetric? And in transitivity: What is c in this case? I only have two elements T and T –  Nov 17 '19 at 21:44
  • @Bothurin Correct on first two questions. For transitivity: the $a$, $b$, and $c$ need not be different elements. In fact, note that for the AND, in order to have $aRb$ and $bRc$, they all needed to be the same. – Bram28 Nov 17 '19 at 21:48
  • Thank you so much! Pretty sure I have it all under control now thanks to you. Figured out that you can multiply the matrix by itself, and if the matrix product is the same as the original then it is transitive, while if it changes it is not transitive. –  Nov 17 '19 at 22:21
  • @Bothurin You're welcome! :) And yes, multiplying the matrix is indeed something you can do top check transitivity. And that is also how you can change a non-transitive relation into a transitive one: just keep multiplying until it no longer changes: the new relation is called the 'transitive closure' of the original relation. – Bram28 Nov 18 '19 at 00:19