1

in relation, anti-symmetric -> if xRy and yRx, then x=y.

Today, my lecturer said that relation $<$, which represents $(\le \bigwedge\ne)$, satisfies anti-symmetric. He did not prove it and He left it for us to exercise. I have no idea why anti-symmetric is satisfied when the relation is $<$.

Can anyone please explain? thanks

Asaf Karagila
  • 393,674
user1292919
  • 1,895

1 Answers1

4

I will assume that by $<$ you mean the "less than" relation on some totally ordered set such as the real numbers.

Is there ever a situation where you have $x<y$ AND $y<x$ at the same time?

No.

The statement then is an example of a Vacuous Truth since the premise is always false, there is no possible way that there is a contradiction.

A statement is only false if the premise is true while the conclusion is false.

JMoravitz
  • 79,518
  • actually,sorry, it is written as mathematical preferences $\prec$, does it make differences? I do not think it makes any difference... – user1292919 Aug 11 '15 at 05:56
  • It is actually a tricky thing to define $<$ in the first place. Whatever relation you are working with, if you have already proven that $\preceq$ is an anti-symmetric relation and you have defined $\prec$ as $\preceq \wedge \neq$, you can piggyback off of what you know about $\preceq$ that again there are no $x$ and $y$ that satisfy both $x\prec y$ and $y\prec x$ simultaneously. – JMoravitz Aug 11 '15 at 05:59
  • @JMoravitz, yes, I realized something like that will happen. So this is an exercise in antisymmetry AND vacuous statements. Wew. – chhro Aug 11 '15 at 05:59
  • actually, $\preceq$ does not satisfy an anti-symmetric relation because $A\preceq B$ and $B\preceq A$ imply $A \sim B$, but it does not imply $A=B$. But the lecturer said that if we change $\preceq$ to $\prec$, it satisfies an antisymmetric relation..... – user1292919 Aug 11 '15 at 06:13
  • @user1292919 then perhaps $\prec$ should have been defined as $(\preceq \wedge \not \sim)$ instead of as $(\preceq \wedge \neq)$ – JMoravitz Aug 11 '15 at 06:17
  • @JMoravitz even if I define $\prec$ as $\preceq \wedge \nsim$, I can't infer that $\prec$ implies an antisymmetric – user1292919 Aug 11 '15 at 06:18
  • @user1292919 Suppose $\prec$ is defined as $(\preceq \wedge \neq)$. Suppose $\preceq$ is not an anti-symmetric relation. Then there is some $A$ and $B$ such that $A\preceq B$ and $B\preceq A$ while $A\neq B$. Then for this same choice of $A$ and $B$, you have $A\prec B$ (since $A\preceq B$ and $A\neq B$) and you have $B\prec A$ (since $B\preceq A$ and $B\neq A$) while $A\neq B$, so it would fail to be anti-symmetric for the same reason that $\preceq$ failed to be. If it were defined instead as $(\preceq \wedge \not \sim)$ there is no problem (assuming $\sim$ is reflexive). – JMoravitz Aug 11 '15 at 06:21
  • @JMoravitz But from your reasoning, you cannot use $A \prec B$ because $\prec$ is defined as $(\prec \wedge \nsim)$, and $A\sim B$ from your second sentence. – user1292919 Aug 11 '15 at 06:25
  • If we defined $\prec$ as $(\preceq \wedge \not \sim)$ then suppose for contradiction that you have some $A$ and $B$ such that $A\prec B$ and $B\prec A$ simultaneously. You have then (by definition of $\prec$) the following: $A\preceq B$, $B\preceq A$, $A\not\sim B$, and $B\not\sim A$. This is however a contradiction since you say that $A\preceq B$ and $B\preceq A$ implies that $A\sim B$, but you cannot have $A\sim B$ and $A\not\sim B$ simultaneously. Thus $\prec$ is anti-symmetric due to vacuous truth. – JMoravitz Aug 11 '15 at 06:29
  • 1
    @JMoravitz Thanks that makes sense now!! Thanks for your help :) – user1292919 Aug 11 '15 at 06:40
  • The assumption that $<$ is some total order on a set is a red herring. – Asaf Karagila Aug 11 '15 at 06:59
  • @Asaf I meant that upon first reading the question that the OP likely meant $(<,\mathbb{R})$ or $(<,\mathbb{Z})$ etc... and that we were working with the usual $<$ meaning "less than." After prodding in the comments above it seems that the OP meant some arbitrary relation $\prec$ which was defined using another arbitrary relation $\preceq$ which has specific properties, none of which were included in the original post of the question. I did not mean to imply that I knew ahead of time that $<$ was a total order, but simply that we weren't working in something weirder like $\mathbb{Z}[i]$. – JMoravitz Aug 11 '15 at 07:04
  • I'm not saying that it's not a reasonable assumption. I'm just saying that in general that assumption is a red herring. (And also $(\Bbb R,<)$ and $(\Bbb Z,<)$, I'm the one used to writing from right-to-left, so between the two of us, I should be making this "switch"... :-)) – Asaf Karagila Aug 11 '15 at 07:05