Discrete Math 4: Properties of relations

Just like with anything else in life, humans spot patterns in math and then name them. There are a few nice properties that relations can have, which mathematicians like to use and which normies (that’s what we call non math people) take for granted.

Recall that a relation R, is a subset of some product of sets A \times B. So it consists of ordered pairs. For the rest of this article I will be worried about a relation on just a single set, so I will be looking at subsets of something like A \times A.

As I mentioned previously, the name relation is a bit tricky due to what we think it means in English. One would assume that everything is related to itself, but that need not be true based strictly on what we defined a relation to be. We do however have a name for a relation with the property that everything is related to itself.

Formally, we say that a relation R on a set A is reflexive if for any element in A we have that a is related to a. In math notation, we say R is reflexive if for all a \in A \text{ we have } (a,a) \in R.

Equality is a reflexive relation, because everything is equal to itself. This is really the only relation that normies get to see, even those that go all the way to Calc 3.
Being less than or greater than is not reflexive, because nothing is less than itself and nothing is greater than itself.

The next “good” property that a relation can have is called symmetry. It is another one that most people would say is obvious in English. We say that a relation R on a set A is symmetric if whenever a is related to b, then b is also related to a. The more mathy way of saying this is, a relation R is symmetric if for every (a,b) \in R we have that (b,a) \in R.

Again equality is symmetric, if a=b then clearly b=a also. Greater than is not symmetric, if a>b then b>a is false.

Lastly we have transitivity. It is a relation which you can think of as a chain of elements. The idea is that when a is related to b, and b is related to c, then a is also related to c. It is a chain from a to c using b as a connecting point.

Mathily, we say that a relation R on a set A is transitive if whenever
(a,b) \in R and (b,c) \in R then (a,c) \in R. So whenever the ending of one element is the same as the beginning of another element, we must have that the beginning of the first one combined with the ending of the second one must also be an element in order for the relation to be transitive.

Again equality is transitive, if a = b and b = c, then of course a = c. Greater than, is also transitive.
If a > b and b > c then of course a > c.

Something nice happens when a relation has all three of these properties at the same time. We call that an equivalence relation and I will talk about that next time.

This entry was posted in Discrete Math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s