# FA18:Lecture 11 relations

We introduce relations, and describe binary relations. We introduce the properties of an equivalence relation, and discuss closures.

# 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:

Definition: Relation
A relation on sets is a subset of .

You can think of the elements of as 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:

Name Birthdate Social
Alice 01/01/2011 111-11-1111
Bob 02/02/1922 222-22-2222

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

There are many ways that people can be related to each other; and these are all relations. For example, "is-a-sister-of" is a binary relation on the set of people; if is a sister of .

Similarly, you could define an "is-a-friend-of" relation, or a "loves" relation, etc.

## Example: functions are relations

You can think of a function as a special kind of relation: you would say if .

## Example: inequalities are relations

There are different ways to compare different kinds of objects; for example, there are the standard inequalities on numbers (), the set comparisons (), function equality, and so on.

All of these can be thought of as relations. For example, we might think of as a relation; if and only if .

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

You can think of systems of equations as relations as well. For example, the equation is a relation on , and defined by if and only if . So but .

# Binary relations

Most of the relations we will discuss in this course are binary relations: they relate a set with itself.

Definition: Binary relation
A binary relation on a set is a subset of (i.e. a set of pairs of elements of ).

Notation: If is a binary relation on a set , and if and are elements of , then is shorthand for .

For example, we usually write instead of .

Examples:

## Drawing binary relations

Although it is hard to draw diagrams of general relations, we can draw a binary relation the same way we draw functions:

However, because binary relations only relate one set to itself, we can draw them more compactly by only including one copy of .

Here, an arrow from to indicates . This diagram represents the relation on the set .

# Binary relation properties

When defining types of objects, we often want to define a new notion of equality. For example, we have already defined equality for pairs, sets, functions, and cardinalities.

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).

## Reflexivity

Definition: Reflexive

In a picture, this means that every element of has a self-loop: an edge back to itself.

## Symmetry

Definition: Symmetric
A binary relation on a set is symmetric if for all pairs of elements and with , we also have .

In a picture, this means that every edge from to has a corresponding edge from back to .

## Transitivity

Definition: Transitive
A binary relation on a set is transitive if for all elements , , and with and , we also have .

In a picture, this means that every path from to has a corresponding direct edge from to .

## Equivalence relation

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.

We would say that is the reflexive closure of . It is the smallest reflexive binary relation that contains .

In general, to form the P-closure of a relation , you keep adding pairs to until it satisfies P. For example:

• 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 .

If is 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.

# Equivalence classes

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 were a set of people and R was the is-related-to relation, 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.

In general, the groups are referred to as equivalence classes. Formally, we have the following definition:

Definition: Equivalence class
If is an equivalence relation on a set , then the equivalence class of by (written ) is the set of elements with .

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.

Definition: A/R
If is an equivalence relation on a set , then A mod R (written ) is the set of all equivalence classes of by . In other words, .

Continuing the above example, we have . Note that is also in , but we don't need to list it separately, since it is equal to .

One more piece of terminology:

Definition: representative
If is an equivalence class of by , and , we say that is a representative of if . Note that is a representative of .