Problem Set 13—Equivalence Relations and Countability

Purpose

This problem set reinforces two things: (1) your ability to reason about relations, particularly equivalence relations, and (2) your ability to determine whether sets are finite or infinite, and, if infinite, to reason about their cardinalities.

Background

Our textbook covers equivalence relations in sections 7.1 through 7.3. We discussed this material in classes on April 17 and 19.

Our textbook covers the cardinalities of sets in sections 9.1 through 9.3. This problem set concentrates on the ideas in sections 9.1 and 9.2. We will talk about those sections between April 21 and April 28.

Activity

Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Problem 1

A slight extension of exercise 10a in section 7.2 of our textbook: define relation ∼ on ℤ by a ∼ b if and only if 2 divides a + b; determine whether ∼ is an equivalence relation, and either prove your answer if it is or give counterexamples that show which properties of equivalence relations ∼ fails to have.

Problem 2

Exercise 5c in section 9.1 of our textbook (prove that if A ∩ B is an infinite set, then A is an infinite set).

Problem 3

Exercise 2b in section 9.2 of our textbook (prove that the set of integers that are multiples of 5 is countably infinite).

Problem 4

This problem continues the set of out of context problems from Prof. Nicodemi that we saw in Problem Sets 5, 9, and 12. Using results from those problem sets if they help (you won’t necessarily need all of them), and the following definitions, answer parts A and B below:

Definition 1.

Let A be a subset of the real numbers ℝ and let c ∈ ℝ. We call c a controller of A if x ≤ c for every x ∈ A.

Definition 2.

A set A ⊂ ℝ is called controlled if there exists a controller of A.

Definition 3.

Let A ⊆ ℝ be a controlled, non-empty set. A real number b is called the best controller of A if

1. b is a controller of A and
2. b ≤ c where c is any controller of A.

Part A

For each of the following sets, determine if it is controlled. If it is, find its best controller.

1. ℕ
2. The open interval { x ∈ ℝ |  0 < x < 1}
3. The closed interval { x ∈ ℝ |  0 ≤ x ≤ 1}
4. The set { x ∈ ℚ |  x ≤ √2 }
5. The set {1-1/n | n ∈ ℕ }

Part B

For each of the controlled sets in part A, prove that your choice of best controller is indeed correct.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.