example of antisymmetric

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

$a\le b$ and $b\le a$ implies $a=b$

for every $a,b\in S$.

For a concrete example consider the natural numbers $\mathbb{N}=\{0,1,2,\mathrm{\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\le b$ if $(a,b)\in R$. That is, $5\le 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\le b$ and $b\le 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\ne m+n$ unless $m=n=0$.

Title	example of antisymmetric
Canonical name	ExampleOfAntisymmetric
Date of creation	2013-03-22 16:00:36
Last modified on	2013-03-22 16:00:36
Owner	Algeboy (12884)
Last modified by	Algeboy (12884)
Numerical id	8
Author	Algeboy (12884)
Entry type	Example
Classification	msc 03E20