The Possible and The Impossible

The Possible and the Impossible:

Some Examples of the Use of Models and Their Consequences.

Martin Flashman

Thursday, December 6 SH 128 4:00 PM

In memory of my mother and father
who both helped me
believe that anything is possible and
understand that that some things are not possible.

Abstract: Throughout history many mathematical problems have turned out to be impossible to solve. Can one trisect an angle? Do parallel lines exist? Can a pair of equations be solved simultaneously? Are the real numbers countably infinite? Some of these problems have been more or less than impossible because they involved models and the way that the problems have been interpreted in models.

Professor Flashman will discuss some examples of models from geometry, algebra, and set theory that provide proofs for both the possible and the impossible.

Kant: Critique of Pure Reason

" The supreme concept with which it is customary to begin a transcendental philosophy is the division into the possible and the impossible.
.
...
.
4. The object of a concept which contradicts itself is nothing, because the concept is nothing, is the impossible, e.g. , a two-sided rectilinear figure."

Early examples of the possible and the impossible from Greek mathematics.

The Possible:

Given a segment AB of one unit length, it is possible to construct a segment AC of two units length.

Proof: Draw a circle with center B and radius AB. Extend the radius AB to meet the circle at C Then the diameter AC has measure two units. EOP

Given a square ABCD of one unit area, it is possible to construct a square of two units area.

Proof: Construct the square on the diagonal AC of the given square. Then the square on AC has area of two square units. EOP

The Impossible:

Given a square, it is not possible to find a segment for a common measuring unit between the side and the diagonal of that square.

Proof: Apply the Euclidean algorithm in an attempt to find a common measuring unit between the diagonal and a side of a square.This will fail. For suppose there is a common measuring unit for the two sides..

Sorry, this page requires a Java-compatible web browser.

Suppose the side of the square is measured by Q units and the diagonal is measured by P units. Then by the Pythagorean Theorem: P²= Q²+ Q² = Q²*2.

Now count the number of 2's on each side of the equation.

P² and Q²must each have an even number of 2's as factors.
[ P² has twice as many 2's as P and similarly Q² has twice as many 2's as Q ]

But then on the left side of the equation there are an even number of 2's as factors while on the right side there are an odd number of 2's. [One more than the even number of 2's that appear as factors of Q².]

This is impossible because there are (must be) the same number of 2's on both sides of the equation P²=Q² *2.

Thus
there is no segment that can be a common measuring unit. EOP

We can state these results in a more modern algebraic/analytic context as follows:

(1) It is possible to solve the equation x² = 2 with real numbers.

In the context of real numbers, the statement

"There is a number x with x² = 2" is true!

(2) It is not possible to solve the equation x² = 2 with rational numbers.

In the context of rational numbers, the statement "There is a number x with x² = 2" is false!

Issue: How can the same statement can be true in one context and false in another?

Response:There is a fundamental difference between the two contexts for the statements.

Furthermore, if we isolate all the statements that are true about both contexts, then the given statement cannot be a logical consequence of any collection of those statements.

[Why? Because the logical consequences of true statements about a context are also true about the context.]

Definition: Suppose S is a set of statements and M is a set together with related mathematical objects corresponding to the terms, relations, functions, etc. used in the statements of S.
M is called a model for S if every statement of S is true when interpeted for the objects in M.

Definition: A set of statements Tis consistent if for any statement A, it is not possible that both A and the negation of A are in T.

Remark: If a set of statements S has a model, then the set of all logical consequences T of the statements in the set (which includes the original set of statements) are consistent.

Here are other examples showing how the context or interpretation of a statement influences possibilities and truth.

Algebraic or analytic: Contexts: Integers vs. Rational Numbers vs. Real Numbers vs ..... [Take abstract algebra Math 343... Take real analysis Math 415]	Geometric: Contexts: Points and/or lines in Euclidean plane vs. projective plane vs. hyperbolic plane vs... [Take geometry Math 371.]
There is a solution to a linear equation. 3x=24; 3x=13	Partition segments: 2AC= AB; KAC=AB Proportions of line. AB:DE::AC:DX (Intersections of parallel lines/ similiar triangles)
There is a solution to a quadratic equation. x²= 2.	bisect angle, double a square- Intersection of line with circle, circle with circle. [Rational vs. real geometry]
There is a solution to a cubic equation. x³= 2. There is a solution to a polynomial equation.	Angle trisection is possible/impossible! The duplication of a cube is possible/impossible.
There exist algebraic irrational and transcendental numbers.	There are "non-constructible" lengths.
There is a common solution to a pair of linear equations. 3x + y = 5; x + y = 3 3x + y = 5; 6x + 2y = 8	A pair of lines has a common point. Lines in the plane. Lines on the sphere.
There is a positive number h>0, so that: if a>0, then h < a.	If AB has length h and CD has length a and then there is some counting number N where Nh>a.
There is a nonzero number x with nx = 0	There is a way to move an oriented object to change its orientation.
An infinite subset of the natural numbers, integers, rational or algebraic numbers can be "counted"	The set of segments "constructible" from a given length can be counted.
[a,b], [c,d]; [a,b], [a,b); [a,b], and the circle- Set theory vs. "bi-continuous" 1:1 functions	A line segment, A Ray, A Circle. Set Theoretic vs. "bi-continuous" 1:1 geometric functions
Any subset of the real numbers can be counted [can be measured.]	Any set of points on a line segment can be counted. [can be measured.]

Issue (revisited): How can the same statement, A, can be true in one context and false in another?

Response: Consider each context as the basis of a separate model.

For the first model consider all statements that are true in both contexts together with the statement A that is true in the first context. We'll call this set of statements S1. Then the context in which the statement A is true is a model for S1.

For the second model consider all statements that are true in both contexts together with the negative of the statement A. We'll call this set of statements S2. Then the context in which the statement A is false is a model for S2.

But the existence of models for both S1and S2 means that it is not possible to prove either the statement A or its negation ~ A from the collection of statements true for both contexts.

Thus when a statement, A, and its negation, ~A, are true (possible) in different but related contexts it is not possible to prove the statement A from a set of statements true in both contexts.

In this sense we say that the statement A (and its negation ~A) is independent from any subset of the statements true for both contexts.

Countability: Possible or Impossible?

Definition: A set X is countable if there is a function f mapping the natural numbers onto X, so that for any x in X there is some natural number n where f (n) = x, i.e. X= { f (1), f (2), f (3), ... }

The Possible:

Proposition: The set of positive rational numbers is countable.
Proof: (1) Cantor's first diagonal argument.

1/1	2/1	3/1	4/1	5/1	6/1	...
1/2	2/2	3/2	4/2	5/2	6/2	...
1/3	2/3	3/3	4/3	5/3	6/3	...
1/4	2/4	3/4	4/4	5/4	6/4	...
1/5	2/5	3/5	4/5	5/5	6/5	...
1/6	2/6	3/6	4/6	5/6	6/6	...
...	...	...	...	...	...	...

0, 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, ...
EOP

Proof (2) "Godel counting" argument.

when a >= 0, b>0 , ...a / b corresponds to 2^b3^a
when a<0, b>0, ... a/b corresponds to 2^b5^a

^EOP

Proposition: The algebraic numbers are countable.
Proof: [ Another first type of diagonal argument.]

Proposition: The set of English language mathematical propositions about the real numbers are countable.

Proof: More Godel counting. Each symbol is given a number used for an exponent. Prime numbers are used as the base for each symbol number, indicating the position of symbol in the statement of the proposition. Each statement corresponds uniquely to the product of powers of prime numbers.
EOP

The Impossible:

The set of points in a line segment is not a countable set. Cantor's Geometric proof (1874)

There is a set of real numbers that is not a countable set.

A decimal based proof (similar to 1891 proof)

There is no onto function from R, the set of real numbers, to the set of all subsets of the real numbers (usually called the power set of the real numbers).

Proof:

The Lowenheim-Skolem "Paradox"

Theorem: If a formal mathematical system is consistent, then there is a model for that system in which the underlying set of objects is countable.

Proof: Take Math 446. :)

Remarks:

There are formal mathematical systems for Set Theory which includes a formal theory for the real numbers.

Such a formal system can be demonstrated to be "relatively" consistent and is believed to be consistent.

Thus, by the Lowenheim - Skolem Theorem there is a model for the theory of real numbers in which the set of objects that correspond to real numbers in this model is a countable set and yet the theory says that the set of real numbers is not countable. How is this possible????

THE END!

Proof that the algebraic numbers are countable. [ Another first type of diagonal argument.] (1874)

Fact 1. An algebraic number is the solution to a polynomial equation with integer coefficients.

Fact 2. A polynomial equation of degree N can have at most N distinct real number solutions.

Fact 3. There are a finite number of integer polynomial equations of degree N where the sum of the absolute values of the coefficients is less than a given number K.

Proof Procedure: (modified slightly from Cantor's)
First list algebraic number roots from integer polynomials of degree 1 with sum of the absolute values of the coefficients equal to 1. (This is just 1x=0 and -1x=0.)
Then use degree 1, sum 2;
(This is 2x=0, -2x=0, 1+1x=0, -1+1x=0, 1-1x=0, -1-1x=0.)
then degree 2, sum 1;
then degree 3, sum 1;
then degree 2, sum 2;
then degree 1, sum 3;. ...

EOP

A decimal based proof that there are an uncountable set of real numbers.(A variation similar to 1891 proof)

Consider the set S of real numbers determined by having the 2k th decimal be a 5 for every k.
For example: .358595953525450505050505... is in S.

A real number b in S is determined uniquely by a sequence of integers, with each integer between 0 and 9, where the kth integer of the sequence corresponds the 2k+1 th decimal place of b.

Suppose there is a function, f, from N to S.
Then let b=.b1 5 b3 5 b5 5 b7 5 b9 5 ... where we choose b2k+1 so that it is not equal to the 2k+1st digit of f(k).

Thus b is not equal to f(k) for any k and f is not "onto."
Hence S is not a countable set. ( And so neither is [0,1].)
EOP

Proof that there is no onto function from R, the set of real numbers, to the set of all subsets of the real numbers.

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.
EOP