Section 5.4 Properties
A relation on \(A\) may satisfy certain properties:
- Reflexive: \(aRa \: \forall a \in A\)
- Symmetric: \(\text{If } aRb \text{ then } bRa \: \forall a, b \in A\)
- Antisymmetric: \(\text{If } aRb \text{ and } bRa \text{ then } a = b \: \forall a, b \in A\)
- Transitive: \(\text{If } aRb \text{ and } bRc \text{ then } aRc \: \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.Subsection 5.4.1 Reflexive
A relation \(R\) is reflexive if \(a\) relates to \(a\) for all elements \(a\) in the set \(A\text{.}\) This means all the elements relate to themselves.
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\text{.}\) This will return
True if the relation is reflexive and False otherwise.If we are working with
DiGraphs, we can use the method has_edge to check if the graph has a loop for each vertex.Subsection 5.4.2 Symmetric
A relation is symmetric if \(a\) relates to \(b\text{,}\) then \(b\) relates to \(a\text{.}\)
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.Subsection 5.4.3 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.
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\text{.}\) Observe that while the standard antisymmetric property forbids the edges to be bidirectional, the Sage antisymmetric property forbids cycles.Let’s define a function to check for the standard definition of antisymmetry in a
DiGraph.Subsection 5.4.4 Transitive
A relation is transitive if \(a\) relates to \(b\) and \(b\) relates to \(c\text{,}\) then \(a\) relates to \(c\text{.}\)
Let’s define a function to check for the transitive property in a
Set: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\text{.}\) Alternatively, we can use built-in Sage
DiGraph methods.
