# There is no greatest cardinal

We have seen in this article several sets that are infinite and countable. Namely, the set of natural numbers $$\mathbb N$$, the set of integers $$\mathbb Z$$, the set of rational numbers $$\mathbb Q$$. We have seen that the product $$\mathbb N \times \mathbb N$$ is also countable. The question then arises, “Are all infinite sets countable?”.

The answer is negative and we prove that $$\mathbb R$$ is not countable.

### The set of all reals $$\mathbb R$$ is not countable

Suppose for the sake of contradiction that $$\mathbb R$$ is countable and that $$\mathbb R = \{x_n \ | \ n \in \mathbb N\}$$, the $$x_n$$ being all distinct. We build by induction two sequences $$(a_n)_{n \in \mathbb N}$$ increasing and $$(b_n)_{n \in \mathbb N}$$ decreasing such that:

• $$a_n < b_n$$ for all $$n \in \mathbb N$$,
• $$\vert a_n – b_n \vert$$ converges to zero,
• and $$x_n \notin [a_{n+1},b_{n+1}]$$.

# Counterexamples around cardinality (part 2)

I follow on here from the initial article on cardinality. In that article, we have seen that $$\mathbb N$$ contains an infinite countable subset whose complement is also infinite. Namely the subsets of even and odd integers.

Let’s now consider the set $$\mathbb N \times \mathbb N$$. $$\mathbb N \times \mathbb N$$ contains a countable infinite number of copies of $$\mathbb N$$, as for all $$i \in \mathbb N$$, $$\{i\} \times \mathbb N \subset \mathbb N \times \mathbb N$$. Surprisingly, it is however possible to define a bijection between $$\mathbb N \times \mathbb N$$ and $$\mathbb N$$.

### $$\mathbb N \times \mathbb N$$ is equinumerous to $$\mathbb N$$

Consider the map $\begin{array}{l|rcl} \varphi : & \mathbb N \times \mathbb N & \longrightarrow & \mathbb N\\ & (n,m) & \longmapsto & 2^{n-1} (2m-1) \end{array}$ $$\varphi$$ is one-to-one. Suppose that $$2^{n_1-1} (2m_1-1) = 2^{n_2-1} (2m_2-1)$$. If $$n_1=1$$, we must also have $$n_2=1$$ as $$2 m_1 – 1$$ is odd. That implies $$(n_1,m_1)=(n_2,m_2)$$. Let’s now suppose $$n_1 >1$$. According to Euclid’s lemma, $$2^{n_1-1}$$ divides $$2^{n_2-1}$$ as $$2^{n_1-1}$$ is even and $$2m_2 – 1$$ odd. By symmetry $$2^{n_2-1}$$ also divides $$2^{n_1-1}$$. Finally, $$2^{n_1 – 1} = 2^{n_2 – 1}$$, $$n_1 = n_2$$ and consequently $$m_1 = m_2$$. Continue reading Counterexamples around cardinality (part 2)

# A non Archimedean ordered field

Let’s recall that an ordered field $$K$$ is said to be Archimedean if for any $$x \in K$$ there exists a natural number $$n$$ such that $$n > x$$.

The ordered fields $$\mathbb Q$$ or $$\mathbb R$$ are Archimedean. We introduce here the example of an ordered field which is not Archimedean. Let’s consider the field of rational functions
$\mathbb R(x) = \left\{\frac{S(x)}{T(x)} \ | \ S, T \in \mathbb R[x] \right\}$ For $$f(x)=\frac{S(x)}{T(x)} \in \mathbb R(x)$$ we can suppose that the polynomials have a constant polynomial greatest common divisor.

Now we define $$P$$ as the set of elements $$f(x)=\frac{S(x)}{T(x)} \in \mathbb R(x)$$ in which the leading coefficients of $$S$$ and $$T$$ have the same sign.

One can verify that the subset $$P \subset \mathbb R(x)$$ satisfies following two conditions:

ORD 1
Given $$f(x) \in \mathbb R(x)$$, we have either $$f(x) \in P$$, or $$f(x)=0$$, or $$-f(x) \in P$$, and these three possibilities are mutually exclusive. In other words, $$\mathbb R(x)$$ is the disjoint union of $$P$$, $$\{0\}$$ and $$-P$$.
ORD 2
For $$f(x),g(x) \in P$$, $$f(x)+g(x)$$ and $$f(x)g(x)$$ belong to $$P$$.

This means that $$P$$ is a positive cone of $$\mathbb R(x)$$. Hence, $$\mathbb R(x)$$ is ordered by the relation
$f(x) > 0 \Leftrightarrow f(x) \in P.$

Now let’s consider the rational fraction $$h(x)=\frac{1}{x} \in \mathbb R(x)$$. $$h(x)$$ is a positive element, i.e. belongs to $$P$$. And for any $$n \in \mathbb N$$, we have
$h(x)-n=\frac{1}{x}-n=\frac{x-n}{x} \in P$ as the leading coefficients of $$x$$ and $$x-n$$ are both equal to $$1$$. Therefore, we have $$h(x) > n$$ for all $$n \in \mathbb N$$, proving that $$\mathbb R(x)$$ is not Archimedean.

# A trigonometric series that is not a Fourier series (Riemann-integration)

We’re looking here at convergent trigonometric series like $f(x) = a_0 + \sum_{k=1}^\infty (a_n \cos nx + b_n \sin nx)$ which are convergent but are not Fourier series. Which means that the terms $$a_n$$ and $$b_n$$ cannot be written$\begin{array}{ll} a_n = \frac{1}{\pi} \int_0^{2 \pi} g(t) \cos nt \, dt & (n= 0, 1, \dots) \\ b_n = \frac{1}{\pi} \int_0^{2 \pi} g(t) \sin nt \, dt & (n= 1, 2, \dots) \end{array}$ where $$g$$ is any integrable function.

This raises the question of the type of integral used. We cover here an example based on Riemann integral. I’ll cover a Lebesgue integral example later on.

We prove here that the function $f(x)= \sum_{n=1}^\infty \frac{\sin nx}{\sqrt{n}}$ is a convergent trigonometric series but is not a Fourier series. Continue reading A trigonometric series that is not a Fourier series (Riemann-integration)

# Counterexamples around cardinality (part 1)

In mathematics, the cardinality of a set is a measure of the “number of elements of the set”. We denote by $$|A|$$ the cardinality of the set $$A$$. We say that $$A$$ and $$B$$ have the same cardinality if there exists a bijection from $$A$$ onto $$B$$. Such sets said to be equinumerous.

The finite sets satisfy the property that if $$A \subset B$$ and $$A$$ and $$B$$ have the same cardinality then $$A=B$$. For example take $$A=\{2,5,42\}$$. If $$A \subset B$$ and $$B$$ has more elements than $$A$$, a bijection $$f$$ from $$A$$ to $$B$$ cannot exist as an element in $$B \setminus \{f(2),f(5),f(42)\}$$ won’t have an inverse image under $$f$$.

This becomes false for infinite sets. Let’s give some examples.

### Proper subsets of $$\mathbb N$$ equinumerous to $$\mathbb N$$

The set $$A$$ of the positive even integers is strictly included in $$\mathbb N$$: there exist odd positive integers! However, $$A$$ is equinumerous to $$\mathbb N$$. The map $$f : n \to 2n$$ is a bijection from $$A$$ onto $$\mathbb N$$.

For our second example, consider the set $$\mathbb P$$ of prime numbers. We recall that $$\mathbb P$$ is infinite. The proof is quite simple by contradiction. Suppose that there is only a finite number $$\{p_1, \dots, p_n\}$$ of prime numbers and consider the number $$N = p_1 p_2 \cdots p_n + 1$$. As a consequence of the fundamental theorem of arithmetic, a prime $$q$$ divides $$N$$. However $$q \notin \{p_1, \dots, p_n\}$$ as this would imply $$q$$ divides $$1$$. From there, we can define by induction a bijection from $$\mathbb N$$ onto $$\mathbb P$$ by defining $f(n)=\begin{cases} 2 & \text{for } n=1\\ \min (\mathbb P \setminus \{p_1, \dots, p_n\}) & \text{else } \end{cases}$ Continue reading Counterexamples around cardinality (part 1)