Dis01b Sol

CS 70 Discrete Mathematics and Probability Theory
Summer 2023 Huang, Suzani, and Tausik DIS 1B
1 Set Operations
Note 0
• R, the set of real numbers

• Q, the set of rational numbers: {a/b : a, b ∈ Z ∧ b ̸= 0}
• Z, the set of integers: {. . . , −2, −1, 0, 1, 2, . . .}
• N, the set of natural numbers: {0, 1, 2, 3, . . .}
(a) Given a set A = {1, 2, 3, 4}, what is P(A) (Power Set)?

(b) Given a generic set B, how do you describe P(B) using set comprehension notation? (Set
Comprehension is {x | x ∈ A}.)
(c) What is R ∩ P(A)?
(d) What is R ∩ Z?
(e) What is N ∪ Q?
(f) What is R \ Q?
(g) If S ⊆ T , what is S \ T ?
Solution:
(a)
P(A) = {{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
(b) P(B) = {T | T ⊆ B}
(c) {} or ∅
(d) Z
(e) Q
(f) The set of irrational numbers
(g) ∅
CS 70, Summer 2023, DIS 1B 1

2 Preserving Set Operations
Note 0 For a function f , define the image of a set X to be the set f (X) = {y | y = f (x) for some x ∈ X}.
Note 2 Define the inverse image or preimage of a set Y to be the set f −1 (Y ) = {x | f (x) ∈ Y }. Prove the
following statements, in which A and B are sets. By doing so, you will show that inverse images
preserve set operations, but images typically do not.
Recall: For sets X and Y , X = Y if and only if X ⊆ Y and Y ⊆ X. To prove that X ⊆ Y , it is sufficient
to show that (∀x) ((x ∈ X) =⇒ (x ∈ Y )).
(a) f −1 (A ∩ B) = f −1 (A) ∩ f −1 (B).
(b) f −1 (A \ B) = f −1 (A) \ f −1 (B).

(c) f (A ∩ B) ⊆ f (A) ∩ f (B), and give an example where equality does not hold.
(d) f (A \ B) ⊇ f (A) \ f (B), and give an example where equality does not hold.
Solution:
In order to prove equality A = B, we need to prove that A is a subset of B, A ⊆ B and that B is a
subset of A, B ⊆ A. To prove that LHS is a subset of RHS we need to prove that if an element is a
member of LHS then it is also an element of the RHS.
(a) Suppose x is such that f (x) ∈ A ∩ B. Then f (x) lies in both A and B, so x lies in both f −1 (A)
and f −1 (B), so x ∈ f −1 (A) ∩ f −1 (B). So f −1 (A ∩ B) ⊆ f −1 (A) ∩ f −1 (B).
Now, suppose that x ∈ f −1 (A) ∩ f −1 (B). Then, x is in both f −1 (A) and f −1 (B), so f (x) ∈ A
and f (x) ∈ B, so f (x) ∈ A ∩ B, so x ∈ f −1 (A ∩ B). So f −1 (A) ∩ f −1 (B) ⊆ f −1 (A ∩ B).
/ B, which means that x ∈ f −1 (A)

(b) Suppose x is such that f (x) ∈ A \ B. Then, f (x) ∈ A and f (x) ∈
/ f −1 (B), which means that x ∈ f −1 (A) \ f −1 (B). So f −1 (A \ B) ⊆ f −1 (A) \ f −1 (B).
and x ∈
Now, suppose that x ∈ f −1 (A) \ f −1 (B). Then, x ∈ f −1 (A) and x ∈ / f −1 (B), so f (x) ∈ A and
/ B, so f (x) ∈ A \ B, so x ∈ f −1 (A \ B). So f −1 (A) \ f −1 (B) ⊆ f −1 (A \ B).
f (x) ∈
(c) Suppose x ∈ A ∩ B. Then, x lies in both A and B, so f (x) lies in both f (A) and f (B), so
f (x) ∈ f (A) ∩ f (B). Hence, f (A ∩ B) ⊆ f (A) ∩ f (B).
Consider when there are elements a ∈ A and b ∈ B with f (a) = f (b), but A and B are disjoint.
Here, f (a) = f (b) ∈ f (A) ∩ f (B), but f (A ∩ B) is empty (since A ∩ B is empty).
(d) Suppose y ∈ f (A) \ f (B). Since y is not in f (B), there are no elements in B which map to y.
Let x be any element of A that maps to y; by the previous sentence, x cannot lie in B. Hence,
x ∈ A \ B, so y ∈ f (A \ B). Hence, f (A) \ f (B) ⊆ f (A \ B).
Consider when B = {0} and A = {0, 1}, with f (0) = f (1) = 0. One has A \ B = {1}, so
f (A \ B) = {0}. However, f (A) = f (B) = {0}, so f (A) \ f (B) = ∅.

3 Inverses and Bijections
Note 0 Recall that a function f : A → B is a bijection if it is an injection and a surjection, and it is invertible
Note 11 if there is a function g : B → A so that g ◦ f = idA and f ◦ g = idB , where idA : A → A and idB : B → B
are the identity functions.
(a) Prove that if f : A → B is invertible then it is a bijection.

(b) Prove that if f : A → B is a bijection then it is invertible.
(c) Let g : B → A be the inverse function for some bijection f . Is g necessarily a bijection?
Solution:
(a) Suppose g : B → A is the inverse of f . First, we show f is injective. Suppose f (x) = f (y) for
some x, y ∈ A. Then, g( f (x)) = g( f (y)). Since g is the inverse of f , g ◦ f = idA , so we get
x = y. Thus, f is injective. Next, we show f is surjective. Consider any b ∈ B. Then, g(b) ∈ A
is such that f (g(b)) = b because f ◦ g = idB . So, f is surjective. Thus, f is a bijection.
(b) Since f is surjective, every element b ∈ B is mapped to by something (in other words, the
preimage f −1 ({b}) is nonempty). Since f is injective, every element b ∈ B is mapped to by at
most one thing (in other words, the preimage f −1 ({b}) has cardinality at most 1). Combining
these facts, for each b ∈ B, f −1 ({b}) = {a} for some a ∈ A. Define g : B → A so that g(b) is
the unique element in f −1 ({b}) for each b ∈ B. We claim g is the inverse of f .
First, consider g ◦ f : A → B. For any a ∈ A, g( f (a)) is the unique element in f −1 ({ f (a)})

which must be a since f maps a to f (a), so g( f (a)) = a and thus g ◦ f = idA . Now, consider
f ◦ g : B → A. For any b ∈ B, g(b) is the unique element in f −1 ({b}), which means f maps it
to b. Thus, f (g(b)) = b and so f ◦ g = idB .
(c) Yes! The condition for being an inverse is symmetric, so f is the inverse of g. Therefore, g is
invertible and hence a bijection by part (a).
4 Rationals and Irrationals

Note 2 Prove that the product of a non-zero rational number and an irrational number is irrational.
Solution: We prove the statement by contradiction. Suppose that ab = c, where a ̸= 0 is rational, b
is irrational, and c is rational. Since a and b are not zero (because 0 is rational), c is also non-zero.
Thus, we can express a = qp and c = rs , where p, q, r, and s are nonzero integers. Then
c rq
b= = ,
a ps
which is the ratio of two nonzero integers, giving that b is rational. This contradicts our initial
assumption, so we conclude that the product of a nonzero rational number and an irrational number
is irrational.

Dis01b Sol

Uploaded by

Copyright:

Available Formats

Dis01b Sol

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dis01b Sol

Uploaded by

Copyright:

Available Formats

CS 70 Discrete Mathematics and Probability Theory

Summer 2023 Huang, Suzani, and Tausik DIS 1B

• R, the set of real numbers

(a) Given a set A = {1, 2, 3, 4}, what is P(A) (Power Set)?

CS 70, Summer 2023, DIS 1B 1

(a) f −1 (A ∩ B) = f −1 (A) ∩ f −1 (B).

(b) f −1 (A \ B) = f −1 (A) \ f −1 (B).

/ B, which means that x ∈ f −1 (A)

CS 70, Summer 2023, DIS 1B 2

(a) Prove that if f : A → B is invertible then it is a bijection.

First, consider g ◦ f : A → B. For any a ∈ A, g( f (a)) is the unique element in f −1 ({ f (a)})

4 Rationals and Irrationals

CS 70, Summer 2023, DIS 1B 3

You might also like