Notes on a (very) Elementary Set Theory—Part II

1 Intersection, Difference, (unordered) Pair,

and Union

Now that we have the axiom of subsets we can introduce intersections.

Definition 1.1 (Intersection). For a any two set variables S, T, the symbol S ∩ T stands for {x|x ∈ S ∧ x ∈ T }. If S ∩ T = ∅, then we say that S and T are disjoint. ■

In view of the axiom of subsets (Part I, 2.18), taking x ∈ S as “A” in the axiom, we see that S ∩ T is always a set. Thus the “stands for” in 1.1 can be replaced by “=”.^{1}

Example 1.2. If S = {1, {2}} and T = {1, 2} then S ∩ T = {1}. If R = {5, 6}, then S ∩ R = ∅. ■

One often sees a shorthand notation for {x|x ∈ S ∧ x ∈ T }. Either {x ∈ S|x ∈ T } or {x ∈ T |x ∈ S} are common.

Proposition 1.3. S ∩ T ⊆ T and S ∩ T ⊆ S are theorems.

Proof. I want (∀x)(x ∈ S ∩ T ⇒ x ∈ T). By definition 1.1 and sWLUS this means the same as (∀x)(x ∈ S ∧ x ∈ T ⇒ x ∈ T). But this is in Ax1.

Ditto for the second part of the proposition. ■ One can generalize the concept of intersection. Suppose we have a set

of sets F = {S, S′, S′′, …}. By the way, we call a set of sets—that is, a set that contains no atoms—a family of sets. We define, intuitively speaking, ⋂ F to mean S ∩ S′ ∩ S′′ ∩ …

To make sure that this is done right^{2} we move away from an attempt to (incompletely) list the members of F and define:

1In case this last comment sounds cryptic, recall that “=” is a formal logical symbol.

Our theory allows sets and atoms only, not any non-set collections—for example, we do not have any axioms for such collections. Thus, we must allow “=” to connect only acceptable objects.

2Fine Print: Writing F = {S, S′, S′′, …} unduly restricts what F might be. It implies either a finite family like, say, {{1}, {1, 2}} or one whose members can be associated with unique natural numbers, because we can think of the absence of a prime as the index (subscript) 0, and n primes as the subscript n. Such a family, whose members we can name using a single name “S” and primes, continuing without end, would be, e.g., the

1. INTERSECTION, DIFFERENCE, (UNORDERED) PAIR, AND UNION

Definition 1.4 (Generalised Intersection). If F is a family of sets, ⋂ F —the intersection of the family—stands for

{x|(∀S ∈ F)x ∈ S}  (1)

where “(∀x ∈ y) …” is commonly used shorthand for “(∀x)(x ∈ y ⇒ …)”.

■

In words, (1) collects all x that satisfy: For every S ∈ F, x is in S. In plain English, it collects all the x that are common to all S found in the family F.

When is ⋂ F a set (i.e., not too big, and not too complicated)?

Suppose that F ≠ ∅. Then there is a T ∈ F —maybe there are quite a few such members in F, but let us fix attention to one.^{3} This T is a set, not an atom (why?). We can prove now

(∀S ∈ F)x ∈ S ⇒ x ∈ T  (2)

Indeed, (∀S ∈ F)x ∈ S translates to (∀S)(S ∈ F ⇒ x ∈ S). Now, specialisation yields

T ∈ F ⇒ x ∈ T  (3)

Since the lhs of ⇒ in (3) is given, we get the rhs by MP, and thus are done. With (2) out of the way, we get from A ⇒ B ⊧_{taut} A ∧ B ≡ A that

ST ⊢ (∀S ∈ F)x ∈ S ∧ x ∈ T ≡ (∀S ∈ F)x ∈ S  (4)

Now

“⋂ F is a set”  (5)

is short for (∃y)y = ⋂ F, or more symbolically^{4}

(∃y)(∀x)(x ∈ y ≡ (∀S ∈ F)x ∈ S)  (6)

So, I can prove (5) iff I can prove (6). But I can prove (6)! Here it goes:

family of rational number sets, {{1}, {1/2}, …, {1/n}, …}.

However, if I want a family that contains precisely the sets {r} for every real number r, I am told by Cantor that I cannot use natural number subscripts, or, equivalently, primes to indicate all these sets with names such as S, S′, S′′, …

3I am arguing informally. The exactly corresponding formal argument would take T ∈ F as an auxiliary assumption, T being the auxiliary “fresh” variable introduced.

4Review definition 1.4 and also definition 2.2 in Part I.

Notes on a (very) Elementary Set Theory\begin{matrix}c \\ ◯ \end{matrix}George Tourlakis, 2003  Page 2

1. INTERSECTION, DIFFERENCE, (UNORDERED) PAIR, AND UNION

First off, (6) equivales to

(∃y)(∀x)(x ∈ y ≡ (∀S ∈ F)x ∈ S ∧ x ∈ T)  (7)

by (4) and sWLUS. But (7) says in plainer English:

“{x|(∀S ∈ F)x ∈ S ∧ x ∈ T } is a set”

which is correct by the axiom of subsets (take “(∀S ∈ F)x ∈ S” as the “A” in the axiom).

Now that we know that F ≠ ∅ implies that ⋂ F is a set, we are allowed to replace, under the circumstances, the “stands for” in definition 1.4 by “=”.

Exercise 1.5. What about the case where F = ∅? What is ⋂ F in that case? Is it a set? ■

Definition 1.6 (Set difference). For a any two set variables S, T, the symbol S − T stands for {x|x ∈ S ∧ x ∉ T }. ■

Again, the “x ∈ S ∧ ” part in the set term, along with the axiom of subsets guarantees that S−T is a set. Here are three examples of difference: {1, 2} − {3, 4} = {1, 2}, {1, 2} − {1} = {2} and {1, 2} − {1, 2, 3} = ∅.

A concept related to difference is that of complement. If you fix a set S and call it your relative (as opposed to the absolute, 𝕍) universe then S − T —taking S for granted—is denoted by many different symbols, among which T′ and \overline{T} are common. It is called the complement of T (with respect to S) but the parenthetical qualification is omitted since S is taken for granted.

Examples of relative universes are ℕ (the universe of the number theorist), ℝ (the universe of the analyst).

All along we gave examples such as {1, 2} and {1, 2, 8} and we took it for granted that they are simple enough to be sets. Indeed, axiomatic set theory makes this official by making it an axiom, the axiom of the (unordered) pair.

If we took it for granted, then why take it as an axiom?

Well, axioms codify the simple believable “truths” that we take for granted. Based on these few truths (nonlogical axioms) and logic we discover more truths by reasoning. That’s why. (We did the same thing with even “simpler” “truths” such as x = x, taking this one as a logical axiom.)

1. INTERSECTION, DIFFERENCE, (UNORDERED) PAIR, AND UNION

Axiom 1.7 (Unordered pair). For any variables z, w (of type set or atom), the collection {z, w} means {x|x = z ∨ x = w} and is a set.

Eliminating free variables and saying “is a set” symbolically, we express the axiom as

(∀z)(∀w)(∃y)(y = {z, w})  (1)
■

This allows us to write {z, w} = {x|x = z ∨ x = w}.

Example 1.8. This new axiom now tells us that we are all right using sets such as {1}, {2, 1}. For example, use specialization on (1) with z := 1 and w := 1 to get the first claim. Use z := 2 and w := 1 to get the 2nd claim. ■

But what about {1, 2, 3}? One may amend the axiom, define {a, b, c} as {x|x = a ∨ x = b ∨ x = c} and add that this is a set. Ditto for {a, b, c, d} etc.

However, a more elegant approach is to wait until we can form unions, which is what we do next.

Definition 1.9 (Union). For any two set variables S and T, S∪T —called the union of S and T —stands for the collection {x|x ∈ S ∨ x ∈ T }. ■

That is, transfer into one “big bag”, S ∪ T, everything contained in S and T.

Our axioms so far don’t help to prove that the “bag” S∪T is a set (i.e., not “too big”). It can be argued on philosophical grounds—for example if one adopts the suggestion of Russell’s that sets are formed in stages, by increasing the nesting level of braces stage by stage—that the union is not that much more complicated or that much larger than its ingredients, S and T, and is thus “safe” (i.e., contradiction-free) to postulate that unions of sets are sets.

We can do that right away, but we will rather adopt a slightly more general axiom. But first

Example 1.10. The axiom of pair allows us to form {1, 2} and {3} as sets. The axiom of union will allow us to conclude that {1, 2} ∪ {3} is a set. But that is {1, 2, 3}. We can obviously continue this as far as we please and show that collections such as {1, 2, 3, 4} and {11, 0, −5, 6, 1000} are sets. ■

1. INTERSECTION, DIFFERENCE, (UNORDERED) PAIR, AND UNION

Definition 1.11 (Generalised Union). If F is a family of sets, then the symbol ⋃ F —the union of the family—stands for

{x|(∃S ∈ F)x ∈ S}

where “(∃x ∈ y) …” is short for “(∃x)(x ∈ y ∧ …)”. ■

Thus, ⋃ F is a container that contains every single x that you can find inside the members of the family F.

For example, ⋃{{1}, {1, {2}}} = {1, {2}}.

Axiom 1.12 (Union Axiom). Let F stand for a family of sets and S and T be set variables. Then both ⋃ F and S ∪ T are sets. ■

Now that we know that ⋃ F and S ∪ T are sets we can replace the “stands for” in definitions 1.9 and 1.11 by “=”.

Example 1.13. We prove here what we must have suspected all along if we reflected about a minute or so on definitions 1.9 and 1.11. That for any set variables S and T,

⋃{S, T } = S ∪ T  (1)

Here it goes 1. FOUNDATION, AND POWER SET

⋃{S, T } = ⟨by definition 1.11⟩ {x|(∃Y)(Y ∈ {S, T } ∧ x ∈ Y)} = ⟨ST ⊢ (∀x)(A ≡ B) ≡ {x|A} = {x|B} and sWLUS; def. 1.7 and ∈-elim.⟩ {x|(∃Y)((Y = S ∨ Y = T) ∧ x ∈ Y )} = ⟨tautology, sWLUS & ST ⊢ (∀x)(A ≡ B) ≡ {x|A} = {x|B}⟩ {x|(∃Y)((Y = S ∧ x ∈ Y) ∨ (Y = T ∧ x ∈ Y))} = ⟨∃ − ∨, sWLUS & ST ⊢ (∀x)(A ≡ B) ≡ {x|A} = {x|B}⟩ {x|(∃Y)(Y = S ∧ x ∈ Y) ∨ (∃Y)(Y = T ∧ x ∈ Y)} = ⟨1pt-rule, sWLUS & ST ⊢ (∀x)(A ≡ B) ≡ {x|A} = {x|B}⟩ {x|x ∈ S ∨ x ∈ T } = ⟨definition 1.9⟩ S ∪ T

■

One proves similarly that ⋂{S, T } = S ∩ T.

2 Foundation, and Power set

The next axiom says that sets are not “bottomless”. They are (well) founded. Thus it is called the axiom of foundation. Axiom 2.1 (Foundation). It is impossible to have an endless-to-the-left chain

… a_{3} ∈ a_{2} ∈ a_{1}  (∗)

where all the a_{i} are sets. ■ We will see when we study relations that condition (∗)—which is not a

formula, as, for one thing, it has infinite length—can be recast as a formula without free variables, namely

2. FOUNDATION, AND POWER SET

(∀y)((∃x)x ∈ y ⇒ (∃x)(x ∈ y ∧ ¬(∃z)(z ∈ x ∧ z ∈ y)))

Example 2.2. Equipped with the foundation axiom we can prove that ST ⊢ ¬x ∈ x, i.e., ST ⊢ x ∉ x for any variable x. Indeed, if the opposite were true and we could have x ∈ x, then repeating the pattern we would also have the infinite sequence … ∈ x ∈ x ∈ x ∈ x. This contradicts 2.1.

Similarly, x ∈ y ∈ x is impossible (contradictory) for otherwise we would have … x ∈ y ∈ x ∈ y ∈ x ∈ y ∈ x.

By the way, there is nothing wrong with an infinite to the right chain, such as 1 ∈ {1} ∈ {{1}} ∈ {{{1}}} ∈ … ■

Example 2.3. As an application, we see that 𝕍, the absolute universe, is not a set. Well suppose it is a set. Then we can use half of the Extensionality theorem (the logical half) starting with 𝕍 = {x|true} and get

(∀x)(x ∈ 𝕍 ≡ x ∈ {x|true})

sWLUS and ∈ elimination give us the equivalent

(∀x)(x ∈ 𝕍 ≡ true)

Specialisation yields 𝕍 ∈ 𝕍 ≡ true, hence (redundant true) 𝕍 ∈ 𝕍. However, by foundation, no set satisfies this last relation. ■

We finally turn to an operation that builds much bigger sets than we started with, but still builds sets—nothing “too” big or too complicated.

We need a definition and an axiom:

Definition 2.4 (Power Set). For any set variable S we let the symbol “𝒫(S)” stand for the collection {x|x ⊆ S}. ■

Example 2.5. Thus, intuitively, 𝒫({1, 2}) = {∅, {1}, {2}, {1, 2}}. ■

Axiom 2.6. For any set variable S, 𝒫(S) is a set. In particular this allows us to write 𝒫(S) = {x|x ⊆ S} ■

The above says that if S, y are of type set, then

(∀S)(∃y)y = {x|x ⊆ S}

or, in more detail (using 2.2 of Part I)

(∀S)(∃y)(∀x)(x ∈ y ≡ x ⊆ S)

Example 2.7. ST ⊢ S ∈ 𝒫(S) where S has type set. Well, the formula translates to S ∈ {x|x ⊆ S}. Using ∈-elimination, this is the same as S ⊆ S which we have proved before. ■

Example 2.8. ST ⊢ 𝒫(∅) = {∅}. We want to prove

{x|x ⊆ ∅} = {∅}

or, bringing both sides into “{x|A} format”

{x|x ⊆ ∅} = {x|x = ∅}  (1)

From the fundamental theorem on the equality of sets expressed in {x|A} format (see Part I, 2.7) we prove (1) by proving

(∀x)(x ⊆ ∅ ≡ x = ∅)  (2)

Since no axiom in ST has free variables, I can prove (2) if I simply prove the quantifier-free formula x ⊆ ∅ ≡ x = ∅. But this is equivalent to

x ⊆ ∅ ∧ ∅ ⊆ x ≡ x = ∅  (3)

since I already have the theorem ∅ ⊆ x and I can use redundant true and Leibniz. However, (3) holds by extensionality theorem (see proposition 2.13, Part I). ■

We conclude Part II of these notes with an informal example that assumes we have access to theory of numbers and set theory simultaneously.

Example 2.9. Let us understand that a set S is finite with n elements, or with \underline{cardinality n}—in symbols |S| = n—either if n = 0 and S = ∅, or n > 0 and S = {a_{1}, a_{2}, a_{3}, …, a_{n}} where for all i, j, if i ≠ j, then a_{i} ≠ a_{j}.

We will prove informally (assuming a lot that we have not introduced axiomatically) that

If |S| = n, then |𝒫(S)| = 2^{n}  (1)

We look at two cases, as in the definition of |S|: Case 1. n = 0. Then S = ∅ and 𝒫(S) = {∅} by 2.8. But {∅} has the form

{a_{1}}, hence |𝒫(S)| = 1 = 2^{0}. OK! Case 2. Let n > 0 and S = {a_{1}, a_{2}, … a_{n}}. Note that every subset T of S

can be uniquely coded by a binary string of length n.

Indeed, the coding is as follows: The string has a 0 in position i (where 1 ≤ i ≤ n) iff a_{i} ∈ T. For example, the string that is all 0’s codes S (of course, S ⊆ S). The string that is all 1’s codes ∅. What does the string below code?

010 \underbrace{1 … 1}_{all 1’s} 0

Answer: {a_{1}, a_{3}, a_{n}}. Now, to count how many members we have in 𝒫(S) we just count how many subsets S has. By the discussion above this boils down to how many strings of length n > 0 we have. Well, we can fill each string position in exactly two ways (0 or 1) independently of what we have done or will do in any other position. Thus we have

\underbrace{2 · 2 · 2 · . . . · 2}_{n factors} = 2^{n}

ways in total. By the way, this little theorem motivates people to sometimes use an alternative symbol for 𝒫(S). They use “2^{S}”. Note that this is just a name; just notation (at least in this course…)

■