FA19:Lecture 11 Relations

From CS2800 wiki

We spent some time talking about the order of quantifiers and how to negate quantified statements.

We introduced relations, binary relations, and equivalence relations.

Order of quantifiers

When writing down quantified statements, the order of the quantifiers matters. For example, the following are very different:

  • [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} x, \href{/cs2800/wiki/index.php/%5Cexists}{\exists} y, x \text{ loves }y [/math] means "everybody loves somebody"
  • [math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} y, \href{/cs2800/wiki/index.php/%5Cforall}{\forall} x, x \text{ loves }y [/math] means "there is somebody that everyone loves"

A proof of the first fact might proceed by choosing an arbitrary [math]x [/math], and then defining [math]y [/math] as [math]x [/math]'s mother; then reasoning that everybody loves their mother, so [math]x [/math] loves </math>y</math>.

A proof of the first fact would have to start by specifying a value of [math]y [/math]; this can't depend on [math]x [/math] because [math]x [/math] isn't defined yet. So, there would have to be a single person (for example, let [math]y := [/math]Raymond), and argue that since loves raymond, [math]x [/math] must love [math]y [/math].

Negating quantified statements

Example:Negation of cardinality relationship

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