Equality (sets)

From CS2800 wiki
(Redirected from Equality (Sets))


The defining feature of a set is the collections of elements that are in or not in it. This suggests that we should consider two sets to be the same if they contain the same elements. This motivates the definition of equality:

Definition: Equality (sets)
Two sets [math]A [/math] and [math]B [/math] are equal if [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math] and [math]B \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} A [/math].

This is equivalent to the following definition:

Definition: Equality (sets)
Two sets [math]A [/math] and [math]B [/math] are equal if, for all [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], [math]x [/math] is also in [math]B [/math] and if for all [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], [math]x [/math] is also in [math]A [/math].

Here is a third variant:

Definition: Equality (sets)
Two sets [math]A [/math] and [math]B [/math] are equal if, for all [math]x [/math], [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] if and only if [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math].

These three definitions are equivalent (proof left as an exercise), so you can use them interchangeably.

This definition tells us that sets "ignore" duplicates and order. For example, [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,1,2,3\}} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]; we can prove this using the definition. First, we check every [math]x [/math] in the left hand side (LHS) is in the right hand side (RHS); by inspection, we see that [math]1 \in \href{/cs2800/wiki/index.php/RHS}{RHS}, 1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS}, 2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], and [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Then, we check that every [math]x [/math] in the RHS is in the LHS; which they are, again by inspection.