[Discrete Math] Relations, symmetric and transitive

In summary, the conversation discusses the relation ~ on integers and the question of whether it is symmetric and transitive. The participants use graphical representations and the idea that 5 divides a^2+4b^2 if and only if 5 divides a^2-b^2 to prove the symmetry of ~. They also mention that adding or subtracting a multiple of 5 does not change the divisibility by 5, which helps prove the transitivity of ~.
  • #1
Servo888
43
0
Ok so here's one of the questions we've been assigned...

Let ~ be a relation on th integer such that for every a,b (integers) we have a ~ b iff [tex]5 | a^2+4b^2[/tex] Prove or disprove the following: b) ~ is symmetric, c) ~ is transitive

So I can graphically see what this relation looks like, and from that I've shown it's reflexive. Now I'm working on proving it as being symmetric, but I can't put it into words.

b) ~ is symmetric. Well we want to show that aRb -> bRa, so [tex]5 | a^2+4b^2[/tex] -> [tex]5 | b^2+4a^2[/tex]. Well I can see graphically once again that [tex]b^2+4a^2[/tex] will always give me a multiple of 5 - this is what I can't put into words... I can't really figure out how to express aRb -> bRa... From another help source I was told this;

[tex]5 | a^2+4b^2[/tex] iff [tex]5 | a^2-b^2[/tex], so then I was told to [tex]a^2+4b^2 - a^2-b^2 = 5b^2[/tex], which is a multiple of 5. But I don't see how the hell that works... But it's based on some equivalance class, modulous 5 (maybe?) that's 4 = -1...

c) ~ is transitive. Graphically this looks true. We need to show that aRb and bRc -> aRc. But I'm not sure where to start on this... I don't see where c fits in.
 
Physics news on Phys.org
  • #2
That 5 divides a2+ 4b2 if and only if 5 divides a2- b2 is a very good hint! Of course, it's clear that it is true: if 5 divides a2- b2 then it certainly divides ab- b2+ 5b2 and vice versa.

The point is that if a2+ 4b2 is not obviously "symmetric" but a2- b2 certainly is: if a2- b2 is divisible by 5 then b2- a2= -(a2- b2) certainly is!

Once again, that lovely "5 divides a2+ 4b2 if and only if 5 divides a2- b2" is key. If 5 divides a2- b2 and 5 divides b2- c2 then what can you say about a2- c2= (a2- b2)- (b2- c2)?
 
  • #3
a^2 - b^2 is obviously symmetric? I don't see it =\ can you explain this further?

[edit] Ohh... So it's like aRb -> bRa (for all a,b in some set). I see it now. But I don't see why we are using a^2-b^2, where did it come from? What made you say, oh well 5|a^2+4b^2 iff 5|a^2-b^2.
 
Last edited:
  • #4
HallsofIvy said:
Once again, that lovely "5 divides a2+ 4b2 if and only if 5 divides a2- b2" is key. If 5 divides a2- b2 and 5 divides b2- c2 then what can you say about a2- c2= (a2- b2)- (b2- c2)?

That 5 must also divide a2- c2= (a2- b2)- (b2- c2) since aRb^bRc -> aRc
 
  • #5
Adding (or subtracting) a multiple of 5 doesn't alter the divisibilty or indivisibilty by 5 of a number. That's just basic modulo arithmetic.

a^2-b^2 = a^2+4b^2 -5b^2

hence one side is divisible 5 if and only if the other side is.

and since a^2-b^2=-(b^2-a^2)

it is obviously a symmetric relation.
 
  • #6
matt grime said:
Adding (or subtracting) a multiple of 5 doesn't alter the divisibilty or indivisibilty by 5 of a number. That's just basic modulo arithmetic.

a^2-b^2 = a^2+4b^2 -5b^2

hence one side is divisible 5 if and only if the other side is.

and since a^2-b^2=-(b^2-a^2)

it is obviously a symmetric relation.

I can follow this really well; but never in a million years would I have used the idea that I could just subtract a mulitple of 5... But yes, this now makes sense.
 

1. What is a relation in discrete math?

A relation in discrete math is a set of ordered pairs that relate elements from two different sets. It is used to describe how elements from one set are related to elements in another set.

2. What does it mean for a relation to be symmetric?

A relation is symmetric if for any two elements in the relation, if (a, b) is in the relation, then (b, a) is also in the relation. In other words, if two elements are related, then their order does not matter.

3. How can I determine if a relation is symmetric?

To determine if a relation is symmetric, you can check if for every element (a, b) in the relation, there is also an element (b, a) in the relation. If this is true for all elements, then the relation is symmetric.

4. What does it mean for a relation to be transitive?

A relation is transitive if for any three elements in the relation, if (a, b) and (b, c) are in the relation, then (a, c) is also in the relation. In other words, if two elements are related and the second element is related to a third element, then the first element is also related to the third element.

5. How can I determine if a relation is transitive?

To determine if a relation is transitive, you can check if for every pair of elements (a, b) and (b, c) in the relation, there is also an element (a, c) in the relation. If this is true for all pairs, then the relation is transitive.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
8K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
17
Views
10K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
11K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Back
Top