1
$\begingroup$

My university "textbook" for discrete math is Schaum's Outline. In this outline he goes over Equivalence Relations and Partitions, and I got confused at a particular theorem.

From the book:

Theorem 2.6: Let R be an equivalence relation on a set S. Then S/R is a partition of S. Specifically:

(i) For each a in S, we have a ∈ [a].

(ii) [a] = [b] if and only if (a,b) ∈ R. (iii) If $[a] \ne [b]$, then [a] and [b] are disjoint. Conversely, given a partition {Ai} of the set S, there is an equivalence relation R on S such that the sets Aiare the equivalence classes. This important theorem will be proved in Problem 2.17.

EXAMPLE 2.13

(a) Consider the relation R = {(1,1),(1,2),(2,1),(2,2),(3,3)} on S = {1,2,3}. One can show that R is reflexive, symmetric, and transitive, that is, that R is an equivalence relation.

Also: [1] = {1,2},[2] = {1,2},[3] = {3} Observe that [1] = [2] and that S/R = {[1],[3]} is a partition of S. One can choose either {1,3} or {2,3} as a set of representatives of the equivalence classes.

My confusion arises from the S/R = {[1],[3]}. I don't understand how one can subtract a relation from a set of integers. What fundamental understanding am I missing?

  • 0
    This is [related](http://math.stackexchange.com/questions/182343/general-questions-about-equivalence-classes-and-partitions/182346#182346)2012-10-17

2 Answers 2

3

There's no subtraction there. Set subtraction is denoted by a backslash. The forward slash denotes forming the quotient set.

2

Numbers origin as cardinality of sets (how many elements it has).

  • Addition on numbers corresponds to disjoint union
  • Subtraction corresponds to subtraction of a subset
  • Multiplication corresponds to direct product ($A\times B$ contains all $\langle a,b\rangle$ pairs)

And, somehow Division corresponds to a quotient by a regular equivalence relation i.e. such that each partition has the same cardinality.