Preordering/Examples/Finite Set Difference on Natural Numbers

From ProofWiki
Jump to navigation Jump to search

Examples of Preorderings

Consider the relation $\RR$ on the powerset of the natural numbers:

$\forall a, b \in \powerset \N: a \mathrel \RR b \iff a \setminus b \text { is finite}$

where $\setminus$ denotes set difference.


Then $\RR$ is a preordering on $\powerset \N$, but not an ordering on $\powerset \N$.


Proof

We need to show that $\RR$ is both reflexive and transitive, but specifically not antisymmetric.


We have from Set Difference with Self is Empty Set:

$\forall a \in \powerset \N: a \setminus a = \O$

and so as $\O$ is a finite set:

$\forall a \in \powerset \N: a \mathrel \RR a$

That is, $\RR$ is reflexive.

$\Box$


Let $a, b, c \in \powerset \N$ such that $a \setminus b$ is finite and $b \setminus c$ is finite.

In order to show that $\RR$ is transitive we need to show that $a \setminus c$ is also finite.


Aiming for a contradiction, suppose $a \setminus c$ is not finite.

Then $a$ is not finite.

For $x \in \powerset \N$, let $x'$ denote the complement of $x$ in $\N$.

We have that:

\(\ds a \setminus b\) \(=\) \(\ds a \cap b'\) Definition of Set Difference
\(\ds b \setminus c\) \(=\) \(\ds b \cap c'\) Definition of Set Difference
\(\ds a \setminus c\) \(=\) \(\ds a \cap c'\) Definition of Set Difference

We have from De Morgan's Laws: Set Difference with Intersection that:

$\paren {a \setminus b} \cup \paren {a \setminus c} = a \setminus \paren {b \cap c}$

and so:

$\paren {a \setminus b} \cup \paren {a \setminus c} = \paren {a \setminus b} \cup \paren {a \cap b \cap c'}$


Hence if $a \setminus c$ is not finite, then $a \cap b \cap c'$ is not finite.

But then $b \cap c'$ is not finite.

That is, $b \setminus c$ is not finite.

This contradicts our supposition that $b \setminus c$ is finite.

Hence by Proof by Contradiction it follows that $a \setminus c$ is finite.

That is, $a \mathrel \RR c$ is transitive

$\Box$


Let $a = \set {1, 2, 3}$ and $b = \set {2, 3, 4}$.

Then:

$a \setminus b = \set 1$
$b \setminus a = \set 4$

Both $a \setminus b$ and $b \setminus a$ are finite, and so:

$a \mathrel \RR b$ and $b \mathrel \RR a$

but it is not the case that $a = b$.

That is, $\RR$ is not antisymmetric.

$\Box$


We have shown that $\RR$ is both reflexive and transitive, but specifically not antisymmetric.

Hence $\RR$ is a preordering on $\powerset \N$ which is not an ordering on $\powerset \N$.

$\blacksquare$


Sources