FA18:Lecture 11 relations

From CS2800 wiki

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 [math]R [/math] on sets [math]A_1, A_2, \dots, A_n [/math] is a subset of [math]A_1 \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A_2 \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \cdots \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A_n [/math].

You can think of the elements of [math]R [/math] 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 [math]R := \{\href{/cs2800/wiki/index.php/Pair}{(Alice, 01/01/2011, 111-11-1111)}, \href{/cs2800/wiki/index.php/Pair}{(Bob, 02/02/1922, 222-22-2222)}\} [/math].

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; [math](a, b) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} is-a-sister-of [/math] if [math]a [/math] is a sister of [math]b [/math].

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 [math]f [/math] as a special kind of relation: you would say [math]\href{/cs2800/wiki/index.php/Pair}{(x,y)} \href{/cs2800/wiki/index.php/%5Cin}{\in} f [/math] if [math]f(x) = y [/math].

Example: inequalities are relations

There are different ways to compare different kinds of objects; for example, there are the standard inequalities on numbers ([math]\gt, \lt, ≥, ≤, = [/math]), the set comparisons ([math]\href{/cs2800/wiki/index.php/Equality_(sets)}{=}, \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆}, \href{/cs2800/wiki/index.php/%E2%8A%87}{⊇} [/math]), function equality, and so on.

All of these can be thought of as relations. For example, we might think of as a relation; [math](X,Y) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} "\href{/cs2800/wiki/index.php/%E2%8A%86}{⊆}" [/math] if and only if [math]X \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} Y [/math].

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 [math]x + y = z [/math] is a relation [math]R [/math] on [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] defined by [math](x,y,z) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} R [/math] if and only if [math]x + y = z [/math]. So [math](1,2,3) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} R [/math] but [math](1,2,5) \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} R [/math].

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 [math]R [/math] on a set [math]A [/math] is a subset of [math]A \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A [/math] (i.e. a set of pairs of elements of [math]A [/math]).

Notation: If [math]R [/math] is a binary relation on a set [math]A [/math], and if [math]x [/math] and [math]y [/math] are elements of [math]A [/math], then [math]xRy [/math] is shorthand for [math](x,y) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} R [/math].

For example, we usually write [math]x ≤ y [/math] instead of [math](x,y) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ≤ [/math].


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 [math]A [/math] to itself, we can draw them more compactly by only including one copy of [math]A [/math].


Here, an arrow from [math]x [/math] to [math]y [/math] indicates [math]x R y [/math]. This diagram represents the relation [math]R := \{(a,b), (b,c), (c,c), (d,e), (e,e), (e,d)\} [/math] on the set [math]A := \{a,b,c,d,e,f\} [/math].

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


Definition: Reflexive
A binary relation [math]R [/math] on a set [math]A [/math] is reflexive if for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]\href{/cs2800/wiki/index.php/XRy}{xRx} [/math].

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


Definition: Symmetric
A binary relation [math]R [/math] on a set [math]A [/math] is symmetric if for all pairs of elements [math]x [/math] and [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{yRx} [/math].

In a picture, this means that every edge from [math]x [/math] to [math]y [/math] has a corresponding edge from [math]y [/math] back to [math]x [/math].


Definition: Transitive
A binary relation [math]R [/math] on a set [math]A [/math] is transitive if for all elements [math]x [/math], [math]y [/math], and [math]z \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math] and [math]\href{/cs2800/wiki/index.php/XRy}{yRz} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{xRz} [/math].

In a picture, this means that every path from [math]x [/math] to [math]y [/math] has a corresponding direct edge from [math]x [/math] to [math]y [/math].

Equivalence relation

A binary relation [math]R [/math] is an equivalence relation if [math]R [/math] is reflexive, symmetric, and transitive.

Reflexivity lets you plug in definitions to show that things are equal (for example, it lets you conclude that [math]2^2 = 4 [/math]). 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 "[math]x_1 = x_2 = x_3 = x_4 [/math], so [math]x_1 = x_4 [/math]").

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 ([math]S [/math]), and decide that you don't want to say that you are your own sibling. This would make [math]S [/math] non-reflexive, but it's very similar to the reflexive version [math]S' [/math] where you do consider people to be their own siblings.

We would say that [math]S' [/math] is the reflexive closure of [math]S [/math]. It is the smallest reflexive binary relation that contains [math]S [/math].

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

  • To form the reflexive closure of a relation [math]R [/math], you add in the pairs [math]\href{/cs2800/wiki/index.php/Pair}{(x,x)} [/math] for all [math]x [/math]
  • To form the symmetric closure of a relation [math]R [/math], you add in the edge [math]\href{/cs2800/wiki/index.php/Pair}{(y,x)} [/math] for every edge [math]\href{/cs2800/wiki/index.php/Pair}{(x,y)} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} R [/math]
  • To form the transitive closure of a relation [math]R [/math], you add in edges from [math]x [/math] to [math]z [/math] if you can find a path from [math]x [/math] to [math]z [/math].

If [math]R [/math] is the following relation:


then the reflexive closure of [math]R [/math] is given by:


the symmetric closure of [math]R [/math] is given by:


the transitive closure of [math]R [/math] is given by:


and the equivalence relation closure of [math]R [/math] is given by:


Closure is a general idea in mathematics. For example, the set of complex numbers is called the "algebraic closure" of [math]ℝ [/math], because you form it by starting with [math]ℝ [/math] and then throwing in solutions to all polynomial equations.

Equivalence classes

Consider the following equivalence relation [math]R [/math] on the set [math]A := \{a,b,c,d,e,f\} [/math]:


Notice that the elements of [math]A [/math] 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 [math]\{a,b,c\} [/math], [math]\{d,e\} [/math] and [math]\{f\} [/math].

In fact, this is a general phenomenon, and the groups often represent something important. For example, if [math]A [/math] 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 [math]R [/math] is an equivalence relation on a set [math]A [/math], then the equivalence class of [math]a [/math] by [math]R [/math] (written [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} [/math]) is the set of elements [math]b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/ARb}{aRb} [/math].

In other words, [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} \href{/cs2800/wiki/index.php/Definition}{:=} \{b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php/ARb}{aRb}\} [/math]

Note: I usually use the symbols [ and ] instead of ⟦ and ⟧, but the wiki syntax makes this difficult. You may use either notation.

When [math]R [/math] is clear from context, we just write ⟦a⟧.

In the above example, we have three equivalence classes: [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} = \{a,b,c\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦c⟧} [/math], [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧} = \{d,e\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦e⟧} [/math], and [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧} = \{f\} [/math].

You can see in this example that ⟦a⟧=⟦b⟧ if and only if aRb; this is always the case.

Definition: A/R
If [math]R [/math] is an equivalence relation on a set [math]A [/math], then A mod R (written [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math]) is the set of all equivalence classes of [math]A [/math] by [math]R [/math]. In other words, [math]\href{/cs2800/wiki/index.php/A/R}{A/R} := \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\} [/math].

Continuing the above example, we have [math]\href{/cs2800/wiki/index.php/A/R}{A/R} = \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧}\} [/math]. Note that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math] is also in [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math], but we don't need to list it separately, since it is equal to [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].

One more piece of terminology:

Definition: representative
If [math]c \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/A/R}{A/R} [/math] is an equivalence class of [math]A [/math] by [math]R [/math], and [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], we say that [math]a [/math] is a representative of [math]c [/math] if [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} c [/math]. Note that [math]a [/math] is a representative of [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].