Mathematics 239 :  Introduction to Mathematical Proof
Fall 2011
Introduction
Professor:        Jeff Johannes                                    Section 1    MWF    10:30 - 11:20a    Sturges 105
Office:            South 326A                    
Telephone:      245-5403
Office Hours:    Monday 11:30a - 12:20p, Wednesday 4-5p, Thursday 1-2p, 8-9p, Friday 2:30 - 3:30p, and by appointment or visit
Email Address: Johannes@Geneseo.edu
IM:                    JohannesOhrs
Web-page:        http://www.geneseo.edu/~johannes

Textbooks
    Mathematics:  A Discrete Introduction, Second Edition, Edward R. Scheinerman    

Purposes

Overview
    It is often said that mathematics is a language.  In this class you will begin to learn to speak this language.  Just like in an introductory language course, we will start with the most fundamental concepts and grammar rules.  After we have some familiarity with the language of formal mathematics, we will practice this language in the setting of counting problems of different types.  More like an advanced language class, merely memorizing the vocabulary will not suffice  (in fact, hopefully we can keep vocabulary to a minimum), but rather you will be required to understand and speak clearly in this language.  The material learned here will help you understand the mathematics you read and clarify the mathematics you write.  Because we are learning how to write mathematics, exposition will also be a component in your evaluation.

Reading
    I have intentionally chosen a very readable text.  In addition to planning time to do homework, please take time to carefully read the sections in the book.  Notice use of the words “time” and “carefully”.  Read the sections slowly.  As the author indicates in the preface, read actively.  If you do not understand some statement reread it, think of some potential meanings and see if they are consistent, and if all else fails, ask me.  If you do not believe a statement, check it with your own examples.  Finally, if you understand and believe the statements, consider how you would convince someone else that they are true, in other words, how would you prove them?
    Because the text is exceptionally accessible, we will structure classtime more as an interactive discussion of the reading than lecture.  For each class day there is an assigned reading.  Read the section before coming to class.  In addition to the reading, there are also indicated exercises to check that you understood the reading.  If there are no questions from the reading we will discuss those indicated exercises during the class discussion.  

Grading
    Your grade in this course will be based upon your performance on homework, quizzes and three exams.  The weight assigned to each is designated below:
        Homework (6)                5% each
        Quizzes (3)                     5% each
        Colloquium Report (1)   5%
        In-class exams (2)        15% each
        Final exam (1)             20%
        
Homework
    There will be homework assigned at the onset of each new chapter.  Homework will be due shortly after each chapter ends.  You are encouraged to consult with me outside of class on any questions toward completing the homework.  You are also encouraged to work together on homework assignments, but each must write up their own well-written solutions.  A good rule for this is it is encouraged to speak to each other about the problem, but you should not read each other's solutions.  A violation of this policy will result in a zero for the entire assignment and reporting to the Dean of Students for a violation of academic integrity.  Each question will be counted in the following manner:
    0 – missing or plagiarised question
    1 – question copied
    2 – partial question
    3 – completed question (with some solution)
    4 – completed question correctly and well-written
Each entire homework set will then be graded on a 90-80-70-60% (decile) scale.  Late items will not be accepted.  Homework will be returned on the following class day along with solutions to the problems.  Please feel free to discuss any homework with me outside of class or during review. 
    On the assignments throughout the semester there are optional items indicated by parenthesis.  They may be replaced by the replacements following them.  If all of your problem sets at the end of the semester are complete (i.e. at least 2 points on each problem) and you have submitted none of the optional problems, I will add 11 points to your final problem set score.  

Quizzes
    There will be short quizzes after the homework has been returned, covering the material in the chapter from the homework.  For chapters immediately preceding exams, there will be no quiz.  Quizzes will consist of routine questions, and will have limited opportunity for partial credit. Because quizzes will consist of routine questions, they will be graded on a decile scale. There will be no makeup quizzes.

Colloquium Report
    Attend one of the department colloquium talks.  Write a report.  In the report, describe the content of the talk (including a detailed discussion of the mathematics).  In addition to your description of the talk, also write how this talk added to your understanding of the nature of mathematics.  Papers are due within a classweek of the colloquium presentation.  I will gladly look at papers before they are due to provide comments.

Exams
    There will be two exams during the semester and a final exam during finals week.  If you must miss an exam, it is necessary that you contact me before the exam begins.  Exams require that you show ability to solve unfamiliar problems and to understand and explain mathematical concepts clearly.  The bulk of the exam questions will involve problem solving and written explanations of mathematical ideas.  The final exam will be half an exam focused on the final two chapters, and half a cumulative exam.  Exams will be graded on a scale approximately (to be precisely determined by the content of each individual exam) given by
    100 – 80%   A
     79 – 60%    B
     59 – 40%    C
     39 – 20%    D
    below 20%   E
For your interpretive convenience, I will also give you an exam grade converted into the decile scale.  The exams will be challenging and will require thought and creativity.  They will not include filler questions (hence the full usage of the grading scale). 

Feedback
    Occasionally you will be given anonymous feedback forms.  Please use them to share any thoughts or concerns for how the course is running.  Remember, the sooner you tell me your concerns, the more I can do about them.  I have also created a web-site which accepts anonymous comments.  If we have not yet discussed this in class, please encourage me to create a class code.  This site may also be accessed via our course page on a link entitled anonymous feedback.  Of course, you are always welcome to approach me outside of class to discuss these issues as well. 

Social Psychology
    Wrong answers are important.  We as individuals learn from mistakes, and as a class we learn from mistakes.  You may not enjoy being wrong, but it is valuable to the class as a whole - and to you personally.  We frequently will build correct answers through a sequence of mistakes.  I am more impressed with wrong answers in class than with correct answers on paper.  I may not say this often, but it is essential and true.  Think at all times - do things for reasons.  Your reasons are usually more interesting than your choices.  Be prepared to share your thoughts and ideas.  Perhaps most importantly "No, that's wrong." does not mean that your comment is not valuable or that you need to censor yourself.  Learn from the experience, and always try again.  Don't give up. 

Academic Dishonesty
    While working on homework with one another is encouraged, all write-ups of solutions must be your own. You are expected to be able to explain any solution you give me if asked. The Student Academic Dishonesty Policy and Procedures will be followed should incidents of academic dishonesty occur. 

Disability Accommodations
    SUNY Geneseo will make reasonable accommodations for persons with documented physical, emotional or learning disabilities.  Students should consult with the Director in the Office of Disability Services (Tabitha Buggie-Hunt, 105D Erwin, tbuggieh@geneseo.edu) and their individual faculty regarding any needed accommodations as early as possible in the semester.

Religious Holidays
    It is my policy to give students who miss class because of observance of religious holidays the opportunity to make up missed work.  You are responsible for notifying me no later than September 12 of plans to observe the holiday. 


 Schedule (subject to change)

August 29
 - September 12    Chapter I reading discussions
September 14    Chapter I homework due
September 19    Chapter I quiz taken

September 14 - 23   Chapter II reading discussions
September 26    Chapter II homework due

September 26 - 28 review Chapters I and II
September 30         In class exam covering Chapters I and II

October 3 - 14    Chapter III reading discussions
October 17    Chapter III homework due
October 21    Chapter III quiz taken

October 17 - 24    Chapter IV reading discussions
October 26    Chapter IV homework due

October 26 - 28    review Chapters III and IV
October 31    In class exam covering Chapters III and IV

November 2 - 14    Chapter V reading discussions
November 16    Chapter V homework due
November 21    Chapter V quiz taken

November 16
 - December 7    Chapter VII reading discussions
December 9        Chapter VII homework due

December 9 - 12     review Chapters V and VII, and course as whole

Wednesday December 14 8-11a  Final exam, first half covering chapters V and VII
                 second half covering course

Problem Sets:
    Optional items are indicated by ( ).  They may be replaced by the replacement items.  Submitting no question for that item will result in zero points for that item.  

Assignment for Chapter 1:  To the student.1, 2.2, (2.6), 3.2, 3.9, (4.2), 4.9, 4.11, 4.14, 5.2, 5.5, (5.7), 6.8, 6.11
For example, this means that you must complete the second exercise in section 1.  There is also a required exercise at the end of the "to the student" section.

Replacements for Chapter 1:  
1.  Define a perfect number - be as precise as you can - probably use summation notation.
2.  Find a counterexample to the following:  If f is continuous and differentiable on (a, b) and f(a) = f(b), then there exists a real number c in (a, b) such that f'(c) = 0.
3.  Prove and extend or disprove and salvage:  The produce of any three consecutive integers is a multiple of 3.
4.  Prove (using the givens in the appendix):  A negative integer multiplied by a negative integer yields a positive integer.


Assignment for Chapter 2:  7.4, 7.9, 7.14, 8.1, 8.7, 9.2, 9.6, 10.5, 11.16, (11.17)

Replacement for Chapter 2:  
1.  Use the results in 11.17 to prove (A n (A' u B))' u B = U (ask me if this notation is unclear - limitations of html).


Assignment for Chapter 3:  13.2, 13.9, 13.12, (14.4), 14.8, 14.12, (15.11), 15.12, 16.10, (16.18), 16.19, 16.28

Replacements for Chapter 3:
1.   Let R and S be the relations on Z defined as follows:
    * a R b if and only if 2a + 3b = 0 mod 5
    * a S b if and only if a + 3b = 0 mod 5
    Are R and S equivalence relations?  If not, which properties do they hold.  Prove your results.
2.  How many partitions are there of a set with n elements?
3.  Present a combinatorial proof of:  sum

Assignment for Chapter 4:  (19.5) 19.7, 19.9, 21.5, 21.8 (valued as 6 questions)

Replacement for Chapter 4:  
1.  If n is a positive integer, then the smallest perfect square that exceeds n^2 is n^2 + 2n + 1
 

Assignment for Chapter 5:  (23.6), 23.9, 23.11, 23.12, (23.14), 23.15, 24.4, 24.9, 25.4, 25.12, 26.2, 26.12

Replacements for Chapter 5:
1.  Prove  Let A and B be two sets.  If there exist one-to-one functions f:  A -> B and g:  B -> A, then there existsa function h:  A -> B that is a bijection.
2.  Describe a bijection from the closed interval [0, 1] onto the half-closed interval [0, 1).


Assignment for Chapter 7:  34.9, (35.10), 35.13, (36.3), 36.14 (valued as 5 questions), supplemental E-primes.

Replacements for Chapter 7:
1.  Compute d = gcd(3913,  23177) by hand.  Then find integers x, y so that 3913x + 23177y = d.
2.  Prove:  Let p be a prime and a be an integer relatively prime to p, then a^(p-1) = 1 mod p.
3.  Prove:  Let n be any integer, then 15 | 11n^8 + 4n^4.


Intended Learning Outcomes (General)
    Upon successful completion of Math 239 a student will be able to
•    Use both the propositional and predicate calculus of logic
•    Perform set operations on finite and infinite collections of sets
•    Determine attributes of functions and relations
•    Determine countability and non-countability of infinite sets
•    Produce rigorous proofs in various styles (including induction) and in a variety of mathematical settings
•    To use the definitions and known results of a mathematical topic under study to understand and formulate propositions about that topic, and to prove their validity through rigorous argumentation.

Intended Learning Outcomes (Articulated--These are specific skills through which the general learning outcomes are achieved.)
    Upon successful completion of Math 239, a student will be able to:
•    Recognize logical propositions and translate them into symbolic form;
•    Manipulate symbolic propositions according to the first order logical calculus;
•    Recognize and produce valid symbolic arguments;
•    Apply and interpret universal and existential quantifiers;
•    Translate mathematical assertions into predicate notation;
•    Recognize and use standard formats of proof—direct, contrapositive, contradiction;
•    Perceive the relation of set operations and relations to logical operations;
•    Use arbitrary collections of sets and indexing;
•    Produce proofs of set identities symbolically and verbally;
•    Construct proofs by induction and understand the context and appropriateness of this method of proof;
•    Recognize well-defined functions;
•    Establish properties of functions such as injectivity, surjectivity, and bijectivity;
•     Find pre-images and direct images of sets;
•    Recognize the concepts of countability and uncountability;
•    Establish whether a given set is countable or not;
•    Determine properties of a  relation  on set such as reflexivity, symmetry and  transitivity;
•    Determine whether  a relation is an equivalence relation;
•    Produce the equivalence classes of a given equivalence relation
•    Produce rigorous, articulate arguments and proofs in a variety of mathematical settings.