Relations
Relations are a structure on a set that pairs any two objects that satisfy certain properties. Examples of familiar relations in this context are 7 is greater than 5, Alice is married to Bob, and 3 matches 2 . For each of these statements, the elements of a set are related by a statement.
A function is a special kind of relation and derives its meaning from the language of relations.
Contents
Definition
A (binary) relation between two sets and is a subset of the Cartesian product
One way to think about this definition is to think of it as that the ordered pairs correspond to the edges in a graph which links the related things.
This graph could be pictured as a relation between the set and the set .
Every member of a set is related to every member of the other set. So, in roster form, our relation is
Notice that something like is not a part of the relation since we defined the relation to be from to
Also, there is no problem with an edge connecting itself, since it is always possible that an object is related to itself. Consider the following:
This definition is also very useful when describing entities in the Cartesian plane, i.e. relations on
Note: When we have a definition from a set to the same set, we say that the relation is on that set.
The circle above is an illustration of the relation
Finally, we add a logician/computer scientist's definition of a relation.
A relation is a predicate with (at least) two arguments of arbitrary types and
While the set-theoretic definition and the logician's definition differ at an abstract level, they practically mean the same.
The same relation which describes the circle could also be interpreted as the following Haskell predicate:
1 2r :: (Num a, Eq a) => a -> a -> Bool r x y = x^2 + y^2 == 4^2
The usage of is more popular to denote a relation. Very often, we will say things like to mean that is related to , or according to the set-theoretic definition, belong to
So far, we have only talked about relations between two objects. Such relations are called binary relations. As you can see, it is not difficult to extend the notion of a relation to an -ary relation, where there are n
objects involved. However, we will mostly restrict the discussion of relations to binary relations, unless otherwise specified.
An ideal gas follows the ternary relation
This could be pictured as the following subset of the space:
Symmetry, Reflexivity, and Transitivity
Symmetry, reflexivity, and transitivity are some interesting properties that are possessed by relations defined on elements of the same set.
Symmetry
A relation on is said to be symmetric, if
"is married to" is a symmetric relation. Alice is married to Bob implies Bob is married to Alice.
"is older than" isn't symmetric. If Alice is older than Bob, Bob isn't older than Alice.
In fact, this relation is anti-symmetric, meaning that
Reflexivity
A relation on is reflexive if
Equality is a reflexive relation. Everything is equal to itself.
Coprimeness is not reflexive. 1 is coprime to itself. But other integers are not.
Transitivity
A relation on is transitive if
Divisiblity is transitive. If and , then .
If friendship was transitive, you wouldn't have the concept of a mutual friend on Facebook.
Alice and Bob are friends. Also, Bob and Carol are friends. But Alice and Carol might not necessarily be friends.
Can you think of relations which are symmetric but not transitive, transitive but not symmetric, symmetric but not reflexive, reflexive and transitive but not symmetric, and so on?
Inverse Relation
Let be a binary relation.
The inverse relation is defined as
Let be the relation "smaller than" on the real number set, i.e.
Then is the relation "greater than".
This is because .
is also called the dual ordering of .
Let be a function.
Then is the inverse function of .
This notation is consistent with the inverse function notation .
Equivalence Relations
Equivalence relations are those relations which are reflexive, symmetric, and transitive at the same time.
Parallelness is an equivalence relation.
- Symmetry: If , then
- Reflexivity: All lines are parallel to itself.
- Transitivity: If and , then
Other equivalence relations include the following:
- modular congruence
- equality
- being in the same room
- congruence of triangles.
We define the concept of an equivalence class as follows:
The equivalence class of an element under the equivalence relation denoted by is
The two triangles on the left are congruent and in the same equivalence class. The other two triangles form two other distinct equivalence classes.
This is what makes the equivalence classes a useful idea:
Any equivalence on a set partitions into equivalence classes, and conversely, corresponding to any partition of , there is an equivalence relation on
By partition, we mean breaking up the set into disjoint subsets whose union is the set itself.
Consider the equivalence classes formed by the relation on
- Since by reflexivity , the union of all the equivalence classes are
- They are disjoint because if and then by definition, and by symmetry, . Also, by definition. But then by transitivity, so . Every is also in again by transitivity. This means that . Swapping and , proceeding in the same way, we conclude .
Conversely, given any partitioning scheme, we could define as if and only if and belong to the same set.
- Reflexivity: All elements belong to the set in which they belong. So,
- Symmetry: since what this means is that and are essentially in the same set.
- Transitivity: , since once again are all in the same set.
Orderings
See order theory
Orderings are different from equivalences in that they are (mostly) antisymmetric.
Partial Ordering
A (non-strict) partial order is a relation defined on a set which satisfies the following :
- Reflexivity:
- Antisymmetry:
- Transitivity:
Here, we say non-strict, since we allow reflexivity.
A set equipped with a partial ordering is called a partially-ordered set or a poset.
Divisibility of positive integers forms posets. This is a Hasse diagram, a representation for posets. If you choose any walk on this graph, each number is divisible by the number before it.
Notice that not all pairs of elements are related, though. This is why we say the ordering is partial.
A different example would be the vertices of a directed acyclic graph ordered by reachability.
To illustrate, and
Total Order
We define the notion of totality of a relation as follows:
A relation defined on a set is total if , either or
A total order is simply a partial order which also satisfies totality.
- The set of words in a dictionary equipped with a lexicographic ordering
- equipped with
- People standing in a queue, equipped with their position in the queue
How many total orderings of a set consisting of elements are there?
Relations are a structure on a set that pairs any two objects that satisfy certain properties. Examples of familiar relations in this context are 7 is greater than 5, Alice is married to Bob, and 3 matches 2 . For each of these statements, the elements of a set are related by a statement.
Functions as Relations
A special case of relations are functions.
A function from to , denoted
is a relation between to such that for every element (called pre-image), there exists exactly one (called image) which is related to .
and are called the domain and co-domain of respectively.
When we say , we mean . A metaphorical description of a function could be a black-box or a machine that takes in an input and returns a corresponding output.
Not all relations are functions.
For example, the relation
is not a function since there are multiple values of possible for each .
The definition of a function requires us to have exactly one image for each pre-image.
This is why the inverse of a function is not necessarily a function. For example, the inverse of is not a function.
When a student is first introduced to the notion of a function, he tends to believe that a function is an algorithm being run upon the image. However, this is not so. There is no constraint of computability imposed on the notion of a function.
They are just arbitrary mappings. It is perfectly possible that a function is non-computable. Popular examples include a function which could tell if a program halts (halting problem) or the minimum length of a program that outputs a given string (Kolmogorov complexity).