11.27 Total Order

Basic_concepts__Copy_ 1.pdf

Workshop 7

Exercise 1

Let \(E\) be a set and \(A\) and \(B\) two subsets of \(E\). Of which sets are the following functions the characteristic functions?

1. \(\min (1_A, 1_B)\).

   \(A\cap B\)​

2. \(\max (1_A, 1_B)\).

   \(A\cup B\)​

3. \(1_A \cdot 1_B\).

   \(A\cap B\)​

4. \(1 - 1_A\).

   \(\bar A\)​

5. \(1_A + 1_B - 1_A \cdot 1_B\).

   \(A\cup B\)​

6. \((1_A - 1_B)^2\).

   0=1-1/0-0

   1=1-0/0-1

   Which means

   0 if \(x\in A\) and \(x\in B\), then \(x\in A\cap B\)

   0 if \(x\notin A\) and \(x\notin B\), then \(x\notin A\cup B\)

   1 if \(x\in A\) and \(x\notin B\), then \(x\in A\setminus B\)

   1 if \(x\notin A\) and \(x\in B\), then \(x\in B\setminus A\)

   Then

   \(\left(A\setminus B\right)\cup\left(B\setminus A\right)\)​

---

Exercise 2

Any finite subset of a totally ordered set \((E, \preceq)\) has a greatest element and a smallest element. Show that this result is false if the order is no longer total.

By contrapositive, we need to prove Any finite subset of a totally ordered set \((E, \preceq)\) has a greatest element and a smallest element.

Let \(E=\{x_1,x_2,\ldots,x_{n}\}\)​

Claim: \(x_1\) is the smallest element and \(x_n\) is the greatest element.

Since

Since \(E\) is a total order set and finite, then \(\forall x,y\in E:x\preceq y\text{ or }y\preceq x\)

Then we can compare until we have the least one called \(x_1\)​

---

Exercise 3

Let \((E, \leq)\) be an ordered set. Let \(A\) be a nonempty subset of \(E\) having a smallest element and a greatest element.

1. Show that \(\min A \leq \max A\).

   \(x\geq \min A\) and \(x\leq \max A\) for any \(x\)​

2. What can we say about \(A\) if \(\min A = \max A\)?

   \(A\) has only one element

---

Exercise 4

Let \(E\) be a nonempty set. Consider the order induced by inclusion on \(P(E)\). Let \(\mathcal{A}\) be a subset of \(P(E)\).

1. Show that \(\bigcap_{A\in \mathcal{A}}A\) is a lower bound for \(\mathcal{A}\).

   We need to prove \(\forall A\in\mathcal{A},\bigcap_{A\in\mathcal{A}}A\subseteq A\)​

   Take a set \(x\in\bigcap_{A\in\mathcal{A}}A\Rightarrow x\in A\text{ for all }A\in\mathcal{A}\Rightarrow\forall A\in\mathcal{A},x\in A\)

2. Deduce that \(\mathcal{A}\) has a minimum in \((P(E),\subset)\). for B a lower bound then \(B \subset \bigcap\)

   From (1), we know \(\mathcal{A}\) has a lower bound \(\bigcap_{A\in \mathcal{A}}A\), then \(\mathcal{A}\) has a lower bound in \((P(E),\subset)\).

3. Show that \(\mathcal{A}\)​ has an upper bound in \((P(E), \subset)\).

   Claim: \(\bigcup_{A\in \mathcal{A}}A\) is an upper bound for \(\mathcal{A}\).

   We need to prove \(\forall A\in\mathcal{A}, A\subseteq\bigcup_{A\in\mathcal{A}}A\)

   Take \(x\in A\Rightarrow x\in A\text{ for some }A\in\mathcal{A}\Rightarrow\bigcup_{A\in\mathcal{A}}A\)​

---

Exercise 5

Let \((E,\leq)\) be an ordered set. Show that if \(A\) and \(B\) are two subsets of \(E\) such that \(\sup(A)\), \(\sup(B)\) and \(\sup\left\lbrace\sup(A),\sup(B)\right\rbrace\) exist, then \(\sup(A \cup B)\) exists and calculate it (we can try on examples to get an idea of the result to prove).

\(A=[1,3]\) and \(B=[2,4]\), \(\sup(A)=3\) and \(\sup(B)=4\)

\(\sup\{\sup\left(A\right)=3,\sup\left(B\right)=4\}=4\)

\(\sup(A\cup B)=\sup\left(\left\lbrack1,4\right\rbrack\right)=4\)

Claim: \(\sup(A\cup B)=\sup\left\lbrace\sup(A),\sup(B)\right\rbrace\)

Two cases

If \(\sup(A)\geq\sup(B)\), then \(\sup\left\lbrace\sup(A),\sup(B)\right\rbrace=\sup(A)\).

Then we have \(\exists a_0\in A:a_0\geq a,\forall a\in A\) and \(\exists a_0\in A:a_0\geq b,\forall b\in B\)

Then \(\exists a_0\in A:a_0\geq x,\forall x\in A\cup B\)

Since \(a_0\in A\subseteq A\cup B\), then \(a_0\) is the sup of \(A\) and the sup of \(A\cup B\)

Thus \(\sup(A\cup B)=\sup(A)\)

Thus \(\sup(A\cup B)=\sup\left\lbrace\sup(A),\sup(B)\right\rbrace\)

Another case is similar

---

Exercise 6

1. Let \(f : \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\), and let \(A = [-1, 4]\). Determine:

   • the direct image of \(A\) by \(f\);

   \([0,16]\)​ * the inverse image of \(A\) by \(f\).

   Since \(x^2>0\), then \(A\) only can be \([0,4]\), thus \(x^2\in[0,4]\)​

   Then \(x\in[-2,2]\)​

2. Consider the function \(\sin : \mathbb{R} \to \mathbb{R}\). What is the direct image, by \(\sin\), of \(\mathbb{R}\)? Of \([0, 2\pi]\)? Of \([0, \pi/2]\)? What is the inverse image, by \(\sin\), of \([0, 1]\)? Of \([3, 4]\)? Of \([1, 2]\)?

   \([-1,1],\left\lbrack-1,1\right\rbrack,\left\lbrack0,1\right\rbrack\)​

   \(\left\lbrack2k\pi,2k\pi+\frac{\pi}{2}\right\rbrack,\emptyset,\left\lbrace x=2k\pi+\frac{\pi}{2}\right\rbrace\)​

---

Exercise 7 (\(\star\))

Let \(E\) and \(F\) be two sets and \(f : E \to F\). Prove that:

\(f:\{1,2,3\}\rightarrow\{2,3,4\}\)​

1. \(\forall A \in P(E), A \subset f^{-1}(f(A))\).

   \(A\in P(E)\Rightarrow A\subseteq E\)​

   Take any element \(x\in A\), then \(x\in E\Rightarrow f\left(x\right)\in f\left(A\right)\Rightarrow x\in f^{-1}\left(f\left(A\right)\right)\)

2. \(\forall B \in P(F), f(f^{-1}(B)) \subset B\).

   \(B\in P(E)\Rightarrow B\subseteq E\)

   Take ant element \(b\in f(f^{-1}(B))\), then \(f^{-1}(b)\in f^{-1}\left(B\right)\Rightarrow b\in B\)​

3. (\(\star\)) Does equality hold in general?

   Yes

---

Exercise 8 (\(\star\))

Let \(E\) and \(F\) be two sets and let \(f : E \to F\). Take \(A\) and \(B\) two subsets of \(F\).

1. Prove that \(A \subset B \implies f^{-1}(A) \subset f^{-1}(B)\). Is the converse true?

   Take \(x\in f^{-1}\left(A\right)\), then \(f(x)\in A\Rightarrow f\left(x\right)\in B\Rightarrow x\in f^{-1}\left(B\right)\)​

2. Prove that \(f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)\).

   \(\Rightarrow\)) Take \(x\in f^{-1}(A \cap B)\), then \(f(x)\in A\cap B\Rightarrow f\left(x\right)\in A\) and \(f(x)\in B\)​

   Then \(x\in f^{-1}(A)\) and \(x\in f^{-1}(B)\Rightarrow x\in f^{-1}\left(A\right)\cap f^{-1}\left(B\right)\)​

   \(\Leftarrow\)) Take \(x\in f^{-1}(A)\cap f^{-1}(B)\), then \(x\in f^{-1}(A)\) and \(x\in f^{-1}(B)\Rightarrow f\left(x\right)\in A\) and \(f(x)\in B\)​

   Then \(f(x)\in A\cap B\Rightarrow x\in f^{-1}(A\cap B)\)​

3. Prove that \(f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)\).

   \(\Rightarrow\)) Take \(x\in f^{-1}(A\cup B)\), then \(f(x)\in A\cup B\Rightarrow f\left(x\right)\in A\) or \(f(x)\in B\)

   Then \(x\in f^{-1}(A)\) or \(x\in f^{-1}(B)\Rightarrow x\in f^{-1}\left(A\right)\cup f^{-1}\left(B\right)\)

   \(\Leftarrow\)) Take \(x\in f^{-1}(A)\cup f^{-1}(B)\), then \(x\in f^{-1}(A)\) or \(x\in f^{-1}(B)\Rightarrow f\left(x\right)\in A\) or \(f(x)\in B\)

   Then \(f(x)\in A\cup B\Rightarrow x\in f^{-1}(A\cup B)\)

---

Exercise 9 (\(\star\))

Let \(E,F\) be two sets and \(f : E \to F\). Let \(A \subset E\) and \(B \subset F\).

Prove the equivalence: \(f(A) \cap B = \emptyset \iff A \cap f^{-1}(B) = \emptyset.\)

\(\Rightarrow\)) To prove \(A\cap f^{-1}(B)=\emptyset\), we need to take \(x\in A\text{ to prove } x\notin f^{-1}\left(B\right)\)

Take \(x\in A\), then \(f(x)\in f(A)\Rightarrow f\left(x\right)\notin B\Rightarrow x\notin f^{-1}\left(B\right)\)

\(\Leftarrow\)) Similarly