Analyzing Relation Properties

Welcome to the next step in our exploration of mathematical structures. In our previous lessons, we've built a solid foundation. We started with the logic of propositions, learned how to handle collections of objects using set theory, and saw how the Cartesian product allows us to form the universe of all possible pairs between elements of sets.

Today, we'll build directly on that foundation to study relations. A relation is just a way of formalizing a relationship between objects, and mathematically, it's defined as a specific subset of a Cartesian product. But simply defining a relation isn't enough. The real power comes from classifying them based on their internal structure. Your goal for this lesson is to learn how to determine if a relation has four key properties: being reflexive, symmetric, antisymmetric, or transitive. Understanding these properties is crucial, as they form the basis for important concepts in computer science like ordering, sorting algorithms, and data partitioning.

What is a Relation?

Let's begin by firming up our core concept. As we've touched upon, a relation $R$ on a set $A$ is simply a subset of the Cartesian product $A \times A$ .

If an ordered pair $(a, b)$ is in the set $R$ , we say that " $a$ is related to $b$ " and can write this as $a R b$ .

For example, let $A = {1, 2, 3}$ . The relation "less than" on this set would be the set of pairs $R = {(1, 2), (1, 3), (2, 3)}$ . Since $(1, 2) \in R$ , we can say $1 R 2$ .

The Four Fundamental Properties

Now, let's dive into the four properties that are the focus of today's lesson. For a relation to be useful, we need to know what rules it follows. These properties are the rules.

The following reading from "A Spiral Workbook for Discrete Mathematics" provides the formal definitions for each property. As you read, pay close attention to the precise logical structure. For a property to hold, the condition must be true for all elements specified.

7.2: Properties of Relations

This reading provides the concise, formal definitions that we will use throughout the lesson. Note how each property is defined using both set membership notation (e.g., (a,a) \in R) and the relational notation (e.g., a \, R \, a).

Please read the definitions provided in the text. Focus on the section that starts with "A relation R on A is said to be" and review both the set notation and relational notation versions. You can stop reading at the "Remark". The key phrases are the definitions.

Let's break these down with some intuition and examples.

1. Reflexive: Is every element related to itself?

A relation $R$ on a set $A$ is reflexive if $(a, a) \in R$ for every element $a \in A$ .

Intuition: Every element has a "self-loop".
Canonical Example: The relation $\leq$ on the set of integers. For any integer $a$ , it is true that $a \leq a$ .
Non-Example: The relation $<$ on integers. It is not true that $a < a$ .

2. Symmetric: Is it a two-way street?

A relation $R$ is symmetric if whenever $(a, b) \in R$ , it must also be that $(b, a) \in R$ .

Intuition: If there's an arrow from $a$ to $b$ , there must be one from $b$ to $a$ .
Canonical Example: The relation "is a sibling of" on the set of people. If Alice is a sibling of Bob, then Bob is a sibling of Alice.
Non-Example: The relation $\leq$ on integers. We know $3 \leq 4$ , but it is not true that $4 \leq 3$ .

3. Antisymmetric: Is it at most a one-way street?

A relation $R$ is antisymmetric if whenever $(a, b) \in R$ and $(b, a) \in R$ , it must be that $a = b$ .

Intuition: The only time you can have arrows going both ways is if it's a self-loop. Between two distinct elements, the relation can only go in one direction, or not at all.
Canonical Example: The divisibility relation $∣$ on positive integers. If $a ∣ b$ and $b ∣ a$ , it must be that $a = b$ . For example, $2∣4$ but $4 ∤ 2$ .
Non-Example: The relation $R$ on integers where $a R b$ if $a + b$ is even. We have $2 R 4$ (since $2 + 4 = 6$ ) and $4 R 2$ (since $4 + 2 = 6$ ), but $2 \neq = 4$ .

This is the most commonly confused property. It's essential to understand that antisymmetric is not the opposite of symmetric.

Let's return to our reading to clarify this point.

7.2: Properties of Relations

The author of this text gives an excellent explanation of why antisymmetry is not the opposite of symmetry and provides a helpful way to think about it using its contrapositive form.

Read the two "Remark" sections just below the definitions you read earlier. Focus on the explanation of symmetry and antisymmetry, particularly the part that begins with this sentence and ends with the key insight.

As the text highlights, a relation can be:

Symmetric and not antisymmetric (e.g., "is a co-worker of").
Antisymmetric and not symmetric (e.g., $\leq$ ).
Both symmetric and antisymmetric (e.g., the identity relation $R = {(x, x) ∣ x \in A}$ is a great example of this).
Neither symmetric nor antisymmetric (e.g., a relation on ${1, 2, 3}$ given by $R = {(1, 2), (2, 1), (2, 3)}$ . It's not symmetric because $(3, 2)$ is missing. It's not antisymmetric because you have both $(1, 2)$ and $(2, 1)$ .)

4. Transitive: Can you chain relationships together?

A relation $R$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$ , it must also be that $(a, c) \in R$ .

Intuition: If you can get from $a$ to $b$ and from $b$ to $c$ , there must be a "shortcut" directly from $a$ to $c$ .
Canonical Example: The relation $<$ on integers. If $a < b$ and $b < c$ , we can conclude that $a < c$ .
Non-Example: The relation "is a friend of". Alice may be friends with Bob, and Bob may be friends with Charlie, but Alice and Charlie might be complete strangers.

Seeing the Properties in Action

Definitions are essential, but seeing them applied is what builds true understanding. The following video by Kimberly Brehm is an excellent, clear walkthrough of checking these properties for several relations defined on integers.

Discrete Math - 9.1.2 Properties of Relations

Watch how the presenter systematically tests each property for a set of four different relations. She uses a combination of direct reasoning and searching for counterexamples, which is exactly the process you'll need to master.

For reflexivity, watch from the beginning. For symmetry, watch the segment from here. For antisymmetry, a particularly tricky topic, pay close attention to her reasoning from this section. Notice how she handles implications where the premise is false (vacuously true). Finally, watch her analysis of transitivity from here, where finding a single counterexample is enough to disprove the property.

A Systematic Check on a Finite Set

When a relation is given on a small, finite set as an explicit list of pairs, we can check the properties exhaustively. This is a common type of problem and a great way to solidify the definitions. The same video continues with a perfect example of this.

Discrete Math - 9.1.2 Properties of Relations

The presenter now takes a specific relation on the set {1, 2, 3} and checks all four properties, one by one. This demonstrates the methodical process required for this kind of problem.

Please watch the final example in the video, from this point onward. Observe how she has to check every relevant pair to confirm or deny a property.

Visualizing Relations

For relations on finite sets, drawing a directed graph can provide powerful visual intuition. Let the elements of the set be the vertices (nodes) of the graph. Draw a directed edge (an arrow) from $a$ to $b$ if and only if $(a, b) \in R$ .

Types of Relations (Solved Problem)

With this visual model, the properties have clear graphical interpretations:

Reflexive: Every vertex has a loop (an edge pointing to itself).
Symmetric: Every edge between two different vertices is a two-way street; if there's an arrow from $a$ to $b$ , there must be one from $b$ to $a$ .
Antisymmetric: There are no two-way streets between distinct vertices.
Transitive: If there is a path from $a$ to $b$ and then to $c$ , there must be a direct "shortcut" edge from $a$ to $c$ .

The math.libretexts article you read earlier has a great summary of these graphical tests at the end of its "Example $\PageIndex 8$ ". You can refer back to it if you find this visualization helpful.

Practice Problems

Let's test your understanding. For each relation defined on the set of integers $Z$ , determine which of the four properties (reflexive, symmetric, antisymmetric, transitive) it possesses.

Relation $R_{1}$ : $a R_{1} b$ if and only if $a + b = 0$ .
Relation $R_{2}$ : $a R_{2} b$ if and only if $∣ a ∣ = ∣ b ∣$ .
Relation $R_{3}$ : $a R_{3} b$ if and only if $a$ divides $b$ (written $a ∣ b$ ). Assume we are on the set of positive integers $Z^{+}$ for this one.

Check your answers

$a R_{1} b ⟺ a + b = 0$
- Not Reflexive: For it to be reflexive, we'd need $a + a = 0$ for all integers $a$ . This is only true for $a = 0$ . Since it's not true for $a = 1$ , it's not reflexive.
- Symmetric: Yes. If $a + b = 0$ , then by commutativity of addition, $b + a = 0$ .
- Not Antisymmetric: We have $2 R_{1} (- 2)$ and $(- 2) R_{1} 2$ , but $2 \neq = - 2$ . This is a clear counterexample.
- Not Transitive: Consider $1 R_{1} (- 1)$ and $(- 1) R_{1} 1$ . If it were transitive, we would need $1 R_{1} 1$ . But $1 + 1 = 2 \neq = 0$ , so $(1, 1)$ is not in the relation.
$a R_{2} b ⟺ ∣ a ∣ = ∣ b ∣$
- Reflexive: Yes. For any integer $a$ , $∣ a ∣ = ∣ a ∣$ .
- Symmetric: Yes. If $∣ a ∣ = ∣ b ∣$ , then $∣ b ∣ = ∣ a ∣$ .
- Not Antisymmetric: We have $∣2∣ = ∣ - 2∣$ and $∣ - 2∣ = ∣2∣$ , so $2 R_{2} (- 2)$ and $(- 2) R_{2} 2$ . But $2 \neq = - 2$ .
- Transitive: Yes. If $∣ a ∣ = ∣ b ∣$ and $∣ b ∣ = ∣ c ∣$ , then by the transitive property of equality on real numbers, $∣ a ∣ = ∣ c ∣$ .
$a R_{3} b ⟺ a ∣ b$ on $Z^{+}$
- Reflexive: Yes. Any positive integer $a$ divides itself, since $a = 1 \cdot a$ .
- Not Symmetric: $2∣4$ , but $4 ∤ 2$ .
- Antisymmetric: Yes. If $a ∣ b$ and $b ∣ a$ for positive integers, then $a$ must equal $b$ .
- Transitive: Yes. If $a ∣ b$ and $b ∣ c$ , then $b = k a$ and $c = j b$ for some integers $k, j$ . Substituting, we get $c = j (k a) = (j k) a$ , which means $a ∣ c$ .

A Computational Perspective

Given your background in Python, we can make these abstract definitions very concrete by expressing them as code. This forces us to be perfectly precise, just like a computer requires.

Imagine we have a set A and a relation R represented as a set of tuples.

# Our base set
A = {1, 2, 3}

# A relation R on A. Let's use the one from the video.
R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

# --- Function Definitions ---

def is_reflexive(relation, base_set):
    # For EVERY element x in the base_set...
    for x in base_set:
        # ...is the pair (x, x) in the relation?
        if (x, x) not in relation:
            return False
    return True

def is_symmetric(relation, base_set):
    # For EVERY pair (a, b) in the relation...
    for a, b in relation:
        # ...is the pair (b, a) also in the relation?
        if (b, a) not in relation:
            return False
    return True

def is_antisymmetric(relation, base_set):
    # For EVERY pair (a, b) in the relation...
    for a, b in relation:
        # If a and b are different...
        if a != b:
            # ...is the reverse pair (b, a) also present?
            if (b, a) in relation:
                return False # If so, it fails the test.
    return True

def is_transitive(relation, base_set):
    # For EVERY pair (a, b) and (b, c)...
    for a, b1 in relation:
        for b2, c in relation:
            if b1 == b2: # We found a chain a -> b -> c
                # Is the shortcut (a, c) in the relation?
                if (a, c) not in relation:
                    return False
    return True

# --- Testing our relation R ---
print(f"Is R reflexive?       {is_reflexive(R, A)}")
print(f"Is R symmetric?      {is_symmetric(R, A)}")
print(f"Is R antisymmetric?  {is_antisymmetric(R, A)}")
print(f"Is R transitive?     {is_transitive(R, A)}")

# Expected output:
# Is R reflexive?       True
# Is R symmetric?      True
# Is R antisymmetric?  False
# Is R transitive?     True

Notice how each function is a direct translation of the formal definition. The logical quantifiers ("for all", "there exists") and implications ("if...then") in the definitions map directly to loops and conditional statements in the code.

Conclusion

In this lesson, you've learned to analyze and classify relations using the fundamental properties of reflexivity, symmetry, antisymmetry, and transitivity. This is a significant step, moving us from simply describing sets to understanding the rich structures that can be built upon them.

Key Takeaways:

A relation on a set $A$ is a subset of $A \times A$ .
Reflexive: Every element is related to itself. ( $\forall a \in A, (a, a) \in R$ )
Symmetric: If $a$ is related to $b$ , then $b$ must be related to $a$ . ( $(a, b) \in R ⟹ (b, a) \in R$ )
Antisymmetric: The only way $a$ is related to $b$ and $b$ to $a$ is if $a$ and $b$ are the same element. ( $(a, b) \in R \land (b, a) \in R ⟹ a = b$ )
Transitive: If you can get from $a$ to $b$ and from $b$ to $c$ , there must be a direct path from $a$ to $c$ . ( $(a, b) \in R \land (b, c) \in R ⟹ (a, c) \in R$ )

These properties are not just abstract labels. When a relation is reflexive, symmetric, and transitive, it has a special name: an equivalence relation. These are incredibly powerful tools for partitioning sets into disjoint subsets, a concept used everywhere from modular arithmetic in cryptography to classifying objects in data science. In our next lesson, we will explore exactly how to use an equivalence relation to partition a set into its equivalence classes.

Recommended resources