Page 657 - Discrete Mathematics and Its Applications

636 9 / Relations

15. a) Give an example to show that the transitive closure a) {(x, y) | x and y have the same sign of the zodiac}
of the symmetric closure of a relation is not necessar-
b) {(x, y) | x and y were born in the same year}
ily the same as the symmetric closure of the transitive
closure of this relation. c) {(x, y) | x and y have been in the same city}
b) Show, however, that the transitive closure of the sym- ∗ 21. How many different equivalence relations with exactly
metricclosureofarelationmustcontainthesymmetric three different equivalence classes are there on a set with
closure of the transitive closure of this relation. five elements?
16. a) Let S be the set of subroutines of a computer pro- 22. Show that {(x, y) | x − y ∈ Q} is an equivalence relation
gram. Define the relation R by PR Q if subroutine P
on the set of real numbers, where Q denotes the set of
calls subroutine Q during its execution. Describe the 1
rational numbers. What are [1], [ ], and [π]?
2
transitive closure of R.
b) For which subroutines P does (P, P) belong to the 23. Suppose that P 1 ={A 1 ,A 2 ,...,A m } and P 2 =
transitive closure of R? {B 1 ,B 2 ,...,B n } are both partitions of the set S. Show
c) Describe the reflexive closure of the transitive closure that the collection of nonempty subsets of the form
of R. A i ∩ B j is a partition of S that is a refinement of both P 1
and P 2 (see the preamble to Exercise 49 of Section 9.5).
17. Suppose that R and S are relations on a set A with R ⊆ S
such that the closures of R and S with respect to a prop- ∗ 24. Show that the transitive closure of the symmetric closure
erty P both exist. Show that the closure of R with respect of the reflexive closure of a relation R is the smallest
to P is a subset of the closure of S with respect to P. equivalence relation that contains R.
18. Show that the symmetric closure of the union of two re-
lations is the union of their symmetric closures. 25. Let R(S) be the set of all relations on a set S. Define the
relation on R(S)by R 1 R 2 if R 1 ⊆ R 2 , where R 1
∗ 19. Devise an algorithm, based on the concept of interior ver-
tices, that finds the length of the longest path between two and R 2 are relations on S. Show that (R(S), ) is a poset.
vertices in a directed graph, or determines that there are 26. Let P(S) be the set of all partitions of the set S. Define the
arbitrarily long paths between these vertices. relation on P(S) by P 1 P 2 if P 1 is a refinement of
20. Which of these are equivalence relations on the set of all P 2 (see Exercise 49 of Section 9.5). Show that (P(S), )
people? is a poset.

PAUL ERD ˝ OS (1913–1996) Paul Erd˝os, born in Budapest, Hungary, was the son of two high school mathe-
matics teachers. He was a child prodigy; at age 3 he could multiply three-digit numbers in his head, and at 4 he
discovered negative numbers on his own. Because his mother did not want to expose him to contagious diseases,
he was mostly home-schooled. At 17 Erd˝os entered E˝otv˝os University, graduating four years later with a Ph.D.
in mathematics. After graduating he spent four years at Manchester, England, on a postdoctoral fellowship. In
1938 he went to the United States because of the difficult political situation in Hungary, especially for Jews.
He spent much of his time in the United States, except for 1954 to 1962, when he was banned as part of the
paranoia of the McCarthy era. He also spent considerable time in Israel.
Erd˝os made many significant contributions to combinatorics and to number theory. One of the discoveries
of which he was most proud is his elementary proof (in the sense that it does not use any complex analysis) of the prime number
theorem, which provides an estimate for the number of primes not exceeding a fixed positive integer. He also participated in the
modern development of the Ramsey theory.
Erd˝os traveled extensively throughout the world to work with other mathematicians, visiting conferences, universities, and
research laboratories. He had no permanent home. He devoted himself almost entirely to mathematics, traveling from one mathe-
matician to the next, proclaiming “My brain is open.” Erd˝os was the author or coauthor of more than 1500 papers and had more
than 500 coauthors. Copies of his articles are kept by Ron Graham, a famous discrete mathematician with whom he collaborated
extensively and who took care of many of his worldly needs.
Erd˝os offered rewards, ranging from $10 to $10,000, for the solution of problems that he found particularly interesting, with the
size of the reward depending on the difficulty of the problem. He paid out close to $4000. Erd˝os had his own special language, using
such terms as “epsilon” (child), “boss” (woman), “slave” (man), “captured” (married), “liberated” (divorced), “Supreme Fascist”
(God), “Sam” (United States), and “Joe” (Soviet Union). Although he was curious about many things, he concentrated almost all
his energy on mathematical research. He had no hobbies and no full-time job. He never married and apparently remained celibate.
Erd˝os was extremely generous, donating much of the money he collected from prizes, awards, and stipends for scholarships and to
worthwhile causes. He traveled extremely lightly and did not like having many material possessions.