0
$\begingroup$

I came across a question as follows: Show that every asymmetric relation over a set $A$ is irreflexive.

The solution instructs one to use the relation < and suppose that it is asymmetric but not irreflexive, so that one derives a contradiction.

Since the relation is not irreflexive, there is an $a\in A$ with $a < a$. By asymmetry, not $a < a$ - contradiction"

But my understanding is that being non-irreflexive doesn't necessary mean it is reflexive, which seems to have been assumed so here. If this assumption is indeed false, wouldn't this proof fail?

Thank you so much!

$\endgroup$
1
$\begingroup$

You're correct, not being irreflexive does not mean that the relation is reflexive.

But it is not assumed to be reflexive. Remember that reflexive means for all $a\in A$ it holds that $a<a$. Here we only assume that for some $a\in A$ it holds that $a<a$, which is exactly what it means not to be irreflexive.

$\endgroup$
1
$\begingroup$

Definition. A relation that is irreflexive, is a binary relation on a set where no element is related to itself; in other words: $$\forall a\in A; \lnot (a<a)$$
Let < not irreflexive. So $$\lnot (\forall a\in A; \lnot (a<a))$$ which means $$\exists a\in A,a < a.$$ And this is what you want: "the relation is not irreflexive, there is an $a∈A$ with $a < a$"

$\endgroup$
  • $\begingroup$ Thank you! With the logic notations I completely get it now, I didn't realise it was an instance of quantification negation $\endgroup$ – Daniel Mak Apr 21 '15 at 5:24
  • $\begingroup$ you are welcome $\endgroup$ – user 1 Apr 21 '15 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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