Sets: short notes (Engineering Mathematics)

Introduction

A set is an unordered collection of distinct objects, called its elements or members. Sets are the common language of discrete mathematics: relations and functions are sets of ordered pairs, a graph is a pair of sets, an event in probability is a set of outcomes, a formal language is a set of strings, and a database relation is a set of tuples.

The topics are the notation, the algebra of set operations, the size of finite sets built from other sets, and the distinction between countable and uncountable infinite sets, which matters in the theory of computation.

Prerequisites

None formally. The connectives of Propositional Logic ( $\neg, \land, \lor$ ) are mirrored by complement, intersection and union.

Core concepts

Notation and conventions

$x \in A$ : $x$ is an element of $A$ ; $x \notin A$ : it is not.
Roster form $\{2, 3, 5, 7\}$ ; set-builder form $\{x \in \mathbb{Z} \mid 0 < x < 10,\ x \text{ prime}\}$ .
Order and repetition do not matter: $\{1, 2, 2, 3\} = \{3, 1, 2\}$ . A collection where repetition matters is a multiset.
Standard sets. $\mathbb{Z}$ integers, $\mathbb{Q}$ rationals, $\mathbb{R}$ reals. Convention in these notes: $\mathbb{N} = \{0, 1, 2, \ldots\}$ includes 0 (as in Rosen); $\mathbb{Z}^{+} = \{1, 2, 3, \ldots\}$ . Some textbooks start $\mathbb{N}$ at 1, so read each question's definition.
The empty set $\emptyset = \{\}$ has no elements. $\emptyset \ne \{\emptyset\}$ : the second set has one element.
$|A|$ is the cardinality (number of elements) of a finite set $A$ .

Subsets and equality

$A \subseteq B$ (subset) means every element of $A$ is in $B$ : $\forall x\,(x \in A \to x \in B)$ .
$A \subset B$ or $A \subsetneq B$ (proper subset) means $A \subseteq B$ and $A \ne B$ . Some books use $\subset$ for $\subseteq$ ; these notes write $\subsetneq$ when properness matters.
$A = B$ if and only if $A \subseteq B$ and $B \subseteq A$ . This "double inclusion" is the standard way to prove two sets equal.
For every set $A$ : $\emptyset \subseteq A$ and $A \subseteq A$ . ( $\emptyset \subseteq A$ is vacuously true.)
Membership and subset differ: for $A = \{1, \{1\}\}$ , both $1 \in A$ and $\{1\} \in A$ hold, and $\{1\} \subseteq A$ also holds; $\{\{1\}\} \subseteq A$ holds too.

Set operations

Fix a universal set $U$ containing every set under discussion.

Operation	Notation	Definition
Union	$A \cup B$	$\{x \mid x \in A \lor x \in B\}$
Intersection	$A \cap B$	$\{x \mid x \in A \land x \in B\}$
Difference	$A - B$ or $A \setminus B$	$\{x \mid x \in A \land x \notin B\}$
Complement	$\overline{A}$ or $A^c$	$U - A$
Symmetric difference	$A \oplus B$ or $A \triangle B$	$(A - B) \cup (B - A)$

$A$ and $B$ are disjoint if $A \cap B = \emptyset$ . A partition of a non-empty set $S$ is a collection of non-empty, pairwise disjoint subsets whose union is $S$ (partitions correspond to equivalence relations; see Relations).

Venn diagrams of the basic set operations — Figure 1. Shaded regions for $A \cup B$ , $A \cap B$ , $A - B$ , $\overline{A}$ and $A \oplus B$ inside a universal set $U$ .

Set identities

Each identity corresponds to a law of propositional logic (replace $\cup$ by $\lor$ , $\cap$ by $\land$ , complement by $\neg$ ).

Law	Identity
Identity	$A \cup \emptyset = A$ , $A \cap U = A$
Domination	$A \cup U = U$ , $A \cap \emptyset = \emptyset$
Idempotent	$A \cup A = A$ , $A \cap A = A$
Complementation	$\overline{\overline{A}} = A$
Commutative, associative	for $\cup$ , $\cap$ and $\oplus$
Distributive	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ , $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
De Morgan	$\overline{A \cup B} = \overline{A} \cap \overline{B}$ , $\overline{A \cap B} = \overline{A} \cup \overline{B}$
Absorption	$A \cup (A \cap B) = A$ , $A \cap (A \cup B) = A$
Complement	$A \cup \overline{A} = U$ , $A \cap \overline{A} = \emptyset$
Difference	$A - B = A \cap \overline{B}$

Useful facts about symmetric difference: $A \oplus A = \emptyset$ , $A \oplus \emptyset = A$ , and $A \oplus B = C$ if and only if $B = A \oplus C$ (so $\oplus$ has cancellation). Union and intersection have no such cancellation: $A \cup B = A \cup C$ does not imply $B = C$ .

Power set

The power set $\mathcal{P}(A)$ (also $2^A$ ) is the set of all subsets of $A$ . If $|A| = n$ , then

|\mathcal{P}(A)| = 2^n,

because each of the $n$ elements is independently in or out of a subset. Example: $\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$ . Note $\mathcal{P}(\emptyset) = \{\emptyset\}$ , which has one element, and $|\mathcal{P}(\mathcal{P}(\emptyset))| = 2$ .

Cartesian product

The Cartesian product $A \times B = \{(a, b) \mid a \in A, b \in B\}$ is a set of ordered pairs: $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ . In general $A \times B \ne B \times A$ , and

|A \times B| = |A| \cdot |B|, \qquad |A_1 \times \cdots \times A_k| = |A_1| \cdots |A_k|.

$A \times \emptyset = \emptyset$ . A relation from $A$ to $B$ is any subset of $A \times B$ , so there are $2^{|A||B|}$ relations from $A$ to $B$ .

Sizes of unions: inclusion-exclusion

For finite sets $A, B, C$ :

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

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

The general $n$ -set formula and its counting applications are in Counting.

Related identities: $|A - B| = |A| - |A \cap B|$ , $|A \oplus B| = |A| + |B| - 2|A \cap B|$ , and $|\overline{A}| = |U| - |A|$ .

Countable and uncountable sets

Two sets have the same cardinality if there is a bijection between them (see Functions). A set is countable if it is finite or has the same cardinality as $\mathbb{N}$ (countably infinite); otherwise it is uncountable.

Countable	Uncountable
$\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ , $\mathbb{N} \times \mathbb{N}$	$\mathbb{R}$ , any interval $(a, b)$ with $a < b$
$\Sigma^*$ , all finite strings over a finite alphabet	$\mathcal{P}(\mathbb{N})$ , the set of all languages over a non-empty alphabet
A countable union of countable sets	The set of all functions $\mathbb{N} \to \{0, 1\}$
The set of all programs (Turing machines)	The set of all real numbers in $[0, 1]$

Cantor's theorem: for every set $A$ , there is no surjection from $A$ onto $\mathcal{P}(A)$ , so $|A| < |\mathcal{P}(A)|$ . Proof sketch (diagonal argument): given any $f : A \to \mathcal{P}(A)$ , the set $D = \{a \in A \mid a \notin f(a)\}$ differs from every $f(a)$ at the element $a$ , so $D$ is not in the range of $f$ .

Consequence for computing: there are countably many programs but uncountably many languages over $\{0, 1\}$ , so some languages are not recognised by any program. This is the counting argument behind undecidability.

Worked examples

Example 1: an identity by algebra

Simplify $\overline{(A \cup B) \cap \overline{C}} \cup B$ .

\overline{(A \cup B) \cap \overline{C}} = \overline{A \cup B} \cup C = (\overline{A} \cap \overline{B}) \cup C .

Union with $B$ : $(\overline{A} \cap \overline{B}) \cup B \cup C = ((\overline{A} \cup B) \cap (\overline{B} \cup B)) \cup C = \overline{A} \cup B \cup C$ .

Example 2: inclusion-exclusion

Among the integers 1 to 100, how many are divisible by 2, 3 or 5?

Let $A_2, A_3, A_5$ be the multiples of 2, 3 and 5. Then $|A_2| = 50$ , $|A_3| = 33$ , $|A_5| = 20$ , $|A_2 \cap A_3| = \lfloor 100/6 \rfloor = 16$ , $|A_2 \cap A_5| = 10$ , $|A_3 \cap A_5| = 6$ , $|A_2 \cap A_3 \cap A_5| = 3$ .

50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 .

So 74 are divisible by at least one of them and $100 - 74 = 26$ by none.

Example 3: power sets and products

Let $A = \{1, 2, 3\}$ , $B = \{x, y\}$ . Then $|A \times B| = 6$ , $|\mathcal{P}(A \times B)| = 2^6 = 64$ (the number of relations from $A$ to $B$ ), and $|\mathcal{P}(A) \times \mathcal{P}(B)| = 8 \cdot 4 = 32$ .

Example 4: a tricky membership question

$S = \{\emptyset, \{\emptyset\}\}$ . Which are true? (i) $\emptyset \in S$ ; (ii) $\emptyset \subseteq S$ ; (iii) $\{\emptyset\} \in S$ ; (iv) $\{\emptyset\} \subseteq S$ ; (v) $\{\{\emptyset\}\} \subseteq S$ ; (vi) $|\mathcal{P}(S)| = 4$ .

All six are true. (i) and (iii) list the two elements; (ii) holds for every set; (iv) holds because the single element $\emptyset$ of $\{\emptyset\}$ is in $S$ ; (v) holds because $\{\emptyset\} \in S$ ; (vi) because $|S| = 2$ .

Example 5: symmetric difference

$A = \{1, 2, 3, 4\}$ , $B = \{3, 4, 5\}$ . $A \oplus B = \{1, 2, 5\}$ , and $|A| + |B| - 2|A \cap B| = 4 + 3 - 4 = 3$ . Check cancellation: $A \oplus \{1, 2, 5\} = \{3, 4, 5\} = B$ .

Important properties and observations

$A \subseteq B$ is equivalent to each of $A \cup B = B$ , $A \cap B = A$ , $A - B = \emptyset$ , and $\overline{B} \subseteq \overline{A}$ .
$A - B \ne B - A$ in general; difference is neither commutative nor associative.
$\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$ , but only $\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$ (equality only when one of $A, B$ contains the other).
$A \times (B \cup C) = (A \times B) \cup (A \times C)$ and $A \times (B \cap C) = (A \times B) \cap (A \times C)$ .
An infinite subset of a countable set is countably infinite; a superset of an uncountable set is uncountable.

GATE examination perspective

Identity MCQs. Reduce with $A - B = A \cap \overline{B}$ and De Morgan, or test with a three-set Venn diagram (8 regions) by checking which regions each side shades.
Counting with sets. Inclusion-exclusion for "divisible by" and "at least one" questions; complements for "none of".
Power-set and product sizes. $2^n$ subsets, $2^{mn}$ relations from an $m$ -set to an $n$ -set.
Countability. Expect statements such as "the set of all languages over $\{0, 1\}$ is countable" (false) or "the set of all Turing machines is countable" (true).
Trap: $\emptyset$ versus $\{\emptyset\}$ , and $\in$ versus $\subseteq$ .
Trap: whether $\mathbb{N}$ contains 0 changes answers about smallest elements and counts. Check the definition given.

Summary

Sets: unordered, no repetition; $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$ .
Operations: $\cup, \cap, -, \overline{\ \ }, \oplus$ ; identities mirror propositional logic.
$|\mathcal{P}(A)| = 2^{|A|}$ ; $|A \times B| = |A||B|$ .
Inclusion-exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$ , three-set version with 7 terms.
Countable: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \Sigma^*$ ; uncountable: $\mathbb{R}$ , $\mathcal{P}(\mathbb{N})$ ; $|A| < |\mathcal{P}(A)|$ always.
Convention here: $\mathbb{N}$ includes 0.

Relations: dependent. Relations are subsets of Cartesian products.
Functions: dependent. Bijections define equal cardinality.
Counting: dependent. General inclusion-exclusion.
First-Order Logic: related. Set-builder notation uses predicates.
Probability Basics: dependent. Events are subsets of a sample space.
Alphabets, Strings and Languages: dependent. Languages are sets of strings.
Relational Algebra: dependent. Union, difference and product of relations.

Sets

Introduction

Prerequisites

Core concepts

Notation and conventions

Subsets and equality

Set operations

Set identities

Power set

Cartesian product

Sizes of unions: inclusion-exclusion

Countable and uncountable sets

Worked examples

Example 1: an identity by algebra

Example 2: inclusion-exclusion

Example 3: power sets and products

Example 4: a tricky membership question

Example 5: symmetric difference

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Notation and conventions

Subsets and equality

Set operations

Set identities

Power set

Cartesian product

Sizes of unions: inclusion-exclusion

Countable and uncountable sets

Worked examples

Example 1: an identity by algebra

Example 2: inclusion-exclusion

Example 3: power sets and products

Example 4: a tricky membership question

Example 5: symmetric difference

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps