# Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$

The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if

$$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$

and it is antireflexive if

$$\forall a\in S:(a,a)\notin\;\sqsubset$$

I want to prove that

$$\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$$

Now... it seem me obvious that is right, eve using some examples in my mind

but when I try to write the formal proof in this way I'm in confusion at the conclusion.

$(a,b)\in\;\sqsubset\rightarrow (b,a)\notin\;\sqsubset$

if $b=a$ I get

$(a,a)\in\;\sqsubset\rightarrow (a,a)\notin\;\sqsubset$

... this is a contraddiction..but I don't understand how it is the proof...

someone can explain me in easy words why this is a proof? I only see that the asymmetry lead to contraddiction when $b=a$ ... there is something I'm missing..

-

$\text{We take as given that the relation is asymmetric.} \tag{Premise}$

We are assuming, for the sake of contradiction, that $\sqsubset$ is NOT antireflexive; that is we assume that there is an $a \in S$:

$$(a,a)\in\,\sqsubset\tag{1}.$$

Since the relation $\;\sqsubset\;$ is asymmetric, then by definition of asymmetry, $$(a,a)\in\,\sqsubset\rightarrow (a,a)\notin\,\sqsubset\tag{2}.$$

By modus ponens, given $(1),\;\text{and}\; (2)$, we are forced to conclude, therefore $$(a, a) \notin \,\sqsubset\tag{3}$$

$(3)$ contradicts $(1)$, so it cannot be the case that in any asymmetric relation, there exists an $a \in S$ such that $(a, a) \in \sqsubset$. That is, our assumption $(1)$ is false, because it leads to a contradiction. Hence a asymmetric relation must necessarily be antireflexive.

Note, what leads to the contradiction is the assumption that $\sqsubset$ contains at least one element that is related to itself, while also being asymmetric. We've shown an asymmetric relation cannot NOT be antireflexive, i.e., an asymmetric relation is necessarily antireflexive.

-
"Antireflexive" is not the negation of "reflexive". A relation can be neither reflexive nor antireflexive. – egreg May 1 '13 at 21:17
@egreg Edited accordingly...thanks for prompting me to "tweak" my answer. – amWhy May 1 '13 at 21:29
@amWhy: Nice cleaups too! +1 – Amzoti May 2 '13 at 0:14
@amWhy Ok, now is better! I think I understand. The justification of the proof, is that in order to avoid contraddiction we must set $(1)$ false. All the proofs by contraddiction work in this way? writing what you said (only if I understood well) we can say this: modus ponens $((P\rightarrow Q)\land P) \vdash Q$ if $Q=\lnot P$ then $((P\rightarrow \lnot P)\land P) \vdash \lnot P$ in our case $\lnot P=¬(x\in \sqsubset)=x\notin \sqsubset$ right? errors? – MphLee May 2 '13 at 7:47
Yes...You've got it! – amWhy May 2 '13 at 7:56

Imagine to display the elements in the cartesian plane, then being asymmetric means that if a point is in the relation, then its symmetric with respect to the bisectrix of first quadrant is not. Taking the point on the bisectrix gives antireflexivity

-
Word of the day = 'bisectrix'. – Quinn Culver May 1 '13 at 22:48
@QuinnCulver What is the right term? bisector? – Federica Maggioni May 2 '13 at 6:52
@FedericaMaggioni Yea, is clear to me why is true and that is the way I understood it: infact the elements of the of the "identity relation" (the set $\Delta_S:=\{(a,a):a\in S\}$) are symmetric to themselves, for the set of the pairs $(a,a)$, or diagonal set $\Delta_S$ of $S$, we have $\sqsubset \cap \Delta_S =\varnothing$ from the definition of antireflexivity. My problem was a bit different, was more about the formal proof and the proof by contraddiction, I just used this case as an example. Grazie lo stesso per la risposta! – MphLee May 2 '13 at 7:29
Well, the more usual term would be 'diagonal'. But I think, given its definition, that 'bisectrix' was clear enough. Thanks for the new word! – Quinn Culver May 2 '13 at 15:12
@QuinnCulver in Italian the "bisettrice" is the symmetry axis of an angle (), in this case it is the axis of symmetry of the the pairs dysplayed in tha cartesian plane, in this case it is the bisectix too of the the angle formed from the two axes ($x$ and $y$). Really I'm not good at english, but I think the right translation is "bisector" or "bisecting line" when we talk about angle. – MphLee May 2 '13 at 19:35

Let $\sqsubset$ be an asymmetric relation on $S$. Let $a\in S$ be arbitrary. Two cases are possible: $a\sqsubset a$ or $a\not\sqsubset a$.

• If $a\sqsubset a$, then by asymmetry $a\not\sqsubset a$
• If $a\not \sqsubset a$, then we have mmediately that $a\not\sqsubset a$

In both cases we find $a\not\sqsubset a$. Hence $\sqsubset$ is antireflexive.

-
Does \not\sqsubset display correctly for you? For me, it looks identical to \sqsubset. – vadim123 May 1 '13 at 21:53