Confusion about reflexivity proof and properties of inequality with regards to a partial order proof

747 Views Asked by At

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?

2

There are 2 best solutions below

8
On BEST ANSWER

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.

0
On

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