wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Question about relations
        
(Message started by: jpk2009 on May 9^th, 2009, 8:02am)

Title: Question about relations
Post by jpk2009 on May 9^th, 2009, 8:02am

I was reading an algebra book recently about relations on sets that discussed reflective, symmetric, and transitive relations. The first one of these is "a~a", the second "if a~b then b~a", and the third one "if a~b and b~c, then a~c." It goes on to state that ~ yields a natural partition of the set S.

There is a problem in that book about this that I never quite knew the answer to but I think I know the answer. The problem is

"The following is a famous incorrect argument. Find the error. The reflective criterion is redundant in the conditions of an equivalence relation, for from a~b and b~a (symmetry) we deduce that a~a by transitivity."

Am I correct that the reason that is not true is that without the reflective criterion it is impossible to conclude any kind of relation to begin with? I mean, if you are unable to determine if a is equivalent to itself, a~a, then how can one make a statement about a being equivalent to anything else?

Title: Re: Question about relations
Post by pex on May 9^th, 2009, 8:18am

No, the reason is a bit more subtle. The key is that you misstated the reflective property: its correct form is "for all a, it holds that a~a".

So, can you come up with a relation that is symmetric and transitive, but not reflective? The problem that you quote is equivalent to showing that the answer to this question is "yes".

Title: Re: Question about relations
Post by jpk2009 on May 9^th, 2009, 9:33am

Thank you for your answer pex. I did neglect to state that first property correctly. I'm glad I asked this question. I need to reread that section before I try to answer your question. Are you a math teacher?

Title: Re: Question about relations
Post by pex on May 9^th, 2009, 9:50am

on 05/09/09 at 09:33:18, jpk2009 wrote:

Are you a math teacher?

Thanks! Not exactly, but it comes close. I'm a PhD student (in Econometrics, so I have mostly "applied" knowledge about math), so part of my job is teaching - statistics courses, in my case.

Concerning the question, it might be worthwhile to look up what the logical statement "if P then Q" means exactly.

Title: Re: Question about relations
Post by jpk2009 on May 9^th, 2009, 10:10am

Cool. I am a fine arts student knowing enough math to be dangerous. Actually I started doing more math recently because I am into bronze and have made quite a few pieces and wanted to work on some knots. Just to make a Trefoil knot in bronze without cheating is quite involved. I would like to figure out a better way to do it.

Title: Re: Question about relations
Post by towr on May 9^th, 2009, 3:34pm

on 05/09/09 at 08:18:46, pex wrote:

So, can you come up with a relation that is symmetric and transitive, but not reflective? The problem that you quote is equivalent to showing that the answer to this question is "yes".

I'd look for a model (graph) where the relation is symmetric and transitive, yet not reflective. It's a bit simpler, I think.
[hide]A single vertex with no edge satisfies this constraint. In fact, any model where there are disconnected vertices works.
In models where all vertices have at least one outgoing edge, however, transitivity+symmetry does imply reflexivity.[/hide]

Title: Re: Question about relations
Post by pex on May 9^th, 2009, 11:49pm

on 05/09/09 at 15:34:47, towr wrote:

Yes, that's what I was implying.

Title: Re: Question about relations
Post by towr on May 10^th, 2009, 1:28am

My last sentence was a bit incomplete; but only I realized that after having shut down my computer. [hide]It holds if all vertices have any edge, incoming or outgoing. Because symmetry means a vertex always either has both or neither.[/hide]

Title: Re: Question about relations
Post by pex on May 10^th, 2009, 2:23am

So, the simplest relation that is symmetric and transitive, but not reflective, is [hide]the empty relation (on a nonempty set), that is, a~b is false for any a and b[/hide]. For example, on the real numbers, we could define a~b to mean [hide]a² + b² + 1 = 0[/hide].

Title: Re: Question about relations
Post by jpk2009 on May 10^th, 2009, 10:17am

I knew not to look at this since it might spoil what I needed to figure out. I never thought about an empty relation. The equation you made makes perfect sense.

Title: Re: Question about relations
Post by jpk2009 on May 10^th, 2009, 6:20pm

I noticed that if you make the relation > or < you really can't do much with it in this fashion. This is what I initially though you meant by an empty relation. 1>2 is about as empty as a²+b²+1 = 0, right?

Title: Re: Question about relations
Post by pex on May 11^th, 2009, 12:00am

on 05/10/09 at 18:20:51, jpk2009 wrote:

1>2 is about as empty as a²+b²+1 = 0, right?

Sure. I just thought it looked nicer if the expression for a~b involved both variables, but there's nothing wrong with the way you define it. (Technically, they're exactly the same relation - a relation is defined by which pairs (a,b) satisfy a~b, not by the way the "rule" is expressed.)

A little more sophisticated examples are also possible. For example, if we define a~b to mean "a = b and a =/= 0", for all real numbers a and b, you can check that this relation is again symmetric and transitive, but it's not reflective (the "for all" part fails).