3.2 Set theory[1YT]

Naive set theory[242]

As already explained in Definition 24, in set theory, the connective "\(\in \)" is added; given two sets \(z,y\) the formula \(x\in y\) reads ”\(x\) belongs to \(y\)” or more simply ”\(x\) is in \(y\)”, and indicates that \(x\) is an element of \(y\).

It is customary to indicate the sets using capitalized letters as variables.

[226]This says that two sets \(a\) and \(b\) are equal when they have the same elements; that is, it excludes that a set can have some other property that distinguishes it  ¹ .

It is usual to write \(x\notin y\) for \(\lnot (x\in y)\), \(x\nsubseteq y\) for \(\lnot (x\subseteq y)\) and so on.

We also define the constant \(\emptyset \), also referred to as \(\{ \} \), which is the empty set, ² that is uniquely identified by the property

Some fundamental concepts are therefore introduced: union, intersection, symmetric difference, power set, Cartesian product, relations, functions etc.

The power set is defined as in 5.

E33

[1W6](Proposed on 2021-10-18) Prove that \(A=B\) if and only if \(((A⊆ B) ∧ (B⊆ A) )\). Hidden solution: [UNACCESSIBLE UUID ’1W7’]

E33

[1W8]Represent operations

• \(∪\) union

• \(∩\) intersection

• \(\setminus \) difference

• \(Δ\) symmetrical difference

between two sets using Venn diagrams.

E33

[1W9]Prerequisites:2.Use the above Venn diagrams to show that in general \((A∪ B)∩ C ≠ A∪ (B∩ C)\).

E33

[1WB] Show that if \(X⊆ Y\) and \(Y⊆ Z\) then \(X⊆ Z\) Hidden solution: [UNACCESSIBLE UUID ’1WD’]

E33

[1W2]Explain why the union operation \(A∪ B\) between two sets is commutative, and show that it is associative; similarly for the intersection; finally show that the union distributes over the intersection, and also that the intersection distributes over the union. Hidden solution: [UNACCESSIBLE UUID ’1W3’]

E33

[1WF](Proposed on 2022-12) Consider the sets:

• \(P\) all the professors,

• \(S\) all scientists,

• \(F\) the set of philosophers,

• \(M\) the set of mathematicians.

For each of the following sentences, write a formula that represents it, using the above sets, the empty set, relations \(⊆,=,≠\), and set operations \(∪,∩,⧵\).

• not all professors are scientists

• some mathematician is philosopher;

• if a philosopher is not a mathematician then s/he is a professor;

• all philosophers are scientists or professors, but not mathematicians;

• if there is a mathematician who is also a scientist, then s/he is neither a philosopher nor a professor.

Hidden solution: [UNACCESSIBLE UUID ’1WG’]

E33

[1Y4]Let \(U\) be the set of human beings, \(A\) the set of animals and \(M\) the set of mortal creatures; convert the following syllogism into formulas and prove it:

every man is an animal, every animal is mortal, therefore every man is mortal.

E33

[1WC] Explain the formula \(⋃_{B∈{\mathcal P}(A)} B\) using the definition 31 of the axiom of union. Then show that \(A=⋃_{B∈{\mathcal P}(A)} B\).

See also 5 where the same result is obtained starting from the axiom of union as defined in 4 in the Zermelo–Fraenkel axiomatic.

Hidden solution: [UNACCESSIBLE UUID ’1WV’]

E33

[24P]Let \(I,C_ i\) as in 31 and let \(A\) be a set; prove that

\[ ⋃_{i∈ I}C_ i \subseteq A \]

if and only if 

\[ \forall {i∈ I} , ~ C_ i \subseteq A~ . \]

While in formal theory all the elements of language are sets, in practice we tend to distinguish between the sets, and other objects of Mathematics (numbers, functions, etc etc); for this in the following we will generally use capital letters to indicate the sets, and lowercase letters to indicate other objects.

Zermelo–Fraenkel axioms[241]

We now briefly discuss the axioms of Zermelo–Fraenkel set theory.

1. Axiom of extensionality, already seen above in 28.

2. [014]The empty set \(\emptyset \) is a set. The formula for this axiom is

   \[ ∃ X : ∀ Y ¬(Y ∈ X) \]

   and by the preceding axiom, \(X\) is unique, so it is denoted by \(\emptyset \).

3. [1Y3] Axiom of pairing. Given any two sets \(X\) and \(Y\) there exists a set \(Z\), denoted by \(Z=\{ X,Y\} \), whose only two elements are \(X\) and \(Y\). In formula

   \[ ∀ X, Y ∃ Z : ∀ W (W ∈ Z) \iff (W = X) ∨ (W = Y )\quad . \]

   Again, by the axiom of extensionality 28, the set \(Z\) unique.

4. [026] The axiom of union ⁵ says that for each set \(A\) there is a set \(B\) that contains all the elements of the elements of \(A\); in symbols,

   \[ ∀ A ∃ B, ∀ x, (x∈ B \iff (∃ y,y∈ A ∧ x∈ y))~ ~ . \]

   This implies that this set is unique, by the axiom of extensionality 28; we indicate this set \(B\) with \({\underline⋃} A\) (so as not to confuse it with the symbol already introduced before).

   For example if

   \[ A = \{ \{ 1,3,\{ 5,2\} \} , \{ 7,19\} \} \]

   then

   \[ {\underline⋃}A = \{ 1,3,\{ 5,2\} , 7,19 \} \quad . \]

   Given \(A_ 1,\ldots A_ k\) sets, let \(D=\{ A_ 1,\ldots A_ k\} \) ⁶ we define

   \[ A_ 1∪ A_ 2\ldots ∪ A_ k {\stackrel{.}{=}}{\underline⋃}D \quad . \]

5. [1Y1] The axiom of the power set says that for every set \(A\), there is a set \(\mathcal{P}(A)\) whose elements are all and only subsets of \(A\). A shortened definition formula is

   \[ {\mathcal P}(A){\stackrel{.}{=}}\bigl\{ B:\ B⊆ A\bigr\} \quad . \]

   \(\mathcal{P}(A)\) is also called set of parts.

   In the formal language of the Zermelo-Fraenkel axioms, the axiom is written:

   \[ ∀ A, ∃\; Z, ∀ y , y ∈ Z \iff (∀ z, z ∈ y \implies z ∈ A)\quad ; \]

   this formula implies that the power set \(Z\) is unique, therefore we can denote it with the symbol \( {\mathcal{P}(A)}\) without fear of misunderstandings.

   Note that

   \[ (∀ z, z ∈ y \implies z ∈ A) \]

   can be shortened with \(y⊆ A\) and therefore the axiom can be written as

   \[ ∀ A, ∃\; Z, ∀ y , y ∈ Z \iff ( y ⊆ A)\quad ; \]

   then using the extensionality, we obtain that

   \[ Z=\{ y: ( y ⊆ A)\} \quad . \]

6. Axiom of infinity (see 86)

7. [1Y0]The axiom of specification, which reads

   If \(A\) is a set, and \(P(x)\) is a logical proposition, then \(\{ x∈ A:P(x)\} \) is a set.

   Formally, setting \(B=\{ x∈ A:P(x)\} \),

   \[ \forall X, X\in B \iff X\in A\land P(x)\quad . \]

   This axiom avoids Russell’s paradox: let \(A\) be the set of \(x\) such that \(x∉ x\), then you have neither \(A∈ A\) nor \(A∉ A\).

8. Axiom of good foundation, or regularity (see 13)

9. Axiom of replacement

(We have omitted the definitions of ”Axiom of replacement”; you can find it in Chap.1 Sec.16 in  [ 2 ] or Chap. 1 in [ 13 ] ).

A further axiom is the Axiom of Choice; it will be discussed in Sec. ??.

E36

[23W]The notation in 4 differs from the usual one, which is \(⋃_{i∈ I}C_ i\), where \(I\) is a non-empty family of indices and \(C_ i\) are sets; as seen in 31.

How can you define \(⋃_{i∈ I}C_ i\) using the axiom of union presented 4? (Sugg. re-read the note 36)

Eventually you should obtain

\begin{equation} \forall x, x\in ⋃_{i∈ I}C_ i \iff ∃ i∈ I, x\in C_ i\quad . \label{eq:unione_ simpl_ in_ logica} \end{equation}

37

Hidden solution: [UNACCESSIBLE UUID ’027’]

E36

[23T](Proposed on 2022-10-11) (Solved on 2022-10-25) Prove that the definition 32 of intersection is well posed, using the Z-F axioms. Eventually prove also that

\begin{equation} ∀ x, x∈ ⋂_{i∈ I}C_ i \iff \left(I≠∅ ∧ ∀ i∈ I, x∈ C_ i\right)\quad . \label{eq:inters_ in_ logica} \end{equation}

38

Hidden solution: [UNACCESSIBLE UUID ’23V’]

E36

[252]Prerequisites:2,4,7,26. Let \(A\) be a non-empty set; we define \(B\) as the set that contains all the elements that are in all the elements of \(A\). Write a well-formed formula that defines \(B\), prove that \(B\) is indeed a set, and show that it is unique; for symmetry with the axiom 4 we will indicate it with

\[ B = \underline⋂ A\quad . \]

It is related to the usual notation by the relation

\[ \underline⋂ A = ⋂ _{x\in A} x \quad . \]

Hidden solution: [UNACCESSIBLE UUID ’254’]

E36

[247]Prerequisites:1,2.(Solved on 2022-10-25) Now that you have correctly defined the union 32 and the intersection 31 using the Z-F axioms, tell what value are assumed by

\[ ⋂_{i∈ I}C_ i \]

and

\[ ⋃_{i∈ I}C_ i \]

when \(I\) is the empty set. Hidden solution: [UNACCESSIBLE UUID ’249’]

E36

[028]Prerequisites:4. Using the definition of \({\underline⋃}\) presented in 4, show that \(A={\underline⋃}({\mathcal P}(A))\).

E36

[248](Solved on 2022-10-25) Given a set \(X\) and \(I,C_ i\) as in 32 and 31, show that

\begin{equation} X\setminus \left( ⋂_{i∈ I}C_ i\right) = ⋃_{i∈ I}(X\setminus C_ i)\quad . \label{eq:setminus_ inter_ union} \end{equation}

39

What happens when \(I\) is the empty set?

Hidden solution: [UNACCESSIBLE UUID ’24B’]

E36

[1W4](Proposed on 2022-12) If \(A\) is a set of \(n\) elements (\(n≥ 0\) natural number) then how many elements are there in \(\mathcal{P}(A)\)?

E36

[023] Write explicitly \(\mathcal{P}\mathcal{P}\mathcal{P}(∅)\). How many elements does it have? Hidden solution: [UNACCESSIBLE UUID ’1WX’]

E36

[1Y9] Let be given \(a,b,x,y\).

1. Show that in the hypothesis

   \[ \{ a,b\} = \{ x,y\} \]

   you have that

   \[ (a= b)\iff (x= y) \iff a=b=x=y \quad . \]

2. In particular, you deduce that if

   \[ \{ a\} = \{ x,y\} \]

   then \(a=x=y\).

3. Then show that if we assume that the four elements \(a,b,x,y\) are not all the same, then we have

   \[ \{ a,b\} = \{ x,y\} \]

   if and only if \(a=x∧ b=y\) or \(a=y∧ b=x\).

To show the above be as precise as possible: use the axiom of extensionality 28, the axiom of pairing 3 and the tautulogies shown in the previous section (or other elementary logical relationships). Hidden solution: [UNACCESSIBLE UUID ’1YB’]

E36

[01N](Solved on 2022-10-25) Prerequisites:9. The ordered pair is defined as

\[ (x,y){\stackrel{.}{=}}\{ \{ x\} ,\{ x,y\} \} \quad ; \]

(note that the axiom of pairing 3 guarantees us that this is a good definition); show that

\begin{equation} (a,b)=(x,y) \iff (a=x\wedge b=y)\quad .\label{eq:identita_ coppia} \end{equation}

40

(First solution that doesn’t use 9) Hidden solution: [UNACCESSIBLE UUID ’1WZ’] )

(Second solution using 9) Hidden solution: [UNACCESSIBLE UUID ’1YC’] )

E36

[1YD]Prerequisites:9,13. Let’s imagine a different definition for the ordered pair, defined as

\[ ⟬x,y ⟭{\stackrel{.}{=}}\{ x,\{ x,y\} \} \quad ; \]

show that

\begin{equation} ⟬a,b⟭=⟬x,y⟭\iff (a=x∧ b=y)\quad .\label{eq:identita_ pseudocoppia} \end{equation}

41

To show it you will need 13. Hidden solution: [UNACCESSIBLE UUID ’1YF’]

E36

[029](Solved on 2022-10-25) Show that, given \(a_ 1,\ldots a_ k\) sets, there is a set that contains all and only these elements. This set is usually denoted by \(\{ a_ 1,\ldots a_ k\} \).

Hidden solution: [UNACCESSIBLE UUID ’02B’]

E36

[01R] (Solved on 2022-10-25) The axiom of good foundation (also called axiom of regularity) of the Zermelo–Fraenkel theory says that every non-empty set \(X\) contains an element \(y\) that is disjoint from \(X\); in formula

\[ ∀ X, X≠ ∅ ⇒ (∃ y\, (y∈ X)∧ (X∩ y=∅))~ ~ \]

(remember that every object in the theory is a set, so \(y\) is a set). Using this axiom prove these facts.

• There is no set \(x\) that is an element of itself, that is, for which \(x∈ x\).

• More generally there is no finite family \(x_ 1,\ldots x_ n\) such that \(x_ 1∈ x_ 2∈ \ldots ∈ x_ n ∈ x_ 1\).

• There is also no \(x_ 1,\ldots x_ n,\ldots \) sequence of sets for which \(x_ 1∋ x_ 2 ∋ x_ 3 ∋ x_ 4\ldots \).

Hidden solution: [UNACCESSIBLE UUID ’01S’]

[UNACCESSIBLE UUID ’01T’]

[UNACCESSIBLE UUID ’01V’] [01W] Prerequisites:13.(Solved on 2021-10-21) Show that for every \(x\) there is a \(y\) such that \(y∉ x\) Hidden solution: [UNACCESSIBLE UUID ’01X’] [01Y] Show instead that the axiom of infinity, and the consequent construction of the natural numbers seen in Sec. 3.8, implies that there is a sequence \(x_ 1,\ldots x_ n,\ldots \) of sets for which \(x_ 1∈ x_ 2∈ x_ 3 \ldots \). Hidden solution: [UNACCESSIBLE UUID ’01Z’] [020] Prerequisites:3.(Solved on 2022-10-25) Given \(A\) non-empty set show that there is a bijection \(f:A→ B\) between \(A\) and a set \(B\) disjoint from \(A\).

More generally, let \(I\) a non-empty set of indexes, and \(A_ i\) a family of non-empty sets indexed by \(i∈ I\);  ⁷ show that there are bijections \(f_ i:A_ i→ B_ i\), where the sets \(B_ i\) enjoy \(∀ i∈ I,∀ j∈ I, B_ i∩ A_ j=∅\) and for \(j≠ j\) also \( B_ i∩ B_ j=∅\).

Hidden solution: [UNACCESSIBLE UUID ’021’] [022]Prerequisites:5.

Show that \(X⊆ Y\) if and only if \({\mathcal P}(X) ⊆ {\mathcal P}(Y)\). Hidden solution: [UNACCESSIBLE UUID ’1WW’] [024]Using the definition of pair \((a,b)\) as \(\{ \{ a\} ,\{ a,b\} \} \) show that, given two sets \(x,y\) , for each \(a∈ x,b∈ y\) you have

Use this fact and the axiom of separation to justify axiomatically the definition of the Cartesian product \(x× y \).

Hidden solution: [UNACCESSIBLE UUID ’025’]

Zorn Lemma, Axiom of Choice, Zermelo’s Theorem[23R]

There are three fundamental statements in set theory, Zorn’s Lemma, the Axiom of Choice, and Zermelo’s Theorem. It is proven, within the Zermelo–Fraenkel axiomatics, that these are equivalent. See in Chap. 1 in [ 2 ] for an elementary presentation, based on the above defined theory. ⁸

The first exercise presents some fundamental equivalent ways to state the Axiom of Choice.

E42

[02H]Prerequisites:36, 4,3 . Let \(I\) be a non-empty set of indexes, let \(A_ i\) a family of non-empty sets indexed by \(i∈ I\). Recall that, by definition, the Cartesian product \(∏_{i∈ I}A_ i\) is the set of functions \(f:I→ ⋃_{i∈ I}A_ i\) such that \(f(i)∈ A_ i\) for each \(i∈ I\).

Show that the following are equivalent formulations of the axiom of choice.

• The Cartesian product of a non-empty family of non-empty sets is non-empty.

• Given a family \(A_ i\) as above, such that the sets are not-empty and pairwise disjoint, there is a subset \(B\) of \(⋃_{i∈ I}A_ i\) such that, for each \(i∈ I\), \(B∩ A_ i\) contains a single element.

• Let \(S\) be a set. Then there is a function \(g: {\mathcal P}(S) \to S\) such that \(g(A) \in A\) for each nonempty \(A \in {\mathcal P}(S)\).

Hidden solution: [UNACCESSIBLE UUID ’02J’]

E43

[2GF] Find a non-empty set of indexes \(I\), and, for each \(i∈ I\), non-empty sets \(A_ i\), so that there does not exists a subset \(B\) of \(⋃_{i∈ I}A_ i\) with the property that, for each \(i∈ I\), \(B∩ A_ i\) contains a single element. Hidden solution: [UNACCESSIBLE UUID ’2GG’]

E43

[2BZ]Prerequisites:13.Consider the Zermelo-Fraenkel set theory, and this statement:

Given any \(A,B\) non-empty sets such that there exists a surjective function \(g:B→ A\), then there exists an injective function \(f:A→ B\) such that \(g◦ f=\text{Id}_ A\).

Prove that this statement implies the Axiom of Choice. Hidden solution: [UNACCESSIBLE UUID ’2C0’]

E43

[02D] Let \(V\) be a real vector space. Let \(B⊆ V\) be a subset. A finite linear combination \(v\) of elements of \(B\) is equivalently defined as

• \(v=∑_{i=1}^ nℓ_ i b_ i\) where \(n=n(v)∈ℕ\), \(ℓ_ 1,\ldots , ℓ_ n∈ℝ\) and \(b_ 1,\ldots ,b_ n\) are elements of \(B\);

• \(v=∑_{b∈ B} 𝜆(b) b\) where \(𝜆:B→ℝ\) but also \(𝜆(b)≠ 0\) only for a finite number of \(b∈ B\).

We call \(Λ⊆ ℝ^ B\) the set of functions \(𝜆\) as above, which are non-null only for a finite number of arguments; \(Λ\) is a vector space: so the second definition is less intuitive but is easier to handle.

We will say that \(B\) generates (or, spans) \(V\) if every \(v∈ V\) is written as finite linear combination of elements of \(B\).

We will say that the vectors of \(B\) are linearly independent if \(0=∑_{b∈ B} 𝜆(b) b\) implies \(𝜆≡ 0\); or equivalently that, given \(n≥ 1\), \(ℓ_ 1,\ldots , ℓ_ n∈ℝ\) and \(b_ 1,\ldots ,b_ n∈ B\) all different, the relation \(∑_{i=1}^ nℓ_ i b_ i=0\) implies \(∀ i≤ n,ℓ_ i=0\).

We will say that \(B\) is an algebraic basis (also known as Hamel basis) if both properties apply.

If \(B\) is a basis then the linear combination that generates \(v\) is unique (i.e. there is only one function \(𝜆∈Λ\) such that \(v=∑_{b∈ B} 𝜆(b) b\)).

Show that any vector space has an algebraic basis. Show more in general that for each \(A,G⊆ V\), with \(A\) family of linearly independent vectors and \(G\) generators, there is an algebraic basis \(B\) with \(A⊆ B⊆ G\).

Hidden solution: [UNACCESSIBLE UUID ’02G’]

The proof in general requires Zorn’s Lemma; indeed this statement is equivalent to the Axiom of Choice; this was proved by A. Blass in [ 6 ] ; see also Part 1 §6 [ 21 ] .

E43

[02M]Difficulty:*. ⁹ Consider the following quotient of the family of all integer valued sequences

\[ {\mathbb X}=\{ a:ℕ→ℕ \} / ∼ \]

where we define \(a∼ b\) iff \(a_ k= b_ k\) eventually in \(k\).

We define the ordering

\[ a⪯ b \iff ∃ n \mbox{ s.t. } ∀ k≥ n, a_ k≤ b_ k \]

that is, \(a⪯ b\) when \(a_ k≤ b_ k\) eventually. This is a preorder and

\[ a\sim b \iff (a⪯ b\land b⪯ a) \]

so it passes to the quotient were it becomes an ordering, see Prop. 82.

Let \(a^ k\) be an increasing sequence of sequences, that is, \(a^ k⪯ a^{k+1}\); we readily see that it has an upper bound \(b\), by defining

\[ b_ n = \sup _{h,k≤ n} a^ k_ h ~ . \]

We can then apply the Zorn Lemma to assert that in the ordered set \(({\mathbb X},⪯)\) there exist maximal elements.

Given \(a,b\) we define

\[ a∨ b = (a_ n∨ b_ n )_ n \]

then it is easily verified that \(a⪯ a∨ b\). So this a direct ordering, see 55.

We conclude that the ordered set \(({\mathbb X},⪯)\) has an unique maximum, by 2.

This is though false, since for any sequence \(a\) the sequence \((a_ n+1)_ n\) is larger than that.

What is the mistake in the above reasoning? What do you conclude about \(({\mathbb X},⪯)\)?

Many other exercise need Zorn’s Lemma, Axiom of Choice, Zermelo’s Theorem in their proof; to cite a few: 13, 111, 2, 2, 2, 2.

[UNACCESSIBLE UUID ’02N’]

[UNACCESSIBLE UUID ’02P’]

[UNACCESSIBLE UUID ’02Q’]

[UNACCESSIBLE UUID ’02R’]