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 (), 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.
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:
- Inequalities (like ) are binary relations on the set of numbers.
- Similarly and are binary relations on the set of sets
- 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 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
In a picture, this means that every element of has a self-loop: an edge back to itself.
Symmetry
In a picture, this means that every edge from to has a corresponding edge from back to .
Transitivity
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 ").
