Reading a book (I do not know if I can mention its title) I found these definition (the following is exactly the quotation from the pages of the book): "For a binary relation R on a set Y, that is, R⊆YxY, it is customary to write xRy rather than (x,y)∈R. A binary relation R on a set X is: - reflexive if xRx; - antisymmetric if xRy and yRx imply x=y. An antisymmetric relation may or may not be reflexive" I do not get how an antisymmetric relation could not be reflexive. Can you explain it conceptually? A concrete example aside the theory would be appreciate. Thanks in advance
Asked
Active
Viewed 2,323 times
1
-
Let $Y={1,2,3}$ and $R={(1,1),(1,2),(2,1),(2,2)}$. Is $R$ reflexive? – Thomas Andrews Feb 21 '16 at 21:11
-
The empty relation on any non empty set is an example. – Jonathan Schilhan Feb 21 '16 at 21:12
-
A strict inequality is an example of such a relation; $xRy$ if and only if $x < y$. It's vacuously antisymmetric as there are no $x, y$ with $x < y$ and $y < x$. – pjs36 Feb 21 '16 at 21:14
-
@ThomasAndrews: I guess no since (3,3) does not belongs to R. Am I correct? – user98139 Feb 21 '16 at 21:14
1 Answers
1
The condition for antisymmetry only says that if $xRy$ and $yRx$ are both true, then $x=y$. Put differently, it says that if $x \neq y$, then it's impossible for both $xRy$ and $yRx$ to be true. This doesn't say anything about whether $xRx$ is true or false for some or all $x$.
Conceptually, think of antisymmetry as ensuring that two distinct elements cannot both be $R$ to each other, but it is completely indifferent to whether or not an element is $R$ with itself.
(By the way "reflexive" means that $xRx$ holds for all $x$ in the set. The quote in the question leaves the variable $x$ unquantified in that definition, which is a serious error.)
The relations $<$ and $\leq$ on natural numbers are both antisymmetric, but only the second one is reflexive: Every number $n$ satisfies $n \leq n$, but no number satisfies $n < n$. Antisymmetry holds for both of them because for two distinct numbers $m,n$, only one of $m \leq n$ and $n \leq m$ can be true, and also only one of $m < n$ and $n < m$.
Alon Amit
- 15,591
-
I did not mention it but previously in the book it is specified that the quantifiers "for every..." are understood as written, sorry about that. Now I am thinking about your answers to see whether I get the concept – user98139 Feb 21 '16 at 21:20
-
Ok your examples are great. However, now I am afraid of misunderstanding something "bigger"? If I say that both $xRy$ and $yRx$ are true, then $x=y$, it comes natural to me to substitute $y$ with $x$, and to say that $xRx$ is true too. Clearly this is wrong in the light of what said right now. What is exactly wrong? Where am I overflowing whit this deduction? – user98139 Feb 21 '16 at 21:28
-
You are welcome to substitute x for y, but what do you get in the condition of anti symmetry when you do that? You get: if xRx and xRx are true, then xRx. This is very different from saying "xRx is true for all x". – Alon Amit Feb 21 '16 at 21:35
-
So, I get nothing but a tautology. Am I correct? In particular, this would be true just for the lets say "reflexive" $x$s (since my hypothesis is exactly $xRx$), but nothing can be said about a generic $x$. Right? – user98139 Feb 21 '16 at 21:52
-
The condition "if xRX then xRX" holds always, as you said. It doesn't hold just for those x's for which xRx; it holds for all x's. Make sure you understand why. ("If m is even then m is divisible by 2" is a statement that holds for m=3, too). – Alon Amit Feb 22 '16 at 06:09
-
I am sorry, but I cannot get what you mean with this "The condition "if xRX then xRX" holds always, as you said. It doesn't hold just for those x's for which xRx; it holds for all x's". However, I think I properly get the idea. – user98139 Feb 29 '16 at 09:42