EF Exercises

Skip to main content

Exercises 12.6 Exercises

1.

Prove: If

B

is finite and

A \subseteq B,

then

A

is finite and

| A | \leq | B | .

2.

Suppose that

A,

B,

and

C

are finite subsets of a universal set

U .

(a)

Prove: If

A

and

B

are disjoint, then

| A ⊔ B | = | A | + | B | .

(b)

Prove:

| A \cup B | = | A | + | B | - | A \cap B | .

See Exercise 9.9.5, and use the equality from Task a.

(c)

Determine a similar formula for

| A \cup B \cup C | .

Draw a Venn diagram first.

3.

Use induction to prove directly that if

| A | = n

then

| P (A) | = 2^{n} .

Use Worked Example 12.2.7 as a model for your proof of the induction step.

4.

Prove: If

| A | = \infty

and

A \subseteq B,

then

| B | = \infty .

5.

Prove Fact 12.3.2.

6.

Combine Example 12.3.7 and Example 12.3.10 to verify that the unit interval

(0, 1)

and

R

have the same size.

First map the punctured circle

\hat{S}

onto some open interval in the

x

-axis by “unrolling”

\hat{S} .

7.

Use Example 12.3.7 and the function

f (x) = \tan x

to prove that the interval

(- π / 2, π / 2)

and

R

have the same size.

The function

f (x) = \tan x

is not one-to-one, but it becomes one-to-one if you restrict its domain to an appropriate interval

8.

Prove that if

A

and

B

have the same size, then so do

P (A)

and

P (B) .

See Exercise 10.7.19.

9.

Suppose

A

is a set with

| A | = n .

Then we can enumerate its elements as

A = {a_{1}, a_{2}, \dots, a_{n}} .

(a)

Construct a bijection from the power set of

A

to the set of words in the alphabet

Σ = {T, F}

of length

n .

Note that there are two tasks required here.

🔗
Explicitly describe a function $f : P (A) \to Σ_{n}^{*}$ by describing the input-output rule: give a detailed description of how, given a subset $B \subseteq A,$ the word $f (B)$ should be produced.
🔗
Prove that your function $f$ is a bijection.

When determining the input-output rule for your function

f : P (A) \to Σ_{n}^{*},

think of how one might construct an arbitrary subset of

A,

and then relate that process to a sequence of answers to

n

true/false questions.

(b)

Use Task a to determine the cardinality of

P (A) .

Explain.

See Note 1.3.1.

(c)

Suppose

k

is some fixed (but unknown) integer, with

0 \leq k \leq n .

Let

P (A)_{k}

represent the subset of

P (A)

consisting of all subsets of

A

that have exactly

k

elements. Describe how your bijection from Task a, could be used to count the elements of

P (A)_{k} .

Consider how restricting the domain might help.

<Prev ^Top Next>