5.3: Properties

A relation on A may satisfy certain properties:

• Reflexive: \(a R a \forall a \in A\)
• Symmetric: If \(a R b\) then \(b R a \forall a, b \in A\)
• Antisymmetric: If \(a R b\) and \(b R a\) then \(a=b \forall a, b \in A\)
• Transitive: If \(a R b\) and \(b R c\) then \(a R c \forall a, b, c \in A\)

So far, we have learned about some of the built-in Sage methods that come out of the box, ready for us to use. Sometimes, we may need to define custom functions to meet specific requirements or check for particular properties. We define custom functions with the def keyword. If you want to reuse the custom functions defined in this book, copy and paste the function definitions into your own Sage worksheet and then call the function to use it.

Reflexive

A relation \(R\) is reflexive if \(a\) relates to \(a\) for all elements \(a\) in the set \(A\). This means all the elements relate to themselves.

A = Set([1, 2, 3])
R = Set([(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)])
show(R)

$$/*<![CDATA[*/\newcommand{\Bold}[1]{\mathbf{#1}}\left\{\left(2, 3\right), \left(1, 2\right), \left(3, 3\right), \left(2, 2\right), \left(1, 1\right)\right\}/*]]>*/$$

Let’s define a function to check if the relation \(R\) on set \(A\) is reflexive. We will create a set of (\(a,a\)) pairs for each element \(a\) in \(A\) and check if this set is a subset of \(R\). This will return True if the relation is reflexive and False otherwise.

def is_reflexive_set(A, R):
    reflexive_pairs = Set([(a, a) for a in A])
    return reflexive_pairs.issubset(R)

is_reflexive_set(A, R)

True

If we are working with DiGraphs, we can use the method has_edge to check if the graph has a loop for each vertex.

def is_reflexive_digraph(A, G):
    return all(G.has_edge(a, a) for a in A)

A = [1, 2, 3]
R = [(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)]

G = DiGraph(R, loops=True)

is_reflexive_digraph(A, G)

True

Symmetric

A relation is symmetric if \(a\) relates to \(b\) then \(b\) relates to \(a\).

def is_symmetric_set(relation_R):
    inverse_R = Set([(b, a) for (a, b) in relation_R])
    return relation_R == inverse_R

A = Set([1, 2, 3])

R = Set([(1, 2), (2, 1), (3, 3)])

is_symmetric_set(R)

True

We can check if a DiGraph is symmetric by comparing the edges of the graph with the reverse edges. In our definition of symmetry, we are only interested in the relation of nodes, so we set edge labels=False.

def is_symmetric_digraph(digraph):
    return digraph.edges(labels=False) == digraph.reverse().edges(labels=False)

relation_R = [(1, 2), (2, 1), (3, 3)]

G = DiGraph(relation_R, loops=true)

is_symmetric_digraph(G)

True

Antisymmetric

When a relation is antisymmetric, the only case that \(a\) relates to \(b\) and \(b\) relates to \(a\) is when \(a\) and \(b\) are equal.

def is_antisymmetric_set(relation):
    for a, b in relation:
        if (b, a) in relation and a != b:
            return False
    return True

relation = Set([(1, 2), (2, 3), (3, 4), (4, 1)])

is_antisymmetric_set(relation)

True

While Sage offers a built-in antisymmetric() method for Graphs, it checks for a more restricted property than the standard definition of antisymmetry. Specifically, it checks if the existence of a path from a vertex \(x\) to a vertex \(y\) implies that there is no path from \(y\) to \(x\) unless \(x=y\). Observe that while the standard antisymmetric property forbids the edges to be bidirectional, the Sage antisymmetric property forbids cycles.

# Example with the more restricted
# Sage built-in antisymmetric method
# Warning: returns False

relation = [(1, 2), (2, 3), (3, 4), (4, 1)]

DiGraph(relation).antisymmetric()

False

Let’s define a function to check for the standard definition of antisymmetry in a DiGraph.

def is_antisymmetric_digraph(digraph):
    for edge in digraph.edges(labels=False):
        a, b = edge
        # Check if there is an edge in both directions (a to b and b to a) and a is not equal to b
        if digraph.has_edge(b, a) and a != b:
            return False
    return True

relation = DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)])

is_antisymmetric_digraph(relation)

True

Transitive

A relation is transitive if \(a\) relates to \(b\) and \(b\) relates to \(c\), then \(a\) relates to \(c\).

Let’s define a function to check for the transitive property in a Set:

def is_transitive_set(A, R):
    for a in A:
        for b in A:
            if (a, b) in R:
                for c in A:
                    if (b, c) in R and not (a, c) in R:
                        return False
    return True

A = Set([1, 2, 3])

R = Set([(1, 2), (2, 3), (1, 3)])

is_transitive_set(A, R)

True

You may be tempted to write a function with a nested loop because the logic is easy to follow. However, when working with larger sets, the time complexity of the function will not be efficient. This is because we are iterating through the set \(A\) three times. We can improve the time complexity by using a dictionary to store the relation \(R\). Alternatively, we can use built-in Sage DiGraph methods.

D = DiGraph([(1, 2), (2, 3), (1, 3)], loops=True)

D.is_transitive()

True