# Equivalence Relations and Partitions

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?

-

– Peter Tamaroff Oct 17 '12 at 22:50

## 2 Answers

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

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8912684917449951, "perplexity_flag": "middle"}