Beginner's mathematical proof / composition of relations

In summary, the homework statement is that D_r\circ D_s is defined as the relation between x and z if and only if x is a friend of z and z is a friend of x.
  • #1
Testify
15
0

Homework Statement


Suppose r and s are two positive real numbers. Let Dr and Ds be defined as in part 3 of Example 4.3.1. What is [tex]D_r \circ D_s[/tex]? Justify your answer with a proof. (Hint: In your proof, you may find it helpful to use the triangle inequality.)

Homework Equations


Example 4.3.1:
For each positive real number r, let Dr = [tex]\left\{(x,y)\in \mathbb{R} \times \mathbb{R} | ( |x - y| < r \right\}[/tex]. Then Dr is a relation on [tex]\mathbb{R}[/tex].

[tex]\circ[/tex] = composition

The Attempt at a Solution



I don't know what the composition of Dr and Ds would be, so I am not even close to being able to prove anything.

thanks
 
Last edited:
Physics news on Phys.org
  • #2
Your textbook probably talks about composition of relations, but in case it doesn't, you can read about the idea on Wikipedia.
 
  • #3
You have (x,y) in Dr if |x - y| < r and (x,y) in Ds if |x - y| < s.

Can you state the definition of [itex] D_s\circ D_r[/itex]? Once you do that, you may see what the triangle inequality has to do with this problem.
 
  • #4
I've read everything my book has to say about the composition of relations, and I cannot figure out what to do with this problem. With the other problems, it would just say, for example, that A was a relation from X to Y and B was a relation from Y to Z, then the composition of B and A would be (x,z), etc.

I just cannot figure out what the definition of [tex]D_s \circ D_r[/tex] would be...
 
  • #5
Testify said:
I've read everything my book has to say about the composition of relations, and I cannot figure out what to do with this problem. With the other problems, it would just say, for example, that A was a relation from X to Y and B was a relation from Y to Z, then the composition of B and A would be (x,z), etc.

I just cannot figure out what the definition of [tex]D_s \circ D_r[/tex] would be...

You don't have to "figure out the definition". Click on the link Tinyboss gave you. It gives you the definition. Write down what that definition says for your particular problem.
 
  • #6
I have been using the definition, and I still have no idea what [tex]D_s \circ D_r[/tex] would be.

I just don't understand how you can use composition with two relations over the same elements. If one of them were (x,y) and the other one were (y,z) then I might be able to figure this out on my own.
 
  • #7
If one relation is on [tex]X\times Y[/tex] and the other is on [tex]Y\times Z[/tex], is there any reason why you can't have [tex]X=Y=Z=\mathbb{R}[/tex]?
 
  • #8
no.

I'm still not really following though. I just cannot figure out how to combine the two relations to create a composition. =/
 
  • #9
You need to talk to your TA or professor, then. You have access to the definition, which is straightforward, but can't make sense of it--you might not have adequate preparation for the class you're in.
 
  • #10
I'm using Velleman's "How to Prove it" and I'm doing this self study. I suppose I am having some trouble understanding some of these definitions. I guess I will just have to re-read a few chapters...

Could you just tell me what [tex]D_s \circ D_r[/tex] would be? Maybe then I would understand how it works.
 
  • #11
[tex](x,y)\in D_s\circ D_r\Leftrightarrow\exists z\in\mathbb{R}:(x,z)\in D_s\text{ and }(z,y)\in D_r[/tex].

An example for intuition: take the relations S (for "sibling") and F (for "friend"). These are both relations on the set "people x people". Then I am related to you by [tex]F\circ S[/tex] if there's some person P such that P is my sibling and your friend, i.e. you're a "friend of a sibling" to me. Likewise, I'm related to you by [tex]S\circ F[/tex] if there's a person Q such that Q is my friend and your sibling, i.e. you're a "sibling of a friend" to me. You can see how the definition is mirrored in the way you read the composition.
 
  • #12
How would I be able to prove that using the triangle inequality? I thought that the answer would be something along the lines of |x-z|< r and s or something like that... I know that is the "answer" but I thought the answer would be more... numerical.

Maybe I just totally misunderstood what the question was asking. =/ I'm sorry that I'm being confusing.
 

1. What is a mathematical proof and why is it important?

A mathematical proof is a logical argument that demonstrates the truth of a mathematical statement. It is important because it allows us to verify the validity of mathematical claims and to build upon existing knowledge.

2. What are the basic elements of a mathematical proof?

The basic elements of a mathematical proof are assumptions, definitions, axioms, and logical reasoning. Assumptions are statements that are accepted as true without proof. Definitions clarify the meaning of mathematical terms. Axioms are self-evident truths that serve as the foundation of a mathematical theory. Logical reasoning is the process of using established principles and rules of logic to arrive at a conclusion.

3. What is the difference between a direct proof and an indirect proof?

A direct proof is a type of proof in which the conclusion is logically deduced from the given assumptions, definitions, and axioms. An indirect proof, also known as a proof by contradiction, is a type of proof in which the assumption of the opposite of the desired conclusion leads to a contradiction, thus proving the original statement to be true.

4. What is a composition of relations and how is it represented?

A composition of relations is a way of combining two or more relations to create a new relation. It is represented by a small circle between the two relations, with the first relation on the left and the second relation on the right. For example, if relation A is "is the father of" and relation B is "is the brother of", then the composition of A and B would be "is the uncle of".

5. How do you know if a composition of relations is a valid operation?

In order for a composition of relations to be a valid operation, the output of the first relation must match the input of the second relation. In other words, the domain of the first relation must be the same as the codomain of the second relation. Additionally, the composition must follow the rules of composition, such as being associative and having a neutral element.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
450
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
3
Views
762
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
Back
Top