Beginning Activity Beginning Activity 2: Functions from a Set to Its Power Set
Let \(A\) be a set. In Section 5.1, we defined the power set \(\mathcal{P} ( A )\) of \(A\) to be the set of all subsets of \(A\text{.}\) This means that \(X \in \mathcal{P} ( A )\) if and only if \(X \subseteq A\text{.}\) Theorem 5.9 in Section 5.1 states that if a set \(A\) has \(n\) elements, then \(A\) has \(2^n\) subsets or that \(\mathcal{P} ( A )\) has \(2^n\) elements. Using our current notation for cardinality, this means that if \(\text{ card} ( A ) = n\text{,}\) then \(\text{ card} ( \mathcal{P} ( A ) ) = 2^n\text{.}\) (The proof of this theorem was Activity 29.)
We are now going to define and explore some functions from a set \(A\) to its power set \(\mathcal{P} ( A )\text{.}\) This means that the input of the function will be an element of \(A\) and the output of the function will be a subset of \(A\text{.}\)
1.
Let \(A = \left\{1, 2, 3, 4 \right\}\text{.}\) Define \(f\x A \to \mathcal{P} ( A )\) by
(a)
Is \(1 \in f ( 1 )\text{?}\) Is \(2 \in f ( 2 )\text{?}\) Is \(3 \in f ( 3 )\text{?}\) Is \(4 \in f ( 4 )\text{?}\)
(b)
Determine \(S = \left\{ x \in A \mid x \notin f ( x ) \right\}\text{.}\)
(c)
Notice that \(S \in \mathcal{P} ( A )\text{.}\) Does there exist an element \(t\) in \(A\) such that \(f ( t ) = S\text{?}\) That is, is \(S \in \text{ range} ( f )\text{?}\)
2.
Let \(A = \left\{1, 2, 3, 4 \right\}\text{.}\) Define \(f\x A \to \mathcal{P} ( A )\) by
(a)
Determine \(f ( 1 )\text{.}\) Is \(1 \in f ( 1 )\text{?}\)
(b)
Determine \(f ( 2 )\text{.}\) Is \(2 \in f ( 2 )\text{?}\)
(c)
Determine \(f ( 3 )\text{.}\) Is \(3 \in f ( 3 )\text{?}\)
(d)
Determine \(f ( 4 )\text{.}\) Is \(4 \in f ( 4 )\text{?}\)
(e)
Determine \(S = \left\{ x \in A \mid x \notin f ( x ) \right\}\text{.}\)
(f)
Notice that \(S \in \mathcal{P} ( A )\text{.}\) Does there exist an element \(t\) in \(A\) such that \(f ( t ) = S\text{?}\) That is, is \(S \in \text{ range} ( f )\text{?}\)
3.
Define \(f\x \mathbb{N} \to \mathcal{P} ( \mathbb{N} )\) by
(a)
Determine \(f ( 1 )\text{,}\) \(f ( 2 )\text{,}\) \(f ( 3 )\text{,}\) and \(f ( 4 )\text{.}\) In each of these cases, determine if \(k \in f ( k )\text{.}\)
(b)
Prove that if \(n > 3\text{,}\) then \(n \in f ( n )\text{.}\)
Prove that if \(n >3\text{,}\) then \(n^2 > n\) and \(n^2 - 2n >n\text{.}\)
(c)
Determine \(S = \left\{ x \in \mathbb{N} \mid x \notin f ( x ) \right\}\text{.}\)
(d)
Notice that \(S \in \mathcal{P} ( \mathbb{N} )\text{.}\) Does there exist an element \(t\) in \(\mathbb{N}\) such that \(f ( t ) = S\text{?}\) That is, is \(S \in \text{ range} ( f )\text{?}\)