Problems: Set Theory and Notation

1. Define the following sets: E = { x: x = 2n for n N}, O = {x : x = 2n + 1 for n N}, A = {x R : -4 < x < 3}, B = {x R : -1 < x < 7}, and I = {x R: x * x = -2}. Then:

    1. What, in words, are the sets E, O, and I ?
    2. Find A B, A B, A \ B, comp(A).
    3. Find O E, O I, comp(I).
Solution to 2

2. Let A, B, and C be any sets. Prove the following statements:

    1. C \ (A B) = (C \ A) (C \ B)
    2. C \ (A B) = (C \ A) (C \ B)
Compare

3. Prove that when two even integers are multiplied, the result is an even integer, and when two odd integers are multiplied, the result is an odd integer.

Solution

4. Prove or disprove: if the square of a number is an odd integer, then the original number must also be an odd integer. (Try a proof by contradiction)

Compare

5. Prove that there is no greatest positive integer. Also prove that there is no smallest positive rational number.

6. Prove or disprove: every prime number greater than 2 is odd.

7. Euclid's Theorem states that there is no largest prime. A proof by contradiction would start out by assuming that the statement is false, i.e. there is a largest prime. The advantage now is that if there was a largest prime, there would be only finitely many primes. This seems easier to handle than the original statement which implies the existence of infinitely many primes. Finish the proof.

Solution

8. Let A = {1, 2, 3, 4}, B = {14, 7, 234}, C = {a, b, c}, and R = real numbers. Which of the following relations are functions ?

    1. r is the relation between A and B that associates the pairs 1 ~ 234, 2 ~ 7, 3 ~ 14, 4 ~ 234, 2 ~ 234
    2. f is the relation between A and C that relates the pairs {(1,c), (2,b), (3,a), (4,b)}
    3. g is the relation between A and C consisting of the associations {(1,a), (2,a), (3,a)}
    4. h is the relation between R and itself consisting of pairs {(x,sin(x))}
Solution

9. Give an example of a relation r on a set A such that:

    1. the relation r is reflexive and symmetric but not transitive
    2. the relation r is symmetric and transitive but not reflexive
    3. the relation r is transitive but neither reflexive nor symmetric.
10. Let f(x) = 0 if x is rational and f(x) = 1 if x is irrational. This function is called Dirichlet’s Function. The range for f is R.

    1. What is the image of the function if the domain is Q
    2. What is the image of the function if the domain is R
    3. What is the image of the function if the domain is [0, 1] (the closed interval between 0 and 1)
    4. What is the preimage of R ? What is the preimage of [-1/2, 1/2] ?
Solution to 4

11. Answer the above questions for the function f(x) = 0 if x is rational and f(x) = x if x is irrational.

12. Let f(x) = 1 - , with domain and range being R. Then use the graph of the function to determine:

    1. What is the image of [0, 2] and the preimage of [1, 4] ?
    2. Find the image and the preimage of [-2, 2].
Compare

13. If the graph of a function is known, how can you decide from that graph whether a function is one-to-one (injective) or onto (surjective) ?

Solution

14. Which of the following functions are one-one, onto, or bijections ? The domain for all functions is R.

Solution

15. Show that the range of a function is equal to the image of the domain of the function if and only if the function is surjective.

16. Show that every bijection has an inverse function.

17. Show that if f is a bijection from A to B then is a bijection mapping B onto A. Moreover, show that the inverse of is the original function f.

18. Let A = {1, 2, 3, 4} and B = {a, b, c}. Which of the following relations is an equivalence relation ?

    1. r : { (a,a), (b,b), (a,b), (b,a) }
    2. s : 1 ~ 1, 2 ~ 2, 3 ~ 3, 4 ~ 4, 1 ~ 4, 4 ~ 1, 2 ~ 4, 4 ~ 2
Solution

19. If S = {a, b, c}, then list all possible equivalence relations on the set S.

20. Consider the set Z of all integers. Define a relation r by saying that x and y are related if their difference y - x is divisible by 3. Then

    1. Check that this relation is an equivalence relation
    2. Find the two equivalence classes, and name them appropriately.
    3. How would you add these equivalence classes, if at all ?
Compare

21. Define a relation r on R by saying that two real numbers x and y are related if there exists an integer n such that | x - n | < 1/2 and | y - n | < 1/2. Show that this relation is an equivalence relation and describe the equivalence classes.

Compare

22. Let S be the collection of all polynomials with real coefficients. We say that two polynomials p(x) and q(x) are related if the number 0 is a root of the polynomial p(x) - q(x). Is this an equivalence relation on S ?

23. The Rational Numbers together with addition and multiplication can be defined as follows:

  1. Let A be the set N x N and define a relation r on N x N by saying that (a, b) is related to (a’, b’) if a * b’ = a’ * b. Show that this relation is an equivalence relation.
  2. If [(a, b)] and [(a’, b’)] denotes the equivalence classes containing (a, b) and (a’, b’), respectively, then show that the following operations are well-defined:
  3. Give examples to indicate that the resulting set of all equivalence classes has all of the familiar properties of the rational numbers (and hence can serve to define the rationals based only on the natural numbers).
Compare

24. Why would anyone bother introducing numbers that are more complicated than the rationals, such as the real (or even complex) numbers ? Find as many reasons as you can.

Compare