Condition for Ordered Set of All Mappings to be Total Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\struct {T, \preccurlyeq}$ be an ordered set.

Let $\struct {T^S, \preccurlyeq}$ denote the ordered set of all mappings from $S$ to $T$.


Then:

$\struct {T^S, \preccurlyeq}$ is a totally ordered set

if and only if:

$\card S \le 1$

or:

$\card T \le 1$


Proof

Sufficient Condition

Let $\struct {T^S, \preccurlyeq}$ be a totally ordered set.


Let $f, g \in T^S$ be arbitrary.


Let $S$ and $T$ be such that:

\(\ds \exists a, b \in S: \, \) \(\ds a\) \(\ne\) \(\ds b\)
\(\ds \exists x, y \in T: \, \) \(\ds x\) \(\ne\) \(\ds y\)


Let $f: S \to T$ be defined as:

\(\ds \map f a\) \(=\) \(\ds x\)
\(\ds \map f b\) \(=\) \(\ds y\)
\(\ds \map g a\) \(=\) \(\ds y\)
\(\ds \map g b\) \(=\) \(\ds x\)


As $\struct {T^S, \preccurlyeq}$ is a totally ordered set, either $f \preccurlyeq g$ or $g \preccurlyeq f$.

Suppose $f \preccurlyeq g$.

Then:

\(\ds \map f a\) \(\preccurlyeq\) \(\ds \map g a\)
\(\ds \map f b\) \(\preccurlyeq\) \(\ds \map g b\)
\(\ds \leadsto \ \ \) \(\ds x\) \(\preccurlyeq\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds y\) \(\preccurlyeq\) \(\ds x\)

As $x \ne y$ this shows that $\preccurlyeq$ is not antisymmetric on $T$.

This contradicts the assumption that $\struct {T, \preccurlyeq}$ is an ordered set.

Hence if both $\card T > 1$ and $\card S > 1$ it cannot be the case that $\struct {T^S, \preccurlyeq}$ is a totally ordered set.

Thus by the Rule of Transposition, either $\card T \le 1$ or $\card S \le 1$.




Sources