1. Sets and Basic Concepts

Definition 3.1: Set

A set is an unordered collection of distinct objects. The objects in a set are called elements or members of the set.

Notation:

$a \in A$ means "a is an element of set A"
$a \notin A$ means "a is not an element of set A"
Sets are typically denoted by capital letters: A, B, C, ...
Elements are typically denoted by lowercase letters: a, b, c, ...

Example: Specifying Sets

There are several ways to describe a set:

1. Roster Method (Enumeration):

List all elements: $A = \{1, 2, 3, 4, 5\}$

2. Set-Builder Notation:

$A = \{x \mid x \text{ is a positive integer less than 6}\}$

Read as: "A is the set of all x such that x is a positive integer less than 6"

3. Interval Notation (for real numbers):

$[a, b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}$ (closed interval)

$(a, b) = \{x \in \mathbb{R} \mid a < x < b\}$ (open interval)

Definition 3.2: Common Number Sets

$\mathbb{N}$ = Natural numbers = $\{0, 1, 2, 3, \ldots\}$

$\mathbb{Z}$ = Integers = $\{\ldots, -2, -1, 0, 1, 2, \ldots\}$

$\mathbb{Z}^+$ = Positive integers = $\{1, 2, 3, \ldots\}$

$\mathbb{Q}$ = Rational numbers = $\{\frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0\}$

$\mathbb{R}$ = Real numbers

$\mathbb{C}$ = Complex numbers = $\{a + bi \mid a, b \in \mathbb{R}, i^2 = -1\}$

Definition 3.3: Empty Set and Universal Set

The empty set (or null set), denoted $\emptyset$ or ${}$ , is the set with no elements.
The universal set, denoted $U$ , is the set containing all objects under consideration in a particular context.

Definition 3.4: Set Equality and Subsets

Set Equality:

Two sets A and B are equal, written $A = B$ , if they contain exactly the same elements.

$A = B \iff \forall x (x \in A \leftrightarrow x \in B)$

Subset:

A is a subset of B, written $A \subseteq B$ , if every element of A is also an element of B.

$A \subseteq B \iff \forall x (x \in A \rightarrow x \in B)$

Proper Subset:

A is a proper subset of B, written $A \subset B$ or $A \subsetneq B$ , if $A \subseteq B$ and $A \neq B$ .

Theorem 3.1: Properties of Subsets

For any sets A, B, and C:

$\emptyset \subseteq A$ (the empty set is a subset of every set)
$A \subseteq A$ (every set is a subset of itself)
If $A \subseteq B$ and $B \subseteq C$ , then $A \subseteq C$ (transitivity)
$A = B \iff (A \subseteq B \land B \subseteq A)$

Definition 3.5: Cardinality

The cardinality of a set A, denoted $|A|$ , is the number of elements in A.

For finite sets:

If $A = {1, 2, 3}$ , then $|A| = 3$
$|\emptyset| = 0$

(Infinite sets have infinite cardinality; we'll explore this concept more in Course 5)

2. Set Operations

Definition 3.6: Union

The union of sets A and B, denoted $A \cup B$ , is the set of all elements that are in A, in B, or in both.

A cup B = {x mid x in A lor x in B}

Definition 3.7: Intersection

The intersection of sets A and B, denoted $A \cap B$ , is the set of all elements that are in both A and B.

A cap B = {x mid x in A land x in B}

Definition 3.8: Difference

The difference of sets A and B, denoted $A - B$ or $A \setminus B$ , is the set of elements in A that are not in B.

A - B = {x mid x in A land x otin B}

Definition 3.9: Complement

The complement of set A (relative to universal set U), denoted $\overline{A}$ or $A^c$ , is the set of all elements in U that are not in A.

overline{A} = U - A = {x in U mid x otin A}

Definition 3.10: Disjoint Sets

Two sets A and B are disjoint if they have no elements in common, i.e., $A \cap B = \emptyset$ .

Example: Set Operations

Let $U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ , $A = {1, 2, 3, 4, 5}$ , and $B = {4, 5, 6, 7}$ .

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

$A cap B = {4, 5}$

$A - B = {1, 2, 3}$

$B - A = {6, 7}$

$overline{A} = {6, 7, 8, 9, 10}$

$overline{B} = {1, 2, 3, 8, 9, 10}$

Theorem 3.2: Inclusion-Exclusion Principle

For any finite sets A and B:

|A cup B| = |A| + |B| - |A cap B|

This generalizes to three sets:

|A cup B cup C| = |A| + |B| + |C| - |A cap B| - |A cap C| - |B cap C| + |A cap B cap C|

Proof of Inclusion-Exclusion Principle (two sets)

If we simply add $|A| + |B|$ , we count each element in $A \cap B$ twice (once from A and once from B).

To get the correct count for $A \cup B$ , we must subtract $|A \cap B|$ once to compensate for the double counting.

Therefore, $|A \cup B| = |A| + |B| - |A \cap B|$ .

∎

3. Set Identities

Theorem 3.3: Fundamental Set Identities

Let A, B, and C be sets, and let U be the universal set:

Identity Laws:

$A \cup \emptyset = A$

$A \cap U = A$

Domination Laws:

$A \cup U = U$

$A \cap \emptyset = \emptyset$

Idempotent Laws:

$A \cup A = A$

$A \cap A = A$

Complement Laws:

$A \cup \overline{A} = U$

$A \cap \overline{A} = \emptyset$

$\overline{\overline{A}} = A$ (Double Complement)

Commutative Laws:

$A \cup B = B \cup A$

$A \cap B = B \cap A$

Associative Laws:

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

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

Distributive Laws:

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

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

De Morgan's Laws:

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

$\overline{A \cap B} = \overline{A} \cup \overline{B}$

Absorption Laws:

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

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

Example: Proving Set Identities

Prove: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Method 1: Element Argument

Proof of Distributive Law

We show both $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$ and $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$ .

Part 1: Let $x \in A \cap (B \cup C)$

Then $x \in A$ and $x \in (B \cup C)$

So $x \in A$ and ( $x \in B$ or $x \in C$ )

Case 1: If $x \in B$ , then $x \in A \cap B$ , so $x \in (A \cap B) \cup (A \cap C)$

Case 2: If $x \in C$ , then $x \in A \cap C$ , so $x \in (A \cap B) \cup (A \cap C)$

Therefore $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$

Part 2: Let $x \in (A \cap B) \cup (A \cap C)$

Then $x \in (A \cap B)$ or $x \in (A \cap C)$

Case 1: If $x \in A \cap B$ , then $x \in A$ and $x \in B$ , so $x \in A$ and $x \in B \cup C$

Case 2: If $x \in A \cap C$ , then $x \in A$ and $x \in C$ , so $x \in A$ and $x \in B \cup C$

In both cases, $x \in A \cap (B \cup C)$

Therefore $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$

Since both inclusions hold, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

∎

Remark

Methods for Proving Set Equalities:

Element Argument: Show $A \subseteq B$ and $B \subseteq A$
Logical Equivalence: Use logical equivalences on set-builder notation
Venn Diagrams: Visual verification (not a rigorous proof, but useful for intuition)
Algebraic Manipulation: Use known set identities

4. Power Sets

Definition 3.11: Power Set

The power set of a set A, denoted $\mathcal{P}(A)$ or $2^A$ , is the set of all subsets of A (including the empty set and A itself).

mathcal{P}(A) = {S mid S subseteq A}

Theorem 3.4: Cardinality of Power Set

If A is a finite set with $\left|A\right| = n$ , then $\left|\mathcal{P}(A)\right| = 2^n$ .

Proof of Cardinality of Power Set

To form a subset of A, we make a binary choice for each element: include it or exclude it.

Since there are n elements in A, and each element has 2 choices (in or out), by the multiplication principle, there are $2 \times 2 \times \cdots \times 2 = 2^n$ possible subsets.

Therefore, $\left|\mathcal{P}(A)\right| = 2^n$ .

∎

Example: Power Sets

Example 1: Let $A = {1, 2}$

$mathcal{P}(A) = {emptyset, {1}, {2}, {1, 2}}$

Note: $\left|\mathcal{P}(A)\right| = 4 = 2^2$

Example 2: Let $B = {a, b, c}$

$mathcal{P}(B) = {emptyset, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}$

Note: $\left|\mathcal{P}(B)\right| = 8 = 2^3$

Example 3: Let $C = \emptyset$

$mathcal{P}(emptyset) = {emptyset}$

Note: $\left|\mathcal{P}(\emptyset)\right| = 1 = 2^0$ . The empty set has one subset: itself!

Note

Important Distinctions:

$\emptyset$ is the empty set (contains no elements)
${emptyset}$ is a set containing one element (the empty set)
$\emptyset \in \mathcal{P}(A)$ for any set A
$A \in \mathcal{P}(A)$ for any set A

5. Cartesian Product

Definition 3.12: Ordered Pair

An ordered pair $(a, b)$ is a pair of elements where order matters. Two ordered pairs $(a, b)$ and $(c, d)$ are equal if and only if $a = c$ and $b = d$ .

Note: $(a, b) \neq (b, a)$ unless $a = b$ (unlike sets, where ${a, b} = {b, a}$ )

Definition 3.13: Cartesian Product

The Cartesian product of sets A and B, denoted $A \times B$ , is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$ .

A imes B = {(a, b) mid a in A land b in B}

Theorem 3.5: Cardinality of Cartesian Product

If A and B are finite sets, then $|A \times B| = |A| \cdot |B|$ .

Example: Cartesian Products

Example 1: Let $A = {1, 2}$ and $B = {x, y, z}$

$A imes B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}$

Note: $|A \times B| = 6 = 2 \times 3$

Example 2: $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$

This represents the Cartesian coordinate plane (all points (x, y) where x, y are real numbers)

Example 3: Let $A = {1, 2}$

$A imes A = {(1,1), (1,2), (2,1), (2,2)}$

Also written as $A^2$

Definition 3.14: Cartesian Product of Multiple Sets

The Cartesian product can be extended to multiple sets:

A_1 imes A_2 imes cdots imes A_n = {(a_1, a_2, ldots, a_n) mid a_i in A_i ext{ for } i = 1, 2, ldots, n}

For n copies of the same set A: $A^n = A \times A \times \cdots \times A$ (n times)

Remark

Properties of Cartesian Product:

$A \times B \neq B \times A$ (not commutative, unless A = B)
$A \times \emptyset = \emptyset$
$A \times (B \cup C) = (A \times B) \cup (A \times C)$ (distributive over union)
$A \times (B \cap C) = (A \times B) \cap (A \times C)$ (distributive over intersection)

Example: Application: Database Relations

In databases, a relation (table) can be viewed as a subset of a Cartesian product:

Let $ext{StudentID} = {1001, 1002, 1003}$

Let $ext{Courses} = { ext{Math}, ext{CS}, ext{Physics}}$

An enrollment relation might be: $R subseteq ext{StudentID} imes ext{Courses}$

For example: $R = {(1001, ext{Math}), (1001, ext{CS}), (1002, ext{Physics}), (1003, ext{CS})}$

This represents which students are enrolled in which courses.

Practice Quiz

Sets and Set Operations Quiz

10

Questions

0

Correct

0%

Accuracy

1

Which of the following correctly represents the set of positive even integers less than 10?

Easy

Not attempted

2

If

A = \{1, 2, 3\}

and

B = \{3, 4, 5\}

, what is

A \cup B

?

Easy

Not attempted

3

If

A = \{1, 2, 3, 4\}

and

B = \{3, 4, 5, 6\}

, what is

A - B

?

Medium

Not attempted

4

If

|A| = 5

, how many elements are in the power set

\mathcal{P}(A)

?

Medium

Not attempted

5

Which of the following is true about the empty set

\emptyset

?

Medium

Not attempted

6

If

A \times B = \{(1,3), (1,4), (2,3), (2,4)\}

, what are sets A and B?

Medium

Not attempted

7

Which set identity is represented by

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

?

Easy

Not attempted

8

If U is the universal set and A is any set, what is

A \cap \overline{A}

?

Easy

Not attempted

9

Which of the following represents De Morgan's Law for sets?

Hard

Not attempted

10

If

|A| = m

and

|B| = n

, what is

|A \times B|

?

Hard

Not attempted

Frequently Asked Questions

What's the difference between ∈ and ⊆?

∈ (element of): Relates an element to a set. Example: 3 ∈ {1, 2, 3}

⊆ (subset of): Relates a set to another set. Example: {1, 2} ⊆ {1, 2, 3}

Common mistake: Writing {1} ∈ {1, 2, 3} is FALSE. The correct statement is {1} ⊆ {1, 2, 3} or 1 ∈ {1, 2, 3}.

However, {{ 1 } } ∈ {{ 1 }, { 2 }, 3} is TRUE because {1} is an element of this set.

Why is the empty set a subset of every set?

By definition, A ⊆ B means "for all x, if x ∈ A then x ∈ B".

For the empty set ∅, there are no elements x in ∅, so the statement "if x ∈ ∅ then x ∈ B" is vacuously true (the hypothesis is always false).

Therefore, ∅ ⊆ A for any set A, including ∅ ⊆ ∅.

How do I remember De Morgan's Laws for sets?

De Morgan's Laws: When you negate (take complement of) a union or intersection:

The operation flips: ∪ becomes ∩, and vice versa
Each set gets complemented

Think: "Break the line, change the sign"

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ ("not in A or B" = "not in A and not in B")
$\overline{A \cap B} = \overline{A} \cup \overline{B}$ ("not in both" = "not in A or not in B")

What's the difference between {∅} and ∅?

∅ is the empty set - it contains zero elements: |∅| = 0

{∅} is a set containing one element (which happens to be the empty set): |{∅}| = 1

Analogy: ∅ is like an empty box, while {∅} is a box containing an empty box.

Similarly, ∅ ≠ {∅} ≠ {{∅} } - these are all different sets with cardinalities 0, 1, and 1 respectively.

Why does |𝒫(A)| = 2ⁿ?

To form any subset of A, you make a binary decision for each element: include it or not.

With n elements, that's 2 choices for element 1, times 2 choices for element 2, ..., times 2 choices for element n.

Total: 2 × 2 × ... × 2 (n times) = 2ⁿ subsets.

This is also why the power set is sometimes denoted 2ᴬ - it represents "2 to the power of A".

When would I use Cartesian products in real applications?

Cartesian products appear frequently in computer science and mathematics:

Databases: Relations (tables) are subsets of Cartesian products of attribute domains
Coordinates: ℝ² = ℝ × ℝ represents the 2D plane, ℝ³ represents 3D space
State spaces: In game theory or AI, possible states are often Cartesian products
Testing: Test cases covering all combinations of input values
Cryptography: Key spaces are often Cartesian products of character sets