We pretty much spent most of class trying to wrap our heads around this Kick/Hug thing, which is detailed way more clearly than I could ever explain it in Matt’s blog post, then started working on a new worksheet based around equivalence classes.
Consider the set S = ℝ. Prove or disprove x~y ⇔ xy is odd is an equivalence relation on ℝ.
To be an equivalence relation, you must follow the following conditions:
- Reflective: (∀x∈S)(x~x)
- Symmetric: (∀x,y∈S)(x~y ⇒ y~x)
- Transitive: (∀x,y,z∈S)(x~y + y~z ⇒ x~z)
If we assume that xy is odd and try to prove that x~y, all reals must relate to themselves in some way. But if xy is odd, even numbers cannot be represented, so this cannot be an equivalence relation, because it is not reflexive.
Let S be any set. Prove that equality is an equivalence relation; i.e. that a~b⇔a=b is an equivalence relation.
We’ll assume that a~b⇔a=b is true, and that we’re trying to prove that this equality follows these features:
- Reflective: (∀a∈S)(a~a)
- Symmetric: (∀a,b∈S)(a~b ⇒ b~a)
- Transitive: (∀a,b,c∈S)(a~b + b~c ⇒ a~c)
Which means we’ll try to prove that a=b is reflective, symmetric, and transitive. If a = b, then this can be symmetric, because the order does not matter if a = b. A can also be related to itself because b is the same element. a = b is also transitive, because b~c can be changed to a~c by substitution. Therefore, a=b is an equivalence relation.
I am still a little confused on how to prove equivalence relations, and how ⇔ statements work and are proved. Equivalence relations seem pretty simple to prove, as there are three factors that go into making something an ER, but how do you prove something can wiggle itself? How do you prove something is transitive if only two elements are defined (like in #2)?
How do you go about proving ⇔ statement without getting confused?