My Math Forum > Math Symmetry, transitivity and reflexivity

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

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 "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...

 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.
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 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.

February 5th, 2019, 09:33 AM   #14
Global Moderator

Joined: Dec 2006

Posts: 20,298
Thanks: 1971

Quote:
 Originally Posted by zylo 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.

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 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 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 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.

February 5th, 2019, 09:59 AM   #16
Global Moderator

Joined: Dec 2006

Posts: 20,298
Thanks: 1971

Quote:
 Originally Posted by zylo 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.

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 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.

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 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.

 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.
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 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.

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top