Antisymmetric Relation

Written by

Malcolm McKinsey

January 11, 2023

Fact-checked by

Paul Mazzola

Antisymmetric relation definition

Antisymmetric relation is a concept of set theory that builds upon both symmetric and asymmetric relation in discrete math. At its simplest level (a way to get your feet wet), you can think of an antisymmetric relation of a set as one with no ordered pair and its reverse in the relation.

How to prove a relation is antisymmetric

In antisymmetric relations, you are saying that a thing in one set is related to a different thing in another set, and that different thing is related back to the thing in the first set: a is related to b by some function and b is related to a by the same function.

The only way that can hold true is if the two things are equal.

Suppose your math club has a celebratory spaghetti-and-meatballs dinner for its 34 members and 2 advisers. Before you tuck in, your two club advisers tell you two facts:

1. The number of spaghetti-and-meatball dinners is divisible by the number of club members and advisers in the club

2. The number of club members and advisers is divisible by the number of spaghetti-and-meatball dinners

The information you heard fits neatly into set theory:

• The dinners, and members and advisers, are members of two sets, which could be called X

  and Y.

• Ordered pairs, identified universally as (a, b) where a is related to b by a given rule, can be established to encompass all members in the sets X and Y, as in (number of club members and advisers, number of dinners), or (number of dinners, number of club members and advisers).

• Ordered pairs can also be established within the sets X and Y from only some members of the sets, so your pal Kyle and a dinner are one ordered pair (Kyle, dinner); you and another dinner are a different ordered pair (You, dinner)

• A binary relation, R, is ordered pairs from the sets X and Y related by some rule, so all these ordered pairs are in R: (you, dinner); (Kyle, dinner); (number of club members and advisers, number of dinners); (number of dinners, number of club members advisers)

Rules of antisymmetric relation

Relations can follow just about any rule. Take the relation "is divisible by", which is a relation for ordered pairs in the set of integers. For relation, R, any ordered pair (a , b) can be found where a and b are whole numbers (integers) and a is divisible by b.

Looking at the math club adviser's two facts, we see that the first fact allows the ordered pair (number of dinners, number of club members and advisers) to be in R.

The second fact allows the ordered pair (number of club members and advisers, number of dinners) to be in R also.

Symmetric, asymmetric, and antisymmetric relations

Relations can be symmetric, asymmetric or antisymmetric. We are interested in the last type, but to understand it fully, you need to appreciate the first two types.

We use the graphic symbol ∈ to mean "an element of," as in "the letter A ∈ the set of English alphabet letters."

• Symmetric: Relation R of a set X is symmetric if $(b,a)\in R$ and $(a,b)\in R$; the relation R "is equal to" is a symmetric relation, as with 4 = 3 + 1 and 3 + 1 = 4, like a two-way street.

• Asymmetric: Relation R of a set X is asymmetric if $(a,b)\in R$ but $(b,a)\notin R$; the relation R "is less than" is an asymmetric relation, as with $8<12$ but $12\nless 8$.

• Antisymmetric: Relation R of a set X is antisymmetric if $(a,b)\in$ and $(b,a)\in R$, meaning $a=b$; but if $a\ne b$, then $(b,a)\notin R$, like a one-way street

Antisymmetric relation example

Return to our math club and their spaghetti-and-meatball dinners. For the number of dinners to be divisible by the number of club members with their two advisers AND the number of club members with their two advisers to be divisible by the number of dinners, those two numbers have to be equal.

Both ordered pairs are in relation R:

• (number of members and advisers, number of dinners)

• (number of dinners, number of members and advisers)

Since 34 members and 2 advisers are in the math club, the number of dinners is 36.

Before your club members can eat, the advisers ask your group to prove the antisymmetric relation.

How do you do it? You show that aa is, in fact, divisible by b, b is divisible by a, and therefore a = b:

• 36 member and advisers, 36 dinners: $\frac{36}{36}$

• 36 dinners, 36 members and advisers: $\frac{36}{36}$

• $36=36$

No other integers will satisfy this condition. You can generalize it, too:

Now, let's use these formulas and steps to prove the antisymmetric relation:

1. $b=am$

2. $am=(bn)m$

3. $(bn)m=b(nm)$

4. $\frac{(bn)m}{b}=\frac{b(nm)}{b}$

5. $1=nm$

6. $1=1+1$

With n now shown to be 1, replace n with 1 in the second equation:

1. $a=bn$

2. $a=b(1)$

3. $a=b$

There it is: the ordered pair (a , b) is antisymmetric.