Introduction to Relations

Return to Course Outline

Previous Lecture

Questions?

Relations

Section 7.1

“Real World” Example

Consider Henry VIII’s family tree, at https://www.britroyals.com/tudortree.asp

What are some relations you can see in it? Describe them as sets of ordered pairs, talk about domains and ranges, etc.

Sibling

A “Sibling-Of” relation: { (Arthur, Henry VIII), (Mary I, Elizabeth I), (Mary I, Edward VI), (Elizabeth I, Edward VI), ... }

Father

Or “Father-Of”: { (Henry VIII, Mary I), (Henry VIII, Elizabeth I), (Henry VIII, Edward VI) }

Is this the complete “father-of” relation? It is if the domain is {Henry VIII}, in which case the range is {Mary I,Elizabeth I,Edward VI}. As a Cartesian product, the relation is then {Henry VIII} × {Mary I,Elizabeth I,Edward VI}.

But we can have a different domain, say including Henry VII, in which case there would be more ordered pairs in the relation than shown above. In fact, we could even say the relation is a subset of Tudors × Tudors (where “Tudors” is the set of all people in the family tree), in which case there are many more father relations than we listed.

Moral: the domain of a relation is a more flexible concept than the domain of a function. In particular a relation on A × B doesn’t have to have every element of A in its domain, whereas a function from A to B does.

Marriage

A “Married-To” relation: { (Henry VIII, Catherine of Aragon), (Henry VIII, Anne Boleyn), (Henry VIII, Jane Seymour), ..., (Henry VII, Elizabeth of York) }

Express this as a graph. The graph has vertices (dots) for each person in the domain and range, and a directed edge (arrows) from x to y if x is related to y.

Properties of Relations

We drew all the arrows in the marriage graph one way. But in fact marriage goes both ways, i.e., if Henry VIII was married to Catherine of Aragon, then Catherine was also married to Henry. So we really ought to have arrows going both ways, and whenever (x,y) is in the relation, (y,x) should be too.

In contrast, consider the father relation. Since no-one can be their own father’s father, that relation never has (y,x) in it if it contains (x,y).

These examples suggest that relations can be characterized by other interesting properties besides whether they are functions or not.

The pattern we saw in marriages is called “symmetry,” i.e., a relation R is symmetric if (x,y) being in R implies (y,x) is too.

The pattern we saw in father relations is “asymmetry,” i.e., R is asymmetric if (x,y) being in R implies that (y,x) is not in R.

Key Points

The definition of relations as sets of ordered pairs.

Intuition for what that definition means

Relations as graphs.

Next

Build on the idea of relations that have properties such as symmetry, and look at a particular set of properties similar to what the “equals” relation has: equivalence relations.

Read section 7.2

Next Lecture