Exercise 2.1 Relation
Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) ∈ R if and only if
a) x + y = 0.
b) x − y is a rational number.
c) xy ≥ 0.
Exercise 2.2 Relation
How many transitive relations are there on a set with n elements if a) n = 1?
b) n = 2?
c) n = 3?
Exercise 2.3 Equinumerosity
Prove: Let A be an arbitrary set. Then A and P(A) are not equinumerous.
Exercise 2.4 Equinumerosity
Prove: The set R and the interval (−1,1) are equinumerous.
Exercise 2.5 Pigeonhole Principle
How many numbers must be selected from the set {1,2,3,4,5,6} to guarantee that at least one pair of these numbers add up to 7 ?
Exercise 2.6 Pigeonhole Principle
In the 17th century, there were more than 800,000 inhabitants of Paris. At the time, it was believed that no one had more than 200,000 hairs on their head. Assuming these numbers are correct and that everyone has at least one hair on their head (that is, no one is completely bald), use the pigeonhole principle to show, as the French writer Pierre Nicole did, that there had to be two Parisians with the same number of hairs on their heads. Then use the generalized pigeonhole principle to show that there had to be at least five Parisians at that time with the same number of hairs on their heads.
Exercise 2.7 Pigeonhole Principle
a) Assume that ik ≤ n for k = 1,2,...,n2 +1. Use the generalized pigeonhole principle to show that there are n +1 terms ak1,ak2,...,akn+1 with ik1 = ik2 = ··· = ikn+1, where 1 ≤ k1 < k2 < ··· < kn+1.
b) Show that akj > akj+1 for j = 1,2,...,n. [Hint: Assume that akj < akj+1, and show that this implies that ikj > ikj+1, which is a contradiction.]
c) Use parts (a) and (b) to show that if there is no increasing subsequence of length n+1, then there must be a decreasing subsequence of this length.
