Transcript Real Numbers - Humboldt State University

Real Numbers:
Models and The Proof of The Continuum Hypothesis
by
Martin Flashman
Department of Mathematics
Humboldt State University
In memory of my mentor
Jean van Heijenoort
This presentation will attempt:






To give some background on the Continuum Hypothesis. (CH)
To outline the key concepts in constructing models for the real
numbers.
To indicate a specific model for the real numbers where the CH is
false.
To indicate why the CH is false in the specific model.
******************************************
This presentation is only a rough indication of the organization
and concepts needed to prove “the independence” of CH.
Rigorous details will be omitted.
Quick Break:
Jean Van Heijenoort
and the Revolution
JvH … Trotsky
From Trotsky to Godel:
The Life of Jean van Heijenoort
by Anita Fefferman

 Frida
(movie cast)
Cast:Frida Kahlo Salma Hayek
Diego Rivera Alfred Molina
Leon Trotsky Geoffrey Rush
Jean Van Heijenoort Felipe Fulop
Cantor 1845-1918
Infinite Sets

A set S is countable if there is a function from N onto S.

Any infinite subset of the natural numbers or the integers
is countable.

The set of rational numbers is a countable set.


"Godel counting" argument.
25 38 : 5/8
The algebraic numbers are countable.
[ Another first type of diagonal argument.] 1874
Cantor
Uncountable Infinite Sets
There is an uncountable set of real numbers.
 Any function from N to the interval [0,1] is not onto.


A decimal based proof. (Similar to 1891 proof)
Consider the set of real numbers with decimal expression:
0. a15a25 a35a4… and suppose this set is countable
Let b= 0. b15b25 b35b4… where…

There is no onto function from R, the set of real numbers,
to P(R), the set of all subsets of the real number.

There are sets which are "larger" than the set real numbers
.
Sets and Measure
 The
set of rational numbers between 0 and 1
has "measure" zero.
 Any
countable set of real numbers has "measure"
zero
**************************************
Proof:
For each element an of the countable set, choose the
interval [an – z/4^n, an + z/4^n)] , n = 1,2,...
Then for any z>0, the union of the intervals has length
< z, so the countable set has measure 0.
The Continuum Hypothesis
David Hilbert: (1862-1943)

The continuum hypothesis problem was the first of
Hilbert's famous 23 problems delivered to the Second
International Congress of Mathematicians in Paris in
1900.
 The Hilbert Problems of Mathematics challenged (and
still challenge today ) mathematicians to solve these
fundamental questions for the entire 20th Century.
From Hilbert's original paper "MATHEMATICAL
PROBLEMS.“
Problem 1A

Two systems, i. e, two assemblages of ordinary real numbers or points, are said to be (according to
Cantor) equivalent or of equal cardinal number, if they can be brought into a relation to one another
such that to every number of the one assemblage corresponds one and only one definite number of
the other. The investigations of Cantor on such assemblages of points suggest a very plausible
theorem, which nevertheless, in spite of the most strenuous efforts, no one has succeeded in
proving. This is the theorem:

Every system of infinitely many real numbers, i. e., every
assemblage of numbers (or points), is either equivalent to the
assemblage of natural integers, 1, 2, 3,... or to the assemblage of all
real numbers and therefore to the continuum, that is, to the points of
a line; as regards equivalence there are, therefore, only two
assemblages of numbers, the countable assemblage and the
continuum.

From this theorem it would follow at once that the continuum has the next cardinal number beyond
that of the countable assemblage; the proof of this theorem would, therefore, form a new bridge
between the countable assemblage and the continuum.
Hilbert Problem 1B
Well Ordering The Real Numbers



Let me mention another very remarkable statement of Cantor's which stands in the closest connection with the
theorem mentioned and which, perhaps, offers the key to its proof. Any system of real numbers is said to be ordered,
if for every two numbers of the system it is determined which one is the earlier and which the later, and if at the same
time this determination is of such a kind that, if a is before b and b is before c, then a always comes before c. The
natural arrangement of numbers of a system is defined to be that in which the smaller precedes the larger. But there
are, as is easily seen infinitely many other ways in which the numbers of a system may be arranged.
If we think of a definite arrangement of numbers and select from them a particular system of these numbers, a socalled partial system or assemblage, this partial system will also prove to be ordered. Now Cantor considers a
particular kind of ordered assemblage which he designates as a well ordered assemblage and which is characterized
in this way, that not only in the assemblage itself but also in every partial assemblage there exists a first number. The
system of integers 1, 2, 3, ... in their natural order is evidently a well ordered assemblage. On the other hand the
system of all real numbers, i. e., the continuum in its natural order, is evidently not well ordered. For, if we think of the
points of a segment of a straight line, with its initial point excluded, as our partial assemblage, it will have no first
element.
The question now arises whether the totality of all numbers
may not be arranged in another manner so that every partial
assemblage may have a first element,
i. e., whether the continuum cannot be considered as a well
ordered assemblage--a question which Cantor thinks must be answered in the affirmative. It appears
to me most desirable to obtain a direct proof of this remarkable statement of Cantor's, perhaps by actually giving an
arrangement of numbers such that in every partial system a first number can be pointed out.
Godel: (1906-1978)
Consistency of CH
(and Axiom of Choice)
Consistency of the axiom of choice and of the generalized
continuum-hypothesis with the axioms of set theory (1940)
Kurt Gödel showed, in 1940, that
if the axioms of set theory are consistent,
then adding the Axiom of Choice and/ or the Continuum Hypothesis will
not make the enlarged theory inconsistent.
[This will not be discussed here.]
Cohen: (1934- )
Independence of the CH
(and the Axiom of Choice)

In 1963 Paul Cohen proved that the Axiom of Choice is independent
of the other axioms of set theory. Cohen used a technique called
"forcing" to prove the independence of the axiom of choice and/or of
the generalized continuum hypothesis from the conventional axioms
for set theory.

In 1967 Dana Scott [and Robert Solovay] published Models for the
real numbers based on Probability-Measure Theory.
A proof of the independence of the continuum hypothesis,
Mathematical Systems Theory, volume 1 (1967), pp. 89-111.
This paper demonstrated the independence of the CH using a
probability based model for the real numbers.


Models for Formal
Mathematical Logical Systems


1.
2.
3.

A Formal System uses symbolic logic with predicates and quantifiers
to try to capture and express completely and uniquely the totality of
statements of a mathematical theory.
Key issues for such a formal system are
Is the system of logically related propositions sound?
Is the system consistent?
Does the system contain all the propositions of the mathematical
theory as theorems…. Is it complete?
A (set theoretic) model for a formal system is an interpretative
correspondence between a part of set theory and the constants,
variables, predicates, and other aspects of the formal system. In the
model’s interpretation every theorem (proven statement) of the
system is true.
How to show the CH is not provable from formal set
theory even with the axiom of choice:
An example of the argument.
Suppose P and S are sets.
We say a set S is P countable if there is a function from P onto S.
The PR- Hypothesis (PRH):
Suppose P is a subset of R. If X is a subset of R and X is not P
countable, then R is X countable.
Note: With P = the natural numbers and
R= the real numbers, PRH = CH.

Two Models For “PRH”

Model 1: Let P = {1,2,3,4,5} and R = { 1,2,3,4,5,6}.
Then R is the only subset of R that is not P countable and PRH is true for this
model.
Thus- PRH is consistent with formal set theory (including the axiom of choice).
Model 2: Let P = {1,2,3,4,5} and R = { 1,2,3,4,5,6,7}
Then let X = { 1,2,3,4,5,6}. X is not P countable but R is not X countable. So the
PRH is false for this model.

Thus- the negation of PRH is consistent with formal set theory (including the axiom
of choice).
SO in general:
If formal Set Theory (including the axiom of choice) is sound (consistent), PRH
cannot be proven as a result of Formal Set Theory, i.e.,
PRH is independent of the axioms of formal set theory.
A Formal System
for the Real Numbers
Is built using a well established formal system for set theory. A
formal system for the real numbers must have enough features
to makes sense of at least such concepts as
 the natural numbers




the rational numbers
the operations of addition and multiplication
the relations of equality and inequality
functions and functionals.
A standard model
or the real numbers







Usual treatment given in many high school courses and justified more
carefully in a university level real analysis course.
Natural numbers connected to cardinal numbers of sets.
Integers and rational numbers as classes of natural numbers.
Real numbers can be understood as represented by infinite decimals
or convergent sequences of rational numbers.
Number equality explains why
1 =.9999999…
Operations are based on sums and disjoint unions of sets.
Functions and functionals are based on ordered pairs.
A Random Real

Definition: A random real is a measurable function from a probability
sample space, Ω, to the real numbers, R:
i.e., r: Ω -> R so that for any a < b,
the probability of the set {s: a<r(s)<=b} is measurable or {s: a<r(s)<=b} is a
measurable sub set of Ω .

Note: The total measure of Ω is 1, and Ω can have sets of measure 0.
In particular Ω can be the cartesian product of a large number of copies of
the interval [0,1].
{We'll decide how large later.}
Think about Ω = [0,1]x[0,1] as an example.
There are several random reals on Ω :
Constant random reals with the natural numbers. 0(s)=0 1(s)=1,2(s)=2, etc.
Projection random reals:
p1(s) = x and p2(s) = y where s = (x,y).




The Formal Real Numbers:
Making a Model Using the Random Reals





Consider how random real numbers might satisfy key formal properties of
the usual real numbers.
For example, one key property that we can use as a TEST STATEMENT
about the real numbers is
If a*b= 0 then either a=0 or b=0.
Unfortunately, if a and b are random real numbers then the fact that a*b=0
doesn't imply that a=0 or b=0.
Here is a specific counterexample:
Let a(x,y)=0 when y<=.5 and
a(x,y) = 1 when y >.5 and
b(x,y) = 1- a(x,y).
Then, for any s=(x,y), either a(s)=0 or b(s)=0,
so a*b(s) =a(s)*b(s)=0,
but neither a = 0 nor b = 0.
Simple Statements that are true for The
Random Reals Model

Definition: We will say that a simple arithmetical/algebraic (formal) statement
P(x) about a real number x is true in this probability model ( M- true) for the
random real r if the probability of the set { s : P(r(s)) is true} is 1 and is false in
this probability model (M-false) if the probability of the set { s : P(r(s)) is true}
is 0.

For example, the function defined by
f(s)=0 when s is rational and
f(s)=1 when s is not rational
is a random real for the sample space [0,1]
and the statement that f = 1 is M-true in this model.
[Any countably infinite subset of real numbers has measure 0.]

Even using this standard for truth, our test statement for the random reals to
model the real numbers is not true. The same counter example can be used.
a*b = 0 is M- true but a=0 is not M-true and b=0 is also not M-true.
What we need is an interpretation not only of the real numbers, arithmetic, and
equality, but a different interpretation in this model for the logical connectives and
quantifiers used in the formal statements describing the real numbers.

Logic for the Model

We'll say that value of a formal statement L(x) about a real number x,
v(L), is the probability of the subset of Ω {s:L(r(s)) is true in the
common meaning for a random real r}.

We'll say that a statement is
P-true if its value is 1,
P-false if its value is 0.

Consider the example random real a.
Then the statement a=0 is not P true but is also not P false!
For more complicated statements we use the following procedures to
evaluate a statement:


v(A&B)= prob{s: A(s) and B(s) are true.}

v(A or B) = prob{ s:A(s) or B(s) (or both) is true}

v(not A) = prob {s: not A(s) is true}
Notice: the value of the statement
F(a): “Either a=0 or it is not the case that a=0”
is determined by the probability of {s: a(s)=0 or it is not the case that a(s)= 0}.
This set is Ω, so the probability is 1 and this statement is P-true.

The Value of the Test Statement




Now let's look at the TEST STATEMENT RESTATED using negation
and “or”:
Either a=0, b=0, or it is not the case that a*b=0.
To determine the value of this statement we consider the probability of
the set
{ s: a(s)=0, b(s)=0, or not a(s)*b(s) =0 is true.}
But for any s in Ω, if a(s)*b(s)=0, then either a(s)=0 or b(s)=0 is true.
So the set under consideration is Ω, and the probability is 1.
So the test statement is P-true.
Some Hand Waiving

With more work extending the structures and logic, Scott showed that
the random real numbers for any particular probability measure space
would provide a consistent model for the reals. [Assuming Set Theory
including the axiom of choice is already consistent.]

Now the consistent model we want is one in which the continuum
hypothesis fails to be true in some way, in particular the Continuum
Hypothesis will not be P-true in real number model based on Random
reals as just outlined.
Constructing a model for the real numbers
where the CH fails.

Lemma: There is no onto function from R, the set of real numbers, to
P(R), the set of all subsets of the real number.
Proof: Suppose f: R -> P(R). Let B= {x such that x is not an element
of f(x)}. Suppose B=f(b) for some b. If b is in B then b is not in f(b)=B,
which is a contradiction. So b is not in B, but then b is not in f(b), so b
is in B! Thus B is not f(b) for any b, and f is not onto.

Thus: There are sets which are larger than the reals.

Use Ω = the product of one copy of the interval [0,1] for every subset
of the real numbers.
It is a result of measure theory using the Axiom of Choice, that this Ω
is a sample space for a probability measure and any of the projection
functions are random reals.

The Counterexample to the CH:
A Large Set of
Random Real Numbers

Let the set T contain precisely those random reals that correspond
to the projections for the single element subsets of the reals.

The following can then be shown:
The set of random reals that correspond to the natural
numbers in this model cannot count (be mapped
onto) the set T.
The set T cannot map onto the set of all projection
random reals, so it cannot count (be mapped onto) all
the random reals.
THUS, the continuum hypothesis fails to be true in this
probability model for the formal system of real numbers.
1.
2.

References and Reading







Philosophical Introduction to Set Theory by Stephen Pollard
The Mathematical Experience by Philip J. Davis and Reuben
Hersh
P. J. Cohen, The independence of the Continuum Hypothesis. I.
Proc. Nat. Acad. Sci., U.S.A. 50 (1963) 1143-1148, and II. ibid. 51
(1964) 105-110.
Dana Scott, A proof of the independence of the continuum
hypothesis, Mathematical Systems Theory, volume 1 (1967), pp.
89-111.
What is mathematical logic? by J.N. Crossley et al.
Set Theory and the Continuum Hypothesis by Raymond M.
Smullyan and Melvin Fitting
Intermediate Set Theory by F.R. Drake and D. Singh
The End
