Skip to content

11.27 Function

  1. Let \(A\) be a non-empty set and \(\subseteq\) be the ordering for \(\mathcal{P}(A)\).

    1. If \(B \in \mathcal{P}(A)\) and \(x \in B \implies B - \{x\}\) is an immediate predecessor of \(B\).

      Proof

      Suppose \(B-\{x\}\) is not an immediate predecessor of \(B\), then exists \(X\in \mathcal{P}(A)\) such that \(B-\left\lbrace x\right\rbrace RX\wedge XRB\) and \(B-\left\lbrace x\right\rbrace\neq B\neq X\)​

      Then we know \(B-\left\lbrace x\right\rbrace\subset X\subset B\Rightarrow\) exists an element \(b_1\in B,b_1\notin X\) and \(b_2\in X,b_2\notin B-\left\lbrace x\right\rbrace\)

      Thus there exists at least two element in \(B\) but not in \(B-\{x\}\), which is a contradiction to there is only one element \(x\) in \(B\) but not in \(B-\{x\}\) 2. Let \(C, D\) be subsets of \(A\). Prove that the least upper bound of \(\{C, D\}\) is \(C \cup D\), and the greatest lower bound of \(\{C, D\}\) is \(C \cap D\).

      Proof

      To prove that the least upper bound of \(\{C, D\}\) is \(C \cup D\), we need to prove \(\forall X\in\{C,D\},X\subseteq\left(C\cup D\right)\)

      Since \(C \subseteq C \cup D\) and \(D \subseteq C \cup D\), then \(\forall X\in\{C,D\},X\subseteq\left(C\cup D\right)\)

      Thus \(C\cup D\) is an upper bound, then we prove it is the least one

      Suppose it is not the least upper bound, then there exists a set \(M\subset\left(C\cup D\right)\) such that \(\forall X\in\{C,D\},X\subseteq M\)

      Then there exists an element \(m\in(C\cup D)\) but \(\notin M\)

      Since \(m\notin M\), then \(m\notin X\Rightarrow m\notin C\wedge m\notin D\Rightarrow m\notin\left(C\cup D\right)\) Contradiction! 3. Let \(\mathcal{P}\) be a family of subsets of \(A\). Prove that the least upper bound is \(\bigcup_{B \in \mathcal{P}} B\) and the greatest lower bound of \(\mathcal{P}\) is \(\bigcap_{B \in \mathcal{P}} B\).

      Induction

  2. Let \(A\) be the set \(\{1, 2, 3\}\) and let \(R\) be the relation on \(A\) given by \(\left\lbrace\left(x,y\right):3x+y\text{ is prime}\right\rbrace\)​ Prove that \(R\) is a function with domain \(A\).

    If \(x = 1 \implies (1, 2) \in R\), so \(1\) is in the domain, and \(2\) is the only element such that \(1\) is related to.

    If \(x = 2 \implies (2, 1) \in R\), so \(x = 2\) is in the domain. Since \(2\cancel{R}2\) and \(2\cancel{R}3\) are false \(\implies (2, 1)\) is the only possible pair.

    If \(x = 3 \implies (3, 2) \in R \implies x = 3\) is in the domain. Since \((3, 1) \notin R\) and \((3, 3) \notin R\) \(\implies (3, 2)\) is the only possible pair.

  3. For the canonical map \(f : \mathbb{Z} \to \mathbb{Z}_6\), find:

    a) \(f(3)\) Solution: \(f(3) = \overline{3} = 3 / \equiv_6 = \{3, 9, 15, \ldots\} = \{n \in \mathbb{Z} \mid n \equiv_6 3\} = \{6k + 3 \mid k \in \mathbb{Z}\}\).

    b) The preimage of \(\overline{1}\). Solution: \(\text{Preimage of } \overline{1} = \{x \in \mathbb{Z} \mid f(x) = \overline{1}\} = \{1, 7, 13, 19, -5, \ldots\} = \{6k + 1 \mid k \in \mathbb{Z}\}\).

  4. True or False?

    a) Let \(A \subseteq X \implies\) the identity function on \(A\) \(\text{id}: A \to A\) is equal to the inclusion function from \(A\) to \(X\) in \(\text{id}: A \to X\). False, because they have different codomains.

    b) The image of the function \(f(x) = \frac{x^2 - 7x + 12}{x - 3}\) is \(\mathbb{R}\). False, because since \(3 \notin \text{Dom}(f)\), \(\implies 3 \notin \text{Im}(f)\).

    c) Let \(A = \bigcap_{n=1}^\infty (0, \frac{1}{n}] \subseteq \mathbb{R} \implies \chi_A(0) = 0\). True, because \(0 \notin A\). For example, \(0 \notin (0, \frac{1}{2}] \cap (0, \frac{1}{3}] \cap \cdots\).