Sets

Part 1 · Numbers and logic · Chapter 1 · lecture notes by Fabio Furini · Chapter PDF

1. Informal introduction to set theory

• Set theory is based on the following three key concepts:

  1. Sets

     The notion of set is generally taken as primitive (that is, not reducible to more elementary concepts). The words collection, class, aggregate, family are used as synonyms of set.

     Example 1: sets

     For example, we have the set of points of a plane, the set of students of a university, or the set of stars of a galaxy.

  2. Elements

     A set is determined by its elements, in the sense that a set is defined when we have a criterion to establish whether a given element is or is not an element of this set.

     There are sets with a finite number of elements (for example the set of students of a university) and sets with an infinite number of elements (for example the set of points of the plane).

     Sets are usually denoted by capital letters. The elements of a set are usually denoted by lowercase letters.

  3. Membership

     The concept of membership links elements to sets. When an object is an element of a set, we say that the element belongs to the set. To indicate that an element \(x\) belongs to a set \(A\) we write:

     \[ x \in A \]

1.1 Informal definition of sets

1. A first way to define sets is definition by listing (roster notation)

   A set can be defined by listing, that is, by listing the elements that belong to it between curly brackets. This technique assumes that the set has a finite number of elements.

   Example 2: definition by listing

   The notation:

   \[ A = \{a,b,c\} \]

   means that the set \(A\) has as elements the three letters \(a\), \(b\) and \(c\). For example, \(a\) belongs to \(A\), that is, \(a \in A\).

2. A second way to define sets is definition by a property:

   A set can be defined by a property as follows:

   \[ A = \big\{~ x \in U: p(x) {\rm~~is~true} ~\big\} \]

   where \(p(x)\) is the property that the element \(x\) of the set \(U\) must have in order to belong to the set \(A\). This technique can be used to define sets with a finite or even an infinite number of elements.

   Example 3: definition by a property

   Consider for example the set of letters of the Latin alphabet:

   \[ U =\{a,~ b,~ c,~ d,~ e,~ f,~ g,~ h,~ i,~ j,~ k,~ l,~ m,~ n,~ o,~ p,~ q,~ r,~ s,~ t,~ u,~ v,~ w,~ x,~ y,~ z \} \]

   Using for example the property \(p(x)\) defined as “\(x\) is a vowel” we can define the following set of vowels:

   \[ A= \underbrace{\{x \in U: x {\rm ~~~is~a~vowel}\}}_{ \{a,~e,~i,~o,~u\} } \]

   Note that to define a set \(A\) by a property we need a set \(U\) to which all the elements of the set \(A\) we want to define belong. The set \(U\) plays the role of the universal set.

   It is important that the property \(p(x)\) we use makes sense for every \(x\) of the set \(U\) (universal set), and therefore is true or false (without ambiguity of meaning) for every particular \(x \in U\); the set \(A\) will then consist of exactly those \(x\) belonging to \(U\) for which the property \(p(x)\) is true.

One must be careful when defining sets, since contradictions may arise. There is a formal definition of the concept of set, developed to avoid contradictions, but it is beyond the scope of this course.

• For example, the set of all sets that do not contain themselves is not a set in the formal definition of sets. Admitting this set would generate the contradiction: “the set of all sets that do not belong to themselves belongs to itself if and only if it does not belong to itself” (Russell's paradox – section ↗).

2. Number sets

Definition 1: numeral system

A positional numeral system is a way of encoding numbers using a sequence of digits, where each digit contributes differently to the number depending on its position. The number of distinct digits is the base of the system.

The decimal expansion of a number is a numerical representation in base 10; it expresses a number as a sum of powers of 10, and it can be finite or infinite depending on the type of number.

• Informal definition of the main number sets:

  1. We denote by \(\N\) the set of natural numbers, that is, the set of numbers that can be written as decimal expansions without decimal point and without sign. We will use the informal notation:

     \[ \N = \{0,~ 1,~ 2,~ 3,~ 4,~ \dots\} \]

  2. We denote by \(\Z\) the set of integers, that is, the set of numbers that can be written as decimal expansions without decimal point and with a sign. We will use the informal notation:

     \[ \Z = \{0,~ \pm 1,~ \pm 2,~ \pm 3,~ \pm 4,~ \dots \} \]

  3. We denote by \(\Q\) the set of rational numbers, that is, the set of numbers that can be written as finite or infinite periodic decimal expansions. In other words, it is the set of numbers that can be written as a fraction \(\frac{p}{q}\) where \(p\) is an integer and \(q\) is a natural number different from zero.

     Example 4: rational numbers

     • For example, with \(p=2\) and \(q=5\) we have the fraction \(\frac{2}{5}\), whose decimal expansion is \(0.4\).

     • For example, with \(p=4\) and \(q=10\) we have the fraction \(\frac{4}{10}\), whose decimal expansion is again \(0.4\). Note that a rational number can be written with more than one fraction.

     • For example, with \(p=13\) and \(q=30\) we have the fraction \(\frac{13}{30}\), whose decimal expansion is \(0.4\bar{3}=0.43333\dots\).

     However, we can represent every rational number different from \(0\) by a single fraction \(\frac{p}{q}\) by choosing \(p \in \Z\) and \(q \in \N\) coprime (that is, relatively prime: \(p\) and \(q\) are not both divisible by the same integer greater than 1).

     Remark 1

     \[ 0,\overline{9}=1 \]
     Proof

     There are different proofs of this remark, based on different mathematical techniques.

     1. A simple proof follows directly from the definition of \(1\) divided by \(3\); indeed, we have:

        \[\begin{align*} \frac{1}{3} &= 0,\overline{3}\\ \frac{1}{3} \cdot 3 &= 0,\overline{3} \cdot 3\\ 1 &= 0,\overline{9} \end{align*}\]

     2. Using algebraic arguments we can write:

        \[\begin{align*} x &= 0.999\dots\\ 10\:x &= 9.999\dots & {\rm multiplying~by~} 10 \\ 10\:x &= 9 + 0.999\dots & {\rm separating~the~integer~part~from~the~fractional~part} \\ 10\:x &= 9 + x & {\rm by~definition~of~} x\\ 9\:x &= 9 & {\rm subtracting~} x\\ x &= 1 & {\rm dividing~by~} 9 \end{align*}\]

     3. A proof by contradiction is the following:

        \[\begin{align*} 0,\overline{9} & \neq 1\\ 0,\overline{9} \cdot 9 & \neq 1 \cdot 9\\ 0,\overline{9} \cdot 9 + 0,\overline{9}& \neq 1 \cdot 9 +0,\overline{9}\\ 0,\overline{9} \cdot 9 + 0,\overline{9}& \neq 9,\overline{9}\\ 0,\overline{9} \cdot (9+1) & \neq 9,\overline{9}\\ 0,\overline{9} \cdot (10) & \neq 9,\overline{9}\\ 9,\overline{9} & \neq 9,\overline{9} ~~~~~~ {\rm contradiction!} \end{align*}\]

     □

  4. We denote by \(\R\) the set of real numbers, that is, the set of numbers identified with finite or infinite decimal expansions, periodic or non-periodic.

     Example 5: real numbers

     • Consider for example the number

       \[ 0,10110111011110 \dots \]

       obtained by putting after the decimal point one digit equal to \(1\), then \(0\), then two digits equal to \(1\), then \(0\), then three digits equal to \(1\) … and so on. The string of nonzero digits after the decimal point is neither finite nor periodic: therefore this number is real but not rational.

     • Other examples of real but not rational numbers are \(\sqrt{2}\) and \(\sqrt{3}\), or \(\pi\) and Euler's number \(e\) (Napier's constant), which have infinite non-periodic decimal expansions and are therefore real but not rational numbers.

• There are formal definitions of the sets of natural, integer and rational numbers that are beyond the scope of this course. Later we will give a formal definition of the real numbers.

3. Relations between sets

1. Equality
   Two sets \(A\) and \(B\) are equal when they have the same elements. We write

   \[ A = B \]

   and this means that every element that belongs to \(A\) also belongs to \(B\) and every element that belongs to \(B\) also belongs to \(A\).

2. Inclusion
   It may happen that only one of the two requirements expressed by the equality relation holds. For example, if we only know that every element of \(A\) is also an element of \(B\), we can say that \(A\) is contained in \(B\). We write:

   \[ A \subseteq B {\rm ~~~or~~} A \subset B \]

   and we read “\(A\) is contained in \(B\)” or “\(A\) is a subset of \(B\)”. If we state that \(A \subseteq B\), we do not exclude that \(A = B\).

   Saying that \(A = B\) is equivalent to saying that \(A \subseteq B\) and \(B \subseteq A\).

   Be careful not to confuse “belongs to” and “is contained in” (in symbols, \(\in\) and \(\subseteq\)). In a sense, they are two ways of indicating that “something is inside something else”, but they have a fundamental logical difference:

   • a set is contained in another set;

   • an element belongs to a set.

   Example 6: “belongs to” vs “is contained in”

   For example:

   \[ 3 \in \{1,3,4\}; \]

   \[ \{3\} \subseteq \{1, 3, 4\}; \]

   \[ \{1,4\} \subseteq \{1,3,4\}. \]

   In particular, do not confuse \(3\) (which is a number) with \(\{3\}\), which is the set that contains the number 3 as its only element.

   Sometimes we consider sets whose elements are other sets. In this case too, the symbols \(\in\) and \(\subseteq\) are not interchangeable, but must be used correctly.

   Example 7: “belongs to” vs “is contained in”

   For example, if we define the set

   \[ A = \bigg\{ ~\{1\},~ \{2\},~ \{1, 2\} ~\bigg\}, \]

   then it is correct to state that \(\{2\} \in A\), because \(\{2\}\) is a set that plays the role of an element of \(A\), whereas it would be incorrect to say that \(\{2\} \subseteq A\), because this would mean that \(2 \in A\), while \(A\) has \(\{2\}\) as an element but not \(2\). Instead, the subset of \(A\) containing only the element \(\{2\}\) is denoted by \(\big\{\{2\}\big\}\) and we have \(\big\{\{2\}\big\} \subset A\).

3.1 Empty set, cardinality and power set

Definition 2: of empty set

The empty set is the set that contains no elements. It is denoted by \(\varnothing.\)

Remark 2

Given a set \(A\), we have:

\[ \varnothing \subseteq A \]

Proof

To prove it, we should show that every element that belongs to \(\varnothing\) also belongs to \(A\); but no element belongs to \(\varnothing\), so the thesis holds. □

Definition 3: of cardinality of a set

The number of elements of a set \(A\) is the cardinality of the set. It is denoted by \(|A|\).

Definition 4: of power set

Given a set \(A\), the set whose elements are all the subsets of \(A\) is called the power set of \(A\) and is denoted by the symbol \(\mathscr{P}(A).\)

• Every set \(A\) has two trivial subsets, namely \(A\) itself and the empty set \(\varnothing\) (they could coincide, if \(A\) is empty).

Example 8: power set

For example, given

\[ A= \{1, 2, 3\} , \]

then

\[ \mathscr{P}(A) = \bigg\{~\varnothing,~ \{1\},~ \{2\},~ \{3\},~ \{1, 2\},~ \{2, 3\},~ \{1 , 3\},~ \{1,2,3\} ~\bigg\} \]

Remark 3

Given a set \(A\) with \(n\) elements, the power set \(\mathscr{P}(A)\) has \(2^n\) elements:

\[ |\mathscr{P}(A)|=2^n \]

Proof

For each of the elements of \(A\), the subsets of \(A\) may or may not contain that element. Hence we must make a choice between two options \(n\) times. The total number of possible subsets is therefore \(2^{n}\). □

Example 9: construction of the power set with a binary tree

Given the set \(A=\{1,2,3\}\) with \(n=3\) elements, the cardinality of its power set is \(2^3=8\). The construction of the power set \(\mathscr{P}(A)\) can be visualized through the following binary tree (an undirected, connected and acyclic graph) in which at each level we decide whether or not to include the object in the subset:

4. Operations on sets

Definition 5: of intersection of sets

The intersection of two sets \(A,B \subseteq U\) is the set defined by:

\[ A \cap B = \big\{x \in U: x \in A {\rm ~~and~~} x \in B \big\} \]

It is the set of elements that belong both to the first and to the second set.

Definition 6: of union of sets

The union of two sets \(A,B \subseteq U\) is the set defined by:

\[ A \cup B = \big\{x \in U: x \in A {\rm ~~or~~} x \in B \big\} \]

It is the set of elements that belong to the first or to the second set, where “or” is meant in the non-exclusive sense (the set of elements that belong to \(A\) or to \(B\) or to both).

Definition 7: of difference of sets

The difference of two sets \(A,B \subseteq U\) is the set defined by:

\[ A \setminus B = \big\{x \in A: x \notin B \big\} \]

It is the set of elements that belong to the first but not to the second set. The symbol “\(\setminus\)” can also be written “-” by analogy with arithmetic subtraction.

4.1 Complementary sets and disjoint sets

Example 10: universal sets

For example, in questions of arithmetic we could have \(U= \N\), while in questions of analysis we could have \(U =\R\).

Definition 8: of set complementation and complementary sets

The complementation of a set \(A \subseteq U\) is the set defined by:

\[ \overline{A} = \big\{x \in U: x \notin A \big\} \]

This set is called the complement (complementary set) of \(A\) with respect to \(U\)

• For every set \(\red{A} \subseteq \violet{U}\), where \(\violet{U}\) is the universal set, we have the following relations:

\[\begin{align*} \overline{ \overline{ \red{A}}} &= \red{A}\\ \red{A} \cap \overline{\red{A}} &= \varnothing\\ \red{A} \cup \overline{\red{A}} &= \violet{U} \end{align*}\]

\[\begin{align*} \red{A} \cap \varnothing &= \varnothing \\ \red{A} \cap \violet{U} &= \red{A} \\ \red{A} \cup \varnothing &= \red{A} \\ \red{A} \cup \violet{U} &= \violet{U} \end{align*}\]

\[\begin{align*} \violet{\overline{U}} &= \varnothing \\ \overline{\varnothing} &= U \end{align*}\]

Definition 9: of disjoint sets

Two sets \(\red{A}\) and \(\blue{B}\) are disjoint if they have no elements in common:

\[ \red{A} \cap \blue{B} = \varnothing \]

4.2 Venn diagrams

Venn diagrams are graphical representations in which sets are represented as regions of the plane

• Venn diagrams of intersection, union and difference:

  

  

  

• Venn diagram of the complement of a set:

  

4.3 Cartesian product

There is another operation on sets, which can be performed on any two sets (i.e., two sets not necessarily contained in the same universal set):

Definition 10: of Cartesian product

Given two (not necessarily distinct) sets \(A\) and \(B\), the set consisting of all ordered pairs \((a, b)\), with \(a \in A\) and \(b \in B\), is called the Cartesian product of \(A\) and \(B\) and is denoted by the symbol \(A \times B\).

When \({A}\) and \({B}\) are two finite sets, the cardinality of their Cartesian product is:

\[ |{A} \times {B}| = |{A}| \cdot |{B}|. \]

Example 11: Cartesian product

\[ \{a,b\} \times \{a,b,c\} = \big\{ (a,a),(a,b),(a,c),(b,a),(b,b),(b,c) \big\} \]

\[ |\{a,b\}|=2,~~ |\{a,b,c\}|=3,~~ |\{a,b\} \times \{a,b,c\}| = 2 \cdot 3 = 6 \]

• A typical use of the Cartesian product is \(\R \times \R\), which is abbreviated by the symbol \(\R^2\) and denotes the set of ordered pairs of real numbers.

• Similarly, \(\R^n\) (abbreviation of the Cartesian product of \(n\) sets equal to \(\R\)) is the set of ordered \(n\)-tuples of real numbers

  \[ \R^n =\big\{ ~(x_1,~x_2,~ \dots,~ x_n)~: ~~x_i \in \R, ~~i \in \{1,2,\dots, n\} ~\big\} \]

4.4 Properties of operations on sets

Remark 4: properties of intersection

Given three sets \(\red{A}, \blue{B}\) and \(\orange{C}\), intersection has the following properties:

• Commutative:

  \[ \red{A} \cap \blue{B} = \blue{B} \cap \red{A} \]

• Associative:

  \[ \red{A} \cap (\blue{B} \cap \orange{C}) = (\red{A} \cap \blue{B}) \cap \orange{C} \]

• Idempotence:

  \[ \red{A} \cap \red{A} = \red{A} \]

Proof

The graphical proof of the associative property of intersection is the following:

□

Remark 5: properties of union

Given three sets \(\red{A}, \blue{B}\) and \(\orange{C}\), union has the following properties:

• Commutative:

  \[ \red{A} \cup \blue{B} = \blue{B} \cup \red{A} \]

• Associative:

  \[ \red{A} \cup (\blue{B} \cup \orange{C}) = (\red{A} \cup \blue{B}) \cup \orange{C} \]

• Idempotence:

  \[ \red{A} \cup \red{A} = \red{A} \]

Proof

The graphical proof of the associative property of union is the following:

□

Remark 6: distributive properties (linking union and intersection)

Given three sets \(\red{A}, \blue{B}\) and \(\orange{C}\) we have:

\[ \red{A} \cap (\blue{B} \cup \orange{C}) = (\red{A} \cap \blue{B}) \cup (\red{A} \cap \orange{C}) \]

\[ \red{A} \cup (\blue{B} \cap \orange{C}) = (\red{A} \cup \blue{B}) \cap (\red{A} \cup \orange{C}). \]

The distributive properties link union and intersection to each other.

Proof

The graphical proof of the first property is the following:

The graphical proof of the second property is the following:

□

Proposition 1: De Morgan's laws (first version)

Given three sets \(\red{A}, \blue{B}\) and \(\orange{C}\) we have:

\[ \red{A} \setminus (\blue{B} \cap \orange{C}) = (\red{A} \setminus \blue{B}) \cup (\red{A} \setminus \orange{C}) \]

\[ \red{A} \setminus (\blue{B} \cup \orange{C}) = (\red{A} \setminus \blue{B}) \cap (\red{A} \setminus \orange{C}) \]

Proof

The graphical proof of the first property is the following:

The graphical proof of the second property is the following:

□

Proposition 2: De Morgan's laws (second version)

Given the sets \(\blue{B}, \orange{C} \subseteq \violet{U}\), we have

\[ \overline{\blue{B} \cap \orange{C}} = \overline{\blue{B}} \cup \overline{\orange{C}} \]

\[ \overline{\blue{B} \cup \orange{C}} = \overline{\blue{B}} \cap \overline{\orange{C}} \]

Proof

These laws can be derived by setting \(A\) equal to \(U\) in the previous De Morgan's laws, as follows:

\[ \underbrace{\violet{U} \setminus (\blue{B} \cap \orange{C})}_{=\overline{\blue{B} \cap \orange{C}} } = (\underbrace{\violet{U} \setminus \blue{B}}_{= \overline{\blue{B}}}) \cup (\underbrace {\violet{U} \setminus \orange{C}}_{= \overline{\orange{C}}}) \]

\[ \underbrace{\violet{U} \setminus (\blue{B} \cup \orange{C})}_{=\overline{\blue{B} \cup \orange{C}} } = (\underbrace{\violet{U} \setminus \blue{B}}_{= \overline{\blue{B}}}) \cap (\underbrace {\violet{U} \setminus \orange{C}}_{= \overline{\orange{C}}}) \]

□

Proof

The graphical proof of the first property is the following:

The graphical proof of the second property is the following:

□

• The set of elements that belong to a set \(B\) or to a set \(C\) but not to both (meaning “or” in the exclusive sense) is obtained by setting \(U = B \cup C\) and taking the complement of the intersection:

Relation between inclusion and the operations of union and intersection:

\[ A \subseteq B {\rm ~if~and~only~if~} A \cap B = A {\rm ~and~} A \cup B = B. \]

4.5 Properties of the cardinality of sets

• For any two finite sets \(\red{A}\) and \(\blue{B}\), we have

  \[ |\red{A} \cup \blue{B}| = |\red{A}| + |\blue{B}| - |\red{A} \cap \blue{B}| \]

  from which we conclude that

  \[ |\red{A} \cup \blue{B}| \le |\red{A}| + |\blue{B}| \]

• If \(\red{A}\) and \(\blue{B}\) are disjoint then

  \[ |\red{A} \cap \blue{B}| = 0 {\rm~~and~hence~~} |\red{A} \cup \blue{B}| = |\red{A}| + |\blue{B}| \]

• If \(\red{A} \subsetneqq \blue{B}\), then \(|\red{A}| < |\blue{B}|\)

5. Further topics

5.1 Russell's paradox

“can a set be an element of itself or not?”

• For example, the set of all books in a library is not an element of itself (a set of books is not a book). On the other hand, the set of all sets with more than 20 elements is an element of itself.

• Following this reasoning, two categories of sets can be defined:

  1. sets that are not elements of themselves

  2. sets that are elements of themselves

If we consider the set of all sets that are not elements of themselves, is it an element of itself or not?

Let us call this set \(S\); two hypotheses can be made:

• 1 If we suppose \(S \in S\), then \(S\) contains itself as an element and therefore does not belong to \(S\) (since by definition a set belongs to \(S\) only if it does not contain itself as an element). Hence \(S \notin S\), and we have a contradiction. We conclude that the hypothesis must be wrong.

• 2 If we suppose \(S \notin S\), then \(S\) does not contain itself as an element and therefore belongs to \(S\) (since by definition a set belongs to \(S\) if it does not contain itself as an element). Hence \(S \in S\) and we have another contradiction. We conclude that this hypothesis must be wrong too!

Russell's paradox: The set of all sets that do not belong to themselves belongs to itself if and only if it does not belong to itself.

• The formal definition of the concept of set is based on the Zermelo-Fraenkel system of axioms, abbreviated as ZF. This system of axioms includes the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based.

• The axiom of regularity states that “Every non-empty set \(A\) contains an element disjoint from \(A\)”.

• The axiom of pairing states that “Given two objects, there exists a set whose elements are the two objects”

  Remark 7

  No set is an element of itself

  Proof

  Given a set \(A\), we apply the axiom of regularity to \(\{A\}\), which is a set by the axiom of pairing. We thus obtain the set \(\{A,A\}\), which we abbreviate to \(\{A\}\) since sets cannot contain repeated objects (it is a special case of a pair). By the axiom of regularity there must exist an element of \(\{A\}\) disjoint from \(\{A\}\). Since the only element of \(\{A\}\) is \(A\), \(A\) is disjoint from \(\{A\}\). Hence, since \(A\cap \{A\}=\varnothing\), we cannot have \(A \in A\) (by the definition of disjoint). □

• The other ZF axioms are not part of the basic course in Mathematical Analysis.

• A further proof of

  \[ 0,\overline{9}=1 \]

  starts from the assumption that two numbers are equal if and only if their difference is equal to zero, and it is based on computing the value of \(1 - 0,\overline{9}\).

• This proof is based on the fact that 0 is the only non-negative number less than all the reciprocals of the positive integers, or equivalently that there is no number greater than every integer. This is the Archimedean property, which holds for the rational and the real numbers.

Proof

We write the number \(0,999...\) with \(n\) digits after the decimal point as \(0,(9)_n\), hence \(0,(9)_1 = 0.9\), \(0,(9)_2 = 0.99\), \(0,(9)_3 = 0.999\), and so on.

Given \(\frac{1}{10^n} = 0,0 \dots 01\), with \(n\) digits after the decimal point, the addition rules for decimal numbers imply

\[ 0,(9)_n + \frac{1}{10^n} = 1 {\rm ~~moreover~~} 0,(9)_n < 1, \forall n \in \N. \]

We must prove that \(1\) is the smallest number that is not less than all the \(0,(9)_n\). For this it is enough to prove that, if a number \(x\) is not greater than 1 and not less than all the \(0.(9)_n\), then \(x = 1\).

So let \(x\) be such that

\[ 0,(9)_n \le x \le 1 \]

for every positive integer \(n\). Hence

\[ 1-1 \le 1 - x \le 1- 0,(9)_n \]

which, using basic arithmetic and the first equality established above, simplifies to

\[ 0 \le 1 - x \le \frac{1}{10^n} \]

This implies that the difference between \(1\) and \(x\) is less than the reciprocal of any positive integer. Hence this difference must be zero, and therefore \(x = 1\); which in turn implies

\[ 0.999\dots = 1 \]

□