[TYPES] teaching discrete math and logic to undergraduates

[prakash]

Thanks for sharing these excellent notes with us.  I had a quick look at 
the logic section.  I think it is worth emphasizing that a proof by 
contradiction of a *negative* statement is perfectly constructive.  In 
fact it is not a proof by contradiction usually, it just looks like it.  
You give the example of showing that sqrt(2) is irrational.  Irrational 
means rational ==> false and thus
a constructive proof of this should proceed exactly in the way you  have 
shown.  Students and professional mathematicians  over-rate the 
importance of  proof-by-contradiction as a  technique.   When do we 
really use proof by contradiction to prove a positive statement?  Fairly 
often, but not as often as is made out.   A lot of proofs by 
contradiction have this pattern:

I want to show A implies B.  So assume A and NOT-B.  Now prove B then 
exclaim, contradiction!  OK, so I was half-joking.  I am sure none of 
the readers of this group do this, but I have seen students do it.

In the example you gave of a truly non-constructive proof: there exist 
two numbers a,b such that a,b are both irrational but a^b is rational 
you can get more of a bang if you point out that there is an obvious 
constructive proof:  take a to be sqrt(2) and b to be 2 log_2 3.  Then 
a^b = (sqrt(2))^[2log_2 3] = 3.  [I found this in Lambek and Scott].
Cheers
Prakash

Jean Gallier wrote:
> [ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
>
> Hi guys,
>
> For now three years, I have been teaching a Discrete Math course
> for undergraduates. I believe that it is important to expose these kids
> to logic, and since they should not be too brainwashed yet, I  try
> to present a proof system in natural deduction format in order
> to show them the difficulties with the "proof by contradiction  
> principle"
> and make them aware of some of the non-constructive aspects
> of classical logic. I
>
>   wrote some notes that I may want to convert into a book.
> There is also some good stuff on combinatorics and graphs.
> I have most solutions to my problems written up and more problems
> should be added.
> I'd be happy if you have any comments or suggestions.
> You'll find the manuscript there:
>
> http://www.cis.upenn.edu/~jean/gbooks/discmath.html
>
> Best,
> -- Jean Gallier
>