My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree4Thanks
Reply
 
LinkBack Thread Tools Display Modes
February 4th, 2019, 02:42 PM   #11
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 307
Thanks: 101

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by zylo View Post
"In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b and b is related to an element c then a is also related to c"

Quoted from wiki, "transitive relation."
This is an equivalent definition, but you must note that "a is related to b" (or, "a R b", as in the alternative definition in the link you posted) is defined to mean "(a,b) is in R". (Indeed, from the wiki on "binary relation": "an element $a$ is related to an element $b$ if and only if the pair $(a, b)$ belongs to the set".)

So, I'll repeat the counterexample once more: 4 is related to 2 (i.e. (4,2) is in R) and 2 is related to 1 (i.e. (2,1) is in R) but 4 is not related to 1 (i.e. (4,1) is not in R). What a surprise...
cjem is offline  
 
February 4th, 2019, 02:43 PM   #12
Global Moderator
 
Joined: Dec 2006

Posts: 20,298
Thanks: 1971

The definition you gave, zylo, is right and uses "then" (meaning "it's implied that") just once. In contrast, you used "implies" three times. What you did was different from what you should have done.
skipjack is offline  
February 5th, 2019, 08:27 AM   #13
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 124

The problem with thread is the absence of a hard and fast unequivocal definition, leading to inanities like "You are wrong."


A binary Relation on a set U is a set S of pairs (a,b) of members of U.

The Relation is transitive if (a,b), (b,c) and (a,c) are in S.


cjem's example: (4,2) and (2,1) are in S. (4,1) isn't.

EDIT: cjem came close.

Quote:
Originally Posted by cjem View Post
You've got the right idea here, but you need to be careful. The statement "(a,a) is not in set" isn't true in general. Indeed, (0,0) is in R. Fortunately, you don't need it to be true in general. To show the relation is not reflexive, you just need one example of a pair of integers of the form (a,a) that isn't in R. (1,1) works.

Similarly for symmetry: if a = 0, then (2a,a) and (a,2a) are both in R. Again, we just need a single example of symmetry failing. e.g. (2,1) is in R but (1,2) isn't.



I'm not sure what you're trying to say here, but this relation is obviously not transitive. Transitivity says: if $(a,b)$ and $(b,c)$ are in $R$, then so is $(a,c)$. But, for example, we see that $(4,2)$ and $(2,1)$ in $R$ while $(4,1)$ isn't.
My only quibble is the if-then. I think it's misleading-it sets you thinking about implication.. There is no if-then. R is transitive if the three pairs are in S.

Last edited by zylo; February 5th, 2019 at 08:41 AM.
zylo is offline  
February 5th, 2019, 09:33 AM   #14
Global Moderator
 
Joined: Dec 2006

Posts: 20,298
Thanks: 1971

Quote:
Originally Posted by zylo View Post
My only quibble is the if-then. I think it's misleading . . .
The use of an implication is necessary, not misleading, as it's intended that R might be transitive even though (a, b) and (a, c) are in R, but (b, c) isn't.

Last edited by skipjack; February 5th, 2019 at 09:44 AM.
skipjack is offline  
February 5th, 2019, 09:37 AM   #15
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 307
Thanks: 101

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by zylo View Post
The problem with thread is the absence of a hard and fast unequivocal definition, leading to inanities like "You are wrong."
You posted a link with a completely clear, unambiguous definition... (The other definition in that link is just another way of phrasing the exact same thing, as is the definition in the wiki article.)

Quote:
Originally Posted by zylo View Post
A binary Relation on a set U is a set S of pairs (a,b) of members of U.

The Relation is transitive if (a,b), (b,c) and (a,c) are in S.
No... the relation is transitive if (a,b) and (b,c) being in S implies that (a,c) is in S. (If (a,b) or (b,c) isn't in S, we don't care whether (a,c) is...)

The definition you've given here is much too restrictive: it would mean the only transitive relation on a set U is the set of all pairs (a,b) of elements of U. (Indeed, suppose S is a relation on U such that (a,b) is not in S for some a,b in U. Then, for example, taking c = a, it is not true that "(a,b), (b,c) and (a,c) are in S".)

Quote:
Originally Posted by zylo View Post
My only quibble is the if-then. I think it's misleading-it sets you thinking about implication.. There is no if-then. R is transitive if the three pairs are in S.
There is an if-then/implies in the definition, and it's crucial.
cjem is offline  
February 5th, 2019, 09:59 AM   #16
Global Moderator
 
Joined: Dec 2006

Posts: 20,298
Thanks: 1971

Quote:
Originally Posted by zylo View Post
But if b appears on right side it can't appear on left side unless (b,b) is in set, which it isn't.
That doesn't hold if you are referring to the left and right side of different elements of R. If b appears on both sides of the same element of R, it's trivially true that the element is (b, b). In either case, "which it isn't" isn't known.
skipjack is offline  
February 5th, 2019, 12:37 PM   #17
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 124

Quote:
Originally Posted by zylo View Post

A binary Relation on a set U is a set S of pairs (a,b) of members of U.

The Relation is transitive if (a,b), (b,c) and (a,c) are in S.
In the last post Skipjack is correct, but it is a dead, irrelevant, issue.

As for implication, what does that mean? it just muddies the water. It implies causality. (a,c) is not in S because (a,b) and (b,c) are. It is there by definition of the relationship, and the test of transitivity is not causality, it is the above definition. If-then in this case is pseudo-mathematics. It is trying to combine a concept from logic with a concept from mathematics.

Does (2<3) and (3<4) imply (2<4)? No, (2<4) is in your set of defined relations.

You are confusing implication with definition of the relationship.
zylo is offline  
February 5th, 2019, 01:14 PM   #18
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 307
Thanks: 101

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by zylo View Post
As for implication, what does that mean? it just muddies the water. It implies causality. (a,c) is not in S because (a,b) and (b,c) are. It is there by definition of the relationship, and the test of transitivity is not causality, it is the above definition. If-then in this case is pseudo-mathematics. It is trying to combine a concept from logic with a concept from mathematics.

Does (2<3) and (3<4) imply (2<4)? No, (2<4) is in your set of defined relations.
Not quite. Unlike in everyday speech, "implies"/"if-then" in mathematics does not suggest causality. For statements A and B, "A implies B" just means "A is false or B is true". So, for example:

1) Suppose A is a false statement and B is any statement. Then A implies B.
2) Suppose C is any statement and D is a true statement. Then C implies D.

Back to the problem at hand: even though 2 being less than 3 and 3 being less than 4 might not "cause" 2 to be less than 4, it does imply it. Indeed, take C to be the statement "2 < 3 and 3 < 4" and D to be the statement "2 < 4". Since D is true, we see that C implies D (as in example 2) above).

Last edited by cjem; February 5th, 2019 at 01:47 PM.
cjem is offline  
February 6th, 2019, 08:05 AM   #19
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 124

Personally I find it easier to just observe (2,3), (3,4), and (2,4) are in the set.

It works for OP without having to think do A and B imply C, and for the order relation among integers. And removes ambiguity of the extra definition.
zylo is offline  
February 6th, 2019, 11:18 AM   #20
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 307
Thanks: 101

Math Focus: Number Theory, Algebraic Geometry
Quote:
Originally Posted by zylo View Post
A binary Relation on a set U is a set S of pairs (a,b) of members of U.

The Relation is transitive if (a,b), (b,c) and (a,c) are in S.
Under your definition, the order relation $S = \{(a,b) \in \mathbb{Z} : a \leq b\}$ on the integers is not transitive. To see this, consider $a = 2$, $b = 1$ and $c = 2$. Then it is not true that $(a,b)$, $(b,c)$ and $(a,c)$ are in $S$.

But perhaps it's best to use the standard definition, or one that's equivalent to it. Here's an "implication-free" definition that is equivalent to the standard one:

A relation U on a set S is transitive if: for all a,b,c in U, (a,c) is in S or (a,b) is not in S or (b,c) is not in S.
cjem is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
reflexivity, symmetry, transitivity



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
lie symmetry youness albert Differential Equations 0 May 14th, 2016 07:33 AM
symmetry mared Algebra 1 January 27th, 2014 07:52 AM
Reflexivity of "modulo" = mod Vasily Applied Math 2 August 26th, 2012 10:24 PM
Set Theory Transitivity Proof jstarks4444 Number Theory 1 October 22nd, 2011 03:40 PM





Copyright © 2019 My Math Forum. All rights reserved.