Cardinality of sets of functions

[mnb96]

Hello,
let's consider the set $\Omega$ of all the continuous and integrable functions $f:R \to R$.
Suppose we now take two subsets A and B, where:

- A is the subset of all the gaussian functions centered at the origin: $\exp(-ax^2)$, where a>0
- B is the set of all the even functions: $f(x)=f(-x)$

It is trivial to prove that $A\subset B$.
However, my question is: is it possible to "quantify" how bigger the subset B is compared to A ?
How should I count the cardinality of A and B ?
My goal is computing the ratio of cardinalities: |B|/|A|. Is it possible?

Thanks.

 

[tiny-tim]

hello mnb96!

the set A can be indexed by one parameter, a …

how many parameters are needed to index the set B ?

 

[mnb96]

uhm...how many parameters do I need to form a continuous and integrable even-function?

I don't know! intuitively I would guess an infinite amount of parameters: the cardinality of $\mathbb{R}^+$, but I might be wrong, as I don't know how to (dis)prove it, and I have no idea on how to constrain the parameters so that the function they represent is in $\Omega$ (= is continuous and integrable).

EDIT: oh wait...maybe I could represent them with Taylor series: in that case all the coefficients of the even-powers are potentially non-zero (still they are infinite, and who knows if they generate an integrable function?).

Btw...how would you use the number of parameters to identify the cardinality of a set? For example A is identified with one parameter. Fine, so what is its cardinality?

 

[AKG]

Let $\mathfrak{c}$ denote the cardinality of the continuum. Then it's easy to see that:

$$|\mathbb{R}| = |\mathbb{R} ^+| = |A| = |B| = |\Omega | = \mathfrak{c}$$

The following equalities/inequalities are obvious:

$$\mathfrak{c} = |\mathbb{R}| \geq |\mathbb{R}^+| = |A| \leq |B| \leq |\Omega |$$

So it'll suffice to show:

$$|\mathbb{R}| = |\mathbb{R} ^+|,\ |\mathbb{R}| = |\Omega |$$

The first is perhaps a good exercise for you to do. For the second, first observe that a continuous function is completely determined by how it acts on the rationals. Moreover, since every real number is the limit of a (countable) sequence of rationals, every function $\mathbb{Q} \to \mathbb{R}$ is the pointwise limit of some (countable) sequence of functions $\mathbb{Q} \to \mathbb{Q}$. So we get an upper bound on $|\Omega |$ if we can count the number of countable sequences of functions from the rationals to the rationals. Since the rationals and naturals have the same cardinality, we want to count the number of countable sequences of functions $\mathbb{N} \to \mathbb{N}$. Such a sequence $f_0, f_1, \dots$ can be regarded as a function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ (where $f(m,n) = f_m(n)$). If you haven't seen it already, you should do the following:

Exercise: $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$

So we've reduced this to counting the number of functions $\mathbb{N} \to \mathbb{N}$. Since such a function can be regarded as a subset of $\mathbb{N} \times \mathbb{N}$, we can reduce the problem to counting the number of subsets of $\mathbb{N}$ by the above exercise. The following exercise finishes it:

Exercise: $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ where $\mathcal{P}$ denotes the power set.

--------------------

So $|A| = |B| = \mathfrak{c}$, but it's also easy to see that $|B \setminus A| = \mathfrak{c}$, so that's one way in which you might want to quantify the intuitive feeling that "$B$ is much bigger than $A$." It doesn't make sense to divide or subtract infinite cardinals, so the ratio $|B|/|A|$ doesn't make sense.

In fact for infinite cardinals, addition and multiplication aren't that interesting:

$$\kappa \times \lambda = \kappa + \lambda = \mbox{max}\{\kappa , \lambda \}$$

Exponentiation however is of great interest, and studying the possibilities of $\kappa ^{\lambda}$ is indeed its own sub-discipline of set theory.

--------------------

Cardinality is the most basic way to measure size, but there are other ways in which you may wish to measure size which let you say more precisely how much bigger $|B|$ is than $A$. Another way is topologically: $\Omega$ has a natural structure as a metric space, using the bounded sup metric. You may want to ask whether $A$ is meager with respect to this topology, and whether $B$ is not. Yet another way is algebraically. $\Omega$ has a natural vector space structure, where $B$ is a subspace and $A$ spans a proper subspace of $B$. You may want to ask about the codimension of $\mbox{Span}(A)$ in $B$.

 

[mnb96]

Hi AKG,
thanks for your precise and interesting explanation.
After having "meditated" a bit on your answer, I came up to the conclusion that for my purposes it would be probably more interesting to consider $\Omega$ as a vector space and try to find the codimension of Span(A) in B.
However, I have two questions:

1) B are continuous integrable even function: how would you find a finite amount of basis functions to represent this subspace?

2) Doesn't the concept of codimension have meaning only for finite-dimensional vector spaces?

Thanks again!

 

[AKG]

Hi AKG,
thanks for your precise and interesting explanation.

You're welcome!

After having "meditated" a bit on your answer, I came up to the conclusion that for my purposes it would be probably more interesting to consider $\Omega$ as a vector space and try to find the codimension of Span(A) in B.
However, I have two questions:

1) B are continuous integrable even function: how would you find a finite amount of basis functions to represent this subspace?

2) Doesn't the concept of codimension have meaning only for finite-dimensional vector spaces?

Thanks again!

1) First observe quickly that $B$ is a subspace of $\Omega$, i.e. it satisfies the required closure properties, so it can be regarded as a vector space by itself. Thus it makes sense to ask whether it has a basis. You're correct, it won't have a finite basis, thus $B$ is an example of an infinite dimensional vector space. Since $|B| = \mathfrak{c}$, the largest its dimension could possibly be is $\mathfrak{c}$. I can find a set of $\mathfrak{c}$ linearly independent vectors in $B$, hence its dimension is also at most $\mathfrak{c}$. Thus its dimension is precisely $\mathfrak{c}$ (as a vector space over $\mathbb{R}$).

2) The definition extends to the infinite-dimensional case: If $W$ is a subspace of $V$, then the codimension of $W$ in $V$ is defined to be the dimension of the quotient space $V/W$. It's not hard to show that if you can find a basis $\alpha$ for $W$ and a basis $\beta$ for $V$ such that $\alpha \subset \beta$, then:

Exercise (if you're comfortable with the notion of quotient spaces):
$$\mbox{dim}(V/W) = |\beta \setminus \alpha|$$

So in our case, we have $W = \mbox{Span}(A)$, and $V = B$.

Exercise: $A$ is in fact linearly independent, hence it forms a basis for $\mbox{Span}(A)$.

So we may set $\alpha = A$. Note also that this justifies the claim I made earlier about being able to find a $\mathfrak{c}$-sized linearly independent subset of $B$. So in theory, what we want to do now is extend $\alpha$ to a basis $\beta \supset \alpha$ of $B$ and then count $|\beta \setminus \alpha |$. In practice, since we already have the guess that $B$ is much bigger than $A$, our guess is that this count will be as large as it can be, namely $\mathfrak{c}$. To prove this guess, it'll be easier to find an easy-to-describe class of functions $\gamma$ such that $\alpha \cup \gamma$ is linearly independent and contained in $B$, and $|\gamma | = \mathfrak{c}$.

The best rule of thumb I have for undergrads is, when coming up with examples or counterexamples, DON'T THINK TOO HARD! A classic example: if you're asked to find an invertible matrix that's not diagonalizable, try to think of a 2x2 matrix with only 0-1 entries, rather than a 3x3 or 4x4 matrix with all sorts of various numerical entries. In this case, we already know that the family of functions $x \mapsto \exp (-ax^2)$ is a linearly independent family of size $\mathfrak{c}$ belonging to $B$.

Exercise: The family $\gamma$ of functions $x \mapsto \exp(-ax^4)$ is contained in $B$, has size $\mathfrak{c}$, and $\alpha \cup \gamma$ is linearly independent.

 

[AKG]

By the way, by "integrable" do you mean that the integral $\int _{-\infty} ^{\infty} f(x)dx$ exists and equals a finite number, or simply that the function $f$ has an antiderivative? If it's the latter, then saying "integrable continuous" is redundant since continuity implies that kind of integrability.

 

[mnb96]

Hi AKB,
thanks a lot! your answers are very dense and complete.
I am still going through it, so let's try to clarify some points.

...First observe quickly that $B$ is a subspace of $\Omega$, ... ... ... ..., the largest its dimension could possibly be is $\mathfrak{c}$. I can find a set of $\mathfrak{c}$ linearly independent vectors in $B$, hence its dimension is also at most $\mathfrak{c}$.

Ok, are you referring, for example, to the Fourier bases (only real part), or perhaps to the Taylor polynomials (only even grade), and so on...?

Thus its dimension is precisely $\mathfrak{c}$ (as a vector space over $\mathbb{R}$).

How did you deduce, that if the dimension is at most $\mathfrak{c}$, then it must be exactly $\mathfrak{c}$?
Intuitively it makes sense, but still, it would be nice to understand it with a bit of rigor.

The definition extends to the infinite-dimensional case: If $W$ is a subspace of $V$, then the codimension of $W$ in $V$ is defined to be the dimension of the quotient space $V/W$

I have to review the notion of quotient space.
When I have refreshed the topic, I will come back to the proof & exercises.

By the way, by "integrable" do you mean that the integral $\int _{-\infty} ^{\infty} f(x)dx$ exists and equals a finite number

Yes, I meant this one.

---
By the way, what is the main difference between what you proved now (using the notion of vector space), and the statement that a set is meager with respect to another set?

Thanks again!

 

[AKG]

We agree that $B$ is a subspace right? The sum of two even functions is even, a scalar multiple of an even function is even, and the zero function is even. Therefore, it makes sense to ask for a basis for $B$. Like with $\mathbb{R}^2$, if we consider the line through the origin $y = x$, it's a subspace, so we can ask to find a basis of it. On the other hand, the line $y = x + 1$ is not a subspace, so it doesn't make sense to ask for a basis for it.

So at this point, all I'm saying is that $B$ has a basis, I'm not saying what it is. Let's quickly review what a basis is:

For $\beta \subset B$, we say $\beta$ is linearly independent[/itex] iff for every finite linear combination of vectors in $\beta$ the linear combination is $\vec{0}$ iff all the coefficients appearing in the linear combination are 0. $\beta$ spans $B$ iff every vector in $B$ can be written as a finite linear combination of vectors in $\beta$.

$\beta$ is a basis for $B$ iff it's linearly independent and spans $B$

or, equivalently

$\beta$ is a basis for $B$ iff every vector in $B$ can be written in a unique way as a finite linear combination of vectors in $\beta$

I emphasized finite throughout my definitions. If you take the second equivalent formulation of "basis" and replace "finite" with "countable," you get a slightly different notion of basis known as a Schauder basis. Sometimes, to make the distinction more clear, the notion of basis where "finite" is used is called a Hamel basis. But when you see the word "basis" used somewhere and it's not specified whether they mean Hamel basis or Schauder basis, i.e. they don't specify whether only finite linear combinations are allowed or whether countably infinite combinations are being allowed, the standard meaning is Hamel basis, i.e. only finite combinations.

So the $\beta$ we're (in theory) looking for is a basis (= Hamel basis) but the examples you gave, such as the real parts of the Fourier basis, are Schauder bases. So, in theory, we're looking for a set of functions $\beta$ such that every even continuous integrable function can be written as a finite linear combination of those functions, in a unique way. I can't give you a nice, explicit list of vectors that'll do the trick. The reason is that the very existence of a basis for $B$ depends on the axiom of choice, and typically anything whose existence require AC cannot be described in an explicit manner (otherwise it wouldn't have required AC!). However, AC is used ubiquitously in mathematics and this is no reason to doubt the existence of a basis. In fact:

Fact: The statement "every vector space has a basis" is equivalent to the axiom of choice.

Also, without AC, the notion of cardinality itself changes drastically.

Anyways, using AC, we have the following fact:

Fact: Every vector space has a basis, and any two bases of the same vector space have the same cardinality, hence "dimension" is a well-defined concept.

Recall the dimension of a vector space is the cardinality one of/all of its bases.

How did you deduce, that if the dimension is at most $\mathfrak{c}$, then it must be exactly $\mathfrak{c}$?
Intuitively it makes sense, but still, it would be nice to understand it with a bit of rigor.

First I said that its dimension is at most $\mathfrak{c}$ since the cardinality of the whole space $B$ itself is $\mathfrak{c}$. Next I said its dimension is at least $\mathfrak{c}$ since it contains a linearly independent subset of size $\mathfrak{c}$. Hence, its dimension equals $\mathfrak{c}$. To get the at least part, I used the following:

Fact: If $V$ is a vector space and it has a linearly independent subset of size $\kappa$, then $\mbox{dim}(V) \geq \kappa$.

This fact should be familiar to you in the case $\kappa$ finite. It happens to hold true in general.

By the way, what is the main difference between what you proved now (using the notion of vector space), and the statement that a set is meager with respect to another set?

Thanks again!

Again, you're welcome!

There's a very big difference between what I proved here and the statement that one set is meager with respect to another. Firstly, not every topological space has a natural vector space structure, so there may be two sets where it makes sense to compare them topologically (e.g. decide if one is meager as a topological subspace of the other) but not be able to compare them algebraically (e.g. decide if one has large codimension as a vector subspace of the other). Likewise, not every vector space has a natural topology.

Furthermore, there are examples of spaces with a natural topology and a natural vector space structure, such that a given subset is large in one sense but small in the other. For example, if we take the space $\mathbb{R}^{\infty}$ of countably infinite sequences of real numbers that are eventually 0, then there's a natural vector space structure:

$$(x_0, x_1, \dots ) + (y_0, y_1, \dots ) = (x_0 + y_0, x_1 + y_1, \dots )$$

and you can guess how scalar multiplication works. The subset:

$$A = \{ (x_0, x_1, \dots ) \in \mathbb{R}^{\infty} : x_0 = 0 \}$$

has codimension 1, hence it's a relatively large algebraically speaking. However $\mathbb{R}^{\infty}$ has some natural topological structures it inherits as a subspace of $\mathbb{R}^{\omega}$, where the latter set can be given the product topology or the box topology as the $\omega$-fold product of the topological space $\mathbb{R}$. Never mind if you don't know what some of those words mean. The bottom line is that, in either of those topologies, A forms a meager subspace of $\mathbb{R}^{\infty}$, in fact it forms a nowhere dense subset.

Finally, it's worth noting that there are different ways to measure relative size, it all depends on the context. If there's a vector space structure, there are algebraic ways of measuring relative size, like codimension, and if there's a topology, the notion of meagerness plays the role of "relatively small" or "negligible." If there's a natural measure, we can ask whether a certain set has measure 0. If we have an ultrafilter on the larger set in question, we can ask whether the subset in question belongs to said ultrafilter. If the larger set in question has a natural well-order, we can ask whether the subset is closed-unbounded, or whether it's stationary. Etc, etc, etc.

 

[AKG]

We agree that $B$ is a subspace right? The sum of two even functions is even, a scalar multiple of an even function is even, and the zero function is even. Therefore, it makes sense to ask for a basis for $B$. Like with $\mathbb{R}^2$, if we consider the line through the origin $y = x$, it's a subspace, so we can ask to find a basis of it. On the other hand, the line $y = x + 1$ is not a subspace, so it doesn't make sense to ask for a basis for it.

So at this point, all I'm saying is that $B$ has a basis, I'm not saying what it is. Let's quickly review what a basis is:

For $\beta \subset B$, we say $\beta$ is linearly independent iff for every finite linear combination of vectors in $\beta$ the linear combination is $\vec{0}$ iff all the coefficients appearing in the linear combination are 0. $\beta$ spans $B$ iff every vector in $B$ can be written as a finite linear combination of vectors in $\beta$.

$\beta$ is a basis for $B$ iff it's linearly independent and spans $B$

or, equivalently

$\beta$ is a basis for $B$ iff every vector in $B$ can be written in a unique way as a finite linear combination of vectors in $\beta$

I emphasized finite throughout my definitions. If you take the second equivalent formulation of "basis" and replace "finite" with "countable," you get a slightly different notion of basis known as a Schauder basis. Sometimes, to make the distinction more clear, the notion of basis where "finite" is used is called a Hamel basis. But when you see the word "basis" used somewhere and it's not specified whether they mean Hamel basis or Schauder basis, i.e. they don't specify whether only finite linear combinations are allowed or whether countably infinite combinations are being allowed, the standard meaning is Hamel basis, i.e. only finite combinations.

So the $\beta$ we're (in theory) looking for is a basis (= Hamel basis) but the examples you gave, such as the real parts of the Fourier basis, are Schauder bases. So, in theory, we're looking for a set of functions $\beta$ such that every even continuous integrable function can be written as a finite linear combination of those functions, in a unique way. I can't give you a nice, explicit list of vectors that'll do the trick. The reason is that the very existence of a basis for $B$ depends on the axiom of choice, and typically anything whose existence require AC cannot be described in an explicit manner (otherwise it wouldn't have required AC!). However, AC is used ubiquitously in mathematics and this is no reason to doubt the existence of a basis. In fact:

Fact: The statement "every vector space has a basis" is equivalent to the axiom of choice.

Also, without AC, the notion of cardinality itself changes drastically.

Anyways, using AC, we have the following fact:

Fact: Every vector space has a basis, and any two bases of the same vector space have the same cardinality, hence "dimension" is a well-defined concept.

Recall the dimension of a vector space is the cardinality one of/all of its bases.

How did you deduce, that if the dimension is at most $\mathfrak{c}$, then it must be exactly $\mathfrak{c}$?
Intuitively it makes sense, but still, it would be nice to understand it with a bit of rigor.

First I said that its dimension is at most $\mathfrak{c}$ since the cardinality of the whole space $B$ itself is $\mathfrak{c}$. Next I said its dimension is at least $\mathfrak{c}$ since it contains a linearly independent subset of size $\mathfrak{c}$. Hence, its dimension equals $\mathfrak{c}$. To get the at least part, I used the following:

Fact: If $V$ is a vector space and it has a linearly independent subset of size $\kappa$, then $\mbox{dim}(V) \geq \kappa$.

This fact should be familiar to you in the case $\kappa$ finite. It happens to hold true in general.

By the way, what is the main difference between what you proved now (using the notion of vector space), and the statement that a set is meager with respect to another set?

Thanks again!

Again, you're welcome!

There's a very big difference between what I proved here and the statement that one set is meager with respect to another. Firstly, not every topological space has a natural vector space structure, so there may be two sets where it makes sense to compare them topologically (e.g. decide if one is meager as a topological subspace of the other) but not be able to compare them algebraically (e.g. decide if one has large codimension as a vector subspace of the other). Likewise, not every vector space has a natural topology.

Furthermore, there are examples of spaces with a natural topology and a natural vector space structure, such that a given subset is large in one sense but small in the other. For example, if we take the space $\mathbb{R}^{\infty}$ of countably infinite sequences of real numbers that are eventually 0, then there's a natural vector space structure:

$$(x_0, x_1, \dots ) + (y_0, y_1, \dots ) = (x_0 + y_0, x_1 + y_1, \dots )$$

and you can guess how scalar multiplication works. The subset:

$$A = \{ (x_0, x_1, \dots ) \in \mathbb{R}^{\infty} : x_0 = 0 \}$$

has codimension 1, hence it's a relatively large algebraically speaking. However $\mathbb{R}^{\infty}$ has some natural topological structures it inherits as a subspace of $\mathbb{R}^{\omega}$, where the latter set can be given the product topology or the box topology as the $\omega$-fold product of the topological space $\mathbb{R}$. Never mind if you don't know what some of those words mean. The bottom line is that, in either of those topologies, A forms a meager subspace of $\mathbb{R}^{\infty}$, in fact it forms a nowhere dense subset.

Finally, it's worth noting that there are different ways to measure relative size, it all depends on the context. If there's a vector space structure, there are algebraic ways of measuring relative size, like codimension, and if there's a topology, the notion of meagerness plays the role of "relatively small" or "negligible." If there's a natural measure, we can ask whether a certain set has measure 0. If we have an ultrafilter on the larger set in question, we can ask whether the subset in question belongs to said ultrafilter. If the larger set in question has a natural well-order, we can ask whether the subset is closed-unbounded, or whether it's stationary. Etc, etc, etc.