FA19:Lecture 11 Relations
- 1 Order of quantifiers
- 2 Negating quantified statements
- 3 Relations in general
- 4 Binary relations
- 5 Binary relation properties
Order of quantifiers
- means "everybody loves somebody"
- means "there is somebody that everyone loves"
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
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 ofas 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:
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
Similarly, you could define an "is-a-friend-of" relation, or a "loves" relation, etc.
Example: functions are relations
Example: inequalities are relations
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
For example, we usually writeinstead of .
- 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
Binary relation properties
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).
In a picture, this means that every element of has a self-loop: an edge back to itself.
In a picture, this means that every edge from to has a corresponding edge from back to .
In a picture, this means that every path from to has a corresponding direct edge from to .
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 ").