Sets and Set Operations

Computer Science I 248 words Free to read

The Foundation of Sets

A set is an unordered collection of distinct objects, its elements. We write $x \in A$ for elementhood and $x \notin A$ otherwise. Sets have no order ( $\{1,2\} = \{2,1\}$ ) and no duplicates.

Relation / Set	Symbol	Meaning	Example
Subset	$A \subseteq B$	Every element of $A$ is in $B$	$\{1\} \subseteq \{1,2\}$
Empty Set	$\emptyset$	Has no elements; subset of all	$\emptyset \subseteq A$
Cardinality	$\|A\|$	Number of elements in $A$	$\|\{a,b,c\}\| = 3$

Set Operations & Logic

Operations combine sets just like boolean logic (Union=OR, Intersection=AND, Complement=NOT).

Operation	Notation	Definition	Logic Mirror
Union	$A \cup B$	In $A$ or $B$ (or both)	OR
Intersection	$A \cap B$	In both $A$ and $B$	AND
Difference	$A \setminus B$	In $A$ , not in $B$	A AND NOT B
Complement	$\overline{A}$	In universe, not in $A$	NOT

De Morgan's laws: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$ .

Inclusion-exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$ . Pitfall: Do not forget to subtract the overlap, or you count it twice.

Sets and Set Operations

Sets and Set Operations

The Foundation of Sets

Set Operations & Logic

Practise this lesson

Practice questions

Discrete Mathematics