📖 Sets and numbers#

| words

References and additional materials
_images/shsc2016.png

[Sydsæter, Hammond, Strøm, and Carvajal, 2016]

Chapters 1.1, 2.1-2.5

  • Veritasium video on paradoxes of set theory and mathematical incompleteness YouTube

Notation cheat sheet

Notation

Meaning

\(P \implies Q\)

\(P\) implies \(Q\)

\(P \iff Q\)

\(P \implies Q\) and \(Q \implies P\)

\(\exists\)

there exists

\(\forall\)

for all [elements in a set]

\(a := \text{[expression]}\)

\(a\) is defined to be equal to \(\text{[expression]}\)

\(a \equiv \text{[expression]}\)

\(a\) is defined to be equal to \(\text{[expression]}\)

\(a \stackrel{def.}{=} \text{[expression]}\)

\(a\) is defined to be equal to \(\text{[expression]}\)

\(\in\)

is element of

\(\subset\)

is subset of

\(\cup\)

union

\(\cap\)

intersection

Naive set theory#

Definition

A set (\(X\)) is a collection of objects.
A particular object within a set (\(x\)) is known as an element of that set.

  • Sets: \(A, B, X\)

  • Elements: \(x,y,z\)

  • \(x \in X\) denotes the idea that x is an element of X

  • \(y \notin X\) denotes the idea that y is not an element of X

  • empty set is denoted by \(\varnothing\)

Definition of a set

A set \(A\) can be defined by either

  • direct enumeration of its elements

  • defining a formula for infinite number of elements

  • as a subset of already defined set \(B\), formula \(\psi(x)\) to form elements of \(A\), and a condition/property on \(x\)

\[A = \{ \psi(x), x \in B \,\colon\, \text{condition on x}\}\]

The idea that x is an element of X is written in mathematical notation as \(x \in X\).

Suppose that there are elements that do not belong to \(X\). Let \(y\) be one such element. The idea that \(y\) is not an element of \(X\) is written in mathematical notation as \(y \notin X\) .

A set that does not contain any elements is said to be empty. An empty set is denoted by either \(\varnothing\) or \(\{\}\).

There are two fundamental ways of defining a particular set:

  1. The first of these is to exhaustively list all of the elements of the set.

    • Example 1: \(X = \{1, 2, 3\}\)

    • Example 2: \(Y = \{1, 2, 3, · · · , 100\}\)

    • Example 3: \(\mathbb{N} = \{1, 2, 3, · · · \}\)

  2. The second of these is to specify one or more properties that characterise all of the elements in the set.

    • Example 4: \(X = \{n \in \mathbb{N} : n < 4\}\)

    • Example 5: \(Y = \{n \in \mathbb{N} : n \leqslant 100\}\)

Some common number sets#

  • The set of natural numbers:

\[\mathbb{N} = \{1, 2, 3, · · · \}\]
  • The set of non-negative intergers:

\[\mathbb{Z}_+ = \{0, 1, 2, · · · \}\]
  • The set of integers:

\[\mathbb{Z} = \{· · · , −2, −1, 0, 1, 2, · · · \}\]
  • The set of rational numbers:

\[\mathbb{Q} = \{ \frac{m}{n} : m \in \mathbb{Z}, n \in \mathbb{N}\}\]
  • The set of non-negative rational numbers:

\[\mathbb{Q}_+ = \{x \in \mathbb{Q} : x \geqslant 0\}\]
  • The set of positive rational numbers:

\[\mathbb{Q}_{++} = \{x \in \mathbb{Q} : x > 0\}\]
  • The set of real numbers:

\[\mathbb{R} = (-\infty, \infty)\]
  • The set of non-negative real numbers:

\[\mathbb{R}_+ = \{x \in \mathbb{R} : x \geqslant 0\}\]
  • The set of positive real numbers:

\[\mathbb{R}_{++} = \{x \in \mathbb{R}: x > 0\}\]
  • The set of complex numbers:

\[\mathbb{C} = \{ a + bi : a \in \mathbb{R}, \: b \in \mathbb{R}, \: i = \sqrt{−1} \}\]

Example

\[\begin{split}\begin{array}{ccc} 1 \in \mathbb{N} & 0 \in \mathbb{Z}_+ & -1 \in \mathbb{Z} \\ \frac{1}{2} \in \mathbb{Q} & \sqrt{2} \in \mathbb{R} & \sqrt{2} \in \mathbb{R}_{++} \end{array}\end{split}\]

Non-negative and positive real orthants#

  • The set of non-negative real numbers is given by

\[R_+ = \{x \in \mathbb{R} : x \geqslant 0\} = [0, \infty)\]
  • The Euclidean \(L\)-dimensional non-negative orthant is

\[R^L_+ = \times_{I = 1}^L \mathbb{R}_+\]
  • The set of positive real numbers is given by

\[R_{++} = \{x \in \mathbb{R} : x > 0\} = (0, \infty)\]
  • The Euclidean \(L\)-dimensional positive orthant is

\[R^L_{++} = \times_{I = 1}^L \mathbb{R}_{++}\]

Non-positive and negative real orthants#

  • The set of non-positive real numbers is given by

\[R_- = \{x \in \mathbb{R} : x \leqslant 0\} = (-\infty, 0]\]
  • The Euclidean \(L\)-dimensional non-positive orthant is

\[R^L_- = \times_{I = 1}^L \mathbb{R}_-\]
  • The set of negative real numbers is given by

\[R_{--} = \{x \in \mathbb{R} : x < 0\} = (-\infty, 0)\]
  • The Euclidean \(L\)-dimensional negative orthant is

\[R^L_{--} = \times_{I = 1}^L \mathbb{R}_{--}\]

Subsets#

Definition

Consider two sets, \(X\) and \(Y\). Suppose that every element of \(X\) also belongs to \(Y\). If this is the case, then we say that \(X\) is a subset of \(Y\).

This is written in mathematical notation as \(X \subseteq Y\).

Definition

Suppose that in addition to every element of \(X\) also belonging to \(Y\), there is at least one element of Y that does not belong to \(X\). If this is the case, then we say that \(X\) is a proper subset of \(Y\).

This is written is mathematical notation as \(X \subset Y\).

Sometimes \(X \subset Y\) is used (rather loosely) to mean \(X \subseteq Y\). If this meaning of the notation is employed, then \(X \subsetneq Y\) would need to be used to indicate that \(X\) is a proper subset of \(Y\).

Suppose that both every element of \(X\) also belongs to \(Y\), and every element of \(Y\) also belongs to \(X\). If this is the case, then we say that \(X\) is equal to \(Y\). This is written in mathematical notation as \(X = Y\).

The nesting of number sets#

Example

Recall the common number sets from above. The following “nesting” relationship exists between these common sets of numbers:

\[\mathbb{N} \subset \mathbb{Z}_+ \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}\]

Note that \(\mathbb{N} \subset \mathbb{Z}_+\) because \(\mathbb{Z}_+ = \mathbb{N} \cup \{0\}\).

Note that \(\mathbb{Z}_+ \subset \mathbb{Z}\) because \(\mathbb{Z} = \mathbb{Z}_+ \cup \{ · · · , −3, −2, −1 \}\).

Note that \(\mathbb{Z} \subset \mathbb{Q}\) because any \(m \in \mathbb{Z}\) can be written as \(\frac{m}{1}\) and \(1 \in \mathbb{N}\), but there are fractions that do not belong to Z (for example \(\frac{1}{2} \notin \mathbb{Z}\)).

Note that \(\mathbb{Q} \subset \mathbb{R}\) because \(\frac{m}{n} \in (−\infty, \infty)\) for all \(m \in \mathbb{Z}\) and \(n \in \mathbb{N}\), but there are numbers on the real line that cannot be expressed as fractions (for example \(\sqrt{2}\), \(\pi\) and \(e\)). Real numbers that cannot be expressed as fractions are known as “irrational numbers”.

Note that \(\mathbb{R} \subset \mathbb{C}\) because

\[\mathbb{R} = \{ a + bi : a \in \mathbb{R}, \: b = 0, \: i = \sqrt{−1} \}\]

and \(0 \in \mathbb{R}\), but \((a + bi) \notin \mathbb{R}\) if \(b \neq 0\).

  • Complex numbers in which a = 0 are known as (purely) “imaginary numbers”.

Intervals as subsets of the real line#

Some (but not all) of the subsets of the real line take the form of an interval.

Let \(a \in \mathbb{R}, b \in \mathbb{R} \text{ and } a \le b\). There are four types of intervals:

  • \([a, b] = \{x \in \mathbb{R} : a \leqslant x \leqslant b\}\)

    • If \(a > b\), then \([a, b] = \varnothing\)

    • If \(a = b\), then \([a, b] = \{a\} = \{b\}\)

  • \((a, b) = \{x \in \mathbb{R} : a < x < b\}\)

    • If \(a > b\), then \((a, b) = \varnothing\)

    • If \(a = b\), then \((a, b) = \varnothing\)

  • \([a, b) = \{x \in \mathbb{R} : a \leqslant x < b\}\)

    • If \(a > b\), then \([a, b) = \varnothing\)

  • \((a, b] = \{x \in \mathbb{R} : a < x \leqslant b\}\)

    • If \(a > b\), then \((a, b] = \varnothing\)

Power sets#

Definition

The power set \(2^X\) of a set \(X\) is the set of all subsets of \(X\).

Note that the elements of a power set are sets themselves.

If there are \(n < \infty\) elements (that is, a finite number of elements) in the set \(X\), then the number of subsets of \(X\) will be equal to \(2^n\). As such, there will be \(2^n\) elements in the set \(2^X\). This might be the reason that the power set for some set \(X\) is often denoted by \(2^X\).

Example

Suppose that \(X = \{1, 2, 3\}\). The power set for the set \(X\) in this example is

\[2^X = \big\{\varnothing, \{1\} , \{2\} , \{3\} , \{1, 2\} , \{1, 3\} , \{2, 3\} , \{1, 2, 3\}\big\}\]

Note that there are three elements in the set \(X\) and eight elements in the power set for \(X\), \(2^3 = 8\).

Cartesian product#

Definition

The Cartesian product of two sets is defined to be the set of all ordered pairs (or doublets) that contain one component from each of the two sets in the order that the sets were specified. This can be formally expressed as

\[X \times Y = \{(x, y) : x \in X , \: y \in Y \}\]

Definition

The Cartesian product of \(n\) sets is defined to be the set of all ordered \(n\)-tuples that contain one component from each of the \(n\) sets in the order that the sets were specified. This can be formally expressed as

\[\times_{i \in \{1,2,··· ,n\}} X_i = \{(x_1, x_2, · · · , x_n) : x_i \in X_i \; \forall i \in \{1, 2, · · · , n\}\}\]

Note that the order of the sets matters here. Cartesian products generate sets of “ordered” n-tuples.

Example

The standard two-dimensional Euclidean coordinate plane from high school:

\[\mathbb{R}^2 = \mathbb{R} \times \mathbb{R} = \{(x, y) : x \in \mathbb{R}, \; y \in \mathbb{R}\}\]

Example

The \(n\)-dimensional Euclidean coordinate plane:

\[\mathbb{R}^n = \times_{i \in \{1,2,··· ,n\}} \mathbb{R} = \{(x_1, x_2, · · · , x_n) : x_i \in \mathbb{R} \; \forall i \in \{1, 2, · · · , n\}\}\]

Example

A discrete-continuous example:

\[\mathbb{N} \times \mathbb{R} = \{(n, y) : n \in \mathbb{N}, \; y \in \mathbb{R}\}\]

A continuous-discrete example:

\[\mathbb{R} \times \mathbb{N} = \{(x, n) : x \in \mathbb{R}, \; n \in \mathbb{N}\}\]

Example

If X = {1, 2, 3}, then the Cartesian product of X with itself is given by

\[X^2 = X \times X = \{(x, y) : x \in X , \; y \in X \}\]
  • This set can also be written out as an exhaustive list of possible cases as follows:

\[X^2 = \{(1, 1) , (1, 2) , (1, 3) , (2, 1), (2, 2) , (2, 3) , (3, 1) , (3, 2) , (3, 3)\}\]

Russell’s Paradox#

It would be nice if we could always associate some type of set with any particular property that we might consider. In other words, it would be nice if for any property \(\mathbb{A}\), we could form a set \(\{x \in X : \mathbb{A}(x) \text{ is true}\}\) that consisted of all of the elements that satisfy this property. Unfortunately, this is not the case.

This was established by British philosopher and mathematician Bertrand Russell and published in 1901. He did this by developing the following paradox.

Let \(\mathbb{A}\) be the property “is a set and does not belong to itself”. Suppose that \(A\) is the set of all sets that possess property \(\mathbb{A}\). Is \(A \in A\)?

If \(A \in A\), then it must be the case that \(A\) possesses property \(\mathbb{A}\). This means that \(A \notin A\). Contradiction! Thus it must be the case that \(A \notin A\). But if \(A\) is a set and \(A \notin A\), then it clearly possesses property \(\mathbb{A}\). Thus \(A \in A\). Contradiction. Thus it must be the case that \(A \in A\).

We have a paradox. It cannot be the case that both \(A \in A\) and \(A \notin A\).

One possible resolution to Russell’s paradox is to not allow mathematical objects like this particular \(A\) to be considered a set. Re-definition of the set theory by Ernst Zermelo, Abraham Fraenkel and Thoralf Skolem in 1908-1920, known today as ZFC axiomatic set theory.

Operations on sets#

Union and intersection#

Suppose that U is some universal set, \(X \subseteq U\) and \(Y \subseteq U\).

Definition

The union of \(X\) and \(Y\), which is denoted by \(X \cup Y\), is the set

\[ X \cup Y = \{a \in U : a \in X \text{ or } a \in Y\} \]

Note that the “or” in this definition is not exclusive. If the element \(a\) belongs to either \(X\) only, or \(Y\) only, or both \(X\) and \(Y\) , then \(a \in X \cup Y\).

Definition

The intersection of \(X\) and \(Y\), which is denoted by \(X \cap Y\), is the set

\[ X \cap Y = \{a \in U : a \in X \text{ and } a \in Y\} \]

Definition

If \(X \cap Y = \varnothing\), then the sets \(X\) and \(Y\) are said to be disjoint.

Venn diagram: union of two (overlapping) sets#

Relationships between sets can be visualized using Venn diagrams.

In this example, the red, brown and green areas are all part of \(A \cup B\): the union of set \(A\) (the left circle) and set \(B\) (the right circle).

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles

v = venn2(subsets=(1, 1, 1))
v.get_label_by_id('10').set_text('')
v.get_label_by_id('01').set_text('')
v.get_label_by_id('11').set_text('')

c = venn2_circles(subsets=(1, 1, 1), linestyle = 'solid')

# Style options
plt.title("Union of two overlapping sets")

# Add bracket showing the union of the two sets
plt.annotate('A ∪ B', xy=(0.5, 0), xytext=(0.5, -0.1), xycoords='axes fraction', 
            fontsize=16, ha='center', va='top',
            bbox=dict(boxstyle='square', fc='white', color='k'),
            arrowprops=dict(arrowstyle='-[, widthB=9.5, lengthB=0.5', lw=2.0, color='k'))

plt.show()

Venn diagram: intersection of two overlapping sets#

The intersection of the two sets, \(A \cap B\), is the brown area.

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles

v = venn2(subsets=(1, 1, 1))
v.get_label_by_id('10').set_text('')
v.get_label_by_id('01').set_text('')
v.get_label_by_id('11').set_text('$A \; ∩ \; B$')

c = venn2_circles(subsets=(1, 1, 1), linestyle = 'solid')

# Style options
plt.title("Intersection of two sets")

# Add legend
cols, texts = [],[]
cols.append(v.get_patch_by_id('11'))
texts.append(v.get_label_by_id('11')._text)
plt.legend(handles=cols, labels=texts, loc='upper right')

plt.show()

Venn diagram: intersection of two disjoint sets#

In this diagram, \(A\) and \(B\) are disjoint sets. Therefore, \(A \cap B = \varnothing\).

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles

v = venn2(subsets=(1, 1, 0))
v.get_label_by_id('10').set_text('')
v.get_label_by_id('01').set_text('')

c = venn2_circles(subsets=(1, 1, 0), linestyle = 'solid')

# Style options
plt.title("Intersection of disjoint sets is the empty set")

# Add legend
cols, texts = [],[]
for i in ('10', '01'):
    cols.append(v.get_patch_by_id(i))
    texts.append(v.get_label_by_id(i)._text)
# plt.legend(handles=cols, labels=texts)

plt.show()

Example

_images/union_example.png

Fig. 1 Union example#

Example

_images/intersection_example.png

Fig. 2 Intersection example#

Exclusion and complementation#

Suppose that U is some universal set, \(X \subseteq U\) and \(Y \subseteq U\).

Definition

The set difference “X excluding Y”, which is denoted by \(X \setminus Y\), is the set

\[X \setminus Y = \{a \in X : a \notin Y \}\]

Definition

Set complementation is a special case of set exclusion. The complement of the set \(X\), which is denoted by \(X^C\) , is defined as \(X^C = U \setminus X\).

Note that \(X \cup X^C = U\) and \(X \cap X^C = \varnothing\).

Note

There are several alternative notations for the complement of a set, including \(X^C\), \(X'\), \(\bar{X}\), and \(\neg X\).

Venn diagram: set difference#

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles

v = venn2(subsets=(1, 1, 1))
v.get_label_by_id('10').set_text('A \\ B')
v.get_label_by_id('01').set_text('B \\ A')
v.get_label_by_id('11').set_text('$A \; ∩ \; B$')

c = venn2_circles(subsets=(1, 1, 1), linestyle = 'solid')

# Style options
plt.title("Set difference")

# Add legend
cols, texts = [],[]
for i in ('10', '01', '11'):
    cols.append(v.get_patch_by_id(i))
    texts.append(v.get_label_by_id(i)._text)
plt.legend(handles=cols, labels=texts, loc='upper right')

plt.show()

Venn diagram: set complementation#

Notice that the large rectangle containing both \(A\) and \(A^C\) is labelled \(U\), the universal set.

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles
from matplotlib.patches import Rectangle, Circle

fig, ax = plt.subplots()



ax.add_patch(Rectangle((-0.7, -0.5), 1.4, 1,
                       fc='lightblue',
                       alpha=0.8,
                       color='none',
                       linewidth=5))


ax.add_patch(Rectangle((-0.7, -0.5), 1.4, 1,
                       fc='none',
                       alpha=0.8,
                       color='black',
                       linewidth=3))


ax.add_patch(Circle((0, 0), 0.4,
                       fc='lightcoral',
                       alpha=0.8,
                       color='black',
                       linewidth=2,
                   linestyle='dashed'))

v = venn2(subsets=(1, 1, 1))
for i in ('10', '01', '11'):
    v.get_patch_by_id(i).set_alpha(0)
    v.get_label_by_id(i).set_text('')

v.get_label_by_id('A').set_text('')
v.get_label_by_id('B').set_text('')
    
# Style options
plt.title("Set complementation")

plt.text(0.65, 0.53, 'U', fontsize=15)
plt.text(-0.05, 0, '$A$', fontsize=15)
plt.text(0.4, 0.3, '$A^C$', fontsize=15)

cols, texts = [],[]
cols.append(ax.patches[2])
texts.append('$A$')
cols.append(ax.patches[0])
texts.append('$A^C$')

plt.legend(handles=cols, labels=texts, loc='lower right',
           bbox_to_anchor=(1, -0.15))


plt.show()

Example

_images/exclusion_example.png

Fig. 3 Exclusion/set difference example#

Example: Set complement

Suppose that the universal set is \(U = \{1, 2, 3\}\). The power set for the set \(U\) in this example is

\[2^U = \{\varnothing, \{1\} , \{2\} , \{3\} , \{1, 2\} , \{1, 3\} , \{2, 3\} , \{1, 2, 3\}\} .\]

The elements of this power set are the subsets of the universal set. The complements for each of these subsets are:

  • \(\varnothing^C = U\)

  • \(\{1\}^C = \{2, 3\}\)

  • \(\{2\}^C = \{1, 3\}\)

  • \(\{3\}^C = \{1, 2\}\)

  • \(\{1, 2\}^C = \{3\}\)

  • \(\{1, 3\}^C = \{2\}\)

  • \(\{2, 3\}^C = \{1\}\)

  • \(U^C = \varnothing\)

Symmetric difference#

Definition

The symmetric difference of \(X\) and \(Y\), which is denoted by \(X \bigtriangleup Y\), is the set

\[X \bigtriangleup Y = (X \setminus Y) \cup (Y \setminus X)\]

It is interesting to compare the operations of union and symmetric difference. They relate to alternative interpretions of the phrase “belongs to either \(X\) or \(Y\)”.

  • The set \(X \cup Y\) consists of all elements that are either in set \(X\) only, or in set \(Y\) only, or in both of these sets.

  • The set \(X \bigtriangleup Y\) consists of all elements that are either in set \(X\) only, or in set \(Y\) only, but are not in both of these sets.

Note

Exclusive or is another name for the symmetric difference operation.

Venn diagram: symmetric difference#

Note that the areas in light red together comprise the symmetric difference.

Hide code cell source
from matplotlib import pyplot as plt
from matplotlib_venn import venn2, venn2_circles

v = venn2(subsets=(1, 1, 1))
v.get_label_by_id('10').set_text('')
v.get_label_by_id('01').set_text('')
v.get_label_by_id('11').set_text('$A \; ∩ \; B$')

v.get_patch_by_id('01').set_color('lightcoral')
v.get_patch_by_id('10').set_color('lightcoral')


c = venn2_circles(subsets=(1, 1, 1), linestyle = 'solid')

# Style options
plt.title("Symmetric difference")

# Add legend
cols, texts = [],[]
cols.append(v.get_patch_by_id('11'))
texts.append(v.get_label_by_id('11')._text)
cols.append(v.get_patch_by_id('10'))
texts.append('$A \; △ \; B$')
plt.legend(handles=cols, labels=texts, loc='upper right')

plt.show()

Example

_images/symmetric_difference_example.png

Fig. 4 Symmetric difference example#

De Morgan’s laws#

De Morgan’s law simple version

Suppose that \(X\) is some set, \(A \subseteq X\) and \(B \subseteq X\). According to De Morgan’s laws, we have

\[X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B) \]

and

\[X \setminus (A \cap B) = (X \setminus A) \cup (X \setminus B) \]

De Morgan’s law general version

Let \(I\) be some index set. Note that while I is allowed to be finite, it does not have to be finite. Let \(X\) be some set and suppose that \(A_i \subseteq U\) for all \(i \in I\). According to De Morgan’s laws, we have

\[X \setminus (\cup_{i \in I} A_i) = \cap_{i \in I} (X \setminus A_i) \]

and

\[X \setminus (\cap_{i \in I} A_i) = \cup_{i \in I} (X \setminus A_i) \]

Example

Let \(X = \{1, 2, 3\}, A = \{1, 2\} \subset X\) and \(B = \{2, 3\} \subset X\). Note that \(A \cup B = \{1, 2, 3\} = X\) and \(A \cap B = \{2\}\). Note also that

  • \(X \setminus A = \{3\}, X \setminus B = \{1\}\),

  • \(X \setminus (A \cup B) = X \setminus X = \varnothing\) and

  • \(X \setminus (A \cap B) = X \setminus \{2\} = \{1, 3\}\).

We have

\[(X \setminus A) \cap (X \setminus B) = \{3\} \cap \{1\} = \varnothing = X \setminus (A \cup B)\]

and

\[(X \setminus A) \cup (X \setminus B) = \{3\} \cup \{1\} = \{1, 3\} = X \setminus (A \cap B)\]

The real number system#

There are several approaches for defining rigorously what numbers are:

  • axiomatic approach (real numbers are something that )

  • model-theoretic approach (Dedekind cuts)

The system of real numbers is an algebraic structure known as a complete ordered field. Indeed, in a sense, it is the only complete ordered field in existence. Any other complete ordered field turns out to be “isomoporhic” to the real number system. (The term “isomorphic” is a mathematical version of “essentially the same”).

The system of real numbers is formally denoted by \((\mathbb{R}, \mathbb{R}_{++}, +, \times)\), where \(+\) and \(\times\) are the familiar addition and multiplication operations for real numbers.

The set of real numbers \(\mathbb{R}\) can be viewed as the completion of the set of rational numbers \(\mathbb{Q}\) because it involves filling in the “holes” that exist in the set of rational numbers. These holes take the form of irrational numbers like \(\sqrt{2}\), \(\pi\) and \(e\).

Why aren’t the rationals enough?#

Why aren’t the rational numbers enough? What makes us think that they contain “holes”? This is a very good question. Especially when you realise that any numerical calculation on a computer will only generate a rational number.

A geometric argument for the existence of irrational numbers is perhaps the easiest way to convince yourself of their existence. Think about a right-angled triangle with a base (horizontal side) that is one metre long and whose (perpendicular) height (which is also its vertical side) is also one metre long. We know from Pythagoras’ Theorem that the length of the hypotenuse for this triangle is “the square root of two” metres long. But it can be shown that \(\sqrt{2}\) is an irrational number!

Proposition

\(\sqrt{2}\) is not a rational number.

Dedekind cuts and the density of set of rational numbers#

  • theoretical model of real numbers

  • allows for rigorous definition of real numbers in a constructive way without relying on the axioms

  • associates a real number to a set (rather, two sets forming a partition of another set)

Definition

A Dedekind cut is a partition of the rational numbers into two non-empty sets \(A\) and \(A'\) such that

  1. every rational number is in either \(A\) or \(A'\), but not in both

\[ A \cup A' = \mathbb{Q} \text{ and } A \cap A' = \varnothing \]
  1. every element of \(A\) is less than every element of \(A'\)

\[ \forall a \in A, \: \forall a' \in A' \implies a < a' \]

The set \(A\) is referred to as lower half, the set \(A'\) as upper half.

Examples of Dedekind cuts

  1. \(A \subset \mathbb{Q}: \forall a \in A \:\: a < 1\), \(A' \subset \mathbb{Q}: \forall a' \in A' \:\: a' \ge 1\)

  2. \(A \subset \mathbb{Q}: \forall a \in A \:\: a \le 1\), \(A' \subset \mathbb{Q}: \forall a' \in A' \:\: a' > 1\)

  3. \(A \subset \mathbb{Q}: \forall a \in A \:\: a^2 < 2\), \(A' \subset \mathbb{Q}: \forall a' \in A' \:\: a'^2 > 2\)

Fact

The above three examples cover all possible cases for Dedekind cuts:

  1. Upper half has the least element

  2. Lower half has the greatest element

  3. Neither half has the least or the greatest element

Fact

Dedekind cut of the third type (those which do not have the least element in the upper half and the greatest element in the lower half) defines an irrational number.

_images/dedekind.png
  • irrational numbers are objects of new type, they are not rational numbers by construction

  • fill in the “holes” between rational numbers

  • rational numbers \(\mathbb{Q}\) and irrational numbers defined by Dedekind cuts form the set of real numbers \(\mathbb{R}\)

Fact

For any real numbers \(a,b \in \mathbb{R}\) where \(a>b\) there is a real number \(c \in \mathbb{R}\) such that \(b<c<a\).

  • it follows from the proof that the number \(c\) is in fact rational

  • it also follows by repeated application of the proposition that an infinite number of rational numbers can be fitted between any two given rational numbers, however close they are in the number line

  • overall, the number line of real numbers has no gaps!

What’s next?#

Same steps as in axiomatic approach to define the common sense operations, but using Dedekind cuts as the definition of real numbers.

  • rigorous definitions of number representation using Dedekind cuts

    • decimal representation

    • continued fractions

  • rigorous definitions of algebraic operations using Dedekind cuts

    • addition

    • subtraction

    • multiplication

    • division

  • rigorous definitions of order relations from set theory

    • less than

    • greater than

    • less than or equal to

    • greater than or equal to

  • rigorous definitions of convergence and limits

  • etc.

This is re-definition of all our “common sense” knowledge about numbers in a rigorous mathematical language \(\implies\) we can use standard arithmetic operations at a deeper level of mathematical rigour.

Example

\[\begin{array}{ccc} 32^{\frac{3}{5}} & \frac{8}{27}^{\frac{2}{3}} & -9^{\frac{3}{2}} \end{array}\]

Note

Division by zero in not defined for any real number \(p\).

Note

When exponent is fractional and base is negative, the result is undefined for non-integer exponents.
See discussion here

Counting elements in sets#

Definition

The number of elements of finite set \(X\) is called the cardinality of \(X\), and is denoted by any of the following notation:

  • \(\lvert X \rvert\)

  • \(\# X\)

  • \(nX\)

  • \(n(X)\)

Counting the number of a union or an intersection of two sets \(A\) and \(B\) applying common sense may be dangerous.

Example

What is the number of elements of \(A \cup B\), \(|A \cup B|\)?

\[| \{1,2,3,4 \} \cup \{5,6,7,8\} | = 8\]

But!

\[| \{1,2,3,4 \} \cup \{3,4,5,6\} | = 6\]
  • It depends on whether \(A\) and \(B\) are disjoint or not!

General rule

\[|A \cup B| = |A| + |B| - |A \cap B|\]

Therefore, \(|A \cup B| = |A| + |B|\) if and only if \(A \cap B = \emptyset\)

Note

Be careful when solving the problems involving cardinality!

Counting Cartesian Products#

Fact

If \(A_n\) are finite for \(n=1, \ldots,N\), then

\[\#(A_1 \times \cdots \times A_N) = (\# A_1) \times \cdots \times (\# A_N)\]

That is, number of possible tuples \(=\) product of the number of possibilities for each element

Example

Number of binary sequences of length \(10\) is

\[\# [\{0, 1\} \times \cdots \times \{0, 1\}] = 2 \times \cdots \times 2 = 2^{10}\]

Examples of sets in economics#

Some sets that you might encounter during your study of economics include:

  • Budget sets

  • Weak preference sets

  • Indifference sets

  • Input requirement sets

  • Isoquants

  • Isocosts

  • Price simplices (simplexes)

We will briefly consider some of these examples below.

Sigma notation

Sigma notation is used to quickly write sums of elements index by \(i\)

\[\sum_{i=1}^n A_i = \sum_{i\in \{1,\dots,n\}} A_i = A_1 + A_2 + \dots + A_n\]

Sigma notation can be used with other operations as well, for example \(\prod_{i=1}^{n} A_i\) denotes a product, \(\times_{i=1}^{n} A_i\) denotes a Cartesian product, \(\cup_{i=1}^{n} A_i\) denotes a inion and \(\cap_{i=1}^{n} A_i\) denotes an intersection of \(A_i,\;\forall i\in\{1,\dots,n\}\).

Budget sets#

  • Linear prices with an income endowment:

\[B(p_1, p_2, · · · , p_L, y ) = \left\{ (x_1, x_2, · · · , x_L) \in \mathbb{R}_+^L : \sum_{I = 1}^{L} p_I x_I \leqslant y \right\}\]
  • Linear prices with a commodity bundle endowment:

\[B(p_1, p_2, · · · , p_L, e_1, e_2, · · · , e_L) = \left\{ (x_1, x_2, · · · , x_L) \in \mathbb{R}_+^L : \sum_{I = 1}^L p_I (x_I − e_I ) \leqslant 0 \right\}\]

These are examples of “lower contour sets” for expenditure by an individual.

Weak preference sets#

  • Reference commodity bundle version:

\[U^+(x_1, x_2, · · · , x_L) = \left\{ (y_1, y_2, · · · , y_L) \in \mathbb{R}^L_+ : U(y_1, y_2, · · · , y_L) \geqslant U (x_1, x_2, · · · , x_L) \right\}\]
  • Reference utility level version:

\[U^+(k) = \left\{ (y_1, y_2, · · · , y_L) \in \mathbb{R}^L_+ : U(y_1, y_2, · · · , y_L) \geqslant k \right\}\]

These are examples of “(weak) upper contour sets” for the utility level attained by an individual.

Indifference sets#

  • Reference commodity bundle version:

\[U^0(x_1, x_2, · · · , x_L) = \left\{ (y_1, y_2, · · · , y_L) \in \mathbb{R}^L_+ : U(y_1, y_2, · · · , y_L) = U(x_1, x_2, · · · , x_L) \right\}\]
  • Reference utility level version:

\[U^0(k) = \left\{ (y_1, y_2, · · · , y_L) \in \mathbb{R}^L_+ : U(y_1, y_2, · · · , y_L) = k \right\}\]

These are examples of “level sets” for the utility level attained by an individual.

Input requirement sets#

Consider a single output, multiple input production technology that can be represented by a production function of the form

\[y = f(x_1, x_2, · · · , x_n).\]

An input requirement set for this production technology takes the form

\[y^+(k) = \left\{(x_1, x_2, · · · , x_n) \in \mathbb{R}^n_+ : f (x_1, x_2, · · · , x_n) \geqslant k \right\}\]

This is an example of a “(weak) upper contour set” for the output level attained by a producer.

Isoquants#

Consider a single output, multiple input production technology that can be represented by a production function of the form

\[y = f(x_1, x_2, · · · , x_n).\]

An isoquant for this production technology takes the form

\[y^0(k) = \left\{(x_1, x_2, · · · , x_n) \in \mathbb{R}^n_+ : f (x_1, x_2, · · · , x_n) = k \right\}\]

This is an example of a “level set” or the output level attained by a producer.

Isocosts#

An isocost depicts the locus of all input combinations that cost the producer the same amount of money to employ.

Suppose that there are \(n \in \mathbb{N}\) distinct production inputs (or factors of production, if you prefer). An isocost for this situation takes the form

\[C^0(k) = \left\{(x_1, x_2, · · · , x_n) \in \mathbb{R}^n_+ : \sum_{i = 1}^{n} w_i x_i = k \right\}\]

where \(w_i\) is the per-unit price of input \(i\).

This is an example of a “level set” for the expenditure on inputs by a producer.

Price simplex#

In some situations in economics, it is relative prices that matter, rather than the absolute level of each individual price. In such cases, some form of price normalisation can be employed.

Common normalisations involve choosing either a particular commodity, or a particular basket of commodities, to be the numeraire. The expenditure on the the numeraire commodity, or numeraire basket of commodities, is then set equal to one.

If the numeraire basket consists of one unit of each of the \(n\) final commodities in an economy, then the set of possible prices is given by:

\[\bigtriangleup (p_1, p_2, · · · , p_n) = \left\{ (p_1, p_2, · · · , p_n) \in \mathbb{R}^n_+ : \sum_{i = 1}^{n} p_i = 1 \right\}\]

This set is known as a price “simplex”.