Question

Problem 3 For two relations R1 and R2 on a set A, we define the composition...

Problem 3

For two relations R1 and R2 on a set A, we define the composition of R2 after R1 as

R2°R1 = { (x, z) ∈ A×A | (∃ y)( (x, y) ∈ R1 ∧ (y, z) ∈ R2 )}

Recall that the inverse of a relation R, denoted R -1, on a set A is defined as:

R -1 = { (x, y) ∈ A×A | (y, x) ∈ R)}

  1. Suppose R = { (1, 1), (1, 2), (3, 3), (3, 4) }.
    1. What is R -1?
    2. What is R °R -1?
  2. Let R be an arbitrary relation on a set A.

    1. Is R °R -1 reflexive?
    2. Is R °R -1 symmetric?
    3. Is R °R -1 transitive?

    For each of these,

    • if the answer is yes, give a justification of why R °R -1 must have the property for every relation R on set A.
    • if the answer is no, give a counter-example, i.e., give an R, show what R -1 and R °R -1 are, and show why the property is not true.

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let R1 and R2 be equivalence relations on a set A. (a) Must R1∪R2 be an...
Let R1 and R2 be equivalence relations on a set A. (a) Must R1∪R2 be an equivalence relation? (b) Must R1∩R2 be an equivalence relation? (c) Must R1⊕R2 be an equivalence relation?[⊕is the symmetric difference:x∈A⊕B if and only if x∈A,x∈B, and x /∈A∩B.]
Let S1 and S2 be any two equivalence relations on some set A, where A ≠...
Let S1 and S2 be any two equivalence relations on some set A, where A ≠ ∅. Recall that S1 and S2 are each a subset of A×A. Prove or disprove (all three): The relation S defined by S=S1∪S2 is (a) reflexive (b) symmetric (c) transitive
Let S1 and S2 be any two equivalence relations on some set A, where A ≠...
Let S1 and S2 be any two equivalence relations on some set A, where A ≠ ∅. Recall that S1 and S2 are each a subset of A×A. Prove or disprove (all three): The relation S defined by S=S1∪S2 is (a) reflexive (b) symmetric (c) transitive
Let A be the set of all lines in the plane. Let the relation R be...
Let A be the set of all lines in the plane. Let the relation R be defined as: “l​1​ R l​2​ ⬄ l​1​ intersects l​2​.” Determine whether S is reflexive, symmetric, or transitive. If the answer is “yes,” give a justification (full proof is not needed); if the answer is “no” you ​must give a counterexample.
For each of the following relations, determine whether the relation is reflexive, irreflexive, symmetric, antisymmetric, and/or...
For each of the following relations, determine whether the relation is reflexive, irreflexive, symmetric, antisymmetric, and/or transitive. Then find R−1. a) R = {(x,y) : x,y ∈Z,x−y = 1}. b) R = {(x,y) : x,y ∈N,x|y}.
Let Z be the set of integers. Define ~ to be a relation on Z by...
Let Z be the set of integers. Define ~ to be a relation on Z by x~y if and only if |xy|=1. Show that ~ is symmetric and transitive, but is neither reflexvie nor antisymmetric.
Consider the relation R defined on the set R as follows: ∀x, y ∈ R, (x,...
Consider the relation R defined on the set R as follows: ∀x, y ∈ R, (x, y) ∈ R if and only if x + 2 > y. For example, (4, 3) is in R because 4 + 2 = 6, which is greater than 3. (a) Is the relation reflexive? Prove or disprove. (b) Is the relation symmetric? Prove or disprove. (c) Is the relation transitive? Prove or disprove. (d) Is it an equivalence relation? Explain.
1. Prove p∧q=q∧p 2. Prove[((∀x)P(x))∧((∀x)Q(x))]→[(∀x)(P(x)∧Q(x))]. Remember to be strict in your treatment of quantifiers .3. Prove...
1. Prove p∧q=q∧p 2. Prove[((∀x)P(x))∧((∀x)Q(x))]→[(∀x)(P(x)∧Q(x))]. Remember to be strict in your treatment of quantifiers .3. Prove R∪(S∩T) = (R∪S)∩(R∪T). 4.Consider the relation R={(x,y)∈R×R||x−y|≤1} on Z. Show that this relation is reflexive and symmetric but not transitive.
Consider the following relation on the set Z: xRy ? x2 + y is even. For...
Consider the following relation on the set Z: xRy ? x2 + y is even. For each question below, if your answer is "yes", then prove it, if your answer is "no", then show a counterexample. (i) Is R reflexive? (ii) Is R symmetric? (iii) Is R antisymmetric? (iv) Is R transitive? (v) Is R an equivalence relation? If it is, then describe the equivalence classes of R. How many equivalence classes are there?
Complete the following table. If a property does not hold give an example to show why...
Complete the following table. If a property does not hold give an example to show why it does not hold. If it does hold, prove or explain why. Use correct symbolism. (Just Yes or No is incorrect) R = {(a,b) | a,b ∃ Z: : a + b-even S = {(a,b) | a,b ∃ Z: : a + b-odd T = {(a,b) | a,b ∃ Z: : a + 2b-even Relation Reflexive Symmetric Anti Symmetric Neither Symmetric or anti-symmetric Transitive...