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$.


This needs considerable tedious hard slog to complete it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Condition_for_Ordered_Set_of_All_Mappings_to_be_Total_Ordering&oldid=567409"