Introduction to Relations

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Misc

End-of-Semester

The final day to grade anything for this class is Thursday May 20 (the last day of finals). Office hours end at 5:00 that day, like any other day.

I expect the week or so leading up to this deadline to be very busy. Work that’s ungraded at the end of it will get grades of 0. So if you have grading to catch up on, or “redos” that you want graded, start acting now to get it done, and do not count on being able to do it during finals week or study day.

You can grade more than 1 problem set in a single meeting, but make meetings you want to do that in a little longer than usual. For example, if you want to grade 2 problem sets, I’d recommend making about a 45 minute appointment.

Math Alumni Talk

Our AWM (Association for Women in Math) chapter is holding a panel with some Geneseo math alumni talking about their educations and careers as women mathematicians.

Wednesday (April 28), 5:00 - 6:00PM

Via Zoom: Meeting ID 931 4225 7839, passcode 237493

Last Problem Set

Problem set 11, the last one, is available to preview now. You should officially start it Wednesday.

Relations

From section 7.1 in the textbook, and this discussion of relations.

Examples

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

What, if any relations can you find in it?

A “parent-of” relation between person A and B if A is one of B’s parents. As a set of ordered pairs, we started to write this relation as follows, using abbreviations for many of the names:

parent-of = { (AnneB, ElizI), (ElizYork, HenryVIII), … }

We also noticed a “HusbandWife” relation, for example

HusbandWife = { (HenryVII, ElizYork), (HenryVIII,CatherineA), (HenryVIII, AnneB), … }

Upon discussion, we decided that we really wanted this relation to reflect marriages, and so it is what’s called a symmetric relation, i.e., any time the pair (A,B) is in it, the pair (B,A) must also be. So we extended it to

HusbandWife = { (HenryVII, ElizYork), (ElizYork, HenryVII), (HenryVIII, CatherineA), (CatherineA, HenryVIII), (HenryVIII, AnneB), (AnneB, HenryVIII), … }

Relations can also be represented as directed graphs. For example, part of the “HusbandWife” relation looks like this as a graph:

Because this is a symmetric relation, every time there’s an arrow (“edge” in the technical terminology of graphs) between two people (“vertices”), there also has to be an edge going the other way.

Part of the parent-of relation looks like this as a graph:

Properties of Relations

Certain patterns show up over and over in relations, and are interesting enough to have names. Being symmetric is one such pattern, but there are many others too.

For example, a relation R on set A is reflexive if for every x in A, x R x, i.e., x is related to itself. For example, the relation between integers that holds between a and b whenever a and b have a non-trivial (i.e., not 1) common divisor is reflexive (as an example of this relation, 4 and 6 are related because they have a common divisor 2). This relation is reflexive because for every integer n, n is related to n by the common divisor n.

A near opposite of symmetric is antisymmetric, where if a is related to b and a ≠ b, then b is not related to a. For example, the “parent-of” relation in Henry VIII’s family is antisymmetric, because a person can’t be their parent’s parent.

Relation R on A is transitive if whenever a R b and b R c, it’s also the case that a R c. For example, a “sibling” relationship, assuming it includes half-siblings, is transitive in Henry VIII’s family tree. For instance, Mary I is Elizabeth I’s half-sibling, and Elizabeth I is Edward VI’s half-sibling, which makes Mary Edward’s half-sibling too. (But beware that transitivity wouldn’t hold in slightly different families; for instance if Arthur and Catherine of Aragon had a child, that child would be Mary’s half-sibling, but not Elizabeth’s, even though Mary and Elizabeth are also half-siblings.)

Finally, relation R  on A is irreflexive if for all x in A, x is not related to itself. For example our “parent-of” relation is irreflexive because no-one is their own parent.

Lots of common relations on numbers are distinguished from each other by having slightly different combinations of these properties. For example…

• The “=” relation is reflexive (every number is equal to itself), symmetric (if a = b then b = a) and transitive (if a = b and b = c then a = c).
• “≤” is reflexive and transitive, but antisymmetric.
• “<” is irreflexive, antisymmetric, and transitive.

These common combinations are important because if you find other relations that have the same combinations of properties as these familiar ones do, you can expect the new relations to behave a lot like the familiar ones. For example, among sets, A ⊆ B is reflexive, antisymmetric, and transitiive, so it behaves in many ways similarly to how ≤ behaves for numbers.

Next

Relations like equality in the sense discussed above: equivalence relations.

Please read section 7.2 in the textbook.

Please also contribute to this discussion of equivalence relations.

Next Lecture