transfinite induction | College Math Teaching

January 13, 2011

A Non-Measurable Set

Filed under: advanced mathematics, analysis, calculus, Lebesgue Integration, Measure Theory, transfinite induction — collegemathteaching @ 5:52 pm

In our previous post, we talked about how to define a measure on a subset of the real line (or on $[0,1]$ ).

In today’s post, we’ll give an example of a type of set for which no reasonable measure can be defined.
Let us recall what we wanted in a measure:

1. $m([a,b])=b-a$ (and the same for open, and half open intervals). After all, this is supposed to be a length function. Of course,
$b > a$ .

2. $m(E+r)=m(E):$ that is, measure should be “translation invariant” that is, if you translate a set $E$ by adding the same constant to every element of $E,$ the translated set should have the same measure.

3. $m(\{x\})=m(\emptyset )=0$ (the measure of a single point and the empty set ought to be zero)

4. If $F\subset E$ then $m(F)\leq m(E)$ and we’d like to have some additivity properties:

5. Suppose $E=\cup _{i=1}^{\infty }E_{i}.$ Then we’d want $m(E)\leq\sum_{i=1}^{\infty }m(E_{i})$ provided the left hand sum converges (of course, this convergence is absolute since all terms are positive; hence the order of the terms is of no consequence; this uses our calculus results).

Of course, we are talking about a countable union; sums don’t make sense otherwise.

And, if the sets $E_{i}$ are disjoint, we’d love to have $m(E)=\sum_{i=1}^{\infty }m(E_{i})$

Now let’s define a set for which we could never have a measure which meets the above properties. Yes, we will be using the Axiom of Choice, which, roughly speaking, states that given an infinite disjoint collection of sets, we can “choose” one element from each set.

Start by selecting an irrational number $x\in \lbrack 0,1]$ . Then let the set $E$ consist of all $y\in \lbrack 0,1]$ in which the following is true: $y - x$ is irrational and if $z\in E$ then $y - z$ is irrational. One way to think of this is to establish one point in $E$ and then consider a maximal set with respect to equality modulo the irrationals. Or one can think of building this set inductively with an uncountable number of steps: start with $x$ , choose $y$ so that $y - x$ is irrational, then add $z$ so that both $x - z$ and $x - y$ are irrational and so on. Of course, all arithmetic is done modulo 1.

Now lets look at the following: the rational numbers are countable so we can order them $q_{1},q_{2}...,q_{k}$ . Then consider the translates of $E$ : $E_1 =E+q_{1}, E_2 = E + q_{2}....$ .
Then we can establish: $E$ is disjoint from each $E_{i}$ because, say, if $y\in E$ and $y = z + q_{i}$ with $z\in E$ then $y - z$ would be rational with both $y, z\in E$ . That is impossible. For a similar reason, all of the $E_{i}$ are disjoint.

Now if $w\in E'$ (the complement of $E$ in [0,1] ), then there is a $z$ in $E$ such that $w - z$ is rational; hence the collection of $E_{i}$ forms the complement of $E$ in [0,1].

So now we have the following situation: if measure is invariant under translation, $E$ and each $E_{i}$ have the same measure. Notice also that all of these sets are disjoint and that $\lbrack 0,1]=E\cup \{\cup _{i=1}^{\infty }E_{i}\}$

If each set has measure zero and we have countable additivity of disjoint sets, we’d have that [0,1] has measure zero. But if $E$ has a non-zero measure and the measure is translation invariant, then we’d have [0,1] having infinite measure (remember we can’t form a positive infinite sum because each $E_{i}$ has to have exactly the same measure.)

So, no matter how we define measure, we will have to exclude at least some sets (such as $E$ ).

One other thing to note: $E$ has as it’s compliment a countable number of translates of itself, hence it is impossible for $E$ to meet the Caratheodory characterization requirement that $E$ and its complement have measures that add up to the measure of $[0,1]$

Comments (3)

March 6, 2010

The Principle of Mathematical Induction: why it works

Filed under: induction, logic, transfinite induction, Uncategorized — collegemathteaching @ 11:03 pm

For those who prefer a video:

I am writing this post because I’ve seen that there is some misunderstanding of what mathematical induction is and why it works.

What is mathematical induction? It is a common proof technique. Basically, if one wants to show that a statement is true in generality and that one can index the set of statements via the integers (or by some other appropriate index set), then one can use induction.Here is a common example: suppose one wants to show that
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ for all positive integers $k$
(for example, $1 + 2 + 3 + 4 + 5 = (1/2)*(5)*(5+1) = 15$ ).

Initial step: $1 = (1/2)*(1)*(1+1)= 1$ so the statement is true for $k = 1$ .

Inductive step: assume that the formula holds for some integer $k$ .
Finish the proof: show that if the formula holds for some integer $k$ , then it holds for $k+1$ as well.

So $1 + 2 + 3 +....+ k + (k+1) = (1 + 2 + ...+ k) + (k+1) =(1/2)*(k)*(k+1) + (k + 1)$
(why? because we assumed that $k$ was an integer for which
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ . )

so $1 + 2 + 3 +....+ k + (k+1) = (1/2)*(k)*(k+1) + (k + 1) = ((1/2)*k + 1)*(k+1)$ (factor out a k+1 term)
$= (1/2)*2*((1/2)*k + 1)*(k+1) = (1/2)*(k+2)*(k+1)=(1/2)*(k+1)*(k+2)=(1/2)*(k+1)*(k+1 + 1)$
which is what we needed to show. So the proof would be done.
Why does induction “prove” anything? Mathematical induction is equivalent to the so called “least positive integer” principle in mathematics.
What is the least positive integer principle? It says this: “any non-empty set of positive integers has a smallest element”. That statement is taken as an axiom; that is, it isn’t something that can be proved.
Notice that this statement is false if we change some conditions. For example, is is NOT true that, say, any set of positive numbers (or even rational numbers) has a smallest element. For example, the set of all numbers between 0 and 1 (exclusive; 0 is not included) does NOT have a least element (not according to the “usual” ordering induced by the real number line; it is an easy exercise to see that the rationals can be ordered so as to have a least element). Why? Let $b$ be a candidate to be the least element. Then $b$ is between 0 and 1. But then $(1/2)b$ is greater than zero but is less than $b$ ; hence $b$ could not have been the least element. Neither could any other number.

Note that the set of negative integers has no least element; hence we need the condition that the integers are positive.

Notice also that there could be groups of positive integers with no greatest element. For example, Let $x$ be the largest element in the set of all even integers. But then $2x$ is also even and is bigger than $x$ . Hence it is impossible to have a largest one.
What does this principle have to do with induction? This is what: an induction proof is nothing more than a least integer argument in disguise. Lets return to our previous example for a demonstation; that is, our proof that $1 + 2 + ....+ n = (1/2)n(n+1)$ We start by labeling our statements: $1 = (1/2)(1)(1+1)$ is statement P(1),
$1 + 2 = (1/2)(2)(2+1)$ is statement P(2), … $1+2+...+ 5 = (1/2)(5)(5+1)$ is statement P(5) and so on.

We assume that the statement is false for some integer. The set of integers for which the statement is false has a least element by the least element principle for positive integers.

We assume that the first integer for which the statement is false is $k+1$ . We can always do this, because we proved that the statement is true for $k = 1$ , so the first possible false statement is $k = 2$ or some larger integer, and these integers can always be written in the form $k + 1$ .

That is why the anchor statement (the beginning) is so important.

We now can assume that the statement is true for $n = 1,....n = k$ since $k+1$ is the first time the statement fails.

Now when we show “if statement P( $k$ ) is true then P( $k+1$ ) is also true (this is where we did the algebra to add up $1 + 2 + .....+ k + (k+1) = ((1/2)k(k+1)) + (k+1) )$ . This contradicts that statement P( $k+1$ ) is false.

Hence the statement cannot be false for ANY positive integer $k$ .
Weak versus strong induction. As you can see, the least positive integer principle supposes that the statement is true for all statements P(1) through P( $k$ ), so in fact there is no difference (when inducting on the set of positive integers) between weak induction (which assumes the induction hypothesis for some integer $k$ ) and strong induction (which assumes the induction hypothesis for $n = 1$ through $n = k$ ).
Other index sets: any index set that one has to induct on has to have the “least element principle” to its subsets. Also, if there is a cardinal w that has no immediate predecessor, then one must “reanchor” the induction hypothesis as $k = w$ prior to proceeding.