# FA19:Lecture 11 Relations

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

We introduced relations, binary relations, and equivalence relations.

- slides
- Last semester: quantifiers, relations

## Contents

# Order of quantifiers

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

- means "everybody loves somebody"
- means "there is somebody that everyone loves"

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

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

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

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 (set comparisons ( ), function equality, and so on.

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

**Binary relation**

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

is aFor example, we usually write

instead of .Examples:

- 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

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 relation on the set .

to indicates . This diagram represents the# 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 peo**Bold text**ple 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

**Reflexive**

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

## Symmetry

**Symmetric**

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

## Transitivity

**Transitive**

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

## Equivalence relation

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