0

Let R be asymmetric.

So we have:

  1. Assumption: (x,y)∈R⟹(y,x)∉R

We need to show R is antisymmetric, i.e.

  1. (x,y)∈R∧(y,x)∈R⟹x=y

Since 2 is a conditional, we can assume

  1. Assumption:(x,y)∈R∧(y,x)∈R

And try to show

  1. x=y.

But if we simplify LHS of 3 and use Modus Ponens on (x,y)∈R and 1, our assumption, we have

  1. (y,x)∉R

Which contradicts RHS of 3.

So how could an asymmetric relation be antisymmetric? Did I do something wrong here?

Constantly confused
  • 1,448

1 Answers1

3

It's vacuously true! The point is that $(x,y) \in R$ and $(y,x) \in R$ can never happen, so whatever you say about it is true.

For example the statement "If $(x,y) \in R$ and $(y,x) \in R$, then $5=7$" is true.

  • You mean since 1 and 3 are contradictory, nothing satisfies both of these assumptions and thus this makes it a vacuous truth. My proof is actually correct - there is a contradiction there.

    But isn't this an entailment? I thought vacuous truth only happens in conditional implication, not entailment.

     – Constantly confused Aug 01 '15 at 05:17
  • 2
    I deleted my answer after realizing it is incorrect and upvoted this one, because that's the correct answer. There are no $x,y$ such that $(x,y) \in R$ and $(y,x) \in R$ due to R being asymmetric, therefore antisymmetric follows vacuously. – benji Aug 01 '15 at 05:53
  • It sounds like the vacuous truth is a product of entailment from (x,y)∈R⟹(y,x)∉R and (x,y)∈R∧(y,x)∈R, but I thought vacuous truths only occur in conditionals where the antecedent is false? – Constantly confused Aug 01 '15 at 10:38
  • 1
    @DanielMak Asymmetry is the property that: $\forall x\forall y\Big( (x,y)\in R ,\to, (y,x)\notin R\Big)$

    It follows from this that: $\forall x\forall y\Big(\neg\big((x,y)\in R\wedge (y,x)\in R \big)\Big)$

    Antisymmetry is the property that: $\forall x\forall y \Big((x,y)\in R\wedge (y,x)\in R \to x=y\Big)$

    Since we have asymmetry, the antecedent is always false, this implication is always true regardless of the consequent. Thus, it is a vacuous truth.

     – Graham Kemp Aug 03 '15 at 00:12
  • @GrahamKemp Cheers mate, putting it in 1st order logic really cleared things up. – Constantly confused Aug 08 '15 at 04:42