Author |
Topic: Question about relations (Read 1633 times) |
|
jpk2009
Junior Member
Gender: 
Posts: 60
|
 |
Question about relations
« on: May 9th, 2009, 8:02am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender: 
Posts: 880
|
|
Re: Question about relations
« Reply #1 on: May 9th, 2009, 8:18am » |
Quote Modify
|
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".
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Question about relations
« Reply #2 on: May 9th, 2009, 9:33am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Question about relations
« Reply #3 on: May 9th, 2009, 9:50am » |
Quote Modify
|
on May 9th, 2009, 9:33am, jpk2009 wrote:
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.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Question about relations
« Reply #4 on: May 9th, 2009, 10:10am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Question about relations
« Reply #5 on: May 9th, 2009, 3:34pm » |
Quote Modify
|
on May 9th, 2009, 8:18am, 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.
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Question about relations
« Reply #6 on: May 9th, 2009, 11:49pm » |
Quote Modify
|
on May 9th, 2009, 3:34pm, towr wrote:
I'd look for a model (graph) where the relation is symmetric and transitive, yet not reflective. It's a bit simpler, I think.
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.
|
|
Yes, that's what I was implying.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Question about relations
« Reply #7 on: May 10th, 2009, 1:28am » |
Quote Modify
|
My last sentence was a bit incomplete; but only I realized that after having shut down my computer. It holds if all vertices have any edge, incoming or outgoing. Because symmetry means a vertex always either has both or neither.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Question about relations
« Reply #8 on: May 10th, 2009, 2:23am » |
Quote Modify
|
So, the simplest relation that is symmetric and transitive, but not reflective, is the empty relation (on a nonempty set), that is, a~b is false for any a and b. For example, on the real numbers, we could define a~b to mean a2 + b2 + 1 = 0.
|
| « Last Edit: May 10th, 2009, 2:24am by pex » |
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Question about relations
« Reply #9 on: May 10th, 2009, 10:17am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Question about relations
« Reply #10 on: May 10th, 2009, 6:20pm » |
Quote Modify
|
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 a2+b2+1 = 0, right?
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Question about relations
« Reply #11 on: May 11th, 2009, 12:00am » |
Quote Modify
|
on May 10th, 2009, 6:20pm, jpk2009 wrote:| 1>2 is about as empty as a2+b2+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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print