Copyright

Antisymmetric Relation: Definition, Proof & Examples

Instructor: Laura Pennington

Laura has taught collegiate mathematics and holds a master's degree in pure mathematics.

This lesson will talk about a certain type of relation called an antisymmetric relation. We will look at the properties of these relations, examples, and how to prove that a relation is antisymmetric.

Antisymmetric Relation

Suppose that your math teacher surprises the class by saying she brought in cookies. The class has 24 students in it and the teacher says that, before we can enjoy the cookies, the class has to figure out how many cookies there are given only the following facts:

  • The number of cookies is divisible by the number of students in the class.
  • The number of students in the class is divisible by the number of cookies.


antisymm1


In mathematics, the facts that your teacher just gave you have to do with a mathematical concept called relations. A relation is a set of ordered pairs, (a, b), where a is related to b by some rule.

Consider the relation 'is divisible by' over the integers. Call it relation R. This relation would consist of ordered pairs, (a, b), such that a and b are integers, and a is divisible by b. Now, consider the teacher's facts again. By fact 1, the ordered pair (number of cookies, number of students) would be in R, and by fact 2, the ordered pair (number of students, number of cookies) would also be in R.

So far, so good. Relations seem pretty straightforward. Let's take things a step further. You see, relations can have certain properties and this lesson is interested in relations that are antisymmetric. An antisymmetric relation satisfies the following property:

  • If (a, b) is in R and (b, a) is in R, then a = b.

In other words, in an antisymmetric relation, if a is related to b and b is related to a, then it must be the case that a = b.

Okay, let's get back to this cookie problem.

As it turns out, the relation 'is divisible by' on the integers is an antisymmetric relation. That is, if a and b are integers, and a is divisible by b and b is divisible by a, it must be the case that a = b.

That means that since (number of cookies, number of students) and (number of students, number of cookies) are both in R, it must be the case that the number of cookies equals the number of students. Since there are 24 students in the class, it must be the case that there are 24 cookies!

Proof of Antisymmetric Relations

Just as we're all salivating getting ready for our cookies, the teacher says that we have to give her justification that the relation 'is divisible by' really is antisymmetric, so that we use our logic to prove that there are 24 cookies.

To prove an antisymmetric relation, we assume that (a, b) and (b, a) are in the relation, and then show that a = b. To prove that our relation, R, is antisymmetric, we assume that a is divisible by b and that b is divisible by a, and we show that a = b.

The definition of divisibility states that, since a is divisible by b and b is divisible by a, a divides into b evenly and b divides into a evenly. We take two integers, call them m and n, such that b = am and a = bn. If we write it out it becomes:

  • b = am = (bn)m = b(nm).

Dividing both sides by b gives that 1 = nm. Since m and n are integers, it must be the case that n = m = 1, since the only pair of integers that multiply to give us 1 is 1 and 1. Since n = 1, we have

  • a = bn = b(1) = b

So a = b.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support