Skip to main content
added 1244 characters in body
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example). The Baire class of functions is the least collection of functions $f:\mathbb R\to\mathbb R$ that contains the continuous functions and is closed under limits.

This argument shows that even if you iterate the process (theThe Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$: Baire class one functions are pointwise limits of sequences of continuous functions. Baire class two functions are pointwise limits of sequences of Baire class one functions, etc. You need to go on much longer through a transfinite process), you have to iterate it forcapture all Baire functions, resulting in a hierarchy of length very long time if$\omega_1$. But even then you hopewill fail to capture all functions this way$f:\mathbb R\to\mathbb R$: There are only $\mathfrak c$ many Baire functions. In fact, these are precisely the Borel measurable functions.

Let me addclose with something of an advertisement, now that I have some time. Pete Clark's comments in another answer show that $\chi_{\mathbb Q}$ is not the pointwise limit of continuous functions. For this, he described a characterization of the Baire class 1 functions that clearly $\chi_{\mathbb Q}$ does not satisfy. Since the answer has been deleted, let me repeat Peter's comment:

A real function $f$ is in Baire class one iff for every nonempty perfect subset $P\subset\mathbb R$, there exists $x\in P$ such that the restriction of $f$ to $P$ is continuous at $x$ (in fact, $f\upharpoonright P$ is continuous at all points of $P$ except for a set that is first category in $P$). Taking $P$ to be a closed interval $[a,b]$, this shows that there is a dense subset of points at which $f$ is either left- or right- continuous. This is not the case for $\chi_{\mathbb Q}$.

(Note the nice corollary that, since derivatives are obviously Baire class one functions, they are continuous on a dense set of reals.)

The simplest kind of definability a function mymay have is that its graph is Borel (this is the case if the function is continuous, for example). From here, a very large hierarchy of levels of complexity of subsets of ${\mathbb R}^m$ is defined, starting by taking projections of Borel subsets of ${\mathbb R}^{m+1}$, and complements, and then iterating this procedure.

The fact that we can actually iterate the procedure, i.e., that the hierarchy does not collapse, is where Cantor's diagonalization appears. Anyway, any class of functions with a simple description is easily seen to belong to a (tipicallytypically, very short) initial segment of this hierarchy, and so we know it cannot capture the class of all functions. Many variants of your question are seen immediately to have negative answers through this procedure, which has the advantage of separating levels of complexity in a more refined way than mere cardinality.

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example).

This argument shows that even if you iterate the process (the Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$. You need to go on much longer through a transfinite process), you have to iterate it for a very long time if you hope to capture all functions this way.

Let me add something of an advertisement, now that I have some time. Pete Clark's comments in another answer show that $\chi_{\mathbb Q}$ is not the pointwise limit of continuous functions. For this, he described a characterization of the Baire class 1 functions that clearly $\chi_{\mathbb Q}$ does not satisfy.

The simplest kind of definability a function my have is that its graph is Borel (this is the case if the function is continuous, for example). From here, a very large hierarchy of levels of complexity of subsets of ${\mathbb R}^m$ is defined, starting by taking projections of Borel subsets of ${\mathbb R}^{m+1}$, and complements, and then iterating this procedure.

The fact that we can actually iterate the procedure, i.e., that the hierarchy does not collapse, is where Cantor's diagonalization appears. Anyway, any class of functions with a simple description is easily seen to belong to a (tipically, very short) initial segment of this hierarchy, and so we know it cannot capture the class of all functions. Many variants of your question are seen immediately to have negative answers through this procedure, which has the advantage of separating levels of complexity in a more refined way than mere cardinality.

Quick answer:

What you want to do is look up ``Baire function'' (in Wikipedia, for example). The Baire class of functions is the least collection of functions $f:\mathbb R\to\mathbb R$ that contains the continuous functions and is closed under limits.

The Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$: Baire class one functions are pointwise limits of sequences of continuous functions. Baire class two functions are pointwise limits of sequences of Baire class one functions, etc. You need to go on much longer through a transfinite process to capture all Baire functions, resulting in a hierarchy of length $\omega_1$. But even then you will fail to capture all functions $f:\mathbb R\to\mathbb R$: There are only $\mathfrak c$ many Baire functions. In fact, these are precisely the Borel measurable functions.

Let me close with something of an advertisement. Pete Clark's comments in another answer show that $\chi_{\mathbb Q}$ is not the pointwise limit of continuous functions. For this, he described a characterization of the Baire class 1 functions that clearly $\chi_{\mathbb Q}$ does not satisfy. Since the answer has been deleted, let me repeat Peter's comment:

A real function $f$ is in Baire class one iff for every nonempty perfect subset $P\subset\mathbb R$, there exists $x\in P$ such that the restriction of $f$ to $P$ is continuous at $x$ (in fact, $f\upharpoonright P$ is continuous at all points of $P$ except for a set that is first category in $P$). Taking $P$ to be a closed interval $[a,b]$, this shows that there is a dense subset of points at which $f$ is either left- or right- continuous. This is not the case for $\chi_{\mathbb Q}$.

(Note the nice corollary that, since derivatives are obviously Baire class one functions, they are continuous on a dense set of reals.)

The simplest kind of definability a function may have is that its graph is Borel (this is the case if the function is continuous, for example). From here, a very large hierarchy of levels of complexity of subsets of ${\mathbb R}^m$ is defined, starting by taking projections of Borel subsets of ${\mathbb R}^{m+1}$, and complements, and then iterating this procedure.

The fact that we can actually iterate the procedure, i.e., that the hierarchy does not collapse, is where Cantor's diagonalization appears. Anyway, any class of functions with a simple description is easily seen to belong to a (typically, very short) initial segment of this hierarchy, and so we know it cannot capture the class of all functions. Many variants of your question are seen immediately to have negative answers through this procedure, which has the advantage of separating levels of complexity in a more refined way than mere cardinality.

added 1965 characters in body
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example).

Here is a simple way of seeing that the answer is negative: Any continuous function $f:{\mathbb R}\to{\mathbb R}$ is determined by its value on the rationals, so by an easy counting argument, there are only as many continuous functions as there are reals. Since a sequence of reals can be easily coded by a single real, there are only $|{\mathbb R}|$-many functions that are limit of sequences of continuous functions (you could replace "pointwise limit" with just about anything you want as long as the countable sequence suffices to describe the new function). But there are $2^{|{\mathbb R}|}$ many functions from ${\mathbb R}$ to itself.

This argument shows that even if you iterate the process (the Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$. You need to go on much longer through a transfinite process), you have to iterate it for a very long time if you hope to capture all functions this way.


Let me add something of an advertisement, now that I have some time. Pete Clark's comments in another answer show that $\chi_{\mathbb Q}$ is not the pointwise limit of continuous functions. For this, he described a characterization of the Baire class 1 functions that clearly $\chi_{\mathbb Q}$ does not satisfy.

The argument above, on the other hand, only refers to cardinality considerations, so it does not apply to specific examples.

One can refine the argument (essentially, by a sophisticated use of Cantor's diagonalization) by appealing to techniques of descriptive set theory. Here, one studies ``definable'' classes of functions $f:{\mathbb R}\to{\mathbb R}$ or, more generally, of subsets of ${\mathbb R}^n$, and it is therefore the right setting for this type of problems.

The simplest kind of definability a function my have is that its graph is Borel (this is the case if the function is continuous, for example). From here, a very large hierarchy of levels of complexity of subsets of ${\mathbb R}^m$ is defined, starting by taking projections of Borel subsets of ${\mathbb R}^{m+1}$, and complements, and then iterating this procedure.

The fact that we can actually iterate the procedure, i.e., that the hierarchy does not collapse, is where Cantor's diagonalization appears. Anyway, any class of functions with a simple description is easily seen to belong to a (tipically, very short) initial segment of this hierarchy, and so we know it cannot capture the class of all functions. Many variants of your question are seen immediately to have negative answers through this procedure, which has the advantage of separating levels of complexity in a more refined way than mere cardinality.

An excellent reference you may want to look at is Alekos Kechris's book.

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example).

Here is a simple way of seeing that the answer is negative: Any continuous function $f:{\mathbb R}\to{\mathbb R}$ is determined by its value on the rationals, so by an easy counting argument, there are only as many continuous functions as there are reals. Since a sequence of reals can be easily coded by a single real, there are only $|{\mathbb R}|$-many functions that are limit of sequences of continuous functions (you could replace "pointwise limit" with just about anything you want as long as the countable sequence suffices to describe the new function). But there are $2^{|{\mathbb R}|}$ many functions from ${\mathbb R}$ to itself.

This argument shows that even if you iterate the process (the Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$. You need to go on much longer through a transfinite process), you have to iterate it for a very long time if you hope to capture all functions this way.

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example).

Here is a simple way of seeing that the answer is negative: Any continuous function $f:{\mathbb R}\to{\mathbb R}$ is determined by its value on the rationals, so by an easy counting argument, there are only as many continuous functions as there are reals. Since a sequence of reals can be easily coded by a single real, there are only $|{\mathbb R}|$-many functions that are limit of sequences of continuous functions (you could replace "pointwise limit" with just about anything you want as long as the countable sequence suffices to describe the new function). But there are $2^{|{\mathbb R}|}$ many functions from ${\mathbb R}$ to itself.

This argument shows that even if you iterate the process (the Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$. You need to go on much longer through a transfinite process), you have to iterate it for a very long time if you hope to capture all functions this way.


Let me add something of an advertisement, now that I have some time. Pete Clark's comments in another answer show that $\chi_{\mathbb Q}$ is not the pointwise limit of continuous functions. For this, he described a characterization of the Baire class 1 functions that clearly $\chi_{\mathbb Q}$ does not satisfy.

The argument above, on the other hand, only refers to cardinality considerations, so it does not apply to specific examples.

One can refine the argument (essentially, by a sophisticated use of Cantor's diagonalization) by appealing to techniques of descriptive set theory. Here, one studies ``definable'' classes of functions $f:{\mathbb R}\to{\mathbb R}$ or, more generally, of subsets of ${\mathbb R}^n$, and it is therefore the right setting for this type of problems.

The simplest kind of definability a function my have is that its graph is Borel (this is the case if the function is continuous, for example). From here, a very large hierarchy of levels of complexity of subsets of ${\mathbb R}^m$ is defined, starting by taking projections of Borel subsets of ${\mathbb R}^{m+1}$, and complements, and then iterating this procedure.

The fact that we can actually iterate the procedure, i.e., that the hierarchy does not collapse, is where Cantor's diagonalization appears. Anyway, any class of functions with a simple description is easily seen to belong to a (tipically, very short) initial segment of this hierarchy, and so we know it cannot capture the class of all functions. Many variants of your question are seen immediately to have negative answers through this procedure, which has the advantage of separating levels of complexity in a more refined way than mere cardinality.

An excellent reference you may want to look at is Alekos Kechris's book.

Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Quick answer since it is late:

What you want to do is look up ``Baire function'' (in Wikipedia, for example).

Here is a simple way of seeing that the answer is negative: Any continuous function $f:{\mathbb R}\to{\mathbb R}$ is determined by its value on the rationals, so by an easy counting argument, there are only as many continuous functions as there are reals. Since a sequence of reals can be easily coded by a single real, there are only $|{\mathbb R}|$-many functions that are limit of sequences of continuous functions (you could replace "pointwise limit" with just about anything you want as long as the countable sequence suffices to describe the new function). But there are $2^{|{\mathbb R}|}$ many functions from ${\mathbb R}$ to itself.

This argument shows that even if you iterate the process (the Wikipedia entry talks about class $n$ Baire functions for all $n\in{\mathbb N}$. You need to go on much longer through a transfinite process), you have to iterate it for a very long time if you hope to capture all functions this way.