SUNY Geneseo Department of Mathematics
Misc
Canvas Problems
Probably due to an upgrade to Chrome.
Work around by disabling upgraded blocker, or sorting notes into most-recent-first order, or using a different browser.
See announcement for more
A day of talks, posters, performances, etc, highlighting students’ scholarly and creative work. No classes, so you can go to the sessions. See https://www.geneseo.edu/great_day for more information.
Next Tuesday (April 25).
Extra credit for writing a summary of any one presentation and the connections you make to it.
Questions?
Equivalence Relations / Classes
Tudor Family Relationships
Equivalence relations among them
- Has-Same-Father. x is related to y if and only if x and y have the same father. For example Mary I, Elizabeth I, and Edward VI are all related to each other by virtue of having Henry VIII as their father.
- Reflexive: x has the same father as him/herself.
- Symmetric: x and y have the same father means y and x have the same father.
- Transitive: x and y have the same father and y and z have the same father means x and z do too.
What are the equivalence classes?
Relevant ideas or questions from the reading
- Definition of equivalence relation: a relation is an equivalence relation if and only if it is reflexive (for all x, x R x), symmetric (if x R y then y R x), and transitive (if x R y and y R z then x R z).
- Definition of equivalence class: Let ~ be an equivalence relation on A, then every a in A has an equivalence class determined by ~, and that equivalence class is the subset {x ∈ A | x ~ a }
- In English, this means that a’s equivalence class is the set of things that are equivalent to a.
- For example, { Mary I, Elizabeth I, Edward VI } is an equivalence class of the “has-same-father” relation among the Tudors; {Arthur, Henry VIII, Mary Tudor, Margaret Tudor } is another.
Comments
- The key things here are relatively informal understandings of what makes something an equivalence relation, and how equivalence relations define equivalence classes.
A More Mathematical Example
Consider the relation ~ on differentiable functions from ℝ to ℝ defined by
f ~ g if and only if f′ = g′ (i.e., the derivatives of f and g are the same function).
Is ~ an equivalence relation?
Theorem: ~ is an equivalence relation. To prove this, show that ~ is reflexive, symmetric,
and transitive.
- Reflexive: Clearly f′ = f′ (and is unique), so f ~ f
- Symmetric: if f ~ g, then f′ = g′ and so g′ = f′ by symmetry of =,
so g ~ f
- Transitive: if f ~ g and g ~ k, it means that f′ = g′ and g′ = k′,
and so f′ = k′ by transitivity of =. Thus f ~ k.
What are the equivalence classes (if ~ is an equivalence relation)?
- [f] = { g | g is a differentiable function and g(x) = f(x) + C for some real number C }
Comments
- This proof was fairly short because the arguments quickly reduced to things that follow from the fact that “=” is an equivalence relation. But that isn’t uncommon in proofs that relations defined in terms of “=” or other common relations are equivalence relations.
Overall Comments
Equivalence relations are an important kind of relation because they occur often and partition their domain/range into equivalence classes.
Equivalence classes are particularly clean ways to divide a set into subsets, because all the subsets are disjoint and every member of the large set is a member of some subset.
Next
Recognizing when sets are the “same” size
Read textbook section 9.1
Problem set on relations and cardinality