Reflexivity, Symmetry and Transitivity

In this post, I will show (using "organic" examples) that Reflexivity, Symmety and Transitivity are independent of each other.

Definitions


(The diamond represents some arbitrary relation)

The following table summarizes this post:

	Reflexive	Symmetric	Transitive
.
	x
		x
	x	x
			x
	x		x
		x	x
	x	x	x

Membership


Non-membership
By the axiom of regularity, no set is a member of itself:
Using the above A,B and C:


Inequality

Everything is equal to itself, therefore (by duality) nothing is not equal to itself, and inequality is irreflexive.


Approximation


This definition for approximation is not universal, but I think it's good enough. The basic idea behind it not being transitive is that little bits added to little bits eventually make big bits.

Less than
By definition, less than is irreflexive, symmetric, and transitive.

Implication

Reflexive:

a	a → a
T    F	T T

Symmetric:

a     b	(a → b) ↔ (b→a)
T     T   T F F T F F	T F F T

Transitive:

a     b     c	((a → b) Λ (b → c)) → (a → c)
T     T     T   T T F T F T T F F F T T F T F F F T F F F	T T T T T T T T

The reflexive and transitive truth tables are tautologies, therefore implication is reflexive and transitive. The symmetric truth table is contingent, therefore implication is not symmetric.

Logical And
And is not reflexive because .
The only time x Λ y is when x = y = 1. Therefore, it is trivially the case that .
The proof for transitivity is similarly trivial.

And is not usually thought of as a relation, but technically it is so I'm using it.

Equals
By definition, equality is reflexive, symmetric, and transitive.

Commutativity and Non-Associativity

This is part three of my three part series on Commutativity and Associativity. In the first part we looked at the definitions of commutativity and associativity. In part two we looked at a system that was associative but not commutative. Now let's look at a system that commutative but not associative.

Rock, Paper, Scissors, Shoot!

This example (found on Wikipedia) is based on the game Rock, Paper, Scissors. (If you don't know how to play look here; if you want to get some practice in, play here.) Recall that Rock beats Scissors, Scissors beats Paper, and Paper beats Rock (for some reason). Let r, p, and s represent rock, paper, and scissors respectively, and let x * y mean "x is played against y." After a match is played, the match is equal to the winner of the match; in a tie, the winner is whatever hand was played. Some examples:

English Language Version	Notation
"rock is played against paper and paper wins"	r * p = p
"scissors is played against paper and scissors wins"	s * p = s
"paper is played against paper and paper wins"	p * p = p

Like before, we can keep all of our information organized by arraigning it as a table:

*	r	p	s
r	r	p	r
p	p	p	s
s	r	s	s

You can tell by the symmetry of the table that it's commutative (the order in which you evaluate expressions doesn't matter). However, it's non-associative:

(s * p) * r = s * r = r

but

s * (p * r) = s * p = s

It doesn't matter what order you evaluate terms, but it matters very much how you group them.

Conclusion

On this three part adventure (no, I don't think adventure is hyperbole) we've looked at structures that were commutative and associative, commutative and non-associative, non-commutative and associative, and non-commutative and non-associative. The table gives an example from all four categories:

	Commutative	Non-Commutative
Associative	Addition	Triangle Transformations
Non Associative	Rock, Paper, Scissors	Division

This shows that commutativity and associativity are independent notions. If you have one, that doesn't say anything about whether you have the other.

Non-Commutativity and Associativity

In my last post, I introduced the ideas of commutativity (order doesn't matter) and associativity (grouping doesn't matter). In this post I want to explore a structure that's associative, but not commutative.

Messing With Triangles: Ultra-Basic Group Theory

I'm going to start with an equilateral triangle:

Triangles are pretty symmetric; rotating it 120 degrees doesn't change it:

flipping it over also leaves the triangle unchanged:

All in all, there are 5 different things I can do to a triangle and still have it appear the same. I can rotate (clockwise or counterclockwise), or I can flip it over one of three axes:

I've labeled the corners to tell the triangles apart. Also included is what mathematicians call the Identity Element (top left corner): it's what you get when you do nothing.

In order to facilitate discussion, I think each of the possible 6 actions should have names. For the purposes of this post, I'm going to call the counterclockwise rotation R1 and the clockwise rotations R2. I've labeled each of the flip actions F1, F2 and F3. In keeping with mathematical tradition, I've labeled the identity I:

At this point, I would recommend cutting your own triangle out of paper (or better yet, cardboard) and playing with it. Notice what happens when you do two actions in a row. For example, if you do F1 followed by R1, then you end up in the same place as just doing F2. If you do F2 followed by F3 you end up at R2. F2 followed by F2 again is I. To make things more readable, I'm going to use use the notation x*y to mean x followed by y. So:

"R1 followed by F1 is R2"

can be written as:

R1 * F1 = R2

and 

"F1 followed by F1 is I"

is simply

F1 * F1 = I

This will making writing and (after some practice) reading about the different triangle operations much easier. I suggest pausing here to play with your newly cut out triangle. If you haven't bothered to make your own triangle (come on, it's not that much work), or if you just want to check what you're doing, you can play with this interactagraph I made:

At this point, you might begin to notice some patterns. For example:

• I * I = I.
• You can always get back to I with just one step.
• A rotation followed by another rotation is always a rotation (or I).
• A flip followed by a rotation (or visa versa) is always a flip.
• A flip followed by the same flip is I.
• A rotation followed by a different rotation is I.

It might be helpful at this point to collect all of our observations into a sort of multiplication table.

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

Reading this is just like reading a times table. If I want to know what R2 * F2 is, I just find where the R2 row meets the F2 column:

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

So R2 * F2 = F1.

Associativity and Non-Commutativity

With our multiplication table in place, we can now begin to look for patterns. It's clear that this structure is associative. For example:

R2 * (F1 * F2) = R2 * R2 = R1

and

(R2 * F1) * F2 = F3 * F2 = R1

More abstractly, 

(x * y) * z = x * (y * z)

for all x, y and z. But the interesting thing is that this structure is non-commutative; when evaluating equations, the order in which you evaluate matters. For example:

F1 * R1 = F3

but

R1 * F1 = F2

So the structure is non-commutative. (An important observation is that some equations are commutative: R1 * R2 = R2 * R1, but you'll remember from my last post that every pair of elements has to commute in order for an operation to be considered commutative.)

Conclusion

In my last post we saw structures that were commutative and associative (like addition), and non-commutative and non-associative (like division). In this post we looked at something non-commutative and associative. Up next, a post about something commutative and non-associative.

Follow-Up Questions:

• Consider just R1, R2 and I (so, ignore flips). Is this structure commutative? Is it still associative?
• Study the rotations and flips of a square. Is this structure commutative? Associative?
• Tetrahedrons also have four corners. Is the set of possible transformations the same as the squares? (i.e. is the tetrahedron multiplication table the same as the square multiplication table?)

Further Reading, (from easiest to hardest):

• Group Theory in the Bedroom, and Other Mathematical Diversions by Brian Hayes (Chapter 12)
• Abel's Proof: An Essay on the Sources and Meaning of Mathematical Unsolvability by Peter Pesic (Chapter 8)
• The Equation That Couldn't Be Solved: How Mathematical Genius Discovered the Language of Symmetry by Mario Livio (Chapter 6)

Happy Mother's Day

Hey Mom:




I spent quite a bit of time tweaking this relation. (It's a relation and not a function because the "o" can't pass the vertical line test). Ultimately I settled for something relatively simple.

If you want to put this into your graphing calculator, I recommended:

Y1 = (1+(1-x*x)^(1/3))(abs(x) < 1)
Y2 = (1-(1-x*x)^(1/3))(abs(x) < 1)
Y3= (1+cos(πx))(abs(x) < 5 and abs(x) < 1)

"abs()" can be found under MATH => NUM. The "<" can be found under TEST (2nd MATH) and the "and" is under TEST => LOGIC.

You get this weird vertical line thing at x = 1 or -1, but that's because the calculator has a hard time handling discontinuities and fills in the gap the best it can. In a perfect world, there would be a tiny gap between the bottom of m and the side of the o.

 If you're not a fan of piecewise functions, then you have to do some magic with absolute values:



I know what you're thinking, absolute values are piecewise functions, you're not fixing the problem at all. Well, that's only if you define absolute value as:



If you define it as:



Then everything is good to go.

Commutativity and Associativity

This is the first of a three part post on the commutative and associative properties (stay tuned for parts two and three).

Commutativity: Order Doesn't Matter
When you add two things, the order in which you add them doesn't matter (2+4 is the same as 4+2). The name of this property is the commutative property. Examples of commutative operations are [note 1]:

• Multiplication: 2×3 is the same as 3×2
• Preparing a bowl of Cereal: it doesn't matter what order you add the milk and the cereal
• Putting on shoes: It doesn't matter what shoe you put on first
• Rotation: rotate left then right or right  then left , you end up at the same place
• The logical operator or: "Him or her" is the same as "Her or him."  
• Vector addition: 
• The intersection of sets: :
• Multidimensional Integration:

Sometimes the order of things do matter. For example, division: is not the same as (the first is 2 the second is one half). When an operation does not commute, we call it non-commutative (that's simple enough). Some examples of non-commutativity are:

• Subtraction: 5-3 is 2, but 3-5 is -2
• Division: 
• Exponentiation: 
• Matrix Multiplication: [see note 2]
• Making a cake: mix ingredients and then bake, order matters
• Putting your clothes on in the morning: underwear first, then pants
• Material Implication:  is not the same as
• Rotations on a Rubik's Cube: turning the top then the right is different than turning the right then the top:

One important note on non-commutativity is that the operation doesn't have to be non-commutative on everything for it to be non-commutative. Take exponentiation for example, and are both 16. (Or if you're less mathematically inclined, use the examples of putting on your clothes: it doesn't matter if you put your pants on first, or your shirt.) An operation is still non-commutative if there's at least one pair of things that doesn't commute.

Associativity: I Don't Care Who You Hang Out With

 When adding three (or more) numbers, it doesn't matter how you group those numbers. For example, if you wanted to add 2, 3 and 5, you could add 2 and 3, then add 5, or you could add 2 to 3 plus 5. This is much clearer with notation: 2+(3+5) is the same as (2+3)+5. The way you group the numbers doesn't change the answer. This is called this associativity. Other examples of associativity include:

• Multiplication: 2×(3×4) is the same as (2×3)×4
• Mixing trail mix: mixing raisins and granola then adding walnuts is the same as mixing raisins into a  granola/walnut mixture
• Translations on a plane: going up 4, then going to the left 3 and down 2 is the same as going up 4 and left 3 then going down 2
• Maximum function: max(a, max(b,c)) = max(max(a,b),c) 
• The logical operator and: 
• Composite functions:
• Putting together a puzzle:

You probably guessed it; some things are non-associative. The best example is division: is 1, but is 4. When dividing, the way you group things matters. Other non-associative examples include:

• Subtraction : (8-5)-2 = 1 but 8-(5-2) = 5 
• Exponentiation:  
• Doing the dishes: Washing and drying dishes, then putting them away is definitely not the same as washing dishes that are dried and put away
• English Expressions: A (smart dog) owner is someone that owns a smart dog, a smart (dog owner) is someone that is smart and owns a dog.
• Material implication: is not the same as
• The one dimensional distance formula d(x,y) = |x-y|:

Conclusion
Commutativity and associativity are important mathematical concepts. In part 2, we'll be looking at something associative and non-commutative. In part 3, We'll look at something commutative and non-associative.

[Notes]

[1] Some of my examples come from Wikipedia, some of them I heard before (in a classroom or in a conversation), some of them I just made up.

[2]