Sets and their operations

Here you will get introduced to the term of sets and learn how to work with them.
The branch of mathematics dealing with sets is called set theory. It was founded by Georg Cantor (1845-1918) - with influences from Bernhard Bolzano (1781-1848) - and forms the base of our modern understanding of numbers. Only the smallest part of it will be given here (As more isn't needed so far).

Historically it might be interesing to mention that the ancient greek mathematics avoided numbers for their contrariness and used geometry instead to describe and solve most problems (like quadratic equations for example). Cantor himself suffered from an illness of mind caused by so called antinomies of infinite sets/ numbers that he couldn't solve. But it is thanks to him that they have caused one of the biggest crisis of math that deeply influenced modern logic, math and philosophie.
A small example is Russel's Paradox (Betrand Russel - 1872 - 1970) which lead him and A. N. Whitehead (1861 - 1947) to build a complex and confusing system of axioms and deductions (published 1913 as Principia Mathematica) that he thought free of every contradiction.
Kurt Gödel - one of the greatest mathematiscians of not only the 20th century - showed that allmost every system that describes the numbers could be mapped on them itself and is contradicting. Russel couldn't have known that.
One of the major problems of mathematics remains to show if there is a way to describe numbers that is not covered by Gödels Proof and might be non-contradicting.
So far we need to go through set theory and be careful how to build sets.

Sets

Elements, definition and examples

Sets are commonly understood as collections of elements (finit or infinit in number).
They do not need to have any element at all. It even is quiet useful to name an empty or void set: $\emptyset$ .
Usually sets are denoted by capital letters $(A, B, X, Y, ...)$ and elements by small letters $(a, b, x, y, ...)$ .
Of any element $a$ it can be either said that it is element of a set $M (a \in M "a in M")$ or it is no element of $M (a \notin M "a not in M")$ . Elements of a set M can be named like $\{1, 2, 3, 4\}$ or $\{1, 2, 3, ...\}$ if it is clear how to continue.
Generally if $H(x)$ ("H of x") is an condition that could either be true or false for any x you can declare a set like $M := \{x | H(x) is true\}$ or $M := \{x | H(x)\}$ ("M defined by the set of any x where H(x) [is true]").
Here the ":=" stands for "is defined by". You can also write it as "=:" ("defines") as in $\{1, 2, 3\} =: M$ .
Further examples for sets:
$N := \{1, 2, 3, ...\}$ - The set of naturals
$Z := \{0, 1, -1, 2, -2, ...\}$ - The set of integers
$P := \{p | p is prime\}$ - set of primes
$\emptyset := \{\}$ - The empty set or void set

Comparision, inclusion and some implications

If every element x of a set M $(\forall x \in M "every x in M")$ is also element of a set N $(x \in N)$ it can be said that M is included in N (or M ⊂ N - "M sub N" or "M included in N"). They might even be equal.
A much shorter and more mathematical way to say this is:
$M \subset N \Leftrightarrow \forall x \in M \Rightarrow x \in N$
("M is included in N if and only if for each x in M follows that x is in N").

For the implication ⇒ ("implies") the left hand argument is a sufficient condition for the right hand argument (The right side is allways true if the left side is) and the right hand argument is a necessary condition for the left hand one.
With ⇔ both sides are necessary and sufficient and 'if and only if' (or "iff") one side is true, the other is as well.

Of the set N it could also be said that it is a superset of M or N ⊃ M if M is a subset of N (M ⊂ N).
To symbolise that M may be also equal to N sometimes M ⊆ N ("M included in or equal to N") is written.
On the contrary M ⊊ N means that M is included in but not equal to N. (M is than called a proper subset of N, N a proper superset of M).

Now two sets M and N are equal iff M ⊂ N and N ⊂ M.
The sets M and N are called unequal (M ≠ N) if there is an element (at least one) in N (∃ n ∈ N - "it exists n in N") that is not in M or it exists an element in M that is not in N.
$M \neq N \Leftrightarrow \exists m \in M \Rightarrow m \notin N or \exists n \in N \Rightarrow n \notin M$

Operations on sets

The set that contains all common elements of two sets X and Y is called the intersection of X and Y or X∩Y (read "X cap Y" or "X intersect Y").
X∩Y := {x | x∈X and x∈Y}
The set that contains all the elements of either X or Y is called union of X and Y or X∪Y (read as "X union Y" or "X cup Y") and described by
X∪Y := {x | x∈X or x∈Y}
Instead of "and" and "or" offen the logical symbols are used: ∧ for and; ∨ for or.

For a given set of indices I := {1, 2, ...} for every i∈I X_i be a subset of X. The union of all such sets is given by ∪_i∈I X_i:= {x∈X | ∃ i∈I with x∈X_i}
The intersection is given by ∩_i∈I X_i:= {x∈X | ∀ i∈I x∈X_i}
For finite indice sets they are also given as X₁∪...∪X_n and X₁∩...∩X_n.

A set that contains all elements of set X that are not elements of a set Y is defined by: {x | x∈X ∧ x∉Y} =: X∕Y ("X minus Y" or "X setminus Y") and called the differenz of X and Y or X−Y.
The symmetric difference of two sets is given by X∆Y := (X∪Y)∕(X∩Y) (read: "X triangle Y").
Further the sets X and Y are called disjoint if X∩Y=∅ - They do not share any element.

Equivalence relations and classes

For a set X ℘(X) (the powerset of X) is defined by: ℘(X) := {Y | Y⊂X} and contains every subset of X.
℘(X) is called a partition iff for every X_i, X_j ∈℘(X), i≠j ⇒ X_i∩X_j=∅ and ∪_i∈IX_i=X
Are x and y elements of X and x∈X_i than x˜y means that y∈X_i too and it is said that "x is equivalent to y".
The relation ˜ is:
(E 1) reflective: $x ˜ x$
(E 2) symmetric: $x ˜ x \Rightarrow y ˜ x$
(E 3) transitve: x˜y, y˜z ⇒ x˜z
Such a relation E1-E3 are true for is called a equivalence relation. S_x := {y ∈ X | y ˜ x} is a subset of X. Two such sets S_x and S_y are either disjoint or equal and the union of all S_x∈X is X again. These so called equivalence classes form a partition of X.

Russel's Paradox

Definition: A set is called normal if it does not contain itself. (M ∉ M ⇒ M is normal).
Be M the set that contains all normal sets.
Is M normal?
Supposed M is normal: M ∉ M ⇒ M ∈ M since M does contain all normal sets.
On the other hand: is M not normal ⇒ M ∉ M and is thus normal again and does contain itself (or M ∈ M).
Short: M ∈ M ⇕ M ∉ M