Sets

A set is a fundamental concept in modern mathematics, which means that the term itself is not defined.
However, the set can be imagined as a collection of different elements. The whole modern Mathematics is based on this concept, so it is important to know and understand the theory of sets.
Sets are usually denoted by capital Latin letters $A, B, C...$. Elements of the set are written within the braces $\lbrace$ and $\rbrace$.

Sets can be specified by:
1. its elements $A=\lbrace 1,2,3,4,5 \rbrace$
2. the rules satisfied by the elements of the set $A=\lbrace x\in \mathbb{N} \vert x<6\rbrace$

The set with no elements in it is called the empty set, and is denoted $\emptyset$ or $\lbrace \rbrace$.

Relation Between Sets

Equal Set

Two sets $A$ and $B$ are equal if and only if they contain the same elements; if the elements of the first set are the same as the elements of the second, and vice versa.

$A=B \overset{def}{\Leftrightarrow} (\forall x)(x\in A \Leftrightarrow x\in B)$

Since equal set relation is transitive, reflexive and symmetric it is referred to as the equivalence relation.

Subset

Set $A$ is a subset of $B$ if and only if each element of the set $A$ is also an element of the set $B$.

$A \subseteq B \overset{def}{\Leftrightarrow} (\forall x)(x \in A \Rightarrow x \in B)$

Set $B$ is a superset of set $A$, denoted by $B \supseteq A$.
If set $A$ is a subset of set $B$ and if set $B$ contains at least one element that does not belong to set $A$, then we say that set $A$ is a proper subset of set $B$, denoted by $A \subset B$, or that set $B$ is a proper superset of set $A$, denoted by $B \supset A$.

Relation $\subset$ is transitive: $(A \subset B) \wedge (B \subset C) \Rightarrow A \subset C$.

The empty set is a subset of any set.

Set Operations

Union of Two Sets

The union of two sets, $A$ and $B$, is a set of all elements that belong to at least one set $A$ or $B$.

$A \cup B \overset{def}{=} \lbrace x \vert x \in A \vee x \in B \rbrace$

The union of sets operation is:
1. idempotent: $A\cup A=A$
2. commutative: $A \cup B = B \cup A$
3. associative: $(A \cup B) \cup C = A \cup (B \cup C)$

Intersection of Sets

Intersection of two sets, $A$ and $B$, is a set containing all the elements that belong to both set $A$ and set $B$.

$A \cap B\overset{def}{=}\lbrace x \vert x\in A \wedge x\in B \rbrace$

Intersection of sets operation is:
1. idempotent: $A\cap A=A$
2. commutative: $A \cap B = B \cap A$
3. associative: $(A \cap B) \cap C = A \cap (B \cap C)$

Difference of Two Sets

Difference of two sets, $A$ and $B$, is a set containing all elements of set $A$ which are not contained by set $B$.

$A \setminus B \overset{def}{=} \lbrace x \vert x \in A \wedge x \notin B \rbrace$

Symmetric Difference

Symmetric difference of two sets, $A$ and $B$, is a set containing all the elements which belong only to one of the sets $A$ and $B$.

$A \bigtriangleup B \overset{def}{=} (A \setminus B) \cup (B \setminus A)$

It is obvious that the operation $\bigtriangleup$ is commutative.

Complement of a Set

Let us assume that $A \subset B$. Complement of the set $A$ relative to set $B$ is a set containing all elements of set $B$ which do not belong to set $A$.

$C_B(A)\overset{def}{=}\lbrace x\vert x\in B \wedge x\notin A\rbrace$

Power Set

Power set of set $A$ is a set of all subsets of $A$, including the empty set and the set $A$ itself.

$P(A) \overset{def}{=} \lbrace B \vert B \subset A \rbrace$

Example: Power set of set $A=\lbrace 1,2,3 \rbrace $ is a set $P(A)=\lbrace \emptyset ,\lbrace 1 \rbrace , \lbrace 2\rbrace, \lbrace 3 \rbrace , \lbrace 1,2 \rbrace , \lbrace 1,3 \rbrace , \lbrace 2,3 \rbrace , \lbrace 1,2,3 \rbrace \rbrace $

Cartesian Product

A Cartesian Product of sets $A$ and $B$ is a set containing all ordered pairs $(x,y)$ where $x$ is an element of set $A$, and $y$ is an element of set $B$.

$A \times B \overset{def}{=} \lbrace(x,y) \vert x \in A \wedge y \in B \rbrace $

Properties of Set Operations

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

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

De Morgan's laws
$C_U(A\cup B)=C_U(A)\cap C_U(B)$
$C_U(A\cap B)=C_U(A)\cup C_U(B)$

Relations and Functions

Relations

If $A$ and $B$ are two non-empty sets, then each subset $\rho$ of $A\times B$ is called a binary relation on a set $A\times B$.
If $(a,b)\in \rho$, we say that $a$ and $b$ are in relation, and are denoted by $a\rho b$.

Functions

A binary relation $f\subset X\times Y$ is called a function if and only if for each element $x\in X$ there is exactly one $y\in Y$ for which $(x,y)\in f$ is valid, ie. $(\forall x\in X)(\exists !y\in Y)(x,y)\in f$

Denoted in symbols: $f:X\longmapsto Y$ or $X\overset{f}{\longmapsto} Y$
If $(x,y)\in f$, we write $f(x)=y$. An element $x$ is called an original, and $y$ an image.
The set $X$ is called a domain, and the set $Y$ codomain of function $f$.
Three special types of functions are of a particular significance in mathematics: injections, surjection and bijection.

Injection

A function $f:X\longmapsto Y$ is injective or "1-1" function if and only if for each element $x\in X$ there is exactly one element $y\in Y$ for which $f(x)=y$ is valid.

$f:X\overset{1-1}{\longmapsto}Y\overset{def}{=}(\forall x_1,x_2\in X)(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2))$

Surjection

A function $f:X\longmapsto Y$ is surjective or "onto" function if and only if for each element $y\in Y$ there is an element $x\in X$ for which $f(x)=y$ is true.

$f:X\overset{onto}{\longmapsto}Y\overset{def}{=}(\forall y\in Y)(\exists x\in X)(f(x)=y)$

Bijection

A function $f:X\longmapsto Y$ is bijective if it is both injective and surjective.