Set Theory

Around binary relations on sets

Leave a comment

We are considering here binary relations on a set \(A\). Let’s recall that a binary relation \(R\) on \(A\) is a subset of the cartesian product \(R \subseteq A \times A\). The statement \((x,y) \in R\) is read as \(x\) is \(R\)-related to \(y\) and also denoted by \(x R y \).

Some importants properties of a binary relation \(R\) are:

reflexive
For all \(x \in A\) it holds \(x R y\)
irreflexive
For all \(x \in A\) it holds not \(x R y\)
symmetric
For all \(x,y \in A\) it holds that if \(x R y\) then \(y R x\)
antisymmetric
For all \(x,y \in A\) if \(x R y\) and \(y R x\) then \(x=y\)
transitive
For all \(x,y,z \in A\) it holds that if \(x R y\) and \(y R z\) then \(x R z\)

A relation that is reflexive, symmetric and transitive is called an equivalence relation. Let’s see that being reflexive, symmetric and transitive are independent properties.

Symmetric and transitive but not reflexive

We provide two examples of such relations. For the first one, we take for \(A\) the set of the real numbers \(\mathbb R\) and the relation \[R = \{(x,y) \in \mathbb R^2 \, | \, xy >0\}.\] \(R\) is symmetric as the multiplication is also symmetric. \(R\) is also transitive as if \(xy > 0\) and \(yz > 0\) you get \(xy^2 z >0\). And as \(y^2 > 0\), we have \(xz > 0\) which means that \(x R z\). However, \(R\) is not reflexive as \(0 R 0\) doesn’t hold.

For our second example, we take \(A= \mathbb N\) and \(R=\{(1,1)\}\). It is easy to verify that \(R\) is symmetric and transitive. However \(R\) is not reflexive as \(n R n\) doesn’t hold for \(n \neq 1\). Continue reading Around binary relations on sets →

Algebra

A proper subspace without an orthogonal complement

Leave a comment

We consider an inner product space \(V\) over the field of real numbers \(\mathbb R\). The inner product is denoted by \(\langle \cdot , \cdot \rangle\).

When \(V\) is a finite dimensional space, every proper subspace \(F \subset V\) has an orthogonal complement \(F^\perp\) with \(V = F \oplus F^\perp\). This is no more true for infinite dimensional spaces and we present here an example.

Consider the space \(V=\mathcal C([0,1],\mathbb R)\) of the continuous real functions defined on the segment \([0,1]\). The bilinear map
\[\begin{array}{l|rcl}
\langle \cdot , \cdot \rangle : & V \times V & \longrightarrow & \mathbb R \\
& (f,g) & \longmapsto & \langle f , g \rangle = \displaystyle \int_0^1 f(t)g(t) \, dt \end{array}
\] is an inner product on \(V\).

Let’s consider the proper subspace \(H = \{f \in V \, ; \, f(0)=0\}\). \(H\) is an hyperplane of \(V\) as \(H\) is the kernel of the linear form \(\varphi : f \mapsto f(0)\) defined on \(V\). \(H\) is a proper subspace as \(\varphi\) is not always vanishing. Let’s prove that \(H^\perp = \{0\}\).

Take \(g \in H^\perp\). By definition of \(H^\perp\) we have \(\int_0^1 f(t) g(t) \, dt = 0\) for all \(f \in H\). In particular the function \(h : t \mapsto t g(t)\) belongs to \(H\). Hence
\[0 = \langle h , g \rangle = \displaystyle \int_0^1 t g(t)g(t) \, dt\] The map \(t \mapsto t g^2(t)\) is continuous, non-negative on \([0,1]\) and its integral on this segment vanishes. Hence \(t g^2(t)\) is always vanishing on \([0,1]\), and \(g\) is always vanishing on \((0,1]\). As \(g\) is continuous, we finally get that \(g = 0\).

\(H\) doesn’t have an orthogonal complement.

Moreover we have
\[(H^\perp)^\perp = \{0\}^\perp = V \neq H\]

Topology

A non-compact closed ball

Leave a comment

Consider a normed vector space \((X, \Vert \cdot \Vert)\). If \(X\) is finite-dimensional, then a subset \(Y \subset X\) is compact if and only if it is closed and bounded. In particular a closed ball \(B_r[a] = \{x \in X \, ; \, \Vert x – a \Vert \le r\}\) is always compact if \(X\) is finite-dimensional.

What about infinite-dimensional spaces?

The space \(A=C([0,1],\mathbb R)\)

Consider the space \(A=C([0,1],\mathbb R)\) of the real continuous functions defined on the interval \([0,1]\) endowed with the sup norm:
\[\Vert f \Vert = \sup\limits_{x \in [0,1]} \vert f(x) \vert\]
Is the closed unit ball \(B_1[0]\) compact? The answer is negative and we provide two proofs.

The first one is based on open covers. For \(n \ge 1\), we denote by \(f_n\) the piecewise linear map defined by \[
\begin{cases}
f_n(0)=f_n(\frac{1}{2^n}-\frac{1}{2^{n+2}})=0 \\
f_n(\frac{1}{2^n})=1 \\
f_n(\frac{1}{2^n}+\frac{1}{2^{n+2}})=f_n(1)=0
\end{cases}\] All the \(f_n\) belong to \(B_1[0]\). Moreover for \(1 \le n < m\) we have \(\frac{1}{2^n}+\frac{1}{2^{n+2}} < \frac{1}{2^m}-\frac{1}{2^{m+2}}\). Hence the supports of the \(f_n\) are disjoint and \(\Vert f_n – f_m \Vert = 1\).

Now consider the open cover \(\mathcal U=\{B_{\frac{1}{2}}(x) \, ; \, x \in B_1[0]\}\). For \(x \in B_1[0]\}\) and \(u,v \in B_{\frac{1}{2}}(x)\), \(\Vert u -v \Vert < 1\). Therefore, each \(B_{\frac{1}{2}}(x)\) contains at most one \(f_n\) and a finite subcover of \(\mathcal U\) will contain only a finite number of \(f_n\) proving that \(A\) is not compact.

Second proof based on convergent subsequence. As \(A\) is a metric space, it is enough to prove that \(A\) is not sequentially compact. Consider the sequence of functions \(g_n : x \mapsto x^n\). The sequence is bounded as for all \(n \in \mathbb N\), \(\Vert g_n \Vert = 1\). If \((g_n)\) would have a convergent subsequence, the subsequence would converge pointwise to the function equal to \(0\) on \([0,1)\) and to \(1\) at \(1\). As this function is not continuous, \((g_n)\) cannot have a subsequence converging to a map \(g \in A\).

Riesz’s theorem

The non-compactness of \(A=C([0,1],\mathbb R)\) is not so strange. Based on Riesz’s lemma one can show that the unit ball of an infinite-dimensional normed space \(X\) is never compact. This is sometimes known as the Riesz’s theorem.

The non-compactness of \(A=C([0,1],\mathbb R)\) is just standard for infinite-dimensional normed vector spaces!

Analysis

Continuity under the integral sign

Leave a comment

We consider here a measure space \((\Omega, \mathcal A, \mu)\) and \(T \subset \mathbb R\) a topological subspace. For a map \(f : T \times \Omega \to \mathbb R\) such that for all \(t \in T\) the map \[
\begin{array}{l|rcl}
f(t, \cdot) : & \Omega & \longrightarrow & \mathbb R \\
& \omega & \longmapsto & f(t,\omega) \end{array}
\] is integrable, one can define the function \[
\begin{array}{l|rcl}
F : & T & \longrightarrow & \mathbb R \\
& t & \longmapsto & \int_\Omega f(t,\omega) \ d\mu(\omega) \end{array}
\]

Following theorem is well known (and can be proven using dominated convergence theorem):

THEOREM for an adherent point \(x \in T\), if

  • \(\forall \omega \in \Omega \lim\limits_{t \to x} f(t,\omega) = \varphi(\omega)\)
  • There exists a map \(g : \Omega \to \mathbb R\) such that \(\forall t \in T, \, \forall \omega \in \Omega, \ \vert f(t,\omega) \vert \le g(\omega)\)

then \(\varphi\) is integrable and \[
\lim\limits_{t \to x} F(t) = \int_\Omega \varphi(\omega) \ d\mu(\omega)\]
In other words, one can switch \(\lim\) and \(\int\) signs.

We provide here a counterexample showing that the conclusion of the theorem might not hold if \(f\) is not bounded by a function \(g\) as supposed in the premises of the theorem. Continue reading Continuity under the integral sign →

Analysis

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

Leave a comment

We already provided here an example of a trigonometric series that is not the Fourier series of a Riemann-integrable function (namely the function \(\displaystyle x \mapsto \sum_{n=1}^\infty \frac{\sin nx}{\sqrt n}\)).

Applying an Abel-transformation (like mentioned in the link above), one can see that the function \[f(x)=\sum_{n=2}^\infty \frac{\sin nx}{\ln n}\] is everywhere convergent. We now prove that \(f\) cannot be the Fourier series of a Lebesgue-integrable function. The proof is based on the fact that for a \(2 \pi\)-periodic function \(g\), Lebesgue-integrable on \([0,2 \pi]\), the sum \[\sum_{n=1}^\infty \frac{c_n-c_{-n}}{n}\] is convergent where \((c_n)_{n \in \mathbb Z}\) are the complex Fourier coefficients of \(g\): \[c_n = \frac{1}{2 \pi} \int_0^{2 \pi} g(t)e^{-ikt} \ dt.\] As the series \(\displaystyle \sum_{n=2}^\infty \frac{1}{n \ln n}\) is divergent, we will be able to conclude that the sequence defined by \[\gamma_0=\gamma_1=\gamma_{-1} = 0, \, \gamma_n=- \gamma_{-n} = \frac{1}{\ln n} \ (n \ge 2)\] cannot be the Fourier coefficients of a Lebesgue-integrable function, hence that \(f\) is not the Fourier series of any Lebesgue-integrable function. Continue reading A trigonometric series that is not a Fourier series (Lebesgue-integration) →

Algebra

Intersection and sum of vector subspaces

Leave a comment

Let’s consider a vector space \(E\) over a field \(K\). We’ll look at relations involving basic set operations and sum of subspaces. We denote by \(F, G\) and \(H\) subspaces of \(E\).

The relation \((F \cap G) + H \subset (F+H) \cap (G + H)\)

This relation holds. The proof is quite simple. For any \(x \in (F \cap G) + H\) there exists \(y \in F \cap G\) and \(h \in H\) such that \(x=y+h\). As \(y \in F\), \(x \in F+H\) and by a similar argument \(x \in F+H\). Therefore \(x \in (F+H) \cap (G + H)\).

Is the inclusion \((F \cap G) + H \subset (F+H) \cap (G + H)\) always an equality? The answer is negative. Take for the space \(E\) the real 3 dimensional space \(\mathbb R^3\). And for the subspaces:

  • \(H\) the plane of equation \(z=0\),
  • \(F\) the line of equations \(y = 0, \, x=z\),
  • \(G\) the line of equations \(y = 0, \, x=-z\),

Continue reading Intersection and sum of vector subspaces →

Analysis

Playing with liminf and limsup

Leave a comment

Let’s consider real sequences \((a_n)_{n \in \mathbb N}\) and \((b_n)_{n \in \mathbb N}\). We look at inequalities involving limit superior and limit inferior of those sequences. Following inequalities hold:
\[\begin{aligned}
& \liminf a_n + \liminf b_n \le \liminf (a_n+b_n)\\
& \liminf (a_n+b_n) \le \liminf a_n + \limsup b_n\\
& \liminf a_n + \limsup b_n \le \limsup (a_n+b_n)\\
& \limsup (a_n+b_n) \le \limsup a_n + \limsup b_n
\end{aligned}\] Let’s prove for example the first inequality, reminding first that \[
\liminf\limits_{n \to \infty} a_n = \lim\limits_{n \to \infty} \left(\inf\limits_{m \ge n} a_m \right).\] For \(n \in \mathbb N\), we have for all \(m \ge n\) \[\inf\limits_{k \ge n} a_k + \inf\limits_{k \ge n} b_k \le a_m + b_m\] hence \[\inf\limits_{k \ge n} a_k + \inf\limits_{k \ge n} b_k \le \inf\limits_{k \ge n} \left(a_k+b_k \right)\] As the sequences \((\inf\limits_{k \ge n} a_k)_{n \in \mathbb N}\) and \((\inf\limits_{k \ge n} b_k)_{n \in \mathbb N}\) are non-increasing we get for all \(n \in \mathbb N\), \[\liminf a_n + \liminf b_n \le \inf\limits_{m \ge n} \left(a_m+b_m \right)\] which leads finally to the desired inequality \[\liminf a_n + \liminf b_n \le \liminf (a_n+b_n).\] Continue reading Playing with liminf and limsup →

Set Theory

There is no greatest cardinal

Leave a comment

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}]\).

Continue reading There is no greatest cardinal →

Set Theory

Counterexamples around cardinality (part 2)

3 Comments

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) →

Algebra

A non Archimedean ordered field

1 Comment

Let’s recall that an ordered field \(K\) is said to be Archimedean if for any \(a,b \in K\) such that \(0 \lt a \lt b\) it exists a natural number \(n\) such that \(na > b\).

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{x}{1} \in \mathbb R(x)\). \(h(x)\) is a positive element, i.e. belongs to \(P\) as \(h-1 = \frac{x-1}{1}\). For any \(n \in \mathbb N\), we have
\[h – n 1=\frac{x-n}{1} \in P\] as the leading coefficients of \(x-n\) and \(1\) are both equal to \(1\). Therefore, we have \(h \gt n 1\) for all \(n \in \mathbb N\), proving that \(\mathbb R(x)\) is not Archimedean.

Mathematical exceptions to the rules or intuition