Skip to content

It should be true for n=k+1 or why I.H. works

April 17, 2014

By I.H. we mean byInductiveLeaf induction hypothesis.

First year in maths students are baffled about mathematical induction(M.I.). It is counter intuitive and it is true, it is hard to wrap one’s head around this concept. So to prove some mathematical property holds we are given the following template:

  1. First show that the property P ( the property of being divisible, being prime or equal to a formula’s value, you name it etc.) is true for the base case. If the base case is c then we prove that the property is true for it. Thus we work on showing P(c) is true.
  2. Second, we assume it is true for k, that is P(k) is true – we take this as fact. This second step is called the induction hypothesis – I.H.
  3. Lastly, we prove that P(k+1) is true as well using I.H. Thus should we succeed in this final step, we have all the right to claim that we have proof that P is true for all n.

It is I.H. that is hard to take. Why is it that a.) we should assume it and b.) why is it that if step 3 succeeds provided we use the fact of step 2, we have the right to say – Q.E.D. or say “proven as required”! What right do we have in assuming I.H.

There are a few comments that we can make about this:

  • Firstly, M.I. is about the property of numbers (in general). Numbers obey this I. H. property. As a classic example consider a number x such that x > c, for some number like 8. So if we have x > 8, can we say that the next number after x will also be greater than 8? We can guess that this should be true. So let us prove it…Consider x > 8, let us add 1 to both sides still maintaining the inequality. x > 8 \Rightarrow x + 1 > 8 + 1 = 9 > 8 \therefore x + 1 > 8.
  • Secondly, we are allowed to assume I.H. for after all we can set our n = c, i.e., to our base case and check if the property P(c+1) holds — thus by the same token we are allowed to move from the truth of P(c) to the truth that P(c+1). So we can assume I.H. because of this “domino effect”. The crucial bit is to show now that due to our utilisation of I.H. for an arbitrary n = k, we get the truth of P(k+1).
  • Lastly and strongly, we can take M.I. to be an axiom! Meaning, a proposition which is self-evidently (if I can use that word) true! Indeed Wikipaedia has it like this – \forall P[P(0) \wedge \forall k \in \mathbb{N}[P(k) \Rightarrow P(k+1)]] \bold{\Rightarrow} \forall n \in \mathbb{N}[P(n)].
  • Take a good look at this and consider the statement before the last \Rightarrow. If you look we have this form A \Rightarrow B. Remember modus ponens? It says if we have A \Rightarrow B and we have A, deduce B.

Well when we are doing M.I. what we are actually doing is that we are establishing the truth of A and when we succeed – voila, use this with the axiom and so conclude the property P holds for all n.

Looking at a formula is like looking at a piece of art

March 8, 2014

Beautiful_formula__square Dr. Benjamin Levitt alerted me to the article I first heard from a colleague at the university where I work. Apparently a group of neuroscientists examined the brains of 15 mathematicians using Magnetic Resonance Imaging (MRI). They showed these scientists pictures of mathematical formulas and the activity of the brains of these subjects reacted in the same way one’s brain reacts when it experiences viewing a beautiful piece of art or listening to beautiful piece of music.

Read the University College London article here.

Thinking of this now, it is this beauty that attracted me to studying mathematics, aside from of course, being inspired by great teachers who taught me and exposed me to its beauty. Though my father was an engineer (an my uncle a PE and  has a PhD in hydrology), I do not think it was the one which moved me to be a student of maths. I think I was more influenced by enthusiastic teachers who were passionate with the subject – I mean, these teachers loved the subject and their tamed enthusiasm nevertheless showed when they wrote proofs on the blackboard.

I like to study maths because of its beauty yet I am so poor at it.

221B Baker St., I got Sherlocked

February 1, 2014

sherlocked
I am so addicted to this TV series, I hope it stays for a long long time. It is beautifully done and the interaction of complex character personalities is often heartwarming and fun. Whenever I watch an episode, I cannot help but get reminded of what C. S. Peirce said…

From P.J. Davis & R. Hersh, The Mathematical Experience, 1981, Penguin Books

C. S. Pierce in the middle of the nineteenth century, announced that “mathematics is the science of making necessary conclusions.” Conclusions about what? About quantity? About space?The content of mathematics is not defined by this definition; mathematics could be “about” anything as long as it is a subject that exhibits the pattern of assumption-deduction- conclusion. Sherlock Holmes remarks to Watson in  The Sign of Four that “Detection is, or ought to be, an exact science and should be treated in the same cold and unemotional manner. You have attempted to tinge it with romanticism, which produces much the same effect as if you worked a love-story or an elopement into the fifth proposition of Euclid.” Here Conan Doyle, with tongue in cheek, is  asserting that criminal detection might very well be considered  a branch of mathematics. Peirce would agree.

He was correct after all, Gödel’s Proof for the existence of God

November 19, 2013
KG

KG

Kurt Gödel is considered the greatest logician since Aristotle. Prior to his death, Gödel wrote a proof for the existence of God. Some theorise that the reason he did not publish nor share this proof earlier was for fear of being ostracised by the academic community where he belonged. He was afraid it wouldn’t be cool.

Using a MacBook and  proof assistants (Coq and Isabelle), Christoph Benzmüller of Free University of Berlin and Bruno Woltzenlogel Paleo of Free University of Vienna, confirmed that  Gödel’s proof was correct, at least as far as higher order model logic is concerned. We might note that KG’s proof indeed, involved modal operators.  It only took a few minutes (even seconds) for the computer to validate that the steps KG made in his proof were valid and correct.

Christop and Bruno’s paper can be found here. While the report from Spiegel Online can be found here.

An ode to the Myhill-Nerode Theorem or how to show a language is regular without DFAs

November 2, 2013

This is an ode (although it is not a poem) to the Myhill-Nerode Theorem, thank God for it.

I saw a question that required one to show that the language of strings of EVEN length is regular. Formally, it means to show that
EVEN = \{ w | |w| = 2n, n \in \mathbb{N} \} is regular.

The way people have approached this is to specify an alphabet like \{0,1 \} and then construct a NFA or a DFA (finite automaton) that recognises only a even strings from these alphabets. A sample is found below

NFA of Even length

NFA of Even length

Hmmm, I am uncomfortable with this. Why? We have not been given any alphabet information on the problem. Why use or limit it to \{0,1 \}? What if the alphabet is composed of \{a,b,c \}, are we not capable of producing strings of even length from this alphabet? Sure we can but what happens to our DFA proof? It will fall short. I feel it is not a good approach, and I do not think it is rigorous, even though the proof is concisely crisp. The proof should handle the generic case with no appeal as to how the alphabet looks like. I believe that is the best approach. We can of course handle the general case by stating a general assumption on \Sigma and say \Sigma = \{ a_1, a_2,a_3,...,a_n \}. Then we replace the 0/1 notation in the diagram with a_1/a_2/a_3/.../a_n., then we are done. That covers every possibility and will only accept a string of even length.

 

Anyway back to the problem what if we have not been given the composition of  \Sigma ?

The Myhill-Nerode Theorem ( briefly treated here) if we know it is there to rescue you. Briefly it effectively states that the following statements are equivalent:

  • L \subseteq \Sigma^* is regular
  • The relation R_L, such that x,y \in \Sigma^*, (x,y) \in R_L iff \forall z \in \Sigma^*, xz \in L exactly when yz \in L, is finite.

We prove now that EVEN is regular:
Proof:

Form the membership R_L iff the right side is satisfied. Hence, (x,y) \in R_L then we have two cases for z.
1. z may be of even length m. Then xz \in EVEN, because |xz| = |x|+|z| = 2n + m is even because an even number (2n) + even number(m) results an even number, thus xz \in EVEN. Similarly for yz \in EVEN, the same argument applies.
2. z may be of odd length m. Then xz \not \in EVEN, because |xz| = |x|+|z| = 2n + m is odd because an even number (2n) + odd number(m) results an odd number, thus xz \not \in EVEN. Similarly for yz \not \in EVEN, the same argument applies.
3. There is only one equivalence class we can make of R_L, so finite.

We have shown that the second part of the above theorem is satisfied by our EVEN language, and since by the theorem, this is equivalent to the first part, we then conclude that EVEN is regular.

Q.E.D.

LPC

Showing balanced parens to be irregular

September 26, 2013

This is for young people doing CS and are wondering how to use the Pumping Lemma to verify if a formal language is regular or not :-). So let us have a theorem about the balanced parenthesis language :
Theorem:
L_{()} = \{ (^n \varphi )^n | n \geq 1 \wedge \varphi \neq \Lambda \} is not a regular language.
Method:
Some text books use \Lambda to denote the empty string so here \varphi is none empty. The method of proof is by contraction (Reduction ad Absurdium – RAA). So we assume the language is regular and hence can be pumped but show it to be otherwise, or not true by arriving at a contradiction. By the Pumping Lemma (PLem), \exists m so that m can be used to split w \in L_{()} into parts. We actually use this m to form w. We can do this because the Lemma says this m is valid for any w, |w| \geq m.
Proof:
Assume L_{()} to be regular. Then by PLem,  there exists an m such that for w \in L_{()}, |w| \geq m. Consider now the w formed by setting n = m. Then we have w = (^m \varphi )^m. Further we know that |w| = 2m+1 > m satisfying PLem premise, so it can be applied. As per PLem,  we can break w into x, y, z components. As per PLem also |xy| \leq m. Looking at the form of our w this implies that xy must be composed of all left parenthesis, i.e  xy = (^m, then y=(^p for some p < m.  As per PLem, we can pump y  for any k \geq 0.  So let k =0 then the new w = (^{m-p} \varphi )^m. But this implies that |(^{m - p}| = m - p \neq m =|)^m|, i.e. parentheses are not balanced. But this means w \not \in L_{()}. Contradiction. At this point we have found a k where the decomposition results in the string outside of L_{()}and we can stop.

Anyway consider now also y pumped upwards to k. Then we have the new w = (^{m-p}(^{pk} \varphi )^m. Looking at the left of \varphi we have |(^{m-p}(^{pk}|= m - p + pk \neq m= |)^m|. Again the parentheses do not balance out. Thus w \not \in L_{()}. Contradiction.

Q.E.D.

Feedback is appreciated – let me know if it has helped/not helped. Thanks.

Study shows students learn more from adjunct lecturers (like me ;-)

September 12, 2013

120724_DS_TEACHER.jpg.CROP.rectangle3-large

A study in the USA reports that students learn more from non-tenured track teachers. The article is found here at InsideHigherEd.com

This is heart warming. It is nice to know that casual lecturers have their place. Sometimes it is even better because you do not have to always look for funding to justify your existence. I feel for my tenured friends, they also work long hours drafting their grant proposals.

Follow

Get every new post delivered to your Inbox.