CS计算机代考程序代写 compiler FIT2014 Theory of Computation Lecture 5 Proofs: the Good, the Bad and the Ugly

FIT2014 Theory of Computation Lecture 5 Proofs: the Good, the Bad and the Ugly

Monash University
Faculty of Information Technology

FIT2014 Theory of Computation

Lecture 5
Proofs: the Good, the Bad and the Ugly

slides by

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969

Warning
This material has been reproduced and communicated to you by or on behalf of Monash University

in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.

Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.

1 / 15

Overview

I Good proofs
I three proofs from The Book

I Bad proofs

I Ugly proofs

2 / 15

Good proofs
Theorem. (Pythagoras)√

2 is irrational.

Proof.
Suppose, by way of contradiction, that

√
2 is rational.

Then, by definition, there exist positive integers m, n such that
√

2 = m
n

.
Among all such pairs m, n, choose a pair that have no common factors.
Squaring each side of our equation gives: 2 = m

n2
.

Rewrite slightly: 2n2 = m2.
This tells us that m2 is even. Therefore m is even. Therefore m = 2k for some k .
Substituting this back in gives: 2n2 = (2k)2, i.e., 2n2 = 4k2, i.e., n2 = 2k2.
This tells us that n2 is even. Therefore n is even.
Since m and n are both even, they both have a common factor, namely 2.
But we chose them so that they have no common factors. This is a contradiction.
Therefore our initial assumption, that

√
2 is rational, must be wrong.

Therefore
√

2 is irrational.
3 / 15

Good proofs

Theorem. (Euclid)
There are infinitely many prime numbers.

Proof.
Suppose, by way of contradiction, that there are only finitely many primes.
Let n be the number of primes.
Let p1, p2, . . . , pn be all the primes.
Define: q := p1 · p2 · · · · · pn + 1.
This is bigger than every prime pi . Therefore q must be composite.
Therefore q is a multiple of some prime.
But, if you divide q by any prime pi , you get a remainder of 1. So q cannot be a
multiple of pi .
So q cannot be a multiple of any prime. This is a contradiction.
So our initial assumption was wrong.
So there are infinitely many primes.

4 / 15

Good proofs

Definition: A set is countable if either

I it is finite, or

I it can be put in one-to-one correspondence (i.e., bijection) with N.

FIT2014
students

{ Mustafa, Elena, Mingxuan,
Alejandro, Yunhuai, Bernadine,

Leo, Chengjia, Alexander,

Cristian, Philip, Danniel, Omri,

Jingcheng, James, Ethan, John,

Yiyang, Shantanu, Samuel,

Maofan, Kaiyang, Zhen, Kevin,

Jotham, Dominic, Chase,

Shyam, Ziyang, . . . }

finite

1 ←→ 1
2 ←→ 2
3 ←→ 3
4 ←→ 4
5 ←→ 5
…

…
…

…

1 ←→ 0
2 ←→ 1
3 ←→ −1
4 ←→ 2
5 ←→ −2
…

…
…

…

Σ∗

1 ←→ 1 ←→ ε
2 ←→ 10 ←→ a
3 ←→ 11 ←→ b
4 ←→ 100 ←→ aa
5 ←→ 101 ←→ ab
…

…
…

…

5 / 15

Good proofs
Theorem. (Cantor)
The set of all languages is uncountable.

Idea of proof: If {all languages} were countable . . .

ε a b aa ab ba bb aaa aab . . .

1 ←→ L1: 3 7 7 3 7 3 3 3 7 . . .
2 ←→ L2: 7 7 3 3 7 7 7 3 3 . . .
3 ←→ L3: 3 3 7 7 7 3 7 7 3 . . .
…

…
…

… . . .
m ←→ Lm: 3 7 7 3 7 7 3 7 7 . . .
…

…
…

…
. . .

L̂: 7 3 3 . . .
6 / 15

Good proofs
Theorem. (Cantor)
The set of all languages is uncountable.

Proof. Suppose, by way of contradiction, that the set of all languages is countable.
Since we know it’s not finite, there must be a bijection between N and {all languages}.
Let the members of the set of all languages be Lm, m ∈ N.
Recall that the set of all finite strings is countable, so we can list them as xn, n ∈ N.
Define the language L̂ as follows:

∀n ∈ N : xn ∈ L̂⇔ xn 6∈ Ln.

We have constructed L̂ so that, for each n, it differs from Ln in whether or not it
contains xn.
So it differs from all languages. Yet it is a language! This is a contradiction.
So our initial assumption was wrong.
So the set of languages is uncountable.

7 / 15

Bad proofs

From a falsehood, you can prove anything.

Recall the truth table of P ⇒ Q: always True when P is false, regardless of Q.

2+2 = 5
Therefore 4 = 5
Therefore 1 = 2
Now, |{McTaggart, The Pope }| = 2.
Therefore |{McTaggart, The Pope }| = 1.
Therefore McTaggart is the Pope.

attributed to G. H. Hardy in:
, Scientific Inference,

Cambridge University Press, 1931/1957/1973.

8 / 15

Bad proofs
“Theorem”: Every graph has a cycle.
For all n: every graph on n vertices has a cycle.
This implies that trees do not exist.
“Proof”. We prove this by induction on the number of vertices.

1. Assume that every graph on n vertices has a cycle.

2. Let G be any graph on n + 1 vertices.

3. Let v be a vertex of G . Obtain the graph G − v by removing v , and all its
incident edges, from G .

4. Now, the graph G − v has n vertices.
5. By the Inductive Hypothesis, G − v has a cycle.
6. But, since G − v is a subgraph of G , any cycle in G − v is also a cycle in G .
7. Therefore G has a cycle.

8. Therefore, by Mathematical Induction, the result is true for all n.
So every graph has a cycle.

9 / 15

Bad proofs

Definition: A string is uniform if all its letters are identical.

I i.e., it consists entirely of as or entirely of bs

I i.e., it’s either aa · · · a or bb · · · b
Now, it is commonly thought that not all strings are uniform.
But we will now try to “prove”, by induction, that all strings are uniform!

10 / 15

Bad proofs
“Theorem”: Every string over the alphabet {a,b} is uniform.
“Proof”. We prove this by induction on the string length n.

1. Inductive basis: when n = 1, the string can only be “a” or “b”, and these are
each of the required form, so the “theorem” is true in this case.

2. Now assume n ≥ 2, and suppose every string of length n is uniform.
3. Let w be any string of length n + 1.
4. Let w1 be the string obtained from w by deleting the first letter of w , and let w2

be the string obtained from w by deleting the last letter of w .
5. Both w1 and w2 are of length n.
6. By the Inductive Hypothesis, both w1 and w2 must be uniform.
7. w1 and w2 overlap in n − 1 letters. Since n − 1 > 0, this means that the number

of letters shared by w1 and w2 is nonzero. So w1 and w2 must each consist
entirely of the same letter, i.e., either they both consist entirely of as or they both
consist entirely of bs.

8. It follows that w also consists entirely of as or entirely of bs, so it is uniform too.
9. The result follows for all n, by Mathematical Induction.

11 / 15

Ugly proofs

Theorem.
DOUBLEWORD ⊆ EVEN-EVEN

Proof. Let w ∈ DOUBLEWORD.
Assume w is not in EVEN-EVEN.
Then w = xx for some word x .
So, # a’s in w = 2 × ( # a’s in x ), so it’s even.
Also, # b’s in w = 2 × ( # b’s in x ), so it’s even too.
This contradicts our assumption that w is not in EVEN-EVEN.
Therefore that assumption was wrong.
Therefore w ∈ EVEN-EVEN.

When you have a direct proof of your theorem, there’s no need to dress it up as a
proof by contradiction!

12 / 15

Ugly proofs?
A colouring of a graph G is a function that assigns a colour to each vertex of G such
that adjacent vertices receive different colours.

I i.e., a function f : V (G )→ {colours} such that
∀u, v ∈ V (G ) : u ∼ v ⇒ f (u) 6= f (v).

A colouring is a k-colouring if the number of colours used is ≤ k .

Applications:

I scheduling (timetabling)

I compilers (register allocation)

I communications (frequency assignment)

Theorem.
If G is planar then it has a 4-colouring.

13 / 15

Ugly proofs?

Theorem.
If G is planar then it has a 4-colouring.

Proofs:
I very long proof using computer to check 1476 configurations spanning 400 pages.

I K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois
Journal of Mathematics 21 (3) (1977) 429–490.

I K. Appel, W. Haken and J. Koch, Every planar map is four colorable. II.
Reducibility, Illinois Journal of Mathematics 21 (3) (1977) 491–567.

I long proof using computer to check 633 configurations
I N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem,

Journal of Combinatorial Theory, Series B 70 (1997) 2–44.

I proof by Robertson et al. (1997) formalised and formally verified by computer
I G. Gonthier, Formal proof — the Four Color Theorem, Notices of the American

Mathematical Society, 55 (11) (Dec. 2008) 1382–1393.

14 / 15

Ugly proofs?

Recall: to solve quadratic equations, ax2 + bx + c = 0: x =
−b ±

√
b2 − 4ac

2a
.

Formulas also exist for cubic and quartic equations. But . . .

Abel-Ruffini Theorem
There is no general algebraic formula (using arithmetic operations, powers & roots)
for the roots of polynomials of degree ≥ 5.

Incomplete proof, > 500 pages:
I Paolo Ruffini, Teoria generale delle equazioni, in cui si dimostra impossibile la

soluzione algebraica delle equazioni generali di grado superiore al quarto,
Stamperia di S. Tommaso d’Aquino, Bologna, 1799.

Complete proof, six pages:
I Niels , Mémoire sur les équations algébriques, ou l’on démontre

l’impossibilité de la résolution de l’équation générale du cinquième degré,
Groendahl, Christiania (Oslo), 1824.

15 / 15

Related Posts