Skip to content

11.25 Total Order

Proposition

If \(B\) has a supremum (resp. infimum), then it is unique.

Proof

Suppose that \(a\) and \(a'\) are both supremum for \(B\).

  • \(a \leq a'\) because \(a\) is a supremum and \(a'\) is an upper bound,
  • \(a' \leq a\) because \(a'\) is a supremum and \(a\) is an upper bound.

Therefore, \(a = a'\).

From this proposition, we denote \(\sup B = \text{supremum of } B\), \(\inf B = \text{infimum of } B\).

Proposition

  1. If \(a\) is a maximum for \(B\), then \(a = \sup B\).

  2. If \(a\) is a minimum for \(B\), then \(a = \inf B\).

Exercise.

Some Definitions

Total order

Let \((A, \leq)\) be a poset. We say that \(\leq\) is a total order if \(\forall x, y \in A\), we have \(x \leq y\) or \(y \leq x\).

In other words, a relation \(\leq\) on \(A\) is a total order if:

  • \(\leq\) is reflexive.

  • \(\leq\) satisfies trichotomy: \(\forall x, y \in A\), one and only one of the following conditions holds:

  • \(x < y\),

  • \(x = y\),
  • \(x > y\).
  • \(\leq\) is transitive.
Example

The usual order on \(\mathbb{R}\) is a total order.

Non-example

\(\mid\) on \(\mathbb{N}\) is not a total order because \(2 \nmid 3\), \(3 \nmid 2\), \(3 \neq 2\).

Notation

A set \(A\) with a total order is called an ordered set.

Example

  1. Let \(A = \mathbb{R}^2\) and \(\leq\) is defined as:

    \((x,y)\leq(x^{\prime},y^{\prime})\text{ if }(x<x^{\prime})\text{ or }(x=x^{\prime}\text{ and }y\leq y^{\prime}).\)

    This is known as the lexicographical order.

    image​

  2. \(\leq\) is a total order.

    Exercise

Well-Ordered

An ordered set \((A, \leq)\) is called well-ordered if any non-empty subset \(B \subseteq A\) has a minimum (or first element).

Example: \(\mathbb{N}\) with the usual order is a well-ordered set.

Theorem

Any set \(A\) admits a total order \(\leq\) such that \((A, \leq)\) is well-ordered.

Counterexamples:

  • \((0, 1)\) does not have a first element.
  • \(\mathbb{R}\) with the usual order does not have a first element.

Function

Definition

Given two sets \(A, B\), a function from \(A\) to \(B\) is a relation \(f \subseteq A \times B\) such that:

  • \(\text{Dom } f = A\),
  • \(x f y \land x f y' \implies y = y'\).

In other words, a function is a relation such that any \(x \in A\) is related to one and only one element of \(B\).

image​

Non-example

The diagram shows a relation that is not a function from \(A\) to \(B\) because some elements of \(A\) are related to multiple elements of \(B\).

image​

image​

Notation

If \(f\) is a function from \(A\) to \(B\), then we write \(f: A \to B\) or \(A \xrightarrow{f} B\).

If \(x \in A\), \(y \in B\), and \(f(x) = y\), then \(y\) is called the value of \(f\) at \(x\).

More notation

  • \(A =\) domain of \(f = \text{Dom } f\).
  • \(B =\) codomain of \(f = \text{Codom } f\).
  • \(\text{Rg } f =\) image of \(f = \text{Im } f = \{ y \in B : \exists x \text{ s.t. } f(x) = y \}\).

Given \(y \in B\), the preimage of \(y\) is the set: \(f^{-1}(y)=\{x\in A:f(x)=y\}.\)​

Example

Let \(A = \{1, 2, 3, 4\}\) and \(B = \mathbb{R}\).

  • This is a function, where:

  • \(\text{Dom } f = A\),

  • \(f(1) = 2\), \(f(2) = 1\), \(f(3) = \pi\), \(f(4) = 1\),
  • \(\text{Codom } f = \mathbb{R}\),
  • \(\text{Im } f = \{2, 1, \pi\}\).

image​

For preimages:

  • \(f^{-1}(1) = \{2, 4\} \subseteq A\),
  • \(f^{-1}(2) = \{1\}\),
  • \(f^{-1}(\pi) = \{3\}\),
  • \(f^{-1}(y)=\emptyset\ \forall y\notin\{1,2,\pi\}\).

Remark

Some relations are "close" to being functions.

Example 1: \(\{(x, \frac{1}{x}) : x \neq 0\} \subseteq \mathbb{R} \times \mathbb{R}\).

image​

  • This is not a function from \(\mathbb{R}\) to \(\mathbb{R}\) because the domain \(\neq \mathbb{R}\).
  • However, it is a function from \(\mathbb{R} \setminus \{0\} \to \mathbb{R}\).

Example 2: \(\{(x^2, x) : x \in \mathbb{R} \geq 0\}\).

image​

  • This is a relation from \(\mathbb{R}_{\geq 0}\) to \(\mathbb{R}\), but it is not a function from \(\mathbb{R}_{\geq 0}\) to \(\mathbb{R}\) because \(1R1\) and \(1R-1\).
  • However, it is a function from \(\mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}\), defined as \(f(x) = \sqrt{x}\).

image​

Remark

To define a function, we need to tell:

  • \(A\) and \(B\)
  • What is \(f(x)\) for any \(x \in A\).

Example: \(f(n) = n^2\) is a function from \(\mathbb{N} \to \mathbb{N}\).

Remark:

Sometimes, we only give \(f(x)\) and deduce \(A\) and \(B\) from the context.

Example: \(f(x) = \frac{1}{x}\)

Remark:

When are two functions \(A \to B\) and \(A' \to B'\) the same?

  • When \(A = A'\), \(B = B'\) and \(f(x) = f'(x)\) for all \(x \in A\).

Example: \(f: \mathbb{N} \to \mathbb{N}\), \(f(n) = n^2\). \(g: \mathbb{N} \to \mathbb{N}\), \(g(n) = \sum_{k=1}^{n} (2k-1)\). By induction, we can prove that \(g(n) = g(n)\) for all \(k \in \mathbb{N}\), so \(f = g\).

SOME SPECIAL FUNCTIONS.

  • The identity function of a set \(A\): \(\text{Id}_{A}:A\to A.\quad\text{Id}_{A}(x)=x\quad\forall x\in A\)

  • Let \(A \subseteq U\) be a subset. The inclusion is the function \(i: A \to U\), where \(i(x) = x \quad \forall x \in A\).

  • Characteristic function of a subset.

Let \(A \subseteq U\) be a subset. We define \(\chi_{A}:U\to\{0,1\},\quad\chi_{A}(x)=\begin{cases}1 & \text{if }x\in A\\ 0 & \text{if }x\in U-A\end{cases}\)​

image​ * Let \(U = \mathbb{R}\), \(A = [0,1] \cup [2,3]\).

image​

Given a partition \(\mathcal{P} = \{A_i: i \in I\}\) of a set \(A\), and given \(b_i \in B\) for each \(i\), we define a function \(f: A \to B\) as \(f(x) = b_i \quad \text{if} \quad x \in A_i\)

image​ * Let \(\mathbb{R} = \bigcup_{n \in \mathbb{Z}} [n, n+1)\) and define \(f: \mathbb{R} \to \mathbb{Z}\) as \(f(x) = n \quad \text{if} \quad x \in [n, n+1)\)​

This function is also called the floor function, and we write \(f(x) = \left\lfloor x \right\rfloor\)​

image​ * Given an equivalence relation \(\mathcal{R}\) on \(X\), we define the canonical function \(\pi: X \to X / \mathcal{R}\), where \(\pi(x)=x/\mathcal{R}\in X/\mathcal{R}\)​

Example Let \(X = \mathbb{Z}\), \(\mathcal{R}=\equiv _m\) and \(X/\mathcal{R}=\mathbb{Z}_{m}=\{\overline0,\overline1,\dots,\overline{m-1}\}\).

We define \(\pi(a) = \bar{a} = \{a + km : k \in \mathbb{Z}\}\)​ * A function \(f: \mathbb{N} \to B\) is called a sequence.

We denote \(f(1) = f_1\), \(f(2) = f_2\), ..., \(f(n) = f_n\).

Where:

  • The first element is \(f_1\)
  • The \(n\)-th element is \(f_n\).

Example: \(f_n = 1 + \frac{1}{n}\)

‍