Skip to main content

Beginning Activity Beginning Activity 2: Functions from a Set to Its Power Set
A4US

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

\begin{align*} f ( 1 ) \amp = \left\{ 1, 2, 3 \right\} \amp f ( 2 ) \amp = \left\{ 1, 3, 4 \right\}\\ f ( 3 ) \amp = \left\{ 1, 4 \right\} \amp f ( 4 ) \amp = \left\{ 2, 4 \right\} \end{align*}
(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

\begin{equation*} f ( x ) = A - \left\{ x \right\} \text{ for each } x \in A\text{.} \end{equation*}
(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

\begin{equation*} f ( n ) = \mathbb{N} - \left\{n^2, n^2-2n \right\}, \text{ for each } n \in \mathbb{N}\text{.} \end{equation*}
(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{.}\)

Hint.

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{?}\)