Khanh at 21:37, 11 November 2021

2021-11-11T21:37:17Z

Lila at 21:29, 27 September 2021

2021-09-27T21:29:39Z

Lila: Created page with "We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal..."

2021-09-27T21:28:01Z

Created page with "We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal..."

New page

We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal with are very important in discrete mathematics, and are known as ''equivalence relations''. They essentially assert some kind of equality notion, or ''equivalence'', hence the name.

=== Characteristics of equivalence relations ===
For a relation R to be an ''equivalence relation'', it must have the following properties, viz. R must be:
* symmetric
* transitive
* reflexive
(A helpful mnemonic, S-T-R)

In the previous problem set you have shown equality, "=", to be reflexive, symmetric, and transitive. So "=" is an equivalence relation.

We denote an equivalence relation, in general, by <math>x \sim y</math>.

=== Example proof ===
Say we are asked to prove that "=" is an equivalence relation.
We then proceed to prove each property above in turn (Often, the proof of transitivity is the hardest).

* '''Reflexive''': Clearly, it is true that ''a'' = ''a'' for all values a. Therefore, = is reflexive.
* '''Symmetric''': If ''a'' = ''b'', it is also true that ''b'' = ''a''. Therefore, = is symmetric
* '''Transitive''': If ''a'' = ''b'' and ''b'' = ''c'', this says that ''a'' is the same as ''b'' which in turn is the same as ''c''. So ''a'' is then the same as ''c'', so ''a'' = ''c'', and thus = is transitive.

Thus = is an equivalence relation.

=== Partitions and equivalence classes ===
It is true that when we are dealing with relations, we may find that many values are related to one fixed value.

For example, when we look at the quality of ''congruence'', which is that given some number ''a'', a number congruent to ''a'' is one that has the same remainder or ''modulus'' when divided by some number ''n'', as ''a'', which we write
:a &equiv; b (mod n)
and is the same as writing
:''b'' = ''a''+''kn'' for some integer k.
(We will look into congruences in further detail later, but a simple examination or understanding of this idea will be interesting in its application to equivalence relations)

For example, 2 &equiv; 0 (mod 2), since the remainder on dividing 2 by 2 is in fact 0, as is the remainder on dividing 0 by 2.

We can show that congruence is an equivalence relation (This is left as an exercise, below '''Hint''' use the equivalent form of congruence as described above).

However, what is more interesting is that we can group all numbers that are equivalent to each other.

With the relation congruence ''modulo'' 2 (which is using n=2, as above), or more formally:
: x ~ y if and only if x &equiv; y (mod 2)
we can group all numbers that are equivalent to each other. Observe:
: <math>0 \equiv 2 \equiv 4 \equiv \ldots \pmod{2}</math>
: <math>1 \equiv 3 \equiv 5 \equiv \ldots \pmod{2}</math>
This first equation above tells us all the ''even'' numbers are equivalent to each other under ~, and all the ''odd'' numbers under ~.

We can write this in set notation. However, we have a special notation.
We write:
:[0]={0,2,4,...}
:[1]={1,3,5,...}

and we call these two sets ''equivalence classes''.

All elements in an equivalence class by definition are equivalent to each other, and thus note that we do not need to include [2], since 2 ~ 0.

We call the act of doing this 'grouping' with respect to some equivalence relation ''partitioning'' (or further and explicitly ''partitioning a set S into equivalence classes under a relation ~''). Above, we have partitioned '''Z''' into equivalence classes [0] and [1], under the relation of congruence modulo 2.

=== Problem set ===
Given the above, answer the following questions on equivalence relations (Answers follow to even numbered questions)
# Prove that congruence is an equivalence relation as before (See hint above).
# Partition {x | 1 ≤ x ≤ 9} into equivalence classes under the equivalence relation
<math> x \sim y\ \mbox{iff}\ x \equiv y \pmod{6}</math>

==== Answers ====
2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}

← Older revision		Revision as of 21:37, 11 November 2021
Line 63:		Line 63:
	==== Answers ====		==== Answers ====
	2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}		2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}
		+
		+	== Licensing ==
		+	Content obtained and/or adapted from:
		+	* [https://en.wikibooks.org/wiki/Discrete_Mathematics/Functions_and_relations Functions and relations, Wikibooks: Discrete Mathematics] under a CC BY-SA license

@@ Line 46: / Line 46: @@
 We can write this in set notation. However, we have a special notation.
 We write:
-:[0]={0,2,4,...}
+:<math>[0] = \{0,2,4,...\}</math>
-:[1]={1,3,5,...}
+:<math>[1] = \{1,3,5,...\}</math>
 and we call these two sets ''equivalence classes''.

Equivalence Relations - Revision history

Khanh at 21:37, 11 November 2021

Lila at 21:29, 27 September 2021

Lila: Created page with "We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal..."