nyuuzyou/wikis huggingface dataset:
Ordering of Cardinals Compatible with Cardinal Sum

== 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 sum 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 $C$ be chosen such that $A \cap C = \O = B \cap C$.
Let $\mathbf a \le \mathbf b$.
Then by definition of cardinal, there exists an injection $f: A \to B$.
Then the mapping $h: A \cup C \to B \cup C$ defined as:
:$\forall x \in A \cup C: \map h x = \begin{cases}
\map f x & : x \in A \\
x & : x \in C
\end{cases}$
Let $a_1 \in A \cup C$ and $a_2 \in A \cup C$ such that:
:$\map h {a_1} = \map h {a_2}$
Then:
and:
So:
:$\map h {a_1} = \map h {a_2} \implies a_1 = a_2$
demonstrating that $h$ is an injection.
So, by definition of sum of cardinals:
:$\mathbf a + \mathbf c \le \mathbf b + \mathbf c$
== Sources ==
* : $\S 8$: Theorem $8.7$
Category:Cardinals
Ordering of Integers is Reversed by Negation

== Theorem ==
Let $x, y \in \Z$ such that $x > y$.
Then:
:$-x < -y$
== Proof ==
From the formal definition of integers, $\eqclass {a, b} {}$ is an equivalence class of ordered pairs of natural numbers.
Let $x = \eqclass {a, b} {}$ and $y = \eqclass {c, d} {}$ for some $x, y \in \Z$.
We have:
== Sources ==
* : Introduction $\S 5$: The system of integers: Exercise $1$
Category:Orderings on Integers
Ordering of Inverses in Ordered Monoid

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be an ordered monoid whose identity is $e$.
Let $x, y \in S$ be invertible.
Then:
:$x \prec y \iff y^{-1} \prec x^{-1}$
== Proof ==
=== Necessary Condition ===
=== Sufficient Condition ===
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Theorem $15.2$
Category:Order Theory
Category:Monoids
Ordering of Natural Numbers is Provable

== Theorem ==
Let $x, y \in \N$.
Suppose $x < y$.
Let $\sqbrk a$ denote the unary representation of $a \in \N$.
Then $\sqbrk x < \sqbrk y$ is a theorem of minimal arithmetic.
== Proof ==
Fix $x$, and let $z > 0$ be arbitrary.
Proceed by induction on $z$.
=== Basis for the Induction ===
Suppose $z = 1$.
The following is a formal proof:
:By Equality is Reflexive, $\sqbrk x = \sqbrk x$.
:By Rule of Addition, $\sqbrk x < \sqbrk x \lor \sqbrk x = \sqbrk x$.
:By Axiom $\text M 8$, $\sqbrk x < \map s {\sqbrk x} \iff \paren {\sqbrk x < \sqbrk x \lor \sqbrk x = \sqbrk x}$
:By Biconditional Elimination and Modus Ponendo Ponens, $\sqbrk x < \map s {\sqbrk x}$
But:
:$\map s x = x + 1 = x + z$
Therefore:
:$\sqbrk {x + z} = \sqbrk {\map s x} = \map s {\sqbrk x}$
and the above proves:
:$\sqbrk x < \sqbrk {x + z}$
=== Induction Hypothesis ===
Suppose that there is a formal proof of:
:$\sqbrk x < \sqbrk {x + z}$
=== Induction Step ===
The following is a formal proof:
:By the induction hypothesis, $\sqbrk x < \sqbrk {x + z}$
:By Rule of Addition, $\sqbrk x < \sqbrk {x + z} \lor \sqbrk x = \sqbrk {x + z}$
:By Axiom $\text M 8$, $\sqbrk x < \map s {\sqbrk {x + z} } \iff \sqbrk x < \sqbrk {x + z} \lor \sqbrk x = \sqbrk {x + z}$
:By Biconditional Elimination and Modus Ponendo Ponens, $\sqbrk x < \map s {\sqbrk {x + z} }$
But $\map s {\sqbrk {x + z} } = \sqbrk {\map s {x + z} } = \sqbrk {x + \map s z}$.
Therefore, the above proves:
:$\sqbrk x < \sqbrk {x + \map s z}$
which satisfies the induction step.
Thus, by the Principle of Mathematical Induction, there is such a proof for every $z > 0$.
But by definition of ordering:
:$x < y \iff \exists z > 0: x + z = y$.
But then the formal proof above is also a proof for $\sqbrk x < \sqbrk y$.
Category:Ordering on Natural Numbers
Category:Proofs by Induction
Ordering of Naturally Ordered Semigroup is Strongly Compatible

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Then $\preceq$ is strongly compatible with $\circ$:
:$\forall m, n, p \in S: m \preceq n \iff m \circ p \preceq n \circ p$
== Proof ==
The forward implication is immediate from $\preceq$ being compatible with $\circ$:
:$\forall m, n, p \in S: m \preceq n \implies m \circ p \preceq n \circ p$
Conversely, suppose that $m \circ p \preceq n \circ p$.
Suppose that $n \prec m$.
Then as $\preceq$ is compatible with $\circ$:
:$n \circ p \preceq m \circ p$
Since $\preceq$ is an ordering, this implies:
:$n \circ p = m \circ p$
By , it follows that:
:$n = m$
contradicting our assumption that $n \prec m$.
Hence, since $\preceq$ is a total ordering:
:$m \preceq n$
as desired.
== Also see ==
* Strict Ordering of Naturally Ordered Semigroup is Strongly Compatible
Category:Naturally Ordered Semigroup
Ordering of Rational Cuts preserves Ordering of Associated Rational Numbers

== Theorem ==
Let $p \in\ Q$ and $q \in \Q$ be rational numbers.
Let $p^*$ and $q^*$ denote the rational cuts associated with $p$ and $q$.
Then:
:$p^* < q^* \iff p < q$
where $p^* < q^*$ denotes the strict ordering on cuts defined as:
:$\beta < \gamma \iff \exists p \in \Q: p \in \beta, p \notin \gamma$
== Proof ==
Let $p < q$.
Then $p \notin p^*$ but $q \in q^*$.
Thus $p^* < q^*$ by definition of the strict ordering on cuts .
Let $p^* < q^*$.
Then:
:$\exists r \in \Q: r \notin p^*, r \in q^*$
Hence:
:$p \le r < q$
and so:
:$p < q$
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.28$. Theorem: $\text {(c)}$
Category:Cuts
Ordering of Real Numbers is Reversed by Negation

== Theorem ==
Let $x$ and $y$ in $\R$ be real numbers such that:
:$x \le y$
Then:
:$-y \le -x$
where $-y$ and $-x$ are the negatives of $y$ and $x$ respectively.
== Proof ==
By definition of ordering:
:$x \le y$
:
:$x < y \text { or } x = y$
From Order of Real Numbers is Dual of Order of their Negatives:
:$x < y \iff \paren {-x} > \paren {-y}$
Hence the result.
Category:Real Numbers
Ordering of Reciprocals

== Theorem ==
Let $x, y \in \R$ be real numbers such that $x, y \in \openint 0 \to$ or $x, y \in \openint \gets 0$
Then:
:$x \le y \iff \dfrac 1 y \le \dfrac 1 x$
== Proof 1 ==
== Proof 2 ==
Category:Real Numbers
Category:Reciprocals
Category:Inequalities
Category:Ordering of Reciprocals
Ordering of Reciprocals/Proof 1

== Theorem ==
== Proof ==
By Reciprocal Function is Strictly Decreasing, the reciprocal function is strictly decreasing.
By Mapping from Totally Ordered Set is Dual Order Embedding iff Strictly Decreasing, the reciprocal function is a dual order embedding.
That is:
:$x \le y \iff \dfrac 1 y \le \dfrac 1 x$
Category:Ordering of Reciprocals
Ordering of Reciprocals/Proof 2

== Theorem ==
== Proof ==
By Reciprocal Function is Strictly Decreasing, the reciprocal function is strictly decreasing.
Thus 
:$x \le y \implies \dfrac 1 y \le \dfrac 1 x$
Suppose then that $\dfrac 1 y \le \dfrac 1 x$.
If $x, y > 0$, then from Reciprocal of Strictly Positive Real Number is Strictly Positive:
$\dfrac 1 y, \dfrac 1 x > 0$
Similarly, if $x, y < 0$ or $x, y > 0$, then from Reciprocal of Strictly Negative Real Number is Strictly Negative:
:$\dfrac 1 y, \dfrac 1 x < 0$
Thus we can apply the above to show that:
:$\dfrac 1 {1/x} \le \dfrac 1 {1/y}$
By Inverse of Multiplicative Inverse:
:$x \le y$
Category:Ordering of Reciprocals
Ordering of Series of Ordered Sequences

== Theorem ==
Let $\sequence {a_n}$ and $\sequence {b_n}$ be two real sequences.
Let $\ds \sum_{n \mathop = 1}^{\infty} a_n$ and $\ds \sum_{n \mathop = 1}^\infty b_n$ be convergent series.
For each $n \in \N$, let $a_n < b_n$.
Then:
:$\ds \sum_{n \mathop = 0}^\infty a_n < \sum_{n \mathop = 0}^\infty b_n$
== Proof 1 ==
== Proof 2 ==
Category:Ordering of Series of Ordered Sequences
Category:Series
Category:Real Analysis
Ordering of Series of Ordered Sequences/Proof 1

== Theorem ==
== Proof ==
Let $\sequence {\epsilon_n}$ be the real sequence defined by:
:$\forall n \in \N : b_n - a_n$
From Linear Combination of Convergent Series, $\ds \sum_{n \mathop = 0}^\infty \epsilon_n$ is convergent with sum $\epsilon > 0$.
Then:
Hence the result, by definition of inequality.
Category:Ordering of Series of Ordered Sequences
Ordering on 1-Based Natural Numbers is Compatible with Addition

== Theorem ==
Let $\N_{> 0}$ be the $1$-based natural numbers.
Let $+$ denote addition on $\N_{>0}$.
Let $<$ be the strict ordering on $\N_{>0}$.
Then:
:$\forall a, b, n \in \N_{>0}: a < b \implies a + n < b + n$
That is, $>$ is compatible with $+$ on $\N_{>0}$.
== Proof ==
== Sources ==
* : $2.2$: Theorem $2.11 \ \text{(i)}$
Category:Natural Numbers/1-Based
Ordering on 1-Based Natural Numbers is Compatible with Multiplication

== Theorem ==
Let $\N_{> 0}$ be the $1$-based natural numbers.
Let $\times$ denote multiplication on $\N_{>0}$.
Let $<$ be the strict ordering on $\N_{>0}$.
Then:
:$\forall a, b, n \in \N_{>0}: a < b \implies a \times n < b \times n$
That is, $<$ is compatible with $\times$ on $\N_{>0}$.
== Proof ==
== Sources ==
* : $2.2$: Theorem $2.11 \ \text{(ii)}$
Category:Natural Numbers/1-Based
Ordering on 1-Based Natural Numbers is Total Ordering

== Theorem ==
Let $\N_{> 0}$ be the $1$-based natural numbers.
Let $<$ be the strict ordering on $\N_{>0}$.
Then $<$ is a (strict) total ordering.
== Proof ==
From Ordering on $1$-Based Natural Numbers is Trichotomy we have that $<$ is trichotomy.
From Ordering on $1$-Based Natural Numbers is Transitive we have that $<$ is transitive.
From Trichotomy is Antireflexive it follows that $<$ is antireflexive.
It follows by definition that $<$ is a strict ordering.
By the trichotomy law it follows that $<$ is a strict total ordering.
== Sources ==
* : $2.2$: Theorem $2.10$
Category:Natural Numbers/1-Based
Ordering on 1-Based Natural Numbers is Transitive

== Theorem ==
Let $\N_{> 0}$ be the $1$-based natural numbers.
Let $<$ be the strict ordering on $\N_{>0}$.
Then $<$ is a transitive relation.
== Proof ==
Let $a < b$ and $b < c$.
Then:
== Sources ==
* : $2.2$: Theorem $2.9$
Category:Natural Numbers/1-Based
Ordering on 1-Based Natural Numbers is Trichotomy

== Theorem ==
Let $\N_{> 0}$ be the $1$-based natural numbers.
Let $<$ be the strict ordering on $\N_{>0}$.
Then exactly one of the following is true:
:$(1): \quad a = b$
:$(2): \quad a > b$
:$(3): \quad a < b$
That is, $<$ is a trichotomy on $\N_{> 0}$.
== Proof ==
Using the following axioms:
Axiom $E$ states:
:$\forall a, b \in \N_{>0}$, either:
::$a = b$, in which case $(1)$ holds
::$\exists x \in \N_{> 0}: a = b + x$, in which case, by definition of the ordering defined, $a > b$, in which case $(2)$ holds
::$\exists x \in \N_{> 0}: a + x = b$, in which case, by definition of the ordering defined, $a < b$, in which case $(3)$ holds.
Hence the result.
== Sources ==
* : $2.2$: Theorem $2.8$
Category:Natural Numbers/1-Based
Ordering on Closure Operators iff Images are Including

== Theorem ==
Let $L = \struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Let $f, g: S \to S$ be closure operators on $L$.
Then:
:$f \preceq g$ $g \sqbrk S \subseteq f \sqbrk S$
where
:$\preceq$ denotes the ordering on mappings
:$f \sqbrk S$ denotes the image of $f$.
== Proof ==
=== Sufficient Condition ===
Let $f \preceq g$.
Let $x \in g \sqbrk S$
By definition of image of mapping:
:$\exists y \in S: \map g y = x$
By definition of closure operator/idempotent:
:$\map g {\map g y} = \map g y$
By definition of ordering on mappings:
:$\map f {\map g y} \preceq \map g {\map g y}$
By definition of closure operator/inflationary:
:$\map g y \preceq \map f {\map g y}$
By definition of antisymmetry:
:$\map f x = x$
Thus by definition of image of mapping:
:$x \in f \sqbrk S$
=== Necessary Condition ===
Let $g \sqbrk S \subseteq f \sqbrk S$.
Let $x \in S$.
By definition of image of mapping:
:$\map g x \in g \sqbrk S$
By definition of subset:
:$\map g x \in f \sqbrk S$
By definition of image of mapping:
:$\exists a \in S: \map f a = \map g x$
By definition of closure operator/idempotent:
:$\map f {\map g x} = \map g x$
By definition of closure operator/inflationary:
:$x \preceq \map g x$
Thus by definition of closure operator/increasing:
:$\map f x \preceq \map g x$
== Sources ==
* 
* 
Category:Closure Operators
Ordering on Cuts is Compatible with Addition of Cuts

== Theorem ==
Let $\alpha$, $\beta$ and $\gamma$ be cuts.
Let the operation of $\alpha + \beta$ be the sum of $\alpha$ and $\beta$.
Let $\beta < \gamma$ denotes the strict ordering on cuts defined as:
:$\beta < \gamma \iff \exists p \in \Q: p \in \beta, p \notin \gamma$
Then:
:$\beta < \gamma \implies \alpha + \beta < \alpha + \gamma$
=== Corollary ===
== Proof ==
By definition of the strict ordering on cuts and addition of cuts:
:$\alpha + \beta \le \alpha + \gamma$
Suppose $\alpha + \beta = \alpha + \gamma$.
Then:
Thus:
:$\beta = \gamma$
and the result follows.
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.18$. Theorem
Category:Cuts
Category:Addition
Ordering on Cuts is Compatible with Addition of Cuts/Corollary

== Theorem ==
Let $\alpha$ and $\gamma$ be cuts.
Let the operation of $\alpha + \gamma$ be the sum of $\alpha$ and $\gamma$.
Let $0^*$ denote the rational cut associated with the (rational) number $0$.
If:
:$\alpha > 0^*$ and $\gamma > 0^*$
then:
:$\alpha + \gamma > 0^*$
where $>$ denotes the strict ordering on cuts.
== Proof ==
From Ordering on Cuts is Compatible with Addition of Cuts
:$0^* + 0^* < 0^* + \alpha$
:$\alpha + 0^* < \alpha + \gamma$
The result follows from Ordering on Cuts is Transitive.
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.18$. Theorem
Category:Cuts
Category:Addition
Ordering on Cuts is Total

== Theorem ==
Let $\CC$ denote the set of cuts.
Let $<$ denote the strict ordering on cuts defined as:
:$\forall \alpha, \beta \in \CC: \alpha < \beta \iff \exists p \in \Q: p \in \alpha, p \notin \beta$
Then $<$ is a (strict) total ordering on $\CC$.
== Proof ==
Let $\struct {\CC, <}$ denote the relational structure defined from the above.
From Ordering on Cuts is Transitive, $<$ is a transitive relation on $\CC$.
From Ordering on Cuts satisfies Trichotomy Law, we have that:
:$\alpha < \beta \implies \lnot \paren {\beta < \alpha}$
demonstrating that $<$ is asymmetric.
Hence, by definition, $<$ is a strict ordering.
Also by Ordering on Cuts satisfies Trichotomy Law, $\struct {\CC, <}$ has no non-comparable pairs:
:$\forall \alpha, \beta \in \CC: \alpha \ne \beta \implies \alpha < \beta \lor \beta < \alpha$
The result follows by definition of strict total ordering.
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.11$. Theorem
Category:Cuts
Ordering on Cuts is Transitive

== Theorem ==
Let $\alpha$, $\beta$ and $\gamma$ be cuts.
Let:
where $<$ denotes the strict ordering of cuts:
:$\alpha < \beta \iff \exists p \in \Q: p \in \alpha, p \notin \beta$
Then:
:$\alpha < \gamma$
Hence the ordering of cuts $\le$ is a transitive relation.
== Proof ==
We have that:
:$\alpha < \beta$
By definition of strict ordering of cuts:
:$\exists p \in \Q: p \in \beta, p \notin \alpha$
Similarly, we have that:
:$\beta < \gamma$
and so:
:$\exists q \in \Q: q \in \gamma, q \notin \beta$
We have by definition of a cut that:
:$p \in \beta$ and $q \notin \beta$ implies that $p < q$
Together with $p \notin \alpha$, this implies that $q \notin \alpha$.
Thus we have:
:$q \in \gamma$ and $q \notin \alpha$
from which by definition of strict ordering of cuts:
:$\alpha < \gamma$
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.11$. Theorem
Category:Cuts
Category:Examples of Transitive Relations
Ordering on Cuts satisfies Trichotomy Law

== Theorem ==
Let $\alpha$ and $\beta$ be cuts.
Then exactly one of the following applies:
where $<$ and so $>$ denote the strict ordering of cuts:
:$\alpha < \beta \iff \exists p \in \Q: p \in \alpha, p \notin \beta$
Hence the ordering of cuts $\le$ is a total ordering.
== Proof ==
Let $\alpha = \beta$.
By definition of equality of cuts:
:$p \in \alpha \iff p \in \beta$
By definition of strict ordering of cuts it follows that neither $\alpha < \beta$ or $\alpha > \beta$.
 both $\alpha < \beta$ and $\alpha > \beta$.
Because $\alpha < \beta$ there exists $p \in \Q$ such that:
:$p \in \beta, p \notin \alpha$
Because $\alpha > \beta$ there exists $q \in \Q$ such that:
:$q \in \alpha, q \notin \beta$
By Rational Number Not in Cut is Greater than Element of Cut:
:$p \in \beta$ and $q \notin \beta$ implies $p < q$.
:$q \in \alpha$ and $p \notin \alpha$ implies $p > q$.
But from Rational Numbers form Totally Ordered Field, $p < q$ and $p > q$ is not possible.
Hence by Proof by Contradiction, it is not possible for both $\alpha < \beta$ and $\alpha > \beta$.
Suppose either $\alpha < \beta$ or $\alpha > \beta$.
Then by definition of strict ordering of cuts it follows that $\alpha \ne \beta$.
Thus mutual exclusivity of the three conditions has been demonstrated.
That is, at most one of the three conditions holds.
It remains to be shown that at least one of the three conditions holds.
Suppose $\alpha \ne \beta$.
Then by definition of equality of cuts, either:
:$\exists p \in \alpha: p \notin \beta$
in which case $\alpha > \beta$, or:
:$\exists q \in \beta: q \notin \alpha$
in which case $\alpha < \beta$.
Hence the result.
== Sources ==
* : Chapter $1$: The Real and Complex Number Systems: Dedekind Cuts: $1.10$. Theorem
Category:Cuts
Ordering on Extended Real Numbers is Ordering

== Theorem ==
Denote with $\le$ the usual ordering on the extended real numbers $\overline \R$.
Then $\le$ is an ordering, and so $\overline \R$ is an ordered set.
== Proof ==
=== Transitive ===
Let $a, b, c \in \overline \R$.
Suppose that $a \le b$ and $b \le c$.
If $c = +\infty$, then by the definition of $\le$, $a \le c$.
If $b = +\infty$, then by Positive Infinity is Maximal, $b = c$, so $a \le c$.
If $a = +\infty$, then applying Positive Infinity is Maximal twice yields $a \le c$.
The cases for $a$, $b$, or $c$ being $-\infty$ are similar.
The only remaining case is that $a, b, c \in \R$.
Since $\le$ is transitive on $\R$, $a \le c$.
=== Antisymmetric ===
Let $a, b \in \overline{\R}$.
Suppose that $a \le b$ and $b \le a$.
If $a \in \R$ and $b \in \R$, then since $\le$ is antisymmetric on $\R$, $a = b$.
If $a = +\infty$, then since $a \le b$ and Positive Infinity is Maximal, $b = +\infty$.
Thus $a = b$.
If $a = -\infty$, then since $b \le a$ and Negative Infinity is Minimal, $b = -\infty$.
Similarly $b = +\infty \implies a = +\infty$ and $b = -\infty \implies a = -\infty$.
=== Reflexive ===
Let $a \in \overline \R$.
If $a \in \R$, then since $\le$ is reflexive on $\R$, $a \le a$.
If $a = +\infty$, then since $\tuple {+\infty, +\infty} \in \set {\tuple {x, +\infty}: x \in \overline \R}$, $a \le a$.
Similarly, if $a = -\infty$, then $a \le a$.
Category:Usual Ordering on Extended Real Numbers
Ordering on Integers is Transitive

== Theorem ==
Let $\eqclass {a, b} {}$ denote an integer, as defined by the formal definition of integers.
Then:
That is, ordering on the integers is transitive.
== Proof ==
By the formal definition of integers, we have that $a, b, c, d, e, f$ are all natural numbers.
To eliminate confusion between integer ordering and the ordering on the natural numbers, let $a \preccurlyeq b$ denote that the natural number $a$ is less than or equal to the natural number $b$.
We have:
Category:Orderings on Integers
Ordering on Mappings Implies Galois Connection

== Theorem ==
Let $\struct {S, \preceq}$, $\struct {T, \precsim}$ be ordered sets.
Let $g: S \to T$ and $d: T \to S$ be mappings such that:
:$g$ and $d$ are increasing mappings 
and
:$d \circ g \preceq I_S$ and $I_T \precsim g \circ d$
Then
:$\struct {g, d}$ is Galois connection.
where
:$\preceq, \precsim$ denote the orderings on mappings
:$I_S$ denotes the identity mapping of $S$
:$\circ$ denotes the composition of mappings.
== Proof ==
We will prove that:
:$\forall s \in S, t \in T: t \precsim \map g s \iff \map d t \preceq s$
Let $s \in S, t \in T$.
First implication:
Let
:$t \precsim \map g s$
By definition of increasing mapping:
:$\map d t \preceq \map d {\map g s}$
By definition of ordering on mappings:
:$\map {\paren {d \circ g} } s \preceq \map {I_S} s$
By definition of composition:
:$\map d {\map g s} \preceq \map {I_S} s$
By definition of identity mapping:
:$\map d {\map g s} \preceq s$
Thus by definition of transitivity:
:$\map d t \preceq s$
Second implication:
Let
:$\map d t \preceq s$
By definition of increasing mapping:
:$\map g {\map d t} \precsim \map g s$
By definition of ordering on mappings:
:$\map {I_T} t \precsim \map {\paren {g \circ d} } t$
By definition of composition:
:$\map {I_T} t \precsim \map g {\map d t}$
By definition of identity mapping:
:$t \precsim \map g {\map d t}$
Thus by definition of transitivity:
:$t \precsim \map g s$
Thus by definition:
:$\struct {g, d}$ is Galois connection.
== Sources ==
* 
* 
Category:Galois Connections
Ordering on Multiindices is Partial Order

== Theorem ==
Let $Z$ be the set of multiindices indexed by a set $J$.
The ordering on $Z$ is a partial ordering.
== Proof ==
Let $\le$ denote the ordering on integers.
Let $\preceq$ denote the ordeing on multiindices.
Recall that if $k = \family {k_j}_{j \mathop \in J}$ and $\ell = \family {\ell_j}_{j \mathop \in J}$ are multiindices, then $k \le \ell$ if $k_j \preceq \ell_j$ for all $j \in J$.
Let $k$ and $\ell$ be as above, and let $m = \family {m_j}_{j \mathop \in J} \in Z$.
From Integers under Addition form Totally Ordered Group, the integers are totally ordered by $\le$.
Hence the ordering on the integers is reflexive, antisymmetric and transitive.
=== Reflexivity ===
By reflexivity of $\le$, we have for all $j \in J$:
:$k_j \le k_j$
This shows that $\preceq$ is reflexive.
=== Antisymmetry ===
Suppose that $k \preceq \ell$ and $\ell \preceq k$.
Then for all $j \in J$, we have:
:$k_j \le \ell_j \le k_j$
By antisymmetry of $\le$, we have $k_j = \ell_j$ for all $j$, that is, $k = \ell$.
This shows $\preceq$ to be antisymmetric.
=== Transitivity ===
Suppose that $k \preceq \ell$ and $ell \preceq m$.
Then for all $j \in J$, we have:
:$k_j \le \ell_j$ and $\ell_j \le m_j$
By transitivity of $\le$, this shows that for all $j \in J$, $k_j \le m_j$.
Therefore $k \preceq m$, and $\preceq$ is shown to be transitive.
Category:Polynomial Theory
Ordering on Natural Numbers is Compatible with Addition

== Theorem ==
Let $m, n, k \in \N$ where $\N$ is the set of natural numbers.
Then:
:$m < n \iff m + k < n + k$
=== Corollary ===
== Proof ==
Proof by induction:
For all $k \in \N$, let $\map P k$ be the proposition:
:$m < n \iff m + k < n + k$
$\map P 0$ is true, as this just says $m + 0 = m < n = n + 0$.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P j$ is true, where $j \ge 0$, then it logically follows that $\map P {j^+}$ is true.
So this is our induction hypothesis:
:$m < n \iff m + j < n + j$
Then we need to show:
:$m < n \iff m + j^+ < n + j^+$
=== Induction Step ===
This is our induction step:
Let $m < n$.
Then:
This gives:
So $\map P j \implies \map P {j^+}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall m, n, k \in \N: m < n \iff m + k < n + k$
== Sources ==
* : Introduction $\S 4$: The natural numbers
* : $\S 13$: Arithmetic
* : $\S 4$: Number systems $\text{I}$: Peano's Axioms
Category:Natural Number Addition
Category:Examples of Orderings
Ordering on Natural Numbers is Compatible with Addition/Corollary

== Corollary to Ordering on Natural Numbers is Compatible with Addition ==
Let $a, b, c, d \in \N$ where $\N$ is the set of natural numbers.
Then:
:$a > b, c > d \implies a + c > b + d$
== Proof ==
Finally:
== Sources ==
* : Introduction $\S 4$: The natural numbers: Exercise $1$
Category:Natural Number Addition
Category:Examples of Orderings