This notebook uses Python to generate a list of relations and check their properties (reflexive, symmetric, antisymmetric, transitive, and equivalence). Defintions and examples are taken from lecture 15 and 16 of a discrete math course taught by Professor Maltais at the University of Ottawa during the 2017 winter semester.
by Ben Pyrik, 2017/04/17
A function is an assignment of elements from one set (the domain) to another set (the codomain) where every element of the domain is assigned only a single element from the codomain. In other words, every pre-image has one (and only one) image. Relations are similar, but looser in the sense that pre-images can have multiple images. If $1$ is an element of A, it can be related to $5$ and $6$. This kind of assignment is not possible with a function.
A binary relation between two sets (A and B) is defined as "a subset of A x B" (i.e. the "Cartesian product" of A and B). Similarly, a relation between a set (A) and itself is defined as a subset of A x A. What does this mean?
Note: I'm going to use lists instead of sets here due to complications with powerset.
A = [1, 2]
# for simplicity, make B = A
B = [1, 2]
# Applying definition of the Cartesian Product
AB = [(a, b) for a in A for b in B]
AB
[(1, 1), (1, 2), (2, 1), (2, 2)]
Though it may be tempting, the above is not the set of all possible relations between A and B. Rather, it is the superset of any relation between A and B--in other words, any relation between A and B will be a subset of this set.
However, the powerset of AB is the set of all possible relations between A and B.
# http://sevko.io/articles/power-set-algorithms/#tocAnchor-1-9
def is_bit_flipped(num, bit):
return (num >> bit) & 1
def powerset(set_):
subsets = []
for subset in range(2 ** len(set_)):
new_subset = []
for bit in range(len(set_)):
if is_bit_flipped(subset, bit):
new_subset.append(set_[bit])
subsets.append(new_subset)
return subsets
pAB = powerset(AB)
# order sets from smallest to largest
pAB = sorted(pAB, key=len)
pAB
[[], [(1, 1)], [(1, 2)], [(2, 1)], [(2, 2)], [(1, 1), (1, 2)], [(1, 1), (2, 1)], [(1, 2), (2, 1)], [(1, 1), (2, 2)], [(1, 2), (2, 2)], [(2, 1), (2, 2)], [(1, 1), (1, 2), (2, 1)], [(1, 1), (1, 2), (2, 2)], [(1, 1), (2, 1), (2, 2)], [(1, 2), (2, 1), (2, 2)], [(1, 1), (1, 2), (2, 1), (2, 2)]]
pAB contains all possible subsets of A x B (and equivalently) all possible relations between A and B. Some are functions (e.g. #6), but most are not.
How many relations are there? You could count them, but I'll save you the trouble.
len(pAB)
16
There are 16 relations between the set $A$ and itself.
Another way of determining this number is to use the formula
$$ \begin{align} |P(A \times B)| &= 2^{|A \times B|} \\ &= 2^{|A| |B|} \\ &= 2^{|2| |2|} & \text{Substituting the cardinalities of A and B} \\ &= 2^{4} \\ &= 16 \end{align} $$# function that determines if a relation (r) on a set (A) is reflexive (or not)
def reflexive(r, A):
'''(list, list) -> boolean'''
for u in A:
# look for (u, u), return False if it wasn't found
try:
r.index((u, u))
except ValueError:
return False
# loop completed without error, thus the relation must be reflexive
return True
# testing
reflexive([(1, 1)], A)
False
reflexive([(1, 1), (2, 2)], A)
True
For all possible relations on the set $A$, which are reflexive?
for relation in pAB:
if (reflexive(relation, A)):
print(str(relation) + " is reflexive!" +"\n")
else:
print(str(relation) + " is NOT reflexive." +"\n")
[] is NOT reflexive. [(1, 1)] is NOT reflexive. [(1, 2)] is NOT reflexive. [(2, 1)] is NOT reflexive. [(2, 2)] is NOT reflexive. [(1, 1), (1, 2)] is NOT reflexive. [(1, 1), (2, 1)] is NOT reflexive. [(1, 2), (2, 1)] is NOT reflexive. [(1, 1), (2, 2)] is reflexive! [(1, 2), (2, 2)] is NOT reflexive. [(2, 1), (2, 2)] is NOT reflexive. [(1, 1), (1, 2), (2, 1)] is NOT reflexive. [(1, 1), (1, 2), (2, 2)] is reflexive! [(1, 1), (2, 1), (2, 2)] is reflexive! [(1, 2), (2, 1), (2, 2)] is NOT reflexive. [(1, 1), (1, 2), (2, 1), (2, 2)] is reflexive!
A relation $R$ on a set $A$ is called symmetric if
$$\forall \ u,v \in A \ \ \left((u, v) \in R \right) \rightarrow \left((v, u) \in R \right) \text{is true.}$$While the symmetric definition could be implemented exactly as described, there is actually no reason to test $(u, v)$ pairs that are not in a particular relation. If a pair is not in the relation, then the left side of the implication is false and the implication is vacuously true (because false $\rightarrow$ anything is always true). Of course, if $(v, u)$ happens to be in the relation, $(u, v)$ will be sought (and not found) causing symmetric(r)
to return false.
def symmetric(r):
'''(list) -> boolean'''
# for every pair (u, v) in the relation
for pair in r:
# search for (v, u) <- order switched!
try:
r.index((pair[1], pair[0]))
except ValueError:
return False
# if loop completes without error, every pair in the relation has a symmetric counterpart (r is symmetric!)
return True
# test
symmetric([(1, 2), (2, 1), (2, 2)])
True
symmetric([(1, 2), (2, 2)])
False
For all possible relations on the set $A$, which are symmetric?
for relation in pAB:
if (symmetric(relation)):
print(str(relation) + " is symmetric!" +"\n")
else:
print(str(relation) + " is NOT symmetric." +"\n")
[] is symmetric! [(1, 1)] is symmetric! [(1, 2)] is NOT symmetric. [(2, 1)] is NOT symmetric. [(2, 2)] is symmetric! [(1, 1), (1, 2)] is NOT symmetric. [(1, 1), (2, 1)] is NOT symmetric. [(1, 2), (2, 1)] is symmetric! [(1, 1), (2, 2)] is symmetric! [(1, 2), (2, 2)] is NOT symmetric. [(2, 1), (2, 2)] is NOT symmetric. [(1, 1), (1, 2), (2, 1)] is symmetric! [(1, 1), (1, 2), (2, 2)] is NOT symmetric. [(1, 1), (2, 1), (2, 2)] is NOT symmetric. [(1, 2), (2, 1), (2, 2)] is symmetric! [(1, 1), (1, 2), (2, 1), (2, 2)] is symmetric!
A relation $R$ on a set $A$ is called antisymmetric if
$$\forall u, v \in A \ \left((u, v) \in R \ \text{and} \ (v, u) \in R \right) \rightarrow (u = v) \ \text{is true.}$$Equivalently (in its contrapositive form)
$$ (u \ne v) \rightarrow \left( (u,v) \notin R \ \text{or} \ (v,u) \notin R \right)$$For this property (and possibly subsequent properties), I will use a helper function that searches a relation for a particular pair returning True
if found and False
otherwise. This should be easier to read than copy and pasting try/except blocks everywhere.
# helper that searches a relation (r) for a pair (u ,v)
def rsearch(r, pair):
'''(list, tuple) -> boolean'''
try:
r.index(pair)
except ValueError:
# not found
return False
# found
return True
As with symmetric, rather than implement the definition (which requires assigning variables to elements in $A$) I've elected to only test pairs that are in the relation. Also, I worked from the contrapositive definition because it felt easier to code.
def antisymmetric(r):
'''(list) -> boolean'''
# for every pair (u, v) in the relation
for pair in r:
u = pair[0]
v = pair[1]
# only test pairs with unique elements
if (u != v):
# relation can contain (u, v) or (v, u), but it CANNOT contain both
if (rsearch(r, (u, v)) and rsearch(r, (v, u))):
return False
# if loop completes without returning, then the relation is antisymmetric
return True
# test
antisymmetric([(1, 1), (1, 2), (2, 2)]) # Though the relation contains (1, 2), it does not contain (2, 1)
True
antisymmetric([(1, 1), (1, 2), (2, 1)]) # It contains both (1, 2) AND (2, 1) so it must be...
False
For all possible relations on the set $A$, which are antisymmetric?
for relation in pAB:
if (antisymmetric(relation)):
print(str(relation) + " is antisymmetric!" +"\n")
else:
print(str(relation) + " is NOT antisymmetric." +"\n")
[] is antisymmetric! [(1, 1)] is antisymmetric! [(1, 2)] is antisymmetric! [(2, 1)] is antisymmetric! [(2, 2)] is antisymmetric! [(1, 1), (1, 2)] is antisymmetric! [(1, 1), (2, 1)] is antisymmetric! [(1, 2), (2, 1)] is NOT antisymmetric. [(1, 1), (2, 2)] is antisymmetric! [(1, 2), (2, 2)] is antisymmetric! [(2, 1), (2, 2)] is antisymmetric! [(1, 1), (1, 2), (2, 1)] is NOT antisymmetric. [(1, 1), (1, 2), (2, 2)] is antisymmetric! [(1, 1), (2, 1), (2, 2)] is antisymmetric! [(1, 2), (2, 1), (2, 2)] is NOT antisymmetric. [(1, 1), (1, 2), (2, 1), (2, 2)] is NOT antisymmetric.
A relation $R$ on a set $A$ is called an transitive if
$$ \forall u,v,w \in A \ \left( (u, v) \in R \ \text{and} \ (v,w) \in R \right) \rightarrow \left( (u,w) \in R \right) \ \text{is true.} $$I followed the definition exactly for this one, the implementation (with 3 loops!) is costly--$O(n^3)$.
def transitive(r, A):
'''(list, list) -> boolean'''
for u in A:
for v in A:
for w in A:
if (rsearch(r, (u, v)) and rsearch(r, (v, w))):
# (u, w) must be in the relation
if (not rsearch(r, (u, w))):
return False
# loop completed without returning, so the relation is transitive
return True
# test
transitive([(1, 2), (2, 3), (1, 3)], A)
True
transitive([(1, 2), (2, 1), (2, 2)], A) # 1 -> 2 and 2 -> 1, but 1 -> 1 is missing!
False
Can I do better? Spoiler: not really.
def transitive2(r):
# for every pair (u, v)
for pair in r:
# take u and v
u = pair[0]
v = pair[1]
# iterate through the relation looking for a pair with a first element = v
for v_pair in r:
if (v_pair[0] == v):
# take second element from that pair (v, x)
x = v_pair[1]
# iterate through the relation again, looking for the pair (u, x)
if (not rsearch(r, (u, x))):
# if the pair is not found, the relation cannot be transitive
return False
# if function hasn't returned, the relation must be transitive
return True
# the same tests
transitive2([(1, 2), (2, 3), (1, 3)])
True
transitive2([(1, 2), (2, 1), (2, 2)])
False
It is possible that transitive2()
is more efficient than transitive()
, but it is hard to tell and the logic is definitely more convoluted.
For all possible relations on the set $A$, which are transitive?
for relation in pAB:
if (transitive(relation, A)):
print(str(relation) + " is transitive!" +"\n")
else:
print(str(relation) + " is NOT transitive." +"\n")
[] is transitive! [(1, 1)] is transitive! [(1, 2)] is transitive! [(2, 1)] is transitive! [(2, 2)] is transitive! [(1, 1), (1, 2)] is transitive! [(1, 1), (2, 1)] is transitive! [(1, 2), (2, 1)] is NOT transitive. [(1, 1), (2, 2)] is transitive! [(1, 2), (2, 2)] is transitive! [(2, 1), (2, 2)] is transitive! [(1, 1), (1, 2), (2, 1)] is NOT transitive. [(1, 1), (1, 2), (2, 2)] is transitive! [(1, 1), (2, 1), (2, 2)] is transitive! [(1, 2), (2, 1), (2, 2)] is NOT transitive. [(1, 1), (1, 2), (2, 1), (2, 2)] is transitive!
A relation $R$ on a set $A$ is called an equivalence relation if R is reflexive, symmetric, and transitive.
def equivalence(r, A):
'''(list) -> boolean'''
if (reflexive(r, A) and symmetric(r) and transitive(r, A)):
return True
else:
return False
equivalence([(1, 1), (2, 2)], A)
True
equivalence([(1, 1)], A)
False
From a performance standpoint, this one is super expensive!
For all possible relations on the set $A$, which are equivalence relations?
for relation in pAB:
if (equivalence(relation, A)):
print(str(relation) + " is an equivalence relation!" +"\n")
else:
print(str(relation) + " is NOT an equivalence relation." +"\n")
[] is NOT an equivalence relation. [(1, 1)] is NOT an equivalence relation. [(1, 2)] is NOT an equivalence relation. [(2, 1)] is NOT an equivalence relation. [(2, 2)] is NOT an equivalence relation. [(1, 1), (1, 2)] is NOT an equivalence relation. [(1, 1), (2, 1)] is NOT an equivalence relation. [(1, 2), (2, 1)] is NOT an equivalence relation. [(1, 1), (2, 2)] is an equivalence relation! [(1, 2), (2, 2)] is NOT an equivalence relation. [(2, 1), (2, 2)] is NOT an equivalence relation. [(1, 1), (1, 2), (2, 1)] is NOT an equivalence relation. [(1, 1), (1, 2), (2, 2)] is NOT an equivalence relation. [(1, 1), (2, 1), (2, 2)] is NOT an equivalence relation. [(1, 2), (2, 1), (2, 2)] is NOT an equivalence relation. [(1, 1), (1, 2), (2, 1), (2, 2)] is an equivalence relation!
This turned out to be a good exercise. I think I have a better understanding of these properties and how to "prove" they are held by an arbitrary relation.
For me, the most interesting discovery was that every property except reflexive can be determined by looking exclusively at the relation itself. This was not obvious from reading the definitions, but it is something you learn when doing these by hand during an exam. For example, to determine if {(1, 2), (2, 1), (2, 2)}
is symmetric, the steps I find myself taking are:
In a way, the formal definition for symmetry is misleading.
$$\forall \ u,v \in A \ \ \left((u, v) \in R \right) \rightarrow \left((v, u) \in R \right) \text{is true.}$$I see "for all u, v in A" and think "for all possible pairs in the set $A \times A$...oh no, I have to generate a Cartesian Product". But really, this is never necessary. While the reflexive property does require looking at the actual set, each element is considered independently (so the Cartesian Product is not needed).
If it was up to me, I'd define symmetry like this
$$ \begin{align} & \text{Let: u, v} \in A \\ & \forall \ (u,v) \in R \ \ \left((u, v) \in R \right) \rightarrow \left((v, u) \in R \right) \text{is true.} \end{align} $$Which says: "for all ordered pairs in the relation, this implication must be true in order for the relation to be symmetric".
To finish this I should really identify the relations that are functions as well as their types (injective, subjective, bijective), but I think I'll save that for another notebook.