Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2008-09-28 06:45:20

Mapeki
Member
Registered: 2008-09-28
Posts: 4

Discrete Math: Relations

Hello.

I have the question:

        Let A = {a, b, c, x, y, z} Give an example of a relation R on A which is:
               
                (a) reflexive and not transitive,
                (b) transitive and not reflexive,
                (c) transitive and not symmetric,
                (d) antisymmetric, transitive, but not reflexive,
                (e) an equivalence relation,
                (f) an order relation.
                (g) a function.

In my professors notes he never does any examples that have so many elements in the set, and therefore uses them all in every example problem.

Do I have to use every element in the set A for the relation R?

Or can I just say that the answer to (a) would be something like {(a,a), (a,b), (b,b)}

Also, I don't really understand how to do the function question, any explanation would be quite helpful.

Offline

#2 2008-09-28 08:28:31

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Discrete Math: Relations

Or can I just say that the answer to (a) would be something like {(a,a), (a,b), (b,b)}

That is the form you want your answer in.  But that answer is not correct.  It is both not reflexive (is c related to c?) and transitive.

Also, I don't really understand how to do the function question, any explanation would be quite helpful.

What is the definition of a function? (Hint: Use the word "relation" in your definition).


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2008-09-28 10:49:33

Mapeki
Member
Registered: 2008-09-28
Posts: 4

Re: Discrete Math: Relations

So from what Ricky said the answer to (a), would be {(a,a), (b,b), (c,c), (x,x),(y,y),(z,z)}

For (b), for the relation to be transitive is it something like {(a,b), (b,c), (a,c),(b,a),(b,a),(c,a)(c,b).....(z,a),(z,b),(z,c)}
Is their a shorter answer, do I need to use every element from the set A in the relation example? I'm horribly confused.

I'm not really getting this very well, I don't fully understand what constitutes the relation. I only have one example of each
type of the relations and our class isn't really on this. The book for the course doesn't cover this at all so I just have some small notes of the prof's. (I'm actually missing a prerequisite for the course)


I also have basically the same with a different set.
Let A = Z Give an example of a relation R on A which is:
(a) reflexive and not transitive,
(b) transitive and not reflexive,
(c) transitive and not symmetric,
(d) antisymmetric, transitive, but not reflexive,
(e) an equivalence relation,
(f) an order relation.
(g) a function.

For answers for this, I don't really know what to do?

I feel like I'm missing a lot on this, does anyone know of a good web resource on set relations?

Offline

#4 2008-09-28 15:08:50

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Discrete Math: Relations

So from what Ricky said the answer to (a), would be {(a,a), (b,b), (c,c), (x,x),(y,y),(z,z)}

That is not correct.  Transitive means that IF g is related to h, and h related to i, then g is related to i.  However, if nothing is ever related to each other, then you have that this statement is vacuously true.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#5 2008-09-28 16:32:33

Mapeki
Member
Registered: 2008-09-28
Posts: 4

Re: Discrete Math: Relations

So in order for them not to be transitive, they have to be at least related?  I almost feel like you misread the question, or I'm really not getting this at all.

For it to be reflexive and transitive(which is not the question though): {(a,a), (b,b), (c,c), (x,x),(y,y),(z,z), (a,z),(z,a)}
For it to be transitive and non-reflexive: {(a,a), (b,b), (c,c), (x,x),(y,y),(a,z),(z,a)}

That makes sense to me I believe.

Would that be right now?


Thanks Ricky.

Offline

#6 2008-09-28 18:07:10

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Discrete Math: Relations

So in order for them not to be transitive, they have to be at least related?

Think of it this way: In order for it not to be transitive, there must exist a counter example to the transitive property.  So what does it take for something to be a counter example?  You have to satisfy the hypothesis, and the conclusion can not hold.  The hypothesis for transitive is that g is related to h and h is related to i.  The conclusion is that g is related i.

If you have {(a,a), (b,b), (c,c)}, that set is transitive.  The only elements that are related is (a,a), (b,b), and (c,c).  So the only thing that satisfies the hypothesis is a is related to a, and a is related to a (or the same thing with all b's and c's).  And of course, a is related to a, so the conclusion holds as well.  So for everything that satisfies the hypothesis of transitive, the conclusion holds.  Therefore, there are no counter-examples and so the set is transitive.

For it to be reflexive and transitive(which is not the question though): {(a,a), (b,b), (c,c), (x,x),(y,y),(z,z), (a,z),(z,a)}

That relation is indeed reflexive and transitive.

For it to be transitive and non-reflexive: {(a,a), (b,b), (c,c), (x,x),(y,y),(a,z),(z,a)}

That set is not transitive.  z is related to a, and a is related to z, but z is not related to z.  So we have satisfied they hypothesis, but the conclusion of transitive does not hold.  Therefore, we have found a counter example to the property of transitive.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2008-09-29 01:49:04

Mapeki
Member
Registered: 2008-09-28
Posts: 4

Re: Discrete Math: Relations

Thank you Ricky, that makes so much more sense now.

If the set the relation was on was all integers how would I go about writing that as a relation?

Offline

#8 2008-09-29 05:42:51

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Discrete Math: Relations

If the set the relation was on was all integers how would I go about writing that as a relation?

As with any thing that is infinite, we may define functions or recursive algorithms.  For example:

n is related to m if and only if n = m/2.

So we see that 4 is related to 8, but 8 is not related to 4, and so on.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

Board footer

Powered by FluxBB