Sets and relations · Definition

Set operations

discrete mathematicssets

They are the basic language for saying «both», «some» or «none», and they underpin the counting and logic of the whole course.

Definition

Set operations combine two sets \(A\) and \(B\), inside a universe \(U\), to form another one: union, intersection, difference and complement.

\[A\cup B,\quad A\cap B,\quad A\setminus B,\quad A^{c}=U\setminus A\]

The union \(A\cup B\) gathers the elements lying in \(A\), in \(B\) or in both; the intersection \(A\cap B\) keeps only those lying in both. The difference \(A\setminus B\) leaves what is in \(A\) and not in \(B\), and the complement \(A^{c}\) is the difference \(U\setminus A\), so it always depends on the chosen universe \(U\).

The operations obey laws similar to those of algebra: they are commutative and associative, intersection distributes over union and vice versa, and \(A\cap B\subseteq A\subseteq A\cup B\). De Morgan's laws, \((A\cup B)^{c}=A^{c}\cap B^{c}\) and \((A\cap B)^{c}=A^{c}\cup B^{c}\), say how to push a complement inside by swapping union and intersection.

To prove an equality of sets one proves both inclusions with an arbitrary element, or translates each membership into a statement with «and», «or» and «not». A guiding example: \(A\setminus B=A\cap B^{c}\), since being in the difference means being in \(A\) and not in \(B\).

A typical mistake is to confuse \(A\setminus B\) with \(B\setminus A\) (the difference is not symmetric) or to forget that the complement changes when the universe changes. These operations prepare the inclusion-exclusion principle, which counts the elements of a union.

Think about it

Is it true that \(A\setminus B=B\setminus A\) for all \(A\) and \(B\)?

No. With \(A=\{1,2\}\) and \(B=\{2,3\}\), \(A\setminus B=\{1\}\) but \(B\setminus A=\{3\}\). They agree only when both are empty.

Use De Morgan to describe «in neither \(A\) nor \(B\)».

It is \((A\cup B)^{c}=A^{c}\cap B^{c}\): not being in the union is the same as not being in \(A\) and not being in \(B\).

Exercises 10

  1. Let \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7\}\). How many elements does \(A\cup B\) have?
  2. With \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7\}\), what is \(A\cap B\)?
  3. With \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7\}\), what is \(A\setminus B\)?
  4. Let the universe be \(U=\{1,2,3,4,5,6,7,8\}\) and \(A=\{1,2,3,4,5\}\). What is the complement \(A^{c}\)?
  5. With \(U=\{1,2,3,4,5,6,7,8\}\), \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7\}\), what is \((A\cup B)^{c}\)?
  6. With \(U=\{1,2,3,4,5,6,7,8\}\), \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7\}\), what is \((A\cap B)^{c}\)?
  7. Which expression equals the difference \(A\setminus B\)?
  8. Let \(A\) and \(B\) be any sets. Which statement is always true?
  9. Let \(A\) be the even numbers from 1 to 20 and \(B\) the multiples of 3 from 1 to 20. What is \(A\cap B\)?
  10. If \(A\subseteq B\), which statement is always true?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §2.2
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §6.1
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §3.1