Here is a problem that has been puzzling me recently:

Dear David

Let me first of all give you an example of a function which is not everywhere discontinuous. Roughly speaking if a function is not integrable on a small bit, then it is not integrable on the whole. I.e. if you take f on [0,1] to be 0 everywhere apart from all the rational points in the interval [1/3,2/3], then I leave it to you to show that the lower sum is always 0 and the upper sum is at least 1/3.

Examples like these never occur naturally (whatever that means) but pure mathematicans like myself always worry about them and they 'resolve' these problems by trying to define a more general way of integration which excludes these rather awkward cases. One way of doing this is called Lebesgue integration . Write back if you want to know more about that. Could you also let me know what level you are at (GCSE, A-level ,...) so I can tailor my answers accordingly.
Michael

Dear Michael,

I would be very interested to learn more about this form of integration you mentioned. I am currently in year 12 doing double A-level maths.
Is a function of this type always integrable if it has only countably many discontinuities?

David

Dear David

I will soon come back to you and give you a brief introduction to Lebesque integration with as few references to advanced concepts (like sigma algebras, etc ) as possible.
There are two facts though which I will need:
1) the rationals are countable
2) the irrationals are uncountable.
If these things do not mean anything to you, then let me know and I will respond accordingly.

Michael

Dear Michael

(Sorry for not replying to you earlier.) I think I understand the things you mention to a reasonable extent. I have also heard (vaguely) of sigma-algebras - aren't they algebras formed from the subsets of a given set under the operations of union and intersection?
Incidentally, is the Cantor ternary set countable? I have adapted the method used for the proof that the points in the interval [0,1] are uncountable and I think the Cantor set is too, but I don't have much confidence in my proof - it relies on the fact that the representation in base 3 of a number in the set cannot contain any 1s, but it doesn't seem to provide any way of coping with recurring 2s (0.02222...=0.1, etc). The reason this occurred to me is that a function which is 1 on the set and 0 off it would be discontinuous at uncountably many points but still integrable - this really has to take the prize for the worst-behaved integrable function I have seen.
Anyway, I am rambling a bit here. I look forward to your next message.

David

Dear David

I think you actually have proven the the Cantor ternary set is uncountable, yet - as you rightly pointed out - you have to be careful when using the diagonal argument.

Let's first establish exactly what the Cantor set is. Take the unit interval [0,1] and remove the open interval
(1/3,2/3). Then in the next step, remove again the open middle thirds from all existing intervals and continue this process. Then certainly the number 0.1=0.02222... lies in the cantor set.


You are right in pointing out that then elements in the Cantor set do not have a unique expansion (base 3) if we allow infinite expansions and so we adopt the convention that if an infinite expansion exists, then we want to use it.
Thus 1.0 will then be 0.2222... etc. This and the way in which we have removed open intervals will then make it possible for the diagonal argument you outlined to go through.

Michael

Dear David

You probably noticed that there is a lively discussion going on in the open discussion section about Lebesgue integration and some rather advanced concepts and questions have been raised. Anyway, I intend to explain to you the basics of this new type of integration from scratch and I will first of all do this on [0,1] the unit interval, as a lot of notions are very intuitive in this setting.

The new idea

If you take your own example of the function f which is defined on [0,1] and is 0 on irrationals and 1 on rationals, then - as you rightly said - this function is not Riemann integrable. Yet you might well have a good intuitive idea what the integral should be if indeed it was defined. As there are uncountably many irrationals but only countably many rationals, one might suspect that somehow the integral should really be 0. Now this is certainly not a precise statement, but is designed to expose where exactly the weakness in the process of Riemann integration lies. The problem is that you are forced to consider sums over INTERVALS (which partition [0,1]) and that each interval naturally contains both rationals and irrationals.
What if we allow more general sets in the Riemann sum ?

The problem with the new idea

The basic problem is that somehow we have to say how big such a more general set is. Note that we know the width of an interval: this is what the upper and lower sum in the process of Riemann integration is based on !

Thus in order to obtain more general sets we have to
1) define a way of measuring the size of a set
2) define a new analogue of the Riemann upper and lower sum which will then give a new definition of an integral.

Some history before we dive in

Riemann integration as such is not as old as it might seem. It was developed at around 1853 (by Riemann -but you might have guessed that) despite the fact that notions of summing over infinite things and infinitesimal calculus had been aroung for quite some time. But is was only at the beginning of this century (1901) that Henri Lebesgue (sometimes also written Lebesque) extended Riemann's integration method to incorporate more desirable integrable functions. In mathematical terms this is not very long ago.

A humble start

We will now set out to define a way of measuring the size of a set on [0,1].
Mathematicians, when defining things generally make sure that any new definition which is more general than an older one does not destroy the nice properties the older one had. Keeping with this tradition we would certainly like to say that an interval [a,b] contained in [0,1] has measure b-a. Moreover we will also require that if [a₁ ,b₁ ],... is a countable collection of disjoint intervals then we want the size or measure of the union of all these to be the sum
S (b_i -a_i ) where the sum is taken over i ranging from 1 to infinity (Note this converges since the total measure is less than the measure on [0,1]). In fact this is how we define the measure of sets of this form.

Hopefully you should now be able to work out the measure of the following two sets:

1) the union of the intervals [0,1/2] , [3/4,7/8] , [15/16,31/32] , ...

2) the rationals in [0,1]

Let me know if you have any problems with what I said so far. When all is clear we will carry on.

Michael

Dear Michael,

I think I understand so far.

1) 1/2 + 1/8 + 1/32 ... = 1/2 x(1 +1/4 +1/16 ...+1/4ⁿ ..) = 1/2 x(1/(1-1/4) ) = 2/3, so this is the measure of the union of these intervals (as the intervals are disjoint).

2) Each rational x is equivalent to the interval [x,x], having measure 0. Since the measure is additive for countably many sets we have 0+0+0+0... =0, so the rationals have zero measure.

I suppose that the strategy I used to show that my function which is 1 on the Cantor set and 0 off it is integrable is equivalent to proving that the set has measure 0 - I used sets of finitely many small intervals covering the clusters of points, which would thus have measure greater than the Cantor set. I then allowed the number of intervals increase, and their total length - which is greater than the measure of the underlying set - tended to 0.

David

Dear David

I think you understand the above concepts well and we are able to proceed.

Measurable sets

Up to now we are only able to attach a size or measure to very specific sets, namely those which are a countable union of closed sets. The aim of this section is to attach a measure to as many sets as possible.

Given an arbitrary subset A of [0,1] we define the outer measure m^* (A) = inf measure(U) where the infimum is taken over all countable unions of closed sets which contain A. Note that we can attach a measure to all those U by the preceeding section.
Similarly we define the inner measure of A to be m_* (A) = 1 - m^* (A^C ), where A^C means the complement of A in {0,1].
We call a set A measurable if m^* (A)=m_* (A), and write m without any stars for this measure.
I am not quite sure whether you actually know what the supremum and infimum is. Get back to me if you have any problems or if you think you have understood the above definitions so that we can continue.

Dear Michael,

Supremum= least upper bound, Infimum= greatest lower bound - please tell me if this is wrong.

(Sorry for not replying earlier - availability of Internet access at my school is highly variable!)

David

Dear David

You might like to check that the irrationals are measureable.

Here are some questions for you to see if it all makes sense:

1. Find whether or not the following sets are measurable or not and give their measure if they are :
a) (1/3,2/3)
b) (1/3,2/3]
c) [1/3,2/3]
d) the cantor set

Here are some theorems. Can you prove them ? ( If you cannot do not worry ).

1. If A is measurable, then
m(A^C )=1-m(A)

2. A set A is measurable if and only if for any set X a subset of [0,1] we have that
m^* (X)=m^* (X n A) + m^* (X n A^C )

(This is called Caratheodory's criterion).

3. All measurable sets (as defined this time !) form a sigma - algebra.

Remark: Caratheodory's condition is how one 'usually' defines measurable sets. Yet as we are working on a closed interval here, I personally think that the definition above via inner and outer measure is a bit more tangable.

4. Can you find a non-measurable set ? (Do not spend too much time on this because they are extremely messy !).

Sorry about the mess

Michael

Dear Michael,

I have managed to prove theorem 1, but theorem 2 is defeating me. However, please don't tell me the answer as I am still working on it! Anyway, I have managed to find some sets which should be non-measurable if they are non-countable - for example the set of all x in [0,1] where there are only finitely many 0s in the decimal expansion of x. However, I am a little stuck trying to show it to be non-countable. I suppose that a set must be non-measurable if both it and its complement are dense in all sub-intervals of [0,1] and it is not countable. Am I on the right track here?
Thanks for all your help so far.

David

Dear David

I believe that the set you have given me above is in fact a countable union of Cantor like sets (remove the left tenth insead of the middle third...) and is therefore measurable and has measure 0.

Have you ever heared about the Axiom of Choice ? You will have to use it in order to find non-measurable sets which also explains why these sets are so messy.

Write back if you want to know more about the Axiom of Choice. Tell me also when you feel ready to continue.

Take care

Michael

Dear Michael,

Yes, all my supposedly unmeasurable sets were actually measurable. Sorry.
Anyway, I must confess that I am stuck; I cannot prove theorem 2, Caratheodory's criterion. Could you outline a proof for me?
I have heard of the Axiom of Choice - isn't it something along the lines of "it is possible to pick one element of each of any collection of sets to form a new set"? To be honest I haven't a clue how that helps though. Sorry if I'm being a bit stupid here. Thanks again.

David

Just a comment:

I think that the answer to David's original question:

"When can we integrate a bounded function between 0 and 1?"

is this:

The integral is only possible provided that there does not exist an interval between 0 and 1 within which every possible sub-interval contains a discontinuity. However I am not sure as I can only prove this for limited cases (e.g. when the value of the function is either 0 or 1 at each point).

I'd be interested if somebody could prove this in general or find an example when it is not true.

Thanks,

Michael

Unfortunately not!

Define f to be the following function.

(1) It is 0 on the irrationals
(2) If a/b is a rational in its lowest terms then f(a/b) is 1/b

This is a bounded function on (0,1). I'll leave you to prove that it is discontinuous at the rationals and continuous at the irrationals (this property is the interesting thing about this function).

Now its lower sum clearly tends to 0, and again I'll not spoil all your fun by proving that the upper sum also tends to 0. Hence f is Riemann integrable on (0,1) and the integral is 0.

So this is a counter-example to your statement. I have been told that a bounded function is Riemann integrable on an interval if and only if it is continuous almost everywhere (I'll leave Michael to explain what almost everywhere means when he goes into Lebesgue integration... in the above case continuity at the set of irrationals is enough).

AlexB.

Yes, I was a bit worried about what would happen if the value of the function tended to zero infinitely many times in each interval. Would my statement be always correct if the size of the deviation of each discontinuity had a positive lower limit? (In other words suppose y = f(x) has a discontinuity at x = c. For all c, f(c) > lim f(x) + a where a is constant where the sequence used to generate the limit does not include any x values in which f(x) is discontinuous.)

The function you mentioned is discontinuous at the rationals, because if it was continuous then the function should have a limit as x tends to each of the rationals. Also this limit would have to be zero, because the rationals are surrounded by irrationals. And as the function is continuous the limit would have to equal the value. Therefore the value at the rationals would have to be zero, contrary to your definition. Therefore it is discontinuous at the rationals.

To show it is continuous at the irrationals, we must show that if you have a sequence tending to an irrational, then the corresponding values of the function must tend to zero (as the value at the irrationals is zero). Now any irrationals in the sequence are clearly not going to stand in the way of the limit being zero, so I'll only consider a purely rational sequence. To avoid complications, I'll assume that the sequence continually gets closer to the x-value (this will not make a difference as eventually the sequence must reach a certain distance from the x-value and never go further away than this again).

Now no more than 1 of the terms in the sequence can cause a y-value of 1.
No more than 2 can cause a y-value of 1/2
No more than 3 can cause a y-value of 1/3
...
No more than n can cause a y-value of 1/n

So after 1/2n(n+1) terms in the sequence we must have reached a y-value of 1/n at most. So as the number of terms in the sequence tends to infinity, the values of the function must tend to zero. Therefore the function is continuous at the irrationals.

To show that the "upper integral" is zero for your function, I will make a similar over-estimation. Imagine dividing the interval between 0 and 1 into n strips. (I'm not sure if these are required to be the same width or not. But I doubt it matters as long as each of the widths tends to zero and the sum of the widths is one.) How can we maximise the sum of the upper y-values?

Well we could have

one 1
two 1/2s
three 1/3s

n 1/ns.

So each rational denominator can make a maximum contribution of 1 to the sum. Summing up to 1/n gives a maximum sum of n.

We will sum the biggest values first as we are maximising the sum.

But by the time we've summed up to the 1/n 's, we must have had at least 1/2n² strips (just 1/2n(n+1) underestimated).

So an overestimation of the upper sum is:

n / [1/2n² ] which tends to zero as n tends to infinity.

Therefore the integral does exist and has value zero.

This method strikes me as being rather complicated ? is there an easier way of coming to the same conclusion?

Many thanks,

Michael

The working is all correct. And just about the only better way to do it is to use the theorem that I stated in my first post --- which is the answer that you want as it is an if and only if. Well, even better than this is to give up with Riemann integration and use the MUCH NICER (I can't emphasise just how much nicer!) Lebesgue integration.

Off the top of my head I don't know the answer to your question... I'll leave that to Michael whose area is much closer to things like this. But again, even if you can find non-Riemann integrable things then they are normally like this for silly reasons that Lebesgue integration can get round. If only it were possible to teach this one first... (!)

AlexB.

Quick comment. Lebesgue integration is an aspect of measure theory, which has been talked about in the Sequences of consecutive integers discussion. In order to define things like "almost everywhere" you need to know what a sigma algebra is but here's a quick comment which will (hopefully) provide a different viewpoint on it.

The interval [0,1] has measure 1 (you measure an interval in the normal sense, and Lebesgue measure is simply the extension of this to the relevant sigma algebra). We can regard Lebesgue measure on [0,1] as a probability measure, with each point in the interval representing an outcome. In some sense, this is the canonical way to view probability - it's always possible to view a probability space as [0,1] equipped with Lebesgue measure.

Now, a function on [0,1] can be viewed as a random variable (again, this is discussed in the other section) which is continuous. An atomic random variable is something like the Dirac delta function; anything which is bounded will certainly be continuous. Now, the probability of a continuous random variable being equal to a specific value is zero. It's pretty easy to see that this extends at least as far as the probability that it takes one of a countable set of values.

An event is true "almost everywhere" if the set on which it is false has measure zero. Thus if something fails only on a countable set, it is definitely true almost everywhere. There are uncountable sets of measure zero, but I won't go into that. This is enough to understand why no function of the above type is a good counterexample to Lebesgue integration.

You can change f on a countable number of points and it will represent the same random variable. The integral of f is simply the expectation of the random variable. From the above discussion, it must be zero (since I can change f on the rationals to be 0 and I get the function which is identically 0).

Ok, so no proofs here but hopefully this is a nice taster of what real integration can do for you... Anyway, it should show you that there's normally several ways of looking at things and some are more convenient than others, depending on the situation.

HTH,

-Dave

Thank you for your replies. There are obviously some interesting parallels between probability and analysis.

I suppose one sensible way of defining an integral (and I'm not sure if this is the same way as Lebesgue) is to perform a weighted sum of the y-values, weighted by the probability of their occurring. So for example, the function that returns zero at the irrationals and one at the rationals would suddenly become integratable with integral zero (as the chance of picking an rational number at random is clearly zero, by symmetry). Would this sort out most of the problems?

By the way, does my very loose usage of "probability" here (after all it is impossible to perform trials and so we can't find the limit of the success rate as the number of trials tends to infinity) mean the same thing as a "measure"?

Michael

It wouldn't sort out the problems. Imagine trying to integrate the function f(x)=x. Each specific y-value occurs at only one point...

The problem that you are running into here is that it is possible to combine lots of probability zero events to get something that has positive probability. For example the probability that a number in [0,1] is exactly x is zero. But 'summing' over all x< =1 should give a probability of 1.

One way of looking at Lebesgue integration is as follows. Suppose you have a series of functions f(n;x) which converge pointwise to a function f(x). Suppose that we know how to integrate the functions f(n;x). We would love to say that the integral of f(x) is then the limit of the integrals of the f(n;x). The massive problem with Riemann integration is that this just doesn't work. What Lebesgue did was basically to define integration using this sort of idea to make it work. Again, Michael probably explains much better what I'm talking about.

As a little exercise you should look at what the upper and lower sums you get in Riemann integration are. Can you see that you are defining functions which approximate the function f (one is bigger than f the other smaller). Also the functions you are using are really simple ones (they are 'locally constant'). And Riemann is saying the integral of f is the limit of the integrals of these simple functions.

And finally... yes, probability < -> measure.

AlexB.

...until you start to look at Lebesgue integration on the whole of the real line, which has infinite measure and so doesn't correspond in any obvious way to a probability. In fact, there are things worse than the real line too (since it is made of countably many probability measures, ie intervals of the form [n,n+1]) but they're so nasty that I don't know anything about them...

Adding together uncountably many things is basically the same as integration, which is why we can get measure 1 from uncountably many points of measure zero.

Finally, the ideas behind Lebesgue integration can be thought of as doing things with respect to y rather than x, but in a more complicated way than Michael suggested. If you first `rearrange' the function so that it is decreasing, you at least end up with something which has some hope of being approximated easily. This certainly clears up the usual problems with Riemann integration (ie the ones mentioned in this thread). Of course, there are other ways to think about it as well (and I generally find those easier).

-Dave

Thank you for your replies.

With my definition of integration, you would still have to split the range of y-values into intervals and then let the number of intervals tend to infinity. So with f(x) = x between 0 and 1, the range of possible y-values is 0 to 1. So split this into n strips. The probability that the y-value lies within any particular strip is constant (as the width of the y-interval is proportional to the width of the x-interval for f(x) = x).

So we simply get an equally weighted mean of all the y-values of the strips (and it doesn't matter if we take the lower or upper y-values). Multiply this by the width of the x-interval (in this case 1) and you get the integral - here 1/2.

With f(x) = 0 if x is irrational and f(x) = 1 if x is rational then the y-strip that touches y=1 will have probability 0 as the chance of picking a rational number is zero. (I haven't really defined what this means yet. I think that the best bet is to impose a symmetry requirement on probability - i.e. that all numbers are equally likely to come up and the sum of the probabilities must be equal to one). All the rest of the strips will have probability zero apart from the strip at y = 0. Therefore the integral would be zero.

It is a bit difficult to see how you could re-arrange the function so that it is decreasing - especially when the function is 0 on the irrationals and 1 on the rationals. I would appreciate guidance about how to do this.

A slightly different question on integration: integration is the limit of a sum. Suppose I define another operation analagous to integration except this time we have the limit of the product of the y-values. So this operation applied to the interval [0,1] gives the geometric mean of the y-values not the arithmetic mean. I think this operation on f(x) is usually equal to e to the integral of ln(f(x)). Is it possible to attach any geometrical significance to this operation in the same way as the integral is the area? It seems that it is something like the average width of a hypercuboid, but I would like this confirmed.

Thanks,

Michael

By rearrangement of the function I meant that we actually change the function but in a specific way. Say we have an easy function, like f(x)=x, with domain [0,1]. The rearranged function is simply f(x)=1-x. Every value which was taken by the original function has also been taken by the rearranged function, but we've sorted them out into decreasing order.

What this means for your horrible function is that we put all of the times that f(x)=1 before the times that f(x)=0. Now, since the function is defined on uncountably many points, we can't "count" how many times f(x)=0 in the normal sense. This is where measure theory comes in. If f is a measurable function, we can assign a measure to the set {x:f(x)=1}. Say this has measure 0.5. Then the new function has f(x)=1 for x< 0.5, and so on. So we generalise the notion of counting and a rearranged function has the same count of each value, but is decreasing.

Ok, if that's made sense then you can see what the rearranged function of your example is. The measure of the set {x:f(x)=1} is actually zero, since there are countably many such x. The measure of the set {x:f(x)=1} is one, so the rearranged function is simply f(x)=0. That is, it has zero measure where its value is 1, and the rest has value zero. Now we can integrate this function.

I have a feeling that this explanation isn't too great. Sorry - let me know how I could improve it if you don't understand things.

-Dave

Apologies for the delay.

That all made perfect sense - if I have any further queries on how to perform Lebesgue integration I'll write back. I'd be interested to hear how Lebesgue integration is used in pure maths - what problems does it make easier to solve? Is it involved with the measure-theoretic probability you were talking about in the Sequences of Consecutive integers discussion?

Thank you,

Michael

Just a couple more questions:

1) I would still like to know if the Lebesgue integral corresponds to the expectation of the function multiplied by the width of the interval it is being integrated over. Or am I just working backwards and using Lebesgue integration to give meaning to expectation in this context?

2) Is it possible to define a function f(x) with the following properties?

a) for all real x in [0,1] f(x) = 0 or f(x) = 1
b) in every sub interval of [0,1] the number of values of x which give zero is in one-one correspondence with the number of values of x which give one.

Thanks for your help,

Michael

Yes, it's more that the expectation isn't really well defined as an intuitive concept and that integration happens to be a suitable way to implement it. If you want to view integration as expectation, you may wish to consider that a uniform random variable has density 1, so that if you integrate f(x) from 0 to 1, you're actually taking the expectation of f(U), with U uniform on [0,1]. A similar thing can be done for any bounded interval, although you then need to divide by the length of the interval.

As for your second question, I'm not entirely sure what you mean - the "number of values" is ambiguous. In any interval there are uncountably many x so it's probably useless comparing their cardinality. If you mean, "the measure of the set which takes the value 1 is equal to the measure of the set which takes the value 0" then it certainly makes sense. But it's too late for me to realise whether it's possible or not...

-Dave

Thanks for your reply,

I'm not quite sure why it is impossible to set up a one-one correspondence between two sets, neither of which is in one-one correspondence with the integers. For example I can say that the irrationals in [0,1] are in one-one correspondence with the irrationals in [1,2] because you can simply add 1 to move uniquely from one irrational to another.

All I meant is that there exists a function g(x) such that:

1) For x in [0,1] g(x) is in [0,1]
2) g(x) is a one-one function
3) If f(x) = 0 then fg(x) = 1
4) If f(x) = 1 then fg(x) = 0

[Or more simply fg(x) + f(x) = 1].

I suspect that having equal measure would certainly imply the values were in one-one but I doubt that their measures would have to be equal. In fact I suspect that both subsets in [0,1] would both have to only be uncountable to be in one-one, meaning that one of the sets can still hold all the measure and yet be in one-one with a zero-measure set. So all I'm really looking for is two sets that between them contain all the numbers in [0,1]. Each must have uncountably many values in every possible sub-interval.

My own feeling is that while these sets must exist it will be impossible to describe them or give an algorithm for working out which set a number is in. In the decimal expansion, the set they fall into cannot be determined by the first n decimal places for any n. Yet you cannot distinguish them by their forming any sort of infinite pattern as this would make one of them countable.

Thanks,

Michael

One more thing:

I am not very certain of the axioms of set theory. Is it possible to define sets by random methods? For instance can I say, define set A such that for every number in [0,1] there is a 50% chance that the number is in the set? I know that you cannot predict for certain the set you get, but you do know a lot about its properties. For example this set would satisfy the properties I was after in question 2) above and I think it would also be non-measurable (although intuitively the measure should be 0.5).

One other idea I can think of for finding non-measurable sets is to go back to the 1-d symmetric random walk. We need a property of the sequence that does not have a convergent probability as the number of terms tends to infinity. I cannot find such a property yet though and I believe that none exist that can be written in closed form.

By the way, if you represent the random walk sequence as a base two expansion of a number in [0,1] with a 1 for each time the sequence increases and 0 for each decrease, the set A in which the sequence never returns to the origin appears to share quite a few properties of the Cantor set. It is uncountable yet with measure 0. It can also be thought of as the remainder when you remove countably many closed intervals from [0,1] though in a rather more complicated way than in the Cantor set. Is the function which returns 1 on this set and 0 off it Riemann integrable?

Thanks,

Michael