example of antisymmetric

The axioms of a partial ordering demonstrate that every partial ordering is antisymmetric. That is: the relation $\leq$ on a set $S$ forces

$a\leq b$ and $b\leq a$ implies $a=b$

for every $a,b\in S$.

For a concrete example consider the natural numbers $\mathbb{N}=\{0,1,2,\dots\}$ (as defined by the Peano postulates (http://planetmath.org/PeanoArithmetic)). Take the relation set to be:

 $R=\{(a,a+n):a,n\in\mathbb{N}\}\subset\mathbb{N}\times\mathbb{N}.$

Then we denote $a\leq b$ if $(a,b)\in R$. That is, $5\leq 7$ because $(5,7)=(5,5+2)$ and both $5,2\in\mathbb{N}$.

We can prove this relation is antisymmetric as follows: Suppose $a\leq b$ and $b\leq a$ for some $a,b\in\mathbb{N}$. Then there exist $n,m\in\mathbb{N}$ such that $a+n=b$ and $b+m=a$. Therefore

 $b=a+n=b+m+n$

so by the cancellation property of the natural numbers, $0=m+n$. But by the first piano postulate, 0 has no predecessor, meaning $0\neq m+n$ unless $m=n=0$.

Title example of antisymmetric ExampleOfAntisymmetric 2013-03-22 16:00:36 2013-03-22 16:00:36 Algeboy (12884) Algeboy (12884) 8 Algeboy (12884) Example msc 03E20