Recall that a relation R from A to B is a subset RCA B. (So for...

  

Transcribed Image Text:

Recall that a relation R from A to B is a subset RCA B. (So for example, a relation on a set X is a relation from X to X.) Just as we can define new sets from old ones using "set operations" (e.g., N, U, X, etc.) we can also define new relations from old ones. These give rise to what is known as relational algebra. In what follows, use the following sets X, Y, Z: X = {1, 2, 3, 4} Y = {a, b, c, d} Z = {ant, bat, cat} and define relations S from X to Y, and T from Y to Z as follows: S = {(1, a), (1, c), (2, a), (2, c), (2, d), (4, a)} T = {(a, ant), (b, bat), (c, cat)} (a) For a set A, the identity relation on A is the relation on A defined by I = {(a, a) | a A}. Write down Ix in roster form. (b) Given a relation R from A to B, the inverse of R is the relation from B to A defined by 1 R = {(b,a) | (a, b) R}. Write down S-1 in roster form. (c) Suppose that R is a relation from A to B, and that R2 is a relation from B to C. The composition of R and R2 is the relation from A to C defined by R2 R R = {(a, c) | (3b B)((a, b) R ^ (b, c) R)} . 1) Write down So Ix in roster form. What do you observe? 2) Write down Iyo S in roster form. What do you observe? 3) Explain why the expression "Ix S" does not make sense. 4) Write down To T- in roster form. What do you observe? Based on your prior experience with similar notation, is this what you expected? 5) Write down T-1 oT in roster form. What do you observe? Is anything "missing"? Based on your prior experience with similar notation, is this what you expected? 6) Write down To S in roster form. Recall that a relation R from A to B is a subset RCA B. (So for example, a relation on a set X is a relation from X to X.) Just as we can define new sets from old ones using "set operations" (e.g., N, U, X, etc.) we can also define new relations from old ones. These give rise to what is known as relational algebra. In what follows, use the following sets X, Y, Z: X = {1, 2, 3, 4} Y = {a, b, c, d} Z = {ant, bat, cat} and define relations S from X to Y, and T from Y to Z as follows: S = {(1, a), (1, c), (2, a), (2, c), (2, d), (4, a)} T = {(a, ant), (b, bat), (c, cat)} (a) For a set A, the identity relation on A is the relation on A defined by I = {(a, a) | a A}. Write down Ix in roster form. (b) Given a relation R from A to B, the inverse of R is the relation from B to A defined by 1 R = {(b,a) | (a, b) R}. Write down S-1 in roster form. (c) Suppose that R is a relation from A to B, and that R2 is a relation from B to C. The composition of R and R2 is the relation from A to C defined by R2 R R = {(a, c) | (3b B)((a, b) R ^ (b, c) R)} . 1) Write down So Ix in roster form. What do you observe? 2) Write down Iyo S in roster form. What do you observe? 3) Explain why the expression "Ix S" does not make sense. 4) Write down To T- in roster form. What do you observe? Based on your prior experience with similar notation, is this what you expected? 5) Write down T-1 oT in roster form. What do you observe? Is anything "missing"? Based on your prior experience with similar notation, is this what you expected? 6) Write down To S in roster form.