# What topic can I use in an Introduction to Proofs course that would introduce students to a wide variety of proof methods?

What topics are appropriate for an Introduction to Proofs course which is:

1. Aimed at Freshman who have taken integral calculus and nothing else
2. Is designed to introduce them to formal reasoning and writing proofs
3. Includes a unit/chapter on proof techniques (such as contrapositive, cases, etc.)?
• I suspect similar questions have been asked on MSE. (Did you check there?) As a textbook, I would suggest Velleman's "How to prove it." – Benjamin Dickman Apr 9 '14 at 0:57
• I'd like to suggest my own text, as well. In working on it, I've found that it's not so much the set of topics introduced, but rather the order and motivation between each topic that matters much more. If you presume every student entering your course is going to be a highly-devoted math major for the rest of their career, then it really won't matter which topics you choose! It's figuring out how to address the wider audience that matters more. – Brendan W. Sullivan Apr 9 '14 at 4:55
• @BenjaminDickman The only questions I saw were about self-learners looking for books. Math Overflow might have more,but I'm nit sure. – Brian Rushton Apr 9 '14 at 11:27
• Would you like the proofs to be based on axioms and definitions? In some cases (geometry, for instance) the main focus is on argumentation, whereas in others (like analysis or linear algebra) students have not to learn how to (rather) formally proof. Which is your situation? – Anschewski Apr 9 '14 at 15:12
• I have never understood the point of a "proofs" course. Every course beyond a certain level should be a "proofs" course! I would recommend using Axler's linear algebra done right, and just teaching them linear algebra. Plenty of proofs, and very useful content... – Steven Gubkin Apr 9 '14 at 22:08

I would say that one of the main things to make sure is that the material covered satisfies two things:

• The material itself (i.e. those statements they end up proving as part of practicing proofs) will be useful for them later.
• There will be plenty of statements that are not quite obvious, but which are easy to prove by applying the correct technique together with the definitions.

The reason for the first is that this makes it much easier to justify spending a course learning this stuff, and therefore the students will hopefully not think it is a waste of time.

The reason for the second is that many students will get desillutioned if all they are able to prove are statements that are completely obvious, and at the same time, proving something which is "obvious" can in fact be incredibly hard unless you are already very experienced (the students will often end up very confused about which facts they are allowed to use and which ones not).
That the statements should not be too hard to prove when using the right technique and using the definitions seems obvious, as the students will otherwise be stuck not being able to think of the correct "trick", and will end up not getting the proper feeling of what it takes to prove something.

The above then of course begs the question: "Which topics satisfy this", to which my best reply will be from personal experience, having taken a course with these topics myself.

In that course, the curriculum was:

• Naive logic, so everyone knew the precise meaning of the various connectives and what it took to prove a statement involving them.
• Naive set theory to get all the notation in that context settled.
• Relations, especially orderings, equivalence relations and functions.
• Induction and recursion.
• Construction of the reals using Cauchy sequences.

The first two topics are very important to get everyone on the same page when it comes to the notation used, and introducing the various proof techniques fits in well while introducing this notation (since it is related to the rules for how one can manipulate the connectives).

Induction is of course vitally important for all mathematicians to know, and getting introduced to it more formally can hopefully make the students more aware of precisely why and how it works.

Relations, especially the special types covered, are of course something everyone will end up using a lot, and so getting a formal introduction is nice, especially as this is a topic that allows for a huge amount of not quite obvious but not really hard exercises (such as equivalent definitions of being injective or surjective, equivalence relations corresponding to partitions and so on). This topic also allows for a lot of examples, many of which the students will have seen without the formality.

The final topic, construction of the reals, is a little bit different, in that many of the proofs involved will be a lot harder.
But it does introduce some quite nice things to the students, since the construction of something as the set of equivalence classes of something else is done a lot in mathematics (in some sense one might call it the way mathematicians "patch" sets to obtain missing objects, such as in this case obtaining the limits of sequences that should converge but do not, by declaring the sequence itself to represent its limit).
At the same time, this topic will have the students do several epsilon-delta proofs, which is something most students at this level will still need to practice.

The course in question used the book Chapter Zero by Carol Schumacher, which I heartily recommend.

I find that basic inequality proofs are very well recieved.

For instance, given that $x^2 \geq 0$ for $x \in \mathbb R$, prove that $a^2 + b^2 \geq 2ab$ for all $a,b \in \mathbb R$. Bonus points for finding all sets of $a,b$ that satisfy the equality. This is very basic, and requires only some fundamental algebra to sort out.

And from there, there's a wide variety of equalities to prove, that are both important to know, and interesting to discover.

• You surely mean "given that $x^2 >0$ for $x \in \mathbb{R}$,[...]"! – kan Apr 9 '14 at 10:45
• I've found that some students react unenthusiastically to these kinds of proofs. "Why would I care about this inequality?", they think. I'm not denying their efficacy in utilizing different proof methods (they require quantification, implication, contradiction, sometimes induction), but I would really only use these for an audience of already-mathematically-inclined-or-at-least-interested students. – Brendan W. Sullivan Apr 9 '14 at 17:50
• @kan - I surely do! Thanks :) – Alec Apr 10 '14 at 7:04
• @brendansullivan07 - Well, depending on what you mean by "some students", I'd say you're getting your hopes up. Some students will always have a hard time understanding or motivating themselves to learn mathematical concepts. I don't see why these proofs should be reserved for already-mathematically-inclined-or-at-least-interested students. That would mean you're withholding subject matter because you don't feel your students are qualified? Not to mention, OP mentions that his class has conquered integral calculus. I'd say that's a sign of maturity for simple proofs. – Alec Apr 10 '14 at 7:07
• @aleksander Alas, I've found that "taken integral calc" \neq "conquered integral calc". And it's not that I'm withholding something because students aren't qualified. I'm just trying to find alternative inroads to their particular enthusiasms. Thereafter, we can do some inequalities. – Brendan W. Sullivan Apr 10 '14 at 14:15

Each problem is different, I think it is best to illustrate proof techniques with a variety of problems. The problems themselves should be simple, easy to understand, perhaps even well known to the audience. I emphasize writing proofs in a schematic way: announce what strategy will be used, and write down the steps, explaining each one. I like Hammack's The book of proof as a guide.

A full course on this is probably nonsense, I'm a firm believer in that you learn stuff only if you use it in real settings, by applying it. Give a short overview at the beginning of the class, use the schemas introduced consistently, and make frequent references.

Some combinatorics: For example the identity $\binom{n}{r} = \binom{n-1 }{r} + \binom{n-1}{r-1}$ can be proven using the formula involving factorials. It can also be proved using combinatorial interpretation. Similarly Vandermonde's identity can be presented in two ways.

• That are examples of what is called combinatorial proofs. – vonbrand Jan 8 '16 at 15:03