nyuuzyou/wikis huggingface dataset:
Ordering/Examples/Example Ordering on Integers

== Example of Ordering ==
Let $\preccurlyeq$ denote the relation on the set of integers $\Z$ defined as:
:$a \preccurlyeq b$ $0 \le a \le b \text { or } b \le a < 0 \text { or } a < 0 \le b$
where $\le$ is the usual ordering on $\Z$.
Then $\preccurlyeq$ is an ordering on $\Z$.
== Proof ==
=== Reflexivity ===
Let $0 \le a$.
Then $0 \le a \le a$ and so $a \preccurlyeq a$.
Let $a < 0$.
Then $a \le a < 0$ and so $a \preccurlyeq a$.
Thus in both cases $a \preccurlyeq a$.
So $\preccurlyeq$ has been shown to be reflexive.
=== Transitivity ===
Let $a, b, c \in \R$ such that:
:$a \preccurlyeq b \text { and } b \preccurlyeq c$
Let $0 \le a \le b$.
Then:
:$0 \le b \le c$
and so:
:$0 \le a \le c$
That is:
$a \preccurlyeq c$
Let $b \le a < 0$.
Then there are two cases for $c$:
:$(1): \quad c \le b < 0$
Then we have:
:$c \le a < 0$
That is:
$a \preccurlyeq c$
:$(2): \quad b < 0 \le c$
Then we have:
:$a < 0 \le c$
That is:
$a \preccurlyeq c$
In both cases:
$a \preccurlyeq c$
Let $a < 0 \le b$.
Then:
:$0 \le b \le c$
and so:
:$0 < a \le c$
That is:
$a \preccurlyeq c$
In all cases:
$a \preccurlyeq c$
So $\preccurlyeq$ has been shown to be transitive.
=== Antisymmetry ===
Let $a, b \in \R$ such that:
:$a \preccurlyeq b \text { and } b \preccurlyeq a$
Let $0 \le a \le b$.
Then as $b \ge 0$:
:$0 \le b \le a$
Thus:
:$a \le b \text { and } b \le a$
and as $\le$ is the usual ordering, and so antisymmetric:
:$a = b$
Let $b \le a < 0$.
Then as $b < 0$:
:$a \le b < 0$
Thus:
:$a \le b \text { and } b \le a$
and as $\le$ is the usual ordering, and so antisymmetric:
:$a = b$
Let $a < 0 \le b$.
But then because $b \le a$:
:$0 \le b \le a$
which contradicts $a < 0$.
Hence if both $a \le b$ and $b \le a$, it cannot happen that $0 \le b \le a$.
All cases are accounted for, and it has been shown that:
:$a \preccurlyeq b \text { and } b \preccurlyeq a \implies a = b$
So $\preccurlyeq$ has been shown to be antisymmetric.
$\preccurlyeq$ has been shown to be reflexive, transitive and antisymmetric.
Hence by definition it is an ordering.
It is seen that $\preccurlyeq$ looks like:
:$-1 \preccurlyeq -2 \preccurlyeq -3 \preccurlyeq \cdots \preccurlyeq 0 \preccurlyeq 1 \preccurlyeq 2 \preccurlyeq \cdots$
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: $(4)$
Category:Examples of Orderings
Ordering/Examples/Integer Difference on Reals

== Example of Ordering ==
Let $\preccurlyeq$ denote the relation on the set of real numbers $\R$ defined as:
:$a \preccurlyeq b$ $b - a$ is a non-negative integer
Then $\preccurlyeq$ is an ordering on $\R$.
== Proof ==
=== Reflexivity ===
We have that:
:$\forall a \in \R: a - a = 0 \in \Z_{\ge 0}$
Thus:
:$\forall a \in \R: a \preccurlyeq a$
So $\preccurlyeq$ has been shown to be reflexive.
=== Transitivity ===
Let $a, b, c \in \R$ such that:
So $\preccurlyeq$ has been shown to be transitive.
=== Antisymmetry ===
Let $a, b \in \R$ such that:
So $\preccurlyeq$ has been shown to be antisymmetric.
$\preccurlyeq$ has been shown to be reflexive, transitive and antisymmetric.
Hence by definition it is an ordering.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: $(3)$
Category:Examples of Orderings
Ordering/Examples/Monarchy

== Example of Ordering ==
Let $K$ denote the set of .
Let $\MM$ denote the relation on $K$ defined as:
:$a \mathrel \MM b$ $a$ was after or at the same time as $b$.
Its dual $\MM^{-1}$ is defined as:
:$a \mathrel {\MM^{-1} } b$ $a$ was before or at the same time as $b$.
Then $\MM$ and $\MM^{-1}$ are orderings on $K$. 
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings
Category:Examples of Orderings
Ordering Compatible with Group Operation is Strongly Compatible

== Theorem ==
Let $\struct {G, \circ, \preccurlyeq}$ be an ordered group whose identity element is $e$.
Let $\prec$ be the reflexive reduction of $\preccurlyeq$.
The following hold:
=== Corollary ===
== Proof ==
By definition of ordered group, $\preccurlyeq$ is a relation compatible with $\circ$.
Thus by Relation Compatible with Group Operation is Strongly Compatible:
By Reflexive Reduction of Relation Compatible with Group Operation is Compatible, $\prec$ is compatible with $\circ$.
Thus again by Relation Compatible with Group Operation is Strongly Compatible:
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Theorem $15.3$
Category:Ordered Groups
Category:Compatible Relations
Category:Ordering Compatible with Group Operation is Strongly Compatible
Ordering Compatible with Group Operation is Strongly Compatible/Corollary

== Corollary to Ordering Compatible with Group Operation is Strongly Compatible ==
Let $\struct {G, \circ, \preccurlyeq}$ be an ordered group with identity $e$.
Let $\prec$ be the reflexive reduction of $\preccurlyeq$.
The following hold:
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Theorem $15.3$
Category:Ordering Compatible with Group Operation is Strongly Compatible
Ordering Compatible with Group Operation is Strongly Compatible/Corollary/Proof 1

== Theorem ==
Let $\struct {G, \circ, \preccurlyeq}$ be an ordered group with identity $e$.
Let $\prec$ be the reflexive reduction of $\preceq$.
Let $x, y \in G$.
Then the following equivalences hold:
== Proof ==
By the definition of an ordered group, $\preccurlyeq$ is a relation compatible with $\circ$.
Thus by , we obtain the first four results.
By Reflexive Reduction of Relation Compatible with Group Operation is Compatible, $\prec$ is compatible with $\circ$.
Again by , we obtain the remaining results.
Category:Ordering Compatible with Group Operation is Strongly Compatible
Ordering Compatible with Group Operation is Strongly Compatible/Corollary/Proof 2

== Theorem ==
Let $\struct {G, \circ, \preccurlyeq}$ be an ordered group with identity $e$.
Let $\prec$ be the reflexive reduction of $\preccurlyeq$.
Let $x, y \in G$.
Then the following equivalences hold:
== Proof ==
Each result follows from Ordering Compatible with Group Operation is Strongly Compatible.
For example, by Ordering Compatible with Group Operation is Strongly Compatible:
:$x \preccurlyeq y \iff x \circ x^{-1} \preccurlyeq y \circ x^{-1}$
Since $x \circ x^{-1} = e$:
:$x \preccurlyeq y \iff e \preccurlyeq y \circ x^{-1}$
Category:Ordering Compatible with Group Operation is Strongly Compatible
Ordering Cycle implies Equality

== Theorem ==
Let $\struct {S, \preceq}$ be an ordered set.
Let $x_1$, $x_2$, and $x_3$ be elements of $S$.
Suppose that
Then $x_1 = x_2 = x_3$.
=== General Case ===
== Proof ==
Because $\preceq$ is an ordering, it is transitive and antisymmetric.
By transitivity, $x_1 \preceq x_3$.
Because $x_1 \preceq x_3$ and $x_3 \preceq x_1$, antisymmetry allows us to conclude that $x_1 = x_3$.
Because $x_1 = x_3$ and $x_1 \preceq x_2$, we must have $x_3 \preceq x_2$.
Because $x_3 \preceq x_2$ and $x_2 \preceq x_3$, antisymmetry allows us to conclude that $x_2 = x_3$.
Thus $x_1 = x_2 = x_3$.
Category:Order Theory
Ordering Cycle implies Equality/General Case

== Theorem ==
Let $\struct {S,\preceq}$ be an ordered set.
Let $x_0, x_1, \dots, x_n \in S$.
Suppose that for $k = 0, 1, \dots, n - 1: x_k \preceq x_{k + 1}$.
Suppose also that $x_n \preceq x_0$.
Then $x_0 = x_1 = \dots = x_n$.
== Proof ==
Since $\preceq$ is an ordering it is transitive and antisymmetric.
By Transitive Chaining, it follows from the first premise that for all $k$ with $0 \le k \le n$:
:$x_0 \preceq x_k$
and also:
:$x_k \preceq x_n$
The other premise states that $x_n \preceq x_0$.
By transitivity of $\preceq$, this combines with the above to:
:$x_k \preceq x_0$
Since $\preceq$ is antisymmetric, this means that $x_0 = x_k$ for $0 \le k \le n$.
That is, $x_0 = x_1 = \dots = x_n$.
== Also known as ==
 refers to this property as anti-circularity.
== Sources ==
* : $\text I.1$: Lemma $2$
Category:Order Theory
Ordering Induced by Injection is Ordering

== Theorem ==
Let $\left({T, \le}\right)$ be an ordered set, and let $S$ be a set.
Let $f: S \to T$ be an injection.
Then $\le_f$, the ordering induced by $f$, is an ordering.
== Proof ==
To establish that $\le_f$ is an ordering on $S$, we need to show that it is reflexive, antisymmetric and transitive.
So, checking in turn each of the criteria for an ordering:
=== Reflexivity ===
For all $s \in S$, one has $f \left({s}\right) \le f \left({s}\right)$ as $\le$ is an ordering.
Hence, by definition of $\le_f$, $s \le_f s$ for all $s \in S$.
So $\le_f$ is reflexive.
=== Antisymmetry ===
Suppose that for some $s_1, s_2 \in S$, one has both $s_1 \le_f s_2$ and $s_2 \le_f s_1$.
This is equivalent to $f \left({s_1}\right) \le f \left({s_2}\right)$ and $f \left({s_2}\right) \le f \left({s_1}\right)$.
As $\le$ is an ordering, this implies $f \left({s_1}\right) = f \left({s_2}\right)$.
That $f$ is an injection now implies that $s_1 = s_2$.
Hence $\le_f$ is antisymmetric.
=== Transitivity ===
Suppose that for some $s_1, s_2, s_3 \in S$, one has both $s_1 \le_f s_2$ and $s_2 \le_f s_3$.
This is equivalent to $f \left({s_1}\right) \le f \left({s_2}\right)$ and $f \left({s_2}\right) \le f \left({s_3}\right)$.
As $\le$ is an ordering, this implies $f \left({s_1}\right) \le f \left({s_3}\right)$.
The definition of $\le_f$ now implies that $s_1 \le_f s_3$.
So $\le_f$ is transitive.
So we have shown that $\le_f$ is an ordering on $S$.
Category:Order Theory
Category:Injections
Ordering Induced by Join Semilattice

== Theorem ==
Let $\struct {S, \vee, \preceq}$ be a join semilattice.
By Join Semilattice is Semilattice, $\struct {S, \vee}$ is a semilattice.
By Semilattice Induces Ordering, $\struct {S, \vee}$ induces an ordering $\preceq'$ on $S$, by:
:$a \preceq' b$ $a \vee b = b$
for all $a, b \in S$.
The ordering $\preceq'$ coincides with the original ordering $\preceq$.
== Proof ==
It is to be shown that, for all $a, b \in S$:
:$a \preceq b$ $b = \sup \set {a, b}$
by definition of join.
Here $\sup$ denotes supremum.
Since any upper bound $c$ of $\set {a, b}$ must satisfy:
:$b \preceq c$
it suffices to verify that:
:$a \preceq b$ $b$ is an upper bound for $\set {a, b}$
Since $\preceq$ is reflexive, we know that:
:$b \preceq b$
and therefore said equivalence is established.
We conclude that $\preceq'$ and $\preceq$ coincide.
Category:Order Theory
Category:Join Semilattices
Ordering Induced by Preordering is Well-Defined

== Definition ==
Let $\struct {S, \RR}$ be a relational structure such that $\RR$ is a preordering.
Let $\sim_\RR$ denote the equivalence on $S$ induced by $\RR$:
:$x \sim_\RR y$ $x \mathrel \RR y$ and $y \mathrel \RR x$
Let $\preccurlyeq_\RR$ be the ordering on the quotient set $S / {\sim_\RR}$ by $\RR$:
:$\eqclass x {\sim_\RR} \preccurlyeq_\RR \eqclass y {\sim_\RR} \iff x \mathrel \RR y$
where $\eqclass x {\sim_\RR}$ denotes the equivalence class of $x$ under $\sim_\RR$.
Then $\preccurlyeq_\RR$ is a well-defined relation.
== Proof ==
We need to demonstrate that when:
:$a \sim_\RR a'$
:$b \sim_\RR b'$
it follows that:
:$\eqclass a {\sim_\RR} \preccurlyeq_\RR \eqclass b {\sim_\RR} \iff \eqclass {a'} {\sim_\RR} \preccurlyeq_\RR \eqclass {b'} {\sim_\RR}$
So, let:
:$a \sim_\RR a'$
:$b \sim_\RR b'$
for arbitrary $a, b, a', b' \in S$.
By definition of $\sim_\RR$, this means:
:$a \mathrel \RR a'$ and $a' \mathrel \RR a$
:$b \mathrel \RR b'$ and $b' \mathrel \RR b$
So:
That is:
:$\eqclass a {\sim_\RR} \preccurlyeq_\RR \eqclass b {\sim_\RR} \implies \eqclass {a'} {\sim_\RR} \preccurlyeq_\RR \eqclass {b'} {\sim_\RR}$
The same argument is used to prove that:
:$\eqclass {a'} {\sim_\RR} \preccurlyeq_\RR \eqclass {b'} {\sim_\RR} \implies \eqclass a {\sim_\RR} \preccurlyeq_\RR \eqclass b {\sim_\RR}$
Hence the result.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $40 \ \text {(a)}$
Category:Preorderings
Category:Orderings
Ordering Principle

== Theorem ==
Let $S$ be a set.
Then there exists a total ordering on $S$.
== Proof 1 ==
== Proof 2 ==
== Remarks ==
As shown in Proof 2 the Ordering Principle is weaker than the Order-Extension Principle (OE).
It is known that it is in fact strictly weaker than OE.
However, the Ordering Principle cannot be proved in Zermel-Fraenkel set theory without the Axiom of Choice.
In fact it is known to be strictly stronger than the Axiom of Choice for Finite Sets.
Category:Set Theory
Category:Total Orderings
Category:Order Theory
Category:Named Theorems
Category:Ordering Principle
Ordering Relations are Primitive Recursive

== Theorem ==
The ordering relations on $\N^2$:
* $n < m$
* $n \le m$
* $n \ge m$
* $n > m$
are all primitive recursive.
== Proof ==
We note that:
: $n < m \iff m \mathop{\dot -} n > 0$
: $n \ge m \iff m \mathop{\dot -} n = 0$
So it can be seen that the characteristic function of $<$ is given by:
:$\chi_< \left({n, m}\right) = \operatorname{sgn} \left({m \mathop{\dot -} n}\right)$
So $\chi_{<}$ is defined by substitution from:
: the primitive recursive function $\operatorname{sgn}$
: the primitive recursive function $\dot -$
Thus $\chi_<$ is primitive recursive.
So $<$ is a primitive recursive relation.
Next we see that $n \le m \iff n < m \lor n = m$ from the definition of strictly precedes.
From Equality Relation is Primitive Recursive, we have that $=$ is primitive recursive.
From above, we have that $<$ is primitive recursive.
Thus $\le$ is primitive recursive from Set Operations on Primitive Recursive Relations.
We could use the same reasoning for $>$ and $\ge$ but there's a different approach.
Note that $n \le m \iff n \not > m$, and so $>$ is primitive recursive from Set Operations on Primitive Recursive Relations.
Finally the same applies to $\ge$.
Hence the result.
Category:Primitive Recursive Functions
Ordering in terms of Addition

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Then $\forall m, n \in S$: 
:$m \preceq n \iff \exists p \in S: m \circ p = n$
== Proof ==
=== Necessary Condition ===
From , we have:
:$\forall m, n \in S: m \preceq n \implies \exists p \in S: m \circ p = n$
=== Sufficient Condition ===
Suppose that $m \circ p = n$.
So $\forall m, n \in S$: 
:$m \preceq n \iff \exists p \in S: m \circ p = n$
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Theorem $16.2$
Category:Naturally Ordered Semigroup
Ordering is Directed iff Composite with Inverse is Trivial Ordering

== Theorem ==
Let $\struct {S, \RR}$ be an ordered set.
Then $\RR$ is a directed ordering :
:$\RR^{-1} \circ \RR = S \times S$
where:
:$\circ$ denotes composite relation
:$\RR^{-1}$ denotes inverse relation
:$S \times S$ denotes the trivial relation, that is, the Cartesian product of $S$ with itself.
== Proof ==
We are given that $\RR$ is an ordering.
=== Sufficient Condition ===
Let $\RR$ be a directed ordering on $S$.
Then by definition:
:$\forall x, y \in S: \exists z \in S: x \mathrel \RR z \land y \mathrel \RR z$
By definition of inverse relation:
:$\forall x, y \in S: \exists z \in S: z \mathrel {\RR^{-1} } x \land z \mathrel {\RR^{-1} } y$
By definition of composite relation
:$\RR^{-1} \circ \RR := \set {\tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1} }$
Let $\tuple {x, y} \in S \times S$ be arbitrary.
Then:
:$\exists z \in \RR: \tuple {x, z} \in \R \land \tuple {y, z} \in \R$
That is:
:$\exists z \in \RR: \tuple {x, z} \in \R \land \tuple {z, y} \in \R^{-1}$
That is:
:$\tuple {x, y} \in \RR^{-1} \circ \RR$
As $\tuple {x, y}$ is arbitrary, it follows that:
:$\RR^{-1} \circ \RR = S \times S$
=== Necessary Condition ===
Let $\struct {S, \RR}$ be such that:
:$\RR^{-1} \circ \RR = S \times S$
Then by definition of composite relation:
:$\RR^{-1} \circ \RR = S \times S = \set {\tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1} }$
That is:
:$\forall \tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1}$
That is, by definition of inverse relation:
:$\forall \tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {y, z} \in \RR$
That is, $\RR$ is a directed ordering.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.28$
Category:Directed Orderings
Category:Composite Relations
Ordering is Equivalent to Subset Relation

== Theorem ==
Let $\struct {S, \preceq}$ be an ordered set.
Then there exists a set $\mathbb S$ of subsets of $S$ such that:
:$\struct {S, \preceq} \cong \struct {\mathbb S, \subseteq}$
where:
:$\struct {\mathbb S, \subseteq}$ is the relational structure consisting of $\mathbb S$ and the subset relation
:$\cong$ denotes order isomorphism.
Hence any ordering on a set can be modelled uniquely by a set of subsets of that set under the subset relation.
Specifically:
Let
:$\mathbb S := \set {a^\preceq: a \in S}$
where $a^\preceq$ is the lower closure of $a$.
That is:
:$a^\preceq := \set {b \in S: b \preceq a}$
Let the mapping $\phi: S \to \mathbb S$ be defined as:
:$\map \phi a = a^\preceq$
Then $\phi$ is an order isomorphism from $\struct {S, \preceq}$ to $\struct {\mathbb S, \subseteq}$.
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Definition:Representation Theorem, of which this is an example
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $21 \ \text {(b)}$
Category:Orderings
Category:Subset Relation
Category:Representation Theorems
Category:Ordering is Equivalent to Subset Relation
Ordering is Equivalent to Subset Relation/Lemma

== Theorem ==
Let $\struct {S, \preceq}$ be an ordered set.
Then:
:$\forall a_1, a_2 \in S: \paren {a_1 \preceq a_2 \implies {a_1}^\preceq \subseteq {a_2}^\preceq}$
where ${a_1}^\preceq$ denotes the lower closure of $a_1$.
== Proof ==
Let $a_1 \preceq a_2$.
Then by the definition of lower closure:
:$a_1 \in {a_2}^\preceq$
Let $a_3 \in {a_1}^\preceq$.
Then by definition:
:$a_3 \preceq a_1$
As an ordering is transitive, it follows that:
:$a_3 \preceq a_2$
and so:
:$a_3 \in {a_2}^\preceq$
This holds for all $a_3 \in {a_1}^\preceq$.
Thus by definition of subset:
:${a_1}^\preceq \subseteq {a_2}^\preceq$
Category:Ordering is Equivalent to Subset Relation
Ordering is Equivalent to Subset Relation/Proof 1

== Theorem ==
== Proof ==
From Subset Relation is Ordering, we have that $\struct {\mathbb S, \subseteq}$ is an ordered set.
Then let $T$ be defined as:
:$T := \set {a^\prec: a \in S}$
Let the mapping $\phi: S \to T$ be defined as:
:$\map \phi a = a^\prec$
We are to show that $\phi$ is an order isomorphism.
$\phi$ is clearly surjective, as every $a^\prec$ is defined from some $a \in S$.
Now suppose $x^\prec, y^\prec \in T: x^\prec = y^\prec$.
Then:
:$\set {b \in S: b \preceq x} = \set {b \in S: b \preceq y}$
We have that:
:$x \in x^\prec = y^\prec$ and $y \in y^\prec = x^\prec$
which means:
:$x \preceq y$ and $y \preceq x$
So as an ordering is antisymmetric, we have $x = y$ and so $\phi$ is injective.
Hence by definition, $\phi$ is a bijection.
Now let $a_1 \preceq a_2$.
Then by definition:
:$a_1 \in {a_2}^\prec$
Let $a_3 \in {a_1}^\prec$.
Then by definition:
:$a_3 \preceq a_1$
As an ordering is transitive, it follows that:
:$a_3 \preceq a_2$
and so:
:$a_3 \in {a_2}^\prec$
So by definition of a subset:
:${a_1}^\prec \subseteq {a_2}^\prec$
Therefore, $\phi$ is order-preserving
Conversely, suppose that ${a_1}^\prec \subseteq {a_2}^\prec$.
Then, since $a_1 \in {a_1}^\prec$, also $a_1 \in {a_2}^\prec$ by definition of subset.
By definition of ${a_2}^\prec$:
:$a_1 \preceq a_2$
Hence it is seen that $\phi^{-1}$ is also order-preserving.
Thus it follows that $\phi$ is an order isomorphism between $\struct {S, \preceq}$ and $\struct {\mathbb S, \subseteq}$.
== Sources ==
* : $\S 1$: Naive Set Theory: $\S 1.5$: Relations: Theorem $1.5.2$
Category:Ordering is Equivalent to Subset Relation
Ordering is Equivalent to Subset Relation/Proof 2

== Theorem ==
== Proof ==
First a lemma:
=== Lemma ===
From Subset Relation is Ordering, we have that $\struct {\mathbb S, \subseteq}$ is an ordered set.
We are to show that $\phi$ is an order isomorphism.
$\phi$ is clearly surjective, as every $a^\preceq$ is defined from some $a \in S$.
By the Lemma, $\phi$ is order-preserving.
Suppose that ${a_1}^\preceq \subseteq {a_2}^\preceq$.
We have that:
:$a_1 \in {a_1}^\preceq$
Thus by definition of subset:
:$a_1 \in {a_2}^\preceq$
By definition of ${a_2}^\preceq$:
:$a_1 \preceq a_2$
Thus $\phi$ is also order-reflecting.
Thus it follows that $\phi$ is an order isomorphism between $\struct {S, \preceq}$ and $\struct {\mathbb S, \subseteq}$.
Category:Ordering is Equivalent to Subset Relation
Ordering is Preordering

== Theorem ==
Let $S$ be a set.
Let $\RR$ be an ordering on $S$.
Then $\RR$ is also a preordering on $S$.
== Proof ==
By definition of ordering:
By definition of preordering:
Thus an ordering is a preordering which is antisymmetric.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations
Category:Preorderings
Category:Orderings
Ordering is Preserved on Integers by Addition

== Theorem ==
The usual ordering on the integers is preserved by the operation of addition:
:$\forall a, b, c, d, \in \Z: a \le b, c \le d \implies a + c \le b + d$
== Proof ==
Recall that Integers form Ordered Integral Domain.
Then from Relation Induced by Strict Positivity Property is Compatible with Addition:
:$\forall x, y, z \in \Z: x \le y \implies \paren {x + z} \le \paren {y + z}$
:$\forall x, y, z \in \Z: x \le y \implies \paren {z + x} \le \paren {z + y}$
So:
Finally:
== Sources ==
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf Z. \, 7$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
Category:Integer Addition
Category:Orderings on Integers
Ordering of Cardinality of Sets is Well-Defined

== Theorem ==
The relation $\le$ in the context of cardinalities of sets is well-defined in the sense that:
:if $\card A = \card {A'}$ and $\card B = \card {B'}$, then there exists an injection from $A$ into $B$ there exists an injection from $A'$ into $B'$.
== Proof ==
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $3$: Cardinality: Exercise $3$
Category:Cardinality
Category:Orderings
Ordering of Cardinals Compatible with Cardinal Product

== Theorem ==
Let $\mathbf a$, $\mathbf b$ and $\mathbf c$ be cardinals.
Then:
:$\mathbf a \le \mathbf b \implies \mathbf a \mathbf c \le \mathbf b \mathbf c$
where $\mathbf a \mathbf c$ denotes the product of $\mathbf a$ and $\mathbf c$.
== Proof ==
Let $\mathbf a = \map \Card A$, $\mathbf b = \map \Card B$ and $\mathbf c = \map \Card C$ for some sets $A$, $B$ and $C$.
Let $\mathbf a \le \mathbf b$.
Then by definition of cardinal, there exists an injection $f: A \to B$.
Then the mapping $g: A \times C \to B \times C$ defined as:
:$\forall \tuple {a, c} \in A \times C: \map g {a, c} = \tuple {\map f a, c}$
Let $\tuple {a_1, c_1} \in A \times C$ and $\tuple {a_2, c_2} \in A \times C$ such that:
:$\map g {a_1, c_1} = \map g {a_2, c_2}$
That is:
:$\tuple {\map f {a_1}, c_1} = \tuple {\map f {a_2}, c_2}$
By Equality of Ordered Pairs:
:$\map f {a_1} = \map f {a_2}, c_1 = c_2$
and so as $f$ is an injection:
:$a_1 = a_2, c_1 = c_2$
By Equality of Ordered Pairs:
:$\tuple {a_1, c_1} = \tuple {a_2, c_2}$
demonstrating that $g$ is an injection.
So, by definition of product of cardinals:
:$\mathbf a \mathbf c \le \mathbf b \mathbf c$
== Sources ==
* : $\S 8$: Theorem $8.7$
Category:Cardinals