0
$\begingroup$

The confusions stem from this question:

Let $R$ be a relation over a set $A$. For all $a∈A$ and $b∈A$, given that $a < b$ iff $a\leq b$ but $a\neq b$, and $a\leq b$ iff either $a < b$ or $a=b$, show that when $<$ is a transitive asymmetric relation, then the relation $\leq$ is a partial order.

I can prove that $a\leq b$ is transitive and anti-symmetric, but I am not sure how to prove that $a \leq b$ is reflexive.

My focus is on proving $a=b$, because trying to prove $a < b$ seems impossible. My plan was to argue that since $a$ and $b$ are just arbitrary objects from set $A$, $a$ and $b$ could be referring to the same object. If so, necessarily $a=b$. But is this a valid move? The fact that one can simply assume two variables to be the same thing seems like an 'illegal' move, in the sense that it grants one a very powerful assumption.

My next confusion concerns whether an inequality is symmetric. This is because it could make my anti-symmetric proof shorter. It is well known that equality is symmetric, but the same is not apparent for inequality - at least as far as Google can tell me. Could anyone tell me if that is true?

$\endgroup$
  • $\begingroup$ You say that you can prove transitivity and anti-symmetry. You don't have to (and you can't, really), they are assumed in the statement of the problem. $\endgroup$ – Alex M. Aug 16 '15 at 19:58
  • $\begingroup$ I am not sure what you mean; if a relation is a partial order it needs to be transitive, reflexive and anti-symmetric, so shouldn't I be able to prove those properties? $\endgroup$ – Daniel Mak Aug 17 '15 at 14:17
  • $\begingroup$ I quote from what you've written above: "show that when $<$ is a transitive asymmetric relation". Transitivity and anti-symmetry are given by the problem "for free", you only have to prove reflexivity. And I don't think it is "asymmetry", I think it is "anti-symmetry". $\endgroup$ – Alex M. Aug 17 '15 at 14:20
  • $\begingroup$ But can we assume that ≤ is transitive just because < is? And unfortunately it is given that < is asymmetric, not anti-symmetric; I suspect perhaps the writer was hoping to make the readers to fight hard for it (my proof for transitivity is 40 lines lone!) $\endgroup$ – Daniel Mak Aug 17 '15 at 14:53
1
$\begingroup$

You should look again at what "reflexive" means. It is stated as: $$\forall a\in A [a\leq a].$$ Notice that we are only choosing one object - so you've gone wrong if you've already taken two objects $a$ and $b$. In doing it with one object, you won't need to take $a=b$ for granted, you'll just need to take $a=a$ (which is clearly okay to do).

Also, it should be noted that inequality is symmetric as well and that this follows from the symmetry of equality. Notice that the fact that equality is symmetric may be written as $$a=b\Longleftrightarrow b=a$$ and the contrapositive of this (which is always equivalent) is: $$b\neq a \Longleftrightarrow a\neq b$$ meaning inequality is symmetric too.

$\endgroup$
  • $\begingroup$ But if a≤b is defined such that only a=b will make it true, what can we do with a=a? It seems that we will at least need some additional assumption to make this work $\endgroup$ – Daniel Mak Aug 19 '15 at 15:26
  • $\begingroup$ @DanielMak We are not trying to prove $a\leq b$ - we're trying to prove $a\leq a$. $\endgroup$ – Milo Brandt Aug 19 '15 at 15:33
  • $\begingroup$ I totally understand what you said about reflexivity; but it's just that if a≤b iff a<b or a=b, and that we need to prove the RHS is indeed reflexive, it seems that a=a isn't quite what we need? What I mean is, we have proven a=a is reflexive. But since that is not how a≤b is defined (has a 'b' in the equality instead of 'a'), I am not sure how a=a helps to prove a≤b is reflexive? $\endgroup$ – Daniel Mak Aug 19 '15 at 15:37
  • $\begingroup$ I think I am perhaps confused about what variables mean in the context of a definition? $\endgroup$ – Daniel Mak Aug 19 '15 at 15:42
  • 1
    $\begingroup$ @DanielMak Yes, exactly - $a$ and $b$ could refer to the same object and we are here interested in that case. It's no different from the fact that we could set $a=1$ and $b=2$ and get "$1\leq 2$ iff $1<2$ or $1=2$", just making a different choice. When I say "a particular instance" I just mean that we have taken a statement which applies to any pair of $a$ and $b$ and considered it for a particular pair of $a$ and $b$. $\endgroup$ – Milo Brandt Aug 19 '15 at 16:10
2
$\begingroup$

You know that $<$ is transitive and antisymmetric. Now you define the reflexive extension of $<$ to be $\le$ with $a\le b$ iff $a<b$ or $a=b$. You need to prove that $\forall a\in A: a\le a$ (reflexivity), and this is obvious since $a=a$ (and therefore $a\le a$ by definition of $\le$).

As for inequality, it is symmetric. You can show that the complement of a symmetric relation is also symmetric. Let $R\subseteq A\times A$ be symmetric, then $\bar{R} = \left(A\times A \right) \setminus R$ is symmetric. Suppose $a\bar{R}b$ then $a\require{cancel}\cancel{R}b$. $R$ is symmetric therefore $a\require{cancel}\cancel{R}b \Rightarrow b\require{cancel}\cancel{R}a\Rightarrow b\bar{R}a$.

$\endgroup$

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.