Math 381: Exam 2 Study Guide
Key Definitions
• Set
• Union, intersection, Cartesian product, difference, compliment, disjoint
• Relation, domain, range, identity, inverse, composite
• Reflexive, symmetric, transitive, antisymmetric
• Function, domain, codomain, range
• One-to-one, onto, bijective
• Inverse
• Image and pre-image
• Equivalent sets
• Cardinality
• Countably infinite
• Uncountable
Key Theorems
• Theorem 2.2.1
• Theorem 2.2.2
• Theorem 3.1.2
• Theorem 3.1.3
• Theorem 4.3.1
• Theorem 4.3.2
• Theorem 4.3.3
• Theorem 4.3.4
• Theorem 4.4.G1
• Theorem 4.5.G1
• Theorem 4.5.G2
• Theorem 5.1.7
• Theorem 5.2.4
1
Key Skills
• Show whether or not a set is a subset of another set
• Show two sets are equal using the subset method
• Perform set operations to find resulting sets (union, intersection, difference)
• Find the compliment of a set
• Find the Cartesian product of sets
• Determine if a relation is a function
• Determine if a function is one-to-one, onto and/or bijective
• Take the composition of functions
• Determine if two functions are inverses of each other
• Find the image and/or pre-image of a subsets
• Compute infinite unions and intersections
• Compute the cardinality of a finite set
• Compare cardinality of two sets
• Prove an infinite set is countable.
• Prove an infinite set is uncountable.
How to study:
1. Write a Definitions and Theorems sheet. You will be cramped for time on the exam so knowing your
definitions and theorems at the drop of a hat is important. If you forget them, then you definitely
don’t want to have to scramble through your notes to find a certain fact.
2. Practice proving the theorems from the theorem sheet. I don’t think you will use very many of the
theorems, but the skills required to prove these theorems get used over and over.
3. Redo the worksheets, make sure you can do what you should already know. What types of proof
methods were brought used from the first material?
4. Do the review problems. This is a chance to see if you really understood the big picture from the
worksheets. If things feel a bit repetitive, this is good!
5. Redo homework problems and maybe even their neighbors. More practice never hurt. (Unless you’re
now sleep deprived. Now it’s hurting.)
It is important to note that, along with doing the above, you should practice writing clear and organized
solutions. You should aim to be able to produce a “perfect proof” on the exam.
2
Some Review Problems
1. True or False: (no justification required)
(a) {∅} ⊂ {{∅}}
(b) {∅} ∈ {∅, {∅}}
(c) {1, 2, 3} ∈ N
(d) {1, 2, 3} ⊂ {1, 2, 3, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}
(e) {1, 2, 3} ∈ {1, 2, 3, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}
2. Prove that for any sets A and B, A\(A\B) = A ∩ B.
3. Prove that A = {x ∈ Z | x = 2k, k ∈ Z} and B = {x ∈ Z | 0 = x mod 2} are equal.
4. Let A, B, C be sets which are subsets of some universal set U. Use “element chasing” to show that
(a) (A ∪ B ∪ C)\(A ∩ B ∩ C) = (A\(B ∩ C)) ∪ (B\(A ∩ C)) ∪ (C\(A ∩ B))
(b) A\(B ∪ C) = A ∩ (Bc ∩ C
c
)
(c) Ac ∩ Bc ∩ C
c = (A ∪ B ∪ C)
c
(d) A = (A\B) ∪ (A ∩ B)
5. Prove which ones are reflexive, symmetric and/or transitive. (A counter example will do to show
when a relation fails a property.) Which one(s) are an equivalence relation?
(a) Q = {(x, y) ∈ R
2
| x < y}
(b) R = {(x, y) ∈ R
2
| xy ≥ 0}
(c) S = {(x, y) ∈ R
2
| x + y > 0}
(d) T = {(x, y) ∈ R
2
| x 6= y}
6. Let R be nonempty relation on a nonempty set A. If R is symmetric, transitive and ∀y ∈ A there is
an x ∈ A such that (x, y) ∈ R. Prove that R must also be reflexive.
9. Let A be a nonempty set with the partial order R. Prove that if A has an infimum and a supremum,
then (inf A,sup A) ∈ R.
10. Let A be a nonempty set with the partial order R. Prove that if A has a supremum, then it is unique.
(You can do this problem with the infimum as well.)
11. Let f : R
2 × R
2 → R be defined by f(~v, ~u) = ~v · ~u. Is f one-to-one, onto and or bijective?
12. Let f : R
+ → R. Prove whether or not f(x) = ln(x) is:
(a) One-to-one
(b) Onto
(c) Bijective
13. Let f : A → B be invertible. Prove that it has a unique inverse.
14. Let f
−1 denote the pre-image and f : A → B and E, F ⊂ B. Prove f
−1
(E ∪ F) = f
−1
(E) ∪ f
−1
(F).
15. Let f
−1 denote the pre-image.
(a) Prove that S ⊆ f
−1
(f(S)) for any S ⊆ A.
(b) Prove that equality holds for every S ⊆ A if f is injective.
16. Let f
−1 denote the pre-image.
(a) Prove that f(f
−1
(T)) ⊆ T for any T ⊆ B.
(b) Prove that equality holds for every T ⊆ B if f is surjective.
17. Prove that if A1 ⊆ A2 ⊆ A, then f(A1) ⊆ f(A2).
18. Prove that if A1, A2 ⊆ A, then
f(A1) \ f(A2) ⊆ f(A1 \ A2),
and provide an example where equality does not hold. Prove that equality does holds if f is injective.
19. True or False: If |A| = 4 and |B| = 5, then there cannot be a surjective function from A to B.
20. Let M = {ax + b | a, b ∈ Q} and A = {c ∈ R | ∃p(x) ∈ M, p(c) = 0}. Is A countable or uncountable?
4
21. Let A and B be non-empty, finite sets and suppose f : A
onto −−−→ B. Prove that |A| ≥ |B|.
22. Prove that (a, b) and (0, 1) have the same cardinality.
23. Is (1, ∞) countable? Prove your claim.
24. Let f : R → R be defined by f(x) = |x|.
(a) Find the image: f ([0, 1])
(b) Find the pre-image: f
−1
([0, 1])
(c) Find the image: f ([−2, 1])
(d) Find the pre-image: f
−1
([0, 2])
(e) Find the pre-image: f
−1
([3, 4])
25. Let f : [0, 2π] → [−1, 1] be defined by f(x) = sin(x).
(a) Find the image:
Disclaimer: This is only a few problems for you to practice. They do not necessarily cover every topic/skill
you should have but it should give you a taste of how my brain works and ensure you have a firm
foundation.