Set theory

Suppose we have a predicate φ(x) with a domain D. It seems quite natural to group all x from D which satisfy φ together to form a new object. For example, if φ(x) means x is even and D means all natural numbers, such an object would be ‘all even natural numbers’. Clearly, this is a ‘part’ of the domain D carved by the property φ (also known as the extension of the predicate φ). Such a ‘part’, which may consist of many individuals (e. g., numbers) but is to be treated as a unitary object, is an example of what mathematicians call a set.

Intuitively, a set is an assembly (collection, multitude) of some individuals of arbitrary nature. Clearly, this does not comprise a rigorous definition since assembly and objects are still to be defined. The main mission of the notion of set is to be the uniform object of mathematics, generalizing numbers of various kinds (integer, real, complex etc.), functions, geometric figures and many others.

Apparently, we cannot define such a basic notion via any other. However we can avoid any definition but postulate some rules how sets do ‘behave’. Thus, set is nothing more than a code name for a piece in our game, whose ‘meaning’ is just its part in the game rules. (Much like a bishop in the game of chess retaining the very same ‘meaning’ if we call it an elephant or an officer.) This is the essence of the axiomatic method.

Yet which behavior of sets do we define? Basically, one set A can be an element of another set B. Then we also say that A belongs to B and write A ∈ B. Intuitively, this means that the ‘individual’ A is in the ‘collection’ B. But do not allow this intuition to fool you: our sets are just an abstract model (of mathematical or other realities) and are fully entitled to behave counter-intuitively.

For example, in our model everything is a set, which is not in a good accord with the ‘individual– collection’ interpretation because there is no essential difference between the former and the latter.

Hence, any element of any set is a set itself having some sets as elements and so on. We shall see that there exists an empty set that has no elements at all. But anyway, we postulate that there are no infinite chains of the form (x_0)∋(x_1)∋…∋(x_n)∋(x_n+1)∋…. A statement quite clode to this (yet not the same) is called the Axiom of Foundation.

The statement a∈a holds for no set a. Otherwise, there would be the chain a∋a∋a∋….

Lemma 1. For all sets A, B, and C,

1. A ⊆ A;

2. if A ⊆ B and B ⊆ C, then A ⊆ C;

3. A = B iff A ⊆ B and B ⊆ A.

Proof. Let’s prove just the second statement. We need to show that x∈C for all x∈A. Consider an arbitrary set x and assume that x∈A. Then x∈B holds as A⊆B. Likewise, by B⊆C, we get x∈C. Since for an arbitrary x, from x∈A it follows that x∈C, this is true for all x.

Corollary. For all sets A, B, and C,

1. A = A;

2. if A = B and B = C, then A = C;

3. if A = B, then B = A.

Are there any sets in existence? Obviously, if there weren’t any, our model would make no sense. We won’t seek a formal reason for this, but rather assume that there exist the well-known sets N = {0, 1, 2, . . .} of natural, Z of integer, Q of rational, and R of real numbers. Of course, their elements have to be sets themselves. E. g., 1 and 2 are some sets. We omit the definitions yet we take for granted some elementary properties, like 1 6= 2. In other words, we avoid using the internal structure of natural numbers (e. g., whether 1 ∈ 2 or not), but assume that 1 6= 2, 2 < 3, 2 + 3 = 5 etc.

If we have some sets (like N and Z), can we define any other? Indeed, the most important mission of our model is to provide (hopefully) safe ways to do so. (Here safe means logically consistent; the explanation shall follow).

“Out of many, one.” Let (a_1),…,(a_n) be some sets. Then there exists a set {(a_1),…,(a_n)} such that x ∈ {a1, . . . , an} ⇐⇒ x = a1 ∨ x = a2 ∨ . . . ∨ x = an for each set x.

Subset specification. Let us recall that we write φ(x) if x satisfies a property (or predicate) φ. For example, even(2) means that the number 2 satisfies the property to be even, i. e., 2 is even. Let A be a set and φ be some property. Then there exists a set {x ∈ A | φ(x)} such that y ∈ {x ∈ A | φ(x)} ⇐⇒ y ∈ A ∧ φ(y) for all y. In other words, we pick up and put together all the elements of A satisfying φ. Clearly, {x ∈ A | φ(x)} ⊆ A.

Symbols like {x ∈ A | φ(x)} are widely known as set-builder notation.

As was mentioned before, x = x for each x. By definition, x ≠ x for each x ∈ ∅. Hence, there is no x such that x ∈ ∅. A set E is called empty (or void) if x /∈ E for all x. Thus, the set ∅ is empty. Is there any other empty set?

Lemma 2.

1. If E is an empty set, then E ⊆ A for each set A.

2. If sets E1 and E2 are empty, then E1 = E2.

Hence, we have a corollary from lemma 2, which states: The set ∅ is the unique empty set.

Sets and predicates.

As we have just seen, the subset specification principle allows to form a set of all those elements of some given set A which satisfy a predicate φ. This is one of the most important ideas behind sets indeed. Often, we will replace predicates with sets in mathematical arguments.

For example, assume that we want to formalize the statement “every even number equals the sum of two odd numbers”. Stating from the formalization
∀x*(2|x→∃y∃z(2∤y∧2∤x∧x=y+z)),
we may transform it to
∀x*(x∈A→∃y∃z(y∈B∧z∈B∧x=y+z)),
where A and B stand for the sets of even and odd numbers, respectively. Please notice how “satisfying a predicate” has been replaced by “belonging to a set” here. Usually, they would employ a more concise notation (so called bounded quantifiers) in this case:
∀x ∈A∃y ∈B ∃z ∈B*(x=y+z)
(to be read as “for each x from A there exist y and z from B such that. . . ” which sounds very intuitive and natural, does not it?).

Bounded quantifiers come in many varieties (∀x ∈ A, ∀x < 10, ∃x > 10, etc.) but it is important to realize that bounded universal quantifier means implication, while bounded existential quantifier means conjunction. Formally,
∀x ∈A φ≡∀x*(x∈A→φ) and ∃x ∈A φ≡∃x*(x∈A∧φ)

Clearly, we can only specify subsets of a given set A via {x ∈ A | φ(x)}. But could not we put together all x in existence (i. e. not only from A) such that x satisfies φ? Historically, this was the first intuition backing the notion of set: any collection of objects having something in common or satisfying some property.
As we shall see in a moment, this intuition proves to be logically inconsistent.
Russell's Paradox. There is no set R such that ∀x*(x∈R⇔x∉x).
Proof. Suppose there is such a set R. At first, assume R ∉ R. By the constraint on R, this implies R ∈ R. By contradiction, R ∉ R must be false, so we have proved R ∈ R (assuming the existence of R). But thenR∉R by the same constraint on R. Thus, the assumption that such R exists is contradictory. Hence, it does not exist.

So, one cannot define a set {x | x ∉ x} comprising all sets x satisfying quite a natural condition x ∉ x. This very fact was seen as paradoxical and counter-intuitive.

Power set. Let A be a set. Then there exists a set P(A) such that x ∈ P(A) ↔ x ⊆ A for all x. In other words, P(A) is the set of all subsets of the set A.
As ∅ ⊆ A, ∅ ∈ P(A) for any set A. We have P(∅) = {∅}, P(1) = {∅, {1}}, and P({1, 2}) = {∅, {1}, {2}, {1, 2}}. Note that {1, 2} has 2 elements, while P({1, 2}) has 4 = 22 elements, P(∅) has 1 = 20 elements, and P({1}) has 2 = 21 elements. This analogy between power sets and numeric powers of 2 is not a coincidence.

Union. Let A be a set. Then there exists a set ∪A such that x ∈ ∪A ↔ ∃α (x ∈ α ∧ α ∈ A) for all x. Thus, ∪A is the set of elements of elements of the set A.

Algebra of sets.

For arbitrary sets A and B, by A ∪ B we denote the set ∪{A, B}, which is called the union of the sets A and B. It is easy to prove that x ∈A∪B↔x ∈A ∨x ∈B for any x. Indeed,
x ∈ A ∪B ⇔x ∈∪{A,B}
⇔∃α*(x∈α∧α∈{A,B})
⇔∃α*(x∈α∩(α=A∨α=B)) ⇔∃α((x∈α∧α=A)∨(x∈α∧α=B))
⇔∃α(x∈α∧α=A) ∨∃α(x∈α∧α=B)
⇔x ∈A∨x ∈B.
Also, we define the intersection A∩B={x∈A|x∈B} and the difference A ∖B={x∈A|x∉B} of sets A and B. Clearly, x ∈ A ∩ B ⇔x ∈ A ∧ x ∈ B for any x. We say that the set A intersects B if A ∩ B ≠ ∅. Otherwise, these sets are called disjoint.

Lemma 3. For any sets A and B, one has A ∩ B ⊆ X ⊆ A ∪ B if X ∈ {A, B}. Also, A ∖ B ⊆ A and (A∖B) ∩ B = ∅.

Lemma 4. For any sets A and B, the following statements are equivalent:
1. A ⊆ B;
2. A ∩ B = A;
3. A ∪ B = B.
Proof. It suffices to show that the first one implies the second, the second implies the third, and the third one implies the first statement.
Suppose that A ⊆ B. By Lemma 3, we get A ∩ B ⊆ A. Let us check if A ⊆ A ∩ B. Consider an arbitrary x ∈ A. Then x ∈ B as A ⊆ B. Hence, x ∈ A ∩ B. By Lemma 1, from A ∩ B ⊆ A and A ⊆ A ∩ B it follows that A ∩ B = A.
Now assume that A ∩ B = A. By Lemma 3, B ⊆ A ∪ B. It remains to prove that A ∪ B ⊆ B. If x ∈ A ∪ B, then x ∈ A or x ∈ B. In the former case, obtain x ∈ A ∩ B from A = A ∩ B, whence x ∈ B. In the latter one, x ∈ B is immediate.
Finally, suppose that A ∪ B = B. By Lemma 3, we have A ⊆ A ∪ B. By assumption, we get A ∪ B ⊆ B, hence A ⊆ B.

Let's set algebra identities. For all sets U and A, B, C ⊆ U:
1. A ∩ B = B ∩ A; A ∪ B = B ∪ A;
2. (A ∩ B) ∩ C = A ∩ (B ∩ C); (A ∪ B) ∪ C = A ∪ (B ∪ C)
3. A ∩ A = A; A ∪ A = A;
4. A ∩ (A ∪ B) = A; A ∪ (A ∩ B) = A;
5. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
6. A ∩ ∅ = ∅; A ∪ ∅ = A;
The proof is just a rephrasing of logical equivalences for conjunction, disjunction, and negation, which follow from the respective truth tables.

Cartesian product. Most branches of mathematics employ ordered “pairs”, “triplets” etc. E. g., points of the plain are routinely identified with their coordinates, whose order does matter. Indeed, (0, 1) and (1, 0) are distinct points. While sets themselves do not respect any “order of the elements” (as {2, 3} = {3, 2}), ordered pairs can be easily modeled using sets.
For arbitrary sets a and b consider the set (a, b) = {{a}, {a, b}}, which is called an (ordered) pair of sets a и b. The main property of such a pair is the following:
For all sets a, b, c, d, (a, b) = (c, d) ⇐⇒ a = c ∧ b = d.
Proof. Assume that {{a}, {a, b}} = {{c}, {c, d}}. Then {a} ∈ {{c}, {c, d}}, i. e., {a} = {c} or {a} = {c, d}. In the first case, a ∈ {c}, hence a = c. In the second case, c ∈ {a} and c = a again. Thus, a = c.
From the assumption, it also follows that {a, b} = {c} or {a, b} = {c, d}.
In the former case, b ∈ {c}, whence b = c = a. By the assumption, {c, d} = {a} or {c, d} = {a, b}. Therefore, d = a or d = b. Anyway, b = d.
Now suppose that {a, b} = {c, d}. If d = b, there is nothing to prove. Otherwise, d = a = c, i. e., {a, b} = {d}, whence b = d again.
For the other implication, it suffices to recall that equal sets are fully interchangeable; so, from (a, b) = (a, b), a = c and b = d, it follows that (a, b) = (c, d).