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 MATH and $\QTR{Large}{7}$. Try the MATH 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"



Algorithmic Proofs:

Theorem:

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

PROOF:.

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

MATH

                              MATH

 

 

 

Note: Uniqueness follows from the fact that MATH implies

                              MATH

Definition: Let MATH 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}$ . (MATH).

Since $\QTR{Large}{1}$ divides both $\QTR{Large}{m}$ and $\QTR{Large}{n}$ , we can use induction to show that MATH exists. For that matter, since MATH 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: MATH. MATH MATH

Lemma: Suppose MATH then MATH.

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

The Euclidean Algorithm for computing MATH:

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

MATH

$\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

MATH $\ \QTR{bf}{\ \ }$henceMATH

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

Otherwise

MATH $\ \QTR{bf}{\ \ }$henceMATH and

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

Example- Compute MATH

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

Now by the euclidean algorithm,

MATH

MATH

MATH

MATH

MATH

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

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 MATH. Thus there exists integers $\QTR{Large}{a}$ and $\QTR{Large}{b}$ , such that

MATH

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

MATH

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

MATH

In particular,

MATH

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

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

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



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 $ MATH 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, MATH , is a subset $\QTR{Large}{A}$ $\subseteq $ MATH that satisfies these properties:

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

2. MATH is not empty.

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

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

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

Examples:

  1. Let MATH be a rational. Let MATHall MATH . We can consider MATH MATH MATH by observing that different rationals generate different Dedekind cuts.(Exercise: Why?)

  2. MATH . Let MATHall rationals MATH all positive rationals $\QTR{Large}{q}$ such that MATH. This gives us a "construction" of MATH

  3. Let MATH be a strictly increasing sequence of rational numbers that is bounded above.
    Define MATHall $\QTR{Large}{q}$ such that there exists an $\QTR{Large}{i} $ with MATH .
    All bounded increasing sequences in MATH have limits in MATH(WHY?) Note: MATHis correct, since by assumption MATH we know MATH

  4. More generally, Let MATH. Be an arbitrary set of Dedekind cuts that is bounded above, then MATH is a Dedekind cut. Bounded above simply means that there is some $\QTR{Large}{q}$ such that MATH for any $\QTR{Large}{r}$.

  5. Let MATH be a finite set of Dedekind cuts, then MATH 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 MATH , MATH

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

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

But MATH implies MATH .

4. Is essentially the same argument.


Solution for 5.:

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

MATH and MATH for all i. MATH for all i. Hence MATH .

2. Since MATH MATH and MATH MATH we can conclude that MATH MATH .

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

MATH for all i, hence MATH and MATH

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


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

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

MATH0 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 MATH to be more precise MATH

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

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

Assume MATH MATH MATH MATH . Specifically, there is an n with

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

MATH, hence MATH MATH . On the other hand since we can choose some s with MATH 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 MATH we have

MATH MATH MATH.

Definitions:

Real numbers can be compared. Let MATH and MATH be real numbers we define MATH $\leq $ MATH if MATH MATH. 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, MATH , itself, is a candidate for extension by Dedekind cuts. But,in fact, one can show that the inclusion MATH MATH $\QTR{Large}{D}$(MATH) is 1 to 1 and onto.

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