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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.