The aim of this chapter is to introduce elements of the algebra of sets, which is a part of the set theory. The theory came into being at the end of the 19th century. It is considered to be fathered by German mathematician George Cantor. Nowadays, the theory of sets is recognized to be the base of mathematics, and moreover a very important part of the mathematical foundations of computer science. The basic notion of this theory is a set. We are not going to precisely define it, although, in the last part of this lecture, there is a short information about the formal approach to the set theory. In the presented lecture we would like to address the readers intuition, we will discuss several examples of sets and applications. Furthermore, we will talk about the operations on sets, and about the laws that govern them. Any set with operations defined on it is sometimes called the algebra. Hence, the lecture is called "The algebra of sets".

The laws of union, intersection, and complementation are not enough to characterise the notion of a set. In general, the formal definition of a set is not necessary to operate on sets. Although the intuition is sometimes missleading. The unrestricted use of the intuitive definition of a set may lead to paradoxes (antinomies). Russell's paradox is the most famous of the set-theoretical paradoxes.

Russell's Paradox

Let Z be the set of all sets that are not members of themselves. Is the set Z a member of Z?
By the definition of the set Z, Z = {X : X ∉ X}. Hence for every A,

A ∈ Z iff A ∉ A.

Let us take A = Z, Z ∈ Z iff Z ∉ Z iff it is not the case that Z ∈ Z. Hence the paradox.

Russell's paradox may be formulated in several equivalent ways. One of them is known as The Barber of Seville paradox. It can be reworded as follows: every man in Seville is shaved by the barber of Seville, if and only if he does not shave himself. Does the man who is the barber shave himself? If the man who is the barber does not shave himself, then he is shaved by the barber, who is himself, so he does shave himself. Yet if the barber does shave himself, then he is shaved by the barber, but according to the statement the barber only shaves those who do not shave themselves, so he does not shave himself. No matter how we approach the question, the result is self-contradictory.

The paradox caused a turn away from the intuitive set theory of Cantor. An alternative approach was developed by David Hilbert, Ernst Zermelo, and others who drew up a formal apprach to the set theory. In the formal theory one can use only the assumed basic notions and the rules of composing them. The theorem is derived from the given axioms by strictly defined inference rules. It allows to avoid paradoxes.
The axiomatic set theory was first proposed by Zermelo in 1904 and then developed by Fraenkel, Gödel and others. The laws of the algebra of sets, mentioned in this lecture, are the core of the so-called Zermelo-Fraenkel'theory.

"For each non-empty family of non-empty sets there is a set that has exactly one common element with each element of the family".

The wording of the axiom itself seems not to arouse uneasiness. However, its acceptance or denial has serious consequences in the theory of  sets. The theorems in whose proof the axiom of choice is used are called uneffective.
The reader who would like to learn more about set theory should read the monography by A.Mostowski and K.Kuratowski, Set theory (Warsaw, 1966).