Set Operations
- The union of two sets is the set containing all of the elements from both of those sets.
- Written \(A\cup B\) and defined \[A\cup B = \{x \mid x\in A\vee x\in B\}\,.\]
- For example, \[\{1,2,3,4\}\cup\{3,4,5,6\} = \{1,2,3,4,5,6\}\,\\ \mathbf{R} = \mathbf{Q} \cup \overline{\mathbf{Q}}\,.\]
- The intersection of two sets is the set containing elements which are in both of those sets.
- Written \(A\cap B\) and defined \[A\cap B = \{x \mid x\in A\wedge x\in B\}\,\\ \mathbf{Q} \cap \overline{\mathbf{Q}}=\emptyset\,.\]
- For example, \[\{1,2,3,4\}\cap\{3,4,5,6\} = \{3,4\}\,.\]
- The difference between two sets is the set of values in one but not the other:
\[A-B = \{x \mid x\in A\text{ and } x\notin B\}\,.\]
- For example, \[\{1,2,3,4\}-\{3,4,5,6\} = \{1,2\}\,\\ \overline{\mathbf{Q}} = \mathbf{R}-\mathbf{Q} \,.\]
- Also sometimes written \(A\setminus B\).
- Theorem: For any sets, \(|A-B|\le|A|\).
Proof: Suppose not, that \(|A-B|>|A|\). Then there must be an element \(x\) with \(x\in(A-B)\), but \(x\notin A\). Thus \(A-B\not\subseteq A\).
But from the definition of set difference, we see that \[ A-B = \{x \mid x\in A\text{ and } x\notin B\} \subseteq \{x \mid x\in A\} =A\,. \] This is a contradiction, so \(|A-B|\le|A|\).∎
- With similar proofs, we could prove these things:
Theorem: For any sets, \(|A\cap B|\le|A|\) and \(|A\cap B|\le|B|\).
Theorem: For any sets, \(|A\cup B|\ge|A|\) and \(|A\cup B|\ge|B|\).
- When doing set operations we often need to define a universal set, \(U\).
- Like the domain for quantifiers, it's the set of all possible values we're working with.
- Often not explicitly defined, but implicit based on the problem we're looking at.
- e.g. when we're working with real numbers, probably \(U=\mathbf{R}\).
- The complement of a set \(S\) is written \(\overline{S}\) and is the set of all values not in \(S\):
\[\overline{S} = \{x\mid x\notin S\} = U-S \,.\]
- The standard notation for irrational numbers should now make a lot of sense: with universal set \(\mathbf{R}\), the irrationals (\(\overline{\mathbf{Q}}\)) are the complement of the rationals (\(\mathbf{Q}\)).
- Theorem: For any set \(S\cap\overline{S}=\emptyset\).
Proof: Suppose for contradiction that there is an element \(x\in S\cap\overline{S}\). Then by the definition of the operators, \[ x\in S\cap\overline{S}\\ x\in S \wedge x\in\overline{S} \\ x\in S \wedge x\notin{S}\,. \] This is a contradiction, so we must have \(S\cap\overline{S}=\emptyset\).∎
Set Identities
- Notice the similarity between the corresponding set and logical operators: \(\vee,\cup\) and \(\wedge,\cap\) and \(\overline{\mbox{S}},\neg\).
- There's more to it than similar-looking symbols.
- Here are some important set identities:
Name Identity Identity \(A\cap{U}= A\\A\cup\emptyset= A\) Domination \(A\cup{U}= {U}\\A\cap\emptyset= \emptyset\) Idempotent \(A\cap A= A\\A\cup A= A\) Double Negation \(\overline{(\overline{A})}= A\) Commutative \(A\cup B = B\cup A\\A\cap B = B\cap A\) Associative \((A\cup B)\cup C = A\cup(B\cup C)\\(A\cap B)\cap C = A\cap(B\cap C)\) Distributive \(A\cup(B\cap C) =(A\cup B)\cap(A\cup C)\\A\cap(B\cup C) = (A\cap B)\cup(A\cap B)\) De Morgan's Law \(\overline{A\cap B}=\overline{A} \cup \overline{B}\\\overline{A\cup B}= \overline{A} \cap \overline{B}\) Absorption \(A\cup(A\cap B) = A \\ A\cap(A\cup B) = A\) Negation \(A\cup\overline{A} = {U}\\A\cap\overline{A} = \emptyset\) - Look familiar? It's the table of logical equivalences with some search-and-replace done to it.
- As an example, we can prove one of De Morgan's laws (the book proves the other).
- We'll be careful for this one and manipulate the set builder notation.
Theorem: For any sets, \(\overline{A\cup B}= \overline{A} \cap \overline{B}\).
Proof: By definition of the set operations, \[\begin{align*} \overline{A\cup B} &= \{x\mid x\notin (A\cup B)\} \\ &= \{x\mid \neg(x \in (A\cup B))\} \\ &= \{x\mid \neg(x \in A\vee x\in B )\} \\ &= \{x\mid \neg(x \in A)\wedge \neg(x\in B )\} \\ &= \{x\mid x \in \overline{A}\wedge x \in \overline{B} )\} \\ &= \{x\mid x \in (\overline{A}\cap\overline{B}) )\} \\ &= \overline{A}\cap\overline{B}\,.\quad{}∎ \end{align*}\]
- Could have also given a less formal proof. (See section 2.2 example 10 for that.)
- This is a case where it's probably easier to be more formal: it's so painful to write all of the details in sentences, that the seven steps in that proof are nicer to read. (See example 10 for an example of that too.)
- This proof might give a hint why the equivalences and set identities tables are so similiar.
- For any one of the set operations, we can expand to set builder notation, and then use the logical equivalences to manipulate the conditions.
- Since we're doing the same manipulations, we ended up with the same tables.
- Be careful with the other operations. Just because it worked for these, doesn't mean you can assume everything is the same. There is no logical version of set difference, or set version of exclusive or (at least as far as we have defined).
-
Theorem: For any sets, \(A-B = A\cap\overline{B}\).
Less Formal Proof: The set \(A-B\) is the values from \(A\) with any values from \(B\) removed.
The set \(\overline{B}\) is the set of all values not in \(B\). So intersecting with \(\overline{B}\) has the effect of leaving only the values not in \(B\). That is, \(A\cap\overline{B}\) is the \(A\) with all of the values from \(B\) removed. Thus we see that these sets contain the same elements.∎
More Formal Proof: By definition of the set operations, \[\begin{align*} A-B &= \{x\mid x\in A \wedge x\notin B\} \\ &= \{x\mid x\in A \wedge x\in \overline{B}\} \\ &= \{x\mid x\in (A \cap \overline{B})\} \\ &= A\cap\overline{B}\,.\quad{}∎ \end{align*}\]
- I think either of those are valid proofs.
- The “less formal” version has to be written carefully enough to convince the reader (or TA in your case).
- The “more formal” version has more steps and leaves out the intuitive reason (that might help you actually remember why).
- We can use the set identities to prove other facts about sets. For example:
Theorem: \(A-(B\cup C)= (A-B)\cap(A-C)\).
Proof: For sets \(A,B,C\) from the above theorem, we have, \[\begin{align*} A-(B\cup C) &= A\cap \overline{B\cup C} \\ &= A\cap \overline{B}\cap \overline{C} \\ &= A\cap \overline{B}\cap A\cap \overline{C} \\ &= (A-B)\cap (A-C)\,.\quad{}∎ \end{align*}\]
Union/Intersection Notation
- Those identities should convince you that order of unions and intersections don't matter (in the same way as addition, multiplication, conjunction, and disjunction: they're all commutative operations).
- So we can write a bunch of them without brackets, just like with addition/multiplication/conjunction/disjunction: \[A\cup B\cup C \cup D\,,\\A\cap B\cap C \cap D\,.\]
- If we need to do union/intersection of a lot of things, there is a notation like summation that is used occasionally.
- For example, suppose there are \(n\) courses being offered at ZJU this semester. Let the sets \(S_1,S_2,\ldots ,S_n\) be the students in each course. Then the set of students taking classes this semester is \[\bigcup_{i=1}^{n} S_i\,.\] The students taking every course this semester are \[\bigcap_{i=1}^{n} S_i\,.\]
- This is exactly analogous to the summation notation you have seen before, except with union/intersection instead of addition: \[\sum_{i=1}^{n} i^2\,.\]