Problem Set 13—Relations

Purpose

This problem set reinforces your understanding of relations, particularly equivalence relations, and of equivalence classes. It also gives you practice applying ideas from this course in contexts other than the ones covered in our textbook.

Background

This exercise is based on sections 7.1 through 7.3 of our textbook. We discussed, or will discuss, this material in class on November 30, December 2, and December 5.

Problem 4 continues the project of challenging you with Prof. Nicodemi’s real analysis problems, and so does not draw on the material we are discussing now in class.

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

Define ∼ to be the “has more factors” relation on the set {1,2,3,4,5,6}. In other words, a ∼ b if and only if a has more distinct natural number factors than b does. For example 3 ∼ 1 because 3 has 2 distinct factors (1 and 3) whereas 1 has only 1 (1 itself).

Part A

Write ∼ as a set of ordered pairs.

Part B

Draw ∼ as a directed graph.

Problem 2

Exercise 5 in section 7.2 of our textbook, except define relation R to be on ℝ, not ℤ — the book is inconsistent about which set R should be defined on. Justify all your claims with proofs or counter-examples. (The problem defines relation R by the rule a R b if and only if |a-b| ≤ 3, and asks you to determine whether R is an equivalence relation, and if not which of the defining properties of an equivalence relation it has.)

Problem 3

Exercise 5b in section 7.3 of our textbook (For all a and b in ℤ₉, say that a ≈ b if and only if a³ ≡ b³ (mod 9); prove that ≈ is an equivalence relation and find its distinct equivalence classes).

Problem 4

Use the following definitions to answer parts A and B below. You may also use results about the real numbers, rationals, etc. from problem sets 11 and 12:

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.