Set Theory Basics

Sets basics

Set: well-defined collection of distinct objects

• unordered collection
• objects are called elements or members

E.g:

$A=\{2,3,5,7,11,13,17,19,23\}$ $V=\{a,e,i,o,u\}$ $P=\{2,3,5,7,11,13,17,19,23,\dots \}$

$\{a,e,i,o,u\}=\{e,a,o,u,i\}$

Membership: $3\in A$, $4\notin A$

Tuple: ordered list of elements

Cardinality: the cardinality of set $A$, or $|A|$, is the number of elements in $A$.

Sets can be categorised in:

• Finite: $|A|<\infty$
• Countably infinite $\Rightarrow$ 1:1 correspondence in $\mathbb{N}$
• Uncountably infinite: no 1:1 correspondence in $\mathbb{N}$

Set operations

• Union: $A=\{1,2\}$, $B=\{3,4\}$, $A\cup B=\{1,2,3,4\}$
• Intersection: $A=\{1,2\}$, $B=\{2,3\}$, $A\cap B=\{2\}$
• Difference: $A=\{1,2,3\}$, $B=\{1,4\}$, $A-B=\{2,3,4\}$
• Universal set: contains all elements under consideration
• Complement: $A=\{1,2\}$, $A^c$ or $\bar{A}=U-A$