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 P(A) of A to be the set of all subsets of A. This means that X∈P(A) if and only if X⊆A. Theorem 5.9 in Section 5.1 states that if a set A has n elements, then A has 2n subsets or that P(A) has 2n elements. Using our current notation for cardinality, this means that if  card(A)=n, then  card(P(A))=2n. (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 P(A). 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.

1.

Let A={1,2,3,4}. Define f:A→P(A) by

f(1)={1,2,3}f(2)={1,3,4}f(3)={1,4}f(4)={2,4}
(a)

Is 1∈f(1)? Is 2∈f(2)? Is 3∈f(3)? Is 4∈f(4)?

(b)

Determine S={x∈A∣x∉f(x)}.

(c)

Notice that S∈P(A). Does there exist an element t in A such that f(t)=S? That is, is S∈ range(f)?

2.

Let A={1,2,3,4}. Define f:A→P(A) by

f(x)=A−{x} for each x∈A.
(a)

Determine f(1). Is 1∈f(1)?

(b)

Determine f(2). Is 2∈f(2)?

(c)

Determine f(3). Is 3∈f(3)?

(d)

Determine f(4). Is 4∈f(4)?

(e)

Determine S={x∈A∣x∉f(x)}.

(f)

Notice that S∈P(A). Does there exist an element t in A such that f(t)=S? That is, is S∈ range(f)?

3.

Define f:N→P(N) by

f(n)=N−{n2,n2−2n}, for each n∈N.
(a)

Determine f(1), f(2), f(3), and f(4). In each of these cases, determine if k∈f(k).

(b)

Prove that if n>3, then n∈f(n).

Hint.

Prove that if n>3, then n2>n and n2−2n>n.

(c)

Determine S={x∈N∣x∉f(x)}.

(d)

Notice that S∈P(N). Does there exist an element t in N such that f(t)=S? That is, is S∈ range(f)?