1. Mathematical Argument

"The great difficulty in talking about non-algorithmic phenomena is that although we can say what it is in general terms that they do, it is impossible by their very nature to describe how they do it."

Buddhism, mind, mathematics and metamathematics

Exaustive Search:

The Seven Bridges of Konigsberg Over the River Pregel:

Is there a route over the seven bridges that only traverses each bridge once?

Method 1:

Label the bridges and $\QTR{Large}{7}$ . Try the possibilities.

Method 2:

Consider the associated Graph:

and argue about traversal properties of nodes with an odd/even number of edges. In particular, in a "one-time traverse"

of a node with a even number of edges - a path both begins and ends there, or neither begins nor ends there .
of a node with a odd number of edges - a path must begin there or end there but not both.

Algorithmic Proofs:

Theorem:

There does not exist a rational number $\QTR{Large}{r}$ such that

PROOF:.

Fundamental Lemma of Number Theory: Let be two integers. There exits unique integers $\QTR{Large}{q}$ and $\QTR{Large}{r}$ with and

Note: Uniqueness follows from the fact that implies

Definition: Let be two integers. The greatest common divisor of $\QTR{Large}{m}$ and $\QTR{Large}{n}$ is defined to be largest integer $\QTR{Large}{d}$ such that

$\QTR{Large}{d}$ divides both $\QTR{Large}{m}$ and $\QTR{Large}{m}$ . ().

Since $\QTR{Large}{1}$ divides both $\QTR{Large}{m}$ and $\QTR{Large}{n}$ , we can use induction to show that exists. For that matter, since one can compute $\QTR{Large}{d}$ (very inefficiently!) by

trying all values, starting at $\QTR{Large}{1}$ and ending at the least of $\QTR{Large}{|m|}$ and $\QTR{Large}{|n|}.$

Examples: .

Lemma: Suppose then .

$\qquad$ PROOF: In fact all of their common divisors are in common!

The Euclidean Algorithm for computing :

Theorem( Extended Euclidean Algorithm): Let There exists integers $\QTR{Large}{a}$ and $\QTR{Large}{b}$ , computable using the Euclidean Algorithm such that

$\vspace{1pt}$

$\qquad$ PROOF: (By induction)

If $\QTR{Large}{m=n}$ the theorem is trivial so for simplicity assume that $\QTR{Large}{m>n>0}$ . Again if $\QTR{Large}{n}$ divides $\QTR{Large}{m}$ the theorem is trivial so assume

$\ \QTR{bf}{\ \ }$ hence

If $\QTR{Large}{r}_{1}$ divides $\QTR{Large}{n}$ then and .

Otherwise

$\ \QTR{bf}{\ \ }$ hence and

or again if $\QTR{Large}{r}_{2}$ divides $\QTR{Large}{r}_{1}$ we are done else......

Example- Compute

Computing the simple-minded way requires long divisions. Divide $\QTR{Large}{746}$ and $\QTR{Large}{83}$ by $\QTR{Large}{2}$ through $\QTR{Large}{41}$ .

Now by the euclidean algorithm,

This admittedly is an easy example but we see that EA requires long divisions to find .

Lemma: Suppose $\QTR{Large}{p}$ is prime (the only divisors are $\QTR{Large}{p}$ and $\QTR{Large}{1}$ ). Suppose $\QTR{Large}{p}$ divides $\QTR{Large}{cd}$ then $\QTR{Large}{p}$ divides $\QTR{Large}{c}$ or $\QTR{Large}{p}$ divides $\QTR{Large}{d}$ .

$\qquad$ PROOF: Suppose $\QTR{Large}{p}$ does not divide $\QTR{Large}{c}$ , then . Thus there exists integers $\QTR{Large}{a}$ and $\QTR{Large}{b}$ , such that

Multiplying both sides of the equation by $\QTR{Large}{d}$ gives

Finally, setting $\QTR{Large}{pr=cd}$ we get an explicit divisor

In particular,

Proof that there does not exist a rational number $\QTR{Large}{q}$ such that

Let . Assume Given a pair we know how to calculate ! Multiplying, we have . Since $\QTR{Large}{2}$ divides we conclude from the lemma above (again a calculation) that $\QTR{Large}{c=2e}$ for some $\QTR{Large}{e.}$

Hence or . Hence as before $\QTR{Large}{d=2f}$ . Thus .

Existence Proofs:

Theorem: Let f:[0,1] $\rightarrow$ [0,1] be a continuous function then there exists an x such that f(x) = x.

This is a consequence of the following

Intermediate Value Theorem: Let f:[0,1] $\rightarrow$ be a continuous function. Let f(0) $\leq$ c $\leq$ f(1). Then there exists a $\in$ [0,1] such that f(a) $\QTR{Large}{=}$ c.

To see how the first result follows from the second apply the intermediate value theorem to g(x)=x-f(x). One notes that g(0) $\leq$ 0 and g(1) $\geq$ 0

We will discuss this result in some detail, and in greater generality, in the second part of this course. The following brief discussion is simply meant to remind about the nature of the Real numbers and to continue to set the stage for our discussion of Set Theory. We begin with Dedekind's definition of the real numbers.

Definition: A Dedekind cut of the Rationals, , is a subset $\QTR{Large}{A}$ $\subseteq$ that satisfies these properties:

1. $\QTR{Large}{A}$ is not empty.

2. is not empty.

3. $\QTR{Large}{A}$ contains no greatest element

4. For if and $\QTR{Large}{y<x}$ , then .

the set of "Real Numbers" is defined to be the set of all Dedekind cuts of Note that in the definition only the "order property" of is used. We could, in fact, generalize the definition of Dedekind cuts by simply replacing with an appropriatley ordered set. One would then write something like .

Examples:

Let be a rational. Let all . We can consider by observing that different rationals generate different Dedekind cuts.(Exercise: Why?)
. Let all rationals all positive rationals $\QTR{Large}{q}$ such that . This gives us a "construction" of
Let be a strictly increasing sequence of rational numbers that is bounded above.
Define all $\QTR{Large}{q}$ such that there exists an $\QTR{Large}{i}$ with .
All bounded increasing sequences in have limits in (WHY?) Note: is correct, since by assumption we know
More generally, Let . Be an arbitrary set of Dedekind cuts that is bounded above, then is a Dedekind cut. Bounded above simply means that there is some $\QTR{Large}{q}$ such that for any $\QTR{Large}{r}$ .
Let be a finite set of Dedekind cuts, then is a Dedekind cut.

Exercise:(to be turned in Wednesday Jan 26) Prove 4. and 5.

Solution for 4.:

We need check the the 4 properties of a Dedekind cut hold.

1. Since ,

2. Since for any $\QTR{Large}{r}$ , , hence

3. Let then for some $\QTR{Large}{r}$ , since is a cut there is some with .

But implies .

4. Is essentially the same argument.

Solution for 5.:

1. Choose and let since we only have a finite number of this makes sense. Since

and for all i. for all i. Hence .

2. Since and we can conclude that .

3. Let , choose with . Now let As in 1. this exists. Check that

for all i, hence MATH and

4. Is immediate since if , and $\QTR{Large}{y<q}$ , then for all i. hence .

Exercise:(to be turned Wednesday Jan 26). Consider the set of positive infinite decimal fractions

where 0,1,2,3,4,5,6,7,8,9 $\QTR{Large}{\}}$ and there does not exist an n such that

0 for n $\QTR{Large}{\leq }$ i $\QTR{Large}{.}$

Show that there is a 1 to 1 order preserving map from set of positive infinite decimal fractions to the appropriate set of Real numbers.

Solution :

Let to be more precise MATH

Since the infinite decimal fractions is bounded above by 1, we can apply 4. above to conclude is a cut.

To see that distinct fractions result in distinct cuts, we begin by noting that and since the infinite decimal fraction does not end in a string of 0s, there is some m with

Assume . Specifically, there is an n with

MATH . One checks that this implies that for all n,

, hence . On the other hand since we can choose some s with we have

MATH . Thus MATH

Observation :

Based on the examples above and the fact that there does not exist a rational number $\QTR{Large}{q}$ such that we have

Definitions:

Real numbers can be compared. Let and be real numbers we define $\leq$ if . One can also extend the rules of arithmetic so as to give the expected properties of the Real numbers.

Comments:

After making the appropriate observations one might ask if the Dedekind process could be repeated? In particular, , itself, is a candidate for extension by Dedekind cuts. But,in fact, one can show that the inclusion $\QTR{Large}{D}$ () is 1 to 1 and onto.

Thus, for example, one can revise Example 3. to show that all bounded increasing sequences in have limits in . This is the heart of the Intermediate Value Theorem