SP20:Lecture 10 Relations

From CS2800 wiki

We introduced relations, binary relations, and equivalence relations.

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

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:

Binary-relation-2sets.svg

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

Binary-relation.svg

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

Reflexivity

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.

Symmetry

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

Transitivity

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