# Introduction to Set Theory

## Motivation

Take a look at these objects;  what are their similarities and differences? Can you classify them by some criterion?

You can notice that objects denoted by numbers $1, 3$ and $5$ are plane figures, i.e. two – dimensional (2D) shapes, while objects denoted by numbers $2, 4$ and $6$ are solid figures, i.e. three – dimensional (3D) shapes. Therefore, we have two collections: collection of plane figures and collection of solid figures. Obviously, figures in each of the two collections have the same property. We can tell that collection of objects with some property in common is called a set.

Some more examples of sets are: the set of people younger than $25$ years, the set of flowers, the set of four seasons, the set of string instruments and so on.

A set which has no elements is called an empty set or null set. We denote it by $\emptyset$.

## Set notation

Members of set are called elements. Notations for mentioned sets are: A = {$1, 3, 5$} and B = {$2, 4, 6$} or A = {triangle, quadrilateral, circle} and B = {parallelepiped, pentagonal prism, triangular pyramid}. Therefore, we denote sets by a single capital letter, simply list the elements, separate them by comma and put curly brackets.

The notation for set of plants is: {tulip, sunflower, rose, … }; we use the three dots when the set has a large number of elements or when it is infinite. Sets which aren’t infinite are called finite sets.

Size of the set $A$ is called cardinality number and it is denoted by $|A|$. Cardinalities of mentioned sets $A$ and $B$ are: $|A|=3$ and $|B|=3$. Cardinality of empty set is $0$.

Other way of representing a set is describing a property that its element must satisfy. For example, we denote set of all numbers which are divisible by $7$ as:

$\{$ x: x is divisible by 7 $\}$ or $\{$ x|x is divisible by 7 $\}$.

If $x$ is an element of a set $A$, we write: $x \in A$ and say ”$x$ belongs to $A$”.

If $x$ isn’t the element of a set $A$, we write: $x \notin A$ and say ”$x$ doesn’t belong to $A$”.

Example 1:  Write a collection of vowels in English alphabet. How many elements does it have? Are letters $b, d$ and $o$ elements of that collection?

Solution:

$V= \{a, e, i, o, u\}$, it has $5$ elements.

$b \notin V$, $d \notin V$, $o \in V$.

## Properties of sets

The order in which elements of a set are listed is not important. For example, $\{a, e, i, o, u\} = \{u, o, a ,i, e\}$.

If some elements are repeated, set is still the same. For example, $\{3, 3, 7, 8\} = \{3, 7, 8\}$.

Two sets are equal if and only if they have the same elements. For example, $A$ = set of primary colors and $B = \{red, blue, yellow\}$ are equal.

## Subsets

A set $A$ is said to be a subset of the set $B$ if and only if every element of set $A$ is also the element of set $B$. We write:

$A \subseteq B$.

In that case, $B$ is the superset of set $A$.

Empty set is a subset of every set.

If $A$ is not the subset of $B$, we write: $A \not \subseteq B$.

Universal set U is a set that is superset of all sets.

Example 2:  Is $A$ subset of $B$, where $A = \{$x: x is a whole number greater than $4$ $\}$ and $B = \{$x: x is even number $4<x<15$ $\}$?

Solution:

$A= \{$$5, 6, 7, 8, …$$\}$ and $B = \{$$6, 8, 10, 12, 14$$\}$

$A \not \subseteq B$, $B \subseteq A$

A set $A$ is said to be a proper subset of the set $B$ if and only if every element of set $A$ is also the element of set $B$, but there exists at least one element which is in $B$ and not in $A$. We write:

$A \subset B$.

If $A$ is not a proper subset of $B$, we write: $A \not \subset B$.

Example 3:  Find proper subsets of set $A=\{$$a, b$$\}$.

Solution:

Proper subsets are:  $\emptyset$, $\{$a$\}$, $\{$b$\}$.

Note: $A=B \Leftrightarrow (A \subseteq B \wedge B \subseteq A)$

## Power set

A power set of a set $S$, denoted by $\mathcal{P}(S)$, is a set of all the subsets of a set. If a set has $n$ elements, power set has $2^{n}$ elements.

Example 4:  Find $\mathcal{P}(S)$, where $S=\{a, b\}$.

Solution:

$\mathcal{P}(S)= \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$