Section 5.1 Relations
345
exeRcISeS 5.1
1. For each of the following binary relations r on N, decide which of the given ordered pairs belong to r.
a. x r y 4 x + y < 7; (1, 3), (2, 5), (3, 3), (4, 4)
b. x r y 4 x = y + 2; (0, 2), (4, 2), (6, 3), (5, 3)
c. x r y 4 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3)
d. x r y 4 y is a perfect square; (1, 1), (4, 2), (3, 9), (25, 5)
2. For each of the following binary relations r on Z, decide which of the given ordered pairs belong to r.
a. x r y 4 x 0 y; (2, −6), (3, 5), (8, 4), (4, 8)
b. x r y 4 x and y are are relatively prime; (5, 8), (9, 16), (6, 8), (8, 21)
c. x r y 4 gcd(x, y) = 7; (28, 14), (7, 7), (10, 5), (21, 14)
d. x r y 4 x
2
+ y
2
= z
2
for some integer z; (1, 0), (3, 9), (2, 2), (−3, 4)
e. x r y 4 x is a number from the Fibonacci sequence; (4, 3), (7, 6), (7, 12), (20, 20)
3. Decide which of the given items satisfy the relation.
a. r a binary relation on Z, x r y 4 x = −y; (1, − 1), (2, 2), (−3, 3), (−4, −4)
b. r a binary relation on N, x r y 4 x is prime; (19, 7), (21, 4), (33, 13), (41, 16)
c. r a binary relation on Q, x r y 4 x ≤ 1∙y; (1, 2), (−3, −5), (−4, 1∙2), (1∙2, 1∙3)
d. r a binary relation on N × N, (x, y) r (u, v) 4 x + u = y + v; ((1, 2), (3, 2)), ((4, 5), (0, 1))
4. Decide which of the given items satisfy the relation.
a. r a binary relation on S × C, where S = 5states in the United States6, C = 5cities in the United States6,
x r y 4 y is the capital of x; (Indiana, Indianapolis), (Illinois, Chicago), (Kansas, Kansas City),
(Kentucky, Louisville), (North Dakota, Bismarck)
b. r a binary relation on A × P, where A = 5artists6, P = 5paintings6, x r y 4 x painted y; (DaVinci,
Mona Lisa), (Grant Wood, American Gothic), (Remington, Ridden Down), (Picasso, Blue Dancers),
(van Gogh, Starry Night)
c. r a binary relation on C × M, where C = 5composers6, M = 5music6, x r y 4 x composed y;
( Bernstein, West Side Story), (Presley, Blue Suede Shoes), (Gershwin, Rhapsody in Blue), (Beethoven,
Moonlight Sonata), (Rogers and Hammerstein, Phantom of the Opera)
d. r a binary relation on A × B, where A = 5authors6, B = 5books6, x r y 4 x wrote y; (Hemingway,
The Old Man and the Sea), (Sawyer, Huckleberry Finn) (Poe, Moby Dick), (Orwell, 1984), (Tolstoy,
Crime and Punishment)
5. For each of the following binary relations on R, draw a figure to show the region of the plane it describes.
a. x r y 4 y ≤ 2
b. x r y 4 x = y − 1
c. x r y 4 x
2
+ y
2
≤ 25
d. x r y 4 x ≥ y
maIn IDeaS
• A binary relation on a set S is formally a subset of
S × S; the distinctive relationship satisfied by the
relation’s members often has a verbal description
as well.
• Operations on binary relations on a set include
union, intersection, and complementation.
• Binary relations can have properties of reflexivity,
symmetry, transitivity, and antisymmetry.
• Finite partially ordered sets can be represented
graphically.
• An equivalence relation on a set S determines a
partition of S, and conversely. The blocks of the
partition are equivalence classes, which may themselves be treated as entities.
345
exeRcISeS 5.1
1. For each of the following binary relations r on N, decide which of the given ordered pairs belong to r.
a. x r y 4 x + y < 7; (1, 3), (2, 5), (3, 3), (4, 4)
b. x r y 4 x = y + 2; (0, 2), (4, 2), (6, 3), (5, 3)
c. x r y 4 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3)
d. x r y 4 y is a perfect square; (1, 1), (4, 2), (3, 9), (25, 5)
2. For each of the following binary relations r on Z, decide which of the given ordered pairs belong to r.
a. x r y 4 x 0 y; (2, −6), (3, 5), (8, 4), (4, 8)
b. x r y 4 x and y are are relatively prime; (5, 8), (9, 16), (6, 8), (8, 21)
c. x r y 4 gcd(x, y) = 7; (28, 14), (7, 7), (10, 5), (21, 14)
d. x r y 4 x
2
+ y
2
= z
2
for some integer z; (1, 0), (3, 9), (2, 2), (−3, 4)
e. x r y 4 x is a number from the Fibonacci sequence; (4, 3), (7, 6), (7, 12), (20, 20)
3. Decide which of the given items satisfy the relation.
a. r a binary relation on Z, x r y 4 x = −y; (1, − 1), (2, 2), (−3, 3), (−4, −4)
b. r a binary relation on N, x r y 4 x is prime; (19, 7), (21, 4), (33, 13), (41, 16)
c. r a binary relation on Q, x r y 4 x ≤ 1∙y; (1, 2), (−3, −5), (−4, 1∙2), (1∙2, 1∙3)
d. r a binary relation on N × N, (x, y) r (u, v) 4 x + u = y + v; ((1, 2), (3, 2)), ((4, 5), (0, 1))
4. Decide which of the given items satisfy the relation.
a. r a binary relation on S × C, where S = 5states in the United States6, C = 5cities in the United States6,
x r y 4 y is the capital of x; (Indiana, Indianapolis), (Illinois, Chicago), (Kansas, Kansas City),
(Kentucky, Louisville), (North Dakota, Bismarck)
b. r a binary relation on A × P, where A = 5artists6, P = 5paintings6, x r y 4 x painted y; (DaVinci,
Mona Lisa), (Grant Wood, American Gothic), (Remington, Ridden Down), (Picasso, Blue Dancers),
(van Gogh, Starry Night)
c. r a binary relation on C × M, where C = 5composers6, M = 5music6, x r y 4 x composed y;
( Bernstein, West Side Story), (Presley, Blue Suede Shoes), (Gershwin, Rhapsody in Blue), (Beethoven,
Moonlight Sonata), (Rogers and Hammerstein, Phantom of the Opera)
d. r a binary relation on A × B, where A = 5authors6, B = 5books6, x r y 4 x wrote y; (Hemingway,
The Old Man and the Sea), (Sawyer, Huckleberry Finn) (Poe, Moby Dick), (Orwell, 1984), (Tolstoy,
Crime and Punishment)
5. For each of the following binary relations on R, draw a figure to show the region of the plane it describes.
a. x r y 4 y ≤ 2
b. x r y 4 x = y − 1
c. x r y 4 x
2
+ y
2
≤ 25
d. x r y 4 x ≥ y
maIn IDeaS
• A binary relation on a set S is formally a subset of
S × S; the distinctive relationship satisfied by the
relation’s members often has a verbal description
as well.
• Operations on binary relations on a set include
union, intersection, and complementation.
• Binary relations can have properties of reflexivity,
symmetry, transitivity, and antisymmetry.
• Finite partially ordered sets can be represented
graphically.
• An equivalence relation on a set S determines a
partition of S, and conversely. The blocks of the
partition are equivalence classes, which may themselves be treated as entities.