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

# 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 [/itex]y[/itex].

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 .

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