Sets

Chapter overview

Set theory is the language of collections. It is used later in relations, functions, probability, domains, ranges, and logical classification.

1. Basic idea of a set

A set is a well-defined collection of objects.

Examples:

• $A=\{1,2,3,4,5\}$
• $B=\{a,e,i,o,u\}$
• $N=\{1,2,3,\ldots\}$
• $Z=\{\ldots,-2,-1,0,1,2,\ldots\}$

If $a$ belongs to set $A$:

$$a\in A$$

If $a$ does not belong to set $A$:

$$a\notin A$$

2. Important number sets

Inclusion relation:

$$N\subset W\subset Z\subset Q\subset R$$

3. Representation of sets

Roster form

Elements are listed inside braces.

$$A=\{2,4,6,8,10\}$$

Set-builder form

A rule is used to describe the elements.

$$A=\{x:x \text{ is an even natural number and }x\le10\}$$

Equivalent form:

$$\{2,4,6,8,10\} = \{x:x=2n,\ n\in N,\ 1\le n\le5\}$$

4. Types of sets

Cardinality:

$$n(A)=\text{number of elements in }A$$

Example:

$$A=\{2,4,6,8\} \quad\Rightarrow\quad n(A)=4$$

5. Subset and proper subset

If every element of $A$ is also an element of $B$, then:

$$A\subseteq B$$

Meaning:

$$A\subseteq B \iff (x\in A\Rightarrow x\in B)$$

Proper subset:

$$A\subset B$$

This means:

$$A\subseteq B \quad\text{and}\quad A\ne B$$

Important facts:

$$\varnothing\subseteq A$$ $$A\subseteq A$$ $$A\subseteq U$$

6. Power set

The power set of $A$ is the set of all subsets of $A$. It is denoted by $P(A)$.

If:

$$A=\{a,b\}$$

then:

$$P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$$

If $n(A)=m$, then:

$$n(P(A))=2^m$$

Example:

$$n(A)=3 \quad\Rightarrow\quad n(P(A))=2^3=8$$

7. Universal set and complement

The universal set $U$ contains all objects under discussion.

Complement of $A$:

$$A'=\{x:x\in U,\ x\notin A\}$$

Also:

$$A^c=U-A$$

Important:

$$A\cup A'=U$$ $$A\cap A'=\varnothing$$ $$(A')'=A$$

8. Set operations

Union

$$A\cup B=\{x:x\in A \text{ or }x\in B\}$$

Example:

$$\{1,2,3\}\cup\{3,4,5\} = \{1,2,3,4,5\}$$

Intersection

$$A\cap B=\{x:x\in A \text{ and }x\in B\}$$

Example:

$$\{1,2,3\}\cap\{3,4,5\} = \{3\}$$

Difference

$$A-B=\{x:x\in A,\ x\notin B\}$$

Example:

$$\{1,2,3,4\}-\{3,4,5\} = \{1,2\}$$

Symmetric difference

$$A\triangle B=(A-B)\cup(B-A)$$

Also:

$$A\triangle B=(A\cup B)-(A\cap B)$$

9. Venn diagram logic

10. Cardinality formulae

For two finite sets:

$$n(A\cup B) = n(A)+n(B)-n(A\cap B)$$

If $A$ and $B$ are disjoint:

$$A\cap B=\varnothing$$

then:

$$n(A\cup B)=n(A)+n(B)$$

For three finite sets:

$$\begin{aligned} n(A\cup B\cup C) &= n(A)+n(B)+n(C)\\ &\quad -n(A\cap B)-n(B\cap C)-n(C\cap A)\\ &\quad +n(A\cap B\cap C) \end{aligned}$$

Complement:

$$n(A')=n(U)-n(A)$$

Difference:

$$n(A-B)=n(A)-n(A\cap B)$$

11. Laws of algebra of sets

12. De Morgan's laws

$$(A\cup B)'=A'\cap B'$$ $$(A\cap B)'=A'\cup B'$$

For three sets:

$$(A\cup B\cup C)'=A'\cap B'\cap C'$$ $$(A\cap B\cap C)'=A'\cup B'\cup C'$$

13. Intervals as subsets of real numbers

Open interval:

$$(a,b)=\{x:x\in R,\ a<x<b\}$$

Closed interval:

$$[a,b]=\{x:x\in R,\ a\le x\le b\}$$

Left-closed, right-open:

$$[a,b)=\{x:x\in R,\ a\le x<b\}$$

Left-open, right-closed:

$$(a,b]=\{x:x\in R,\ a<x\le b\}$$

Infinite intervals:

$$(a,\infty)=\{x:x>a\}$$ $$(-\infty,b]=\{x:x\le b\}$$

14. Cartesian product

$$A\times B=\{(a,b):a\in A,\ b\in B\}$$

Example:

$$A=\{1,2\},\quad B=\{x,y\}$$

Then:

$$A\times B=\{(1,x),(1,y),(2,x),(2,y)\}$$

Number of ordered pairs:

$$n(A\times B)=n(A)\cdot n(B)$$

Usually:

$$A\times B\ne B\times A$$

15. Solved examples

Example 1

If:

$$A=\{1,2,3,4,5\},\quad B=\{4,5,6,7\}$$

then:

$$A\cup B=\{1,2,3,4,5,6,7\}$$ $$A\cap B=\{4,5\}$$ $$A-B=\{1,2,3\}$$

Example 2

In a group:

$$n(A)=40,\quad n(B)=30,\quad n(A\cap B)=10$$

Therefore:

$$n(A\cup B)=40+30-10=60$$

Example 3

If:

$$U=\{1,2,3,4,5,6,7,8,9,10\}$$

and:

$$A=\{2,4,6,8,10\}$$

then:

$$A'=\{1,3,5,7,9\}$$

16. Common mistakes

• Writing repeated elements: $\{1,1,2\}$ should be $\{1,2\}$.
• Thinking order matters: $\{1,2,3\}=\{3,2,1\}$.
• Confusing $\in$ and $\subseteq$.
• Forgetting to subtract $n(A\cap B)$ in the union formula.
• Writing $A-B=B-A$. In general, this is false.
• Confusing interval notation $(a,b)$ with ordered pair notation $(a,b)$.
• Forgetting that $\varnothing$ is a subset of every set.

17. Quick revision table