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

  

Transcribed Image Text:

Recall that a relation R from A to B is a subset RCA x 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 IA = {(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 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 R is a relation from B to C. The composition of R and R is the relation from A to C defined by R R = {(a, c) | (b B)((a, b) R ^ (b, c) = R)} . 1) Write down So Ix in roster form. What do you observe? 2) Write down Iy o S in roster form. What do you observe? 3) Explain why the expression "Ix o 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- 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 x 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 IA = {(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 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 R is a relation from B to C. The composition of R and R is the relation from A to C defined by R R = {(a, c) | (b B)((a, b) R ^ (b, c) = R)} . 1) Write down So Ix in roster form. What do you observe? 2) Write down Iy o S in roster form. What do you observe? 3) Explain why the expression "Ix o 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- 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.