FA18:Lecture 11 relations
- 1 Relations in general
- 2 Binary relations
- 3 Binary relation properties
- 4 Closure of a relation
- 5 Equivalence classes
Relations in general
Relations are a very general concept; they model relationships between objects. You can think of a relation as a table (potentially with multiple columns). Formally, we have the following definition:
You can think of the elements ofas the rows of a table.
For example, we could think of a table of blood donors containing names, birth dates, and social security numbers as a relation on the set Name of names, the set Date of dates, and the set SSN of social security numbers. We would represent this table:
As the relation .
Thinking of tables as relations is central to the design of certain kinds of databases (so-called relational databases). Operations like "filter out the millenials", "hide the social security number", and "add a hair color column by looking up the name in a second table" are all functions whose domains and codomains are sets of relations.
Example: family relationships
Similarly, you could define an "is-a-friend-of" relation, or a "loves" relation, etc.
Example: functions are relations
Example: inequalities are relations
As you can see, writing out relations this way can be confusing, but it is good to know that these operations are examples of relations.
Example: equations are relations
For example, we usually writeinstead of .
- Inequalities (like ) are binary relations on the set of numbers.
- Similarly binary relations on the set of sets and are
- Family relationships are often binary relations
Drawing binary relations
Binary relation properties
Whenever you redefine a familiar definition or operation, it is important not to change the fundamental properties that peoBold textple expect of that operation: people should still be able to reason about your operator the way they always have.
The properties that people expect "equals" to have are defined below; relations that satisfy all three are called equivalence relations. You should always check these properties if you ever define something called "equals" (for example, when overriding the `.equals()` method in Java or the `__eq__` method in Python).
In a picture, this means that every element of has a self-loop: an edge back to itself.
In a picture, this means that every edge from to has a corresponding edge from back to .
In a picture, this means that every path from to has a corresponding direct edge from to .
Reflexivity lets you plug in definitions to show that things are equal (for example, it lets you conclude that ). Symmetry lets you use equality in both directions (e.g. since x = y, we know that "... = y = x = ..."). Transitivity lets you chain together statements. (For example, we often write things like " , so ").
Closure of a relation
It is occasionally useful to extend a not-nice object to make it nice. For example, you might define an "is-sibling-of" relation ( ), and decide that you don't want to say that you are your own sibling. This would make non-reflexive, but it's very similar to the reflexive version where you do consider people to be their own siblings.
- To form the reflexive closure of a relation , you add in the pairs for all
- To form the symmetric closure of a relation , you add in the edge for every edge
- To form the transitive closure of a relation , you add in edges from to if you can find a path from to .
Ifis the following relation:
then the reflexive closure of is given by:
the symmetric closure of is given by:
the transitive closure of is given by:
and the equivalence relation closure of is given by:
Closure is a general idea in mathematics. For example, the set of complex numbers is called the "algebraic closure" of , because you form it by starting with and then throwing in solutions to all polynomial equations.
Consider the following equivalence relation on the set :
Notice that the elements of are split up into three groups, with everything in one group related to everything else in the same group, and nothing in one group related to anything in any other group.
In this example, the three groups are, and .
In fact, this is a general phenomenon, and the groups often represent something important. For example, if , then the groups of related people would be called "families". Two people are in the same family if and only if they are related to each other. were a set of people and R was the is-related-to relation
In general, the groups are referred to as equivalence classes. Formally, we have the following definition:
In other words,
Note: I usually use the symbols [ and ] instead of ⟦ and ⟧, but the wiki syntax makes this difficult. You may use either notation.When is clear from context, we just write ⟦a⟧.
In the above example, we have three equivalence classes: , , and .
You can see in this example that ⟦a⟧=⟦b⟧ if and only if aRb; this is always the case.
One more piece of terminology: