Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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..

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

$\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.

share|improve this answer
1  
"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
1  
Yes...You've got it! –  amWhy May 2 '13 at 7:56
add comment

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

share|improve this answer
    
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
1  
@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
1  
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
add comment

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.

share|improve this answer
    
Does \not\sqsubset display correctly for you? For me, it looks identical to \sqsubset. –  vadim123 May 1 '13 at 21:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.