courses:math_reasoning:spring_2014:home

- Full Book (through section 4.5, updated 05 May 2014)

We had a midterm exam on Wed, 12 Mar, covering chapter 1.

We had a guest lecturer, Banu, introduce functions, one-to-one, onto, and bijections. We talked briefly about questions over the notes. In addition to the problems we have been preparing, please prepare problems 4.74, 4.80, 4.85, 4.86, 4.87, 4.91, 4.95, 4.96, 4.97, and 4.99. Corrections over 2.94 and 2.111 are due Wednesday.

We've talked a lot about proof techniques. Here is one proof technique that would probably not be accepted in a math journal:

We worked a bit more on the one hole to fill with the proof 3.2, and then saw presentations of several more problems from section 3.1.

We didn't start presenting material from chapter 4, but we did very briefly talk about reflexive, transitive, and symmetric relations.

For Monday, type up and submit a proof of Theorem 3.9. Also, we will be calling for presentations for 4.31, 4.33, 4.34, 4.39, 4.41, 4.42, 4.47, and 4.56.

Today we spent a while on some of the tricky proofs from section 3.1, like 3.2, 3.3, and 3.5. We saw some great work, and emphasized also some important points:

- make sure you don't use theorem A to prove theorem B, and then use theorem B to prove theorem A. Instead, do what Jay mentioned: make sure you prove one of the theorems independently.
- Be careful that your arguments don't allow false statements to be proven true. In David's example, he's right that you need to use more than just those lines about each prime being in the other list to show the two lists of primes are the same. I think David's idea about getting rid of each prime as you use it is a good direction to go to resolve this.
- Be careful when dealing with infinite processes. You can do it (and Courtney had a great process for how an infinite argument showed $\sqrt{2}$ was irrational), but infinity plays funny games with our intuition, so we have to be careful in how we deal with it. If you can do the same proof without appealing to an infinite process, it may be more understandable.

For next time, please continue working on problems from 3.1 or move on to section 4.1. We have a few problems from 3.1 that some of you will still put up. In section 4.1, we will call for presentations for problems 4.9, 4.10, 4.13, 4.21, 4.23, and 4.26.

For next Monday, please tex up your proof for Theorem 3.3. Feel free to come in and talk with me about it, check it with me, etc. I'm happy to give feedback on it before you turn it in.

We again discussed a lot of the proofs from 2.86-2.100. We'll spend one more day on this unit. For Wednesday, the problems we still have to do are: 2.86, 2.90, 2.94, 2.95, 2.96, 2.100, 2.101, 2.102. Some of these problems have a person who gets first shot at it, but everyone should do each of them.

I've also posted the next unit, section 2.5, on induction.

Today we talked about 2.79-2.88. We had a few more proofs up that we didn't have time to get to today. We talked for a while about proving most of the theorems we talked about. These problems are hard, probably the hardest we'll see this semester. It's tricky partly because there are so many quantifiers in each definition. Those of you that have been putting in the time have been making great progress. This is the kind of complicated thinking and reasoning that makes you as a mathematician extremely valuable.

For Monday, proofs for 2.79 and 2.87 are due at the beginning of class. These must be typed in LaTeX using the template at the bottom of this page (which is different than the template you've been using, so make sure to copy this new one). You are welcome to use the Sage Cloud; the icon in the upper right of the preview window will download the pdf file. Please note that I'm expecting printed copies turned in this time, not email or files on the Sage Cloud.

Problems that still have no claim are 2.86, 2.88, 2.90, 2.94, 2.96, 2.99, 2.100, 2.101, 2.102. If you haven't presented this week, you should especially make sure you are presenting one of these on Monday. If you've been missing some class periods, you should *especially* make sure you're coming and presenting.

The study group is meeting again Thursday around 7 or 8 at the library, around the cafe, again—email Chris Dorff for details.

On a final note, I think it's really valuable to see and learn how to handle failure. Ed Burger, a widely-respected math teacher, wrote about the importance of teaching failure. I highly recommend reading that article (and I'm open to adjusting the grade schema like he mentions if the class wants to).

Today we talked about 2.77-2.80, and then about the definition of limit points. We also talked about Cantor's diagonal argument for showing the real numbers are uncountable. It was some hard material we covered today, and you all did great. We'll be hitting it again next time, so do your best to prepare. Please go over your proofs starting with 2.78 to make sure they work well, and push ahead as far as you can, with a goal of going through 2.99.

Chris Dorff is organizing a study group, meeting at the library near the cafe at 8pm Tuesday night.

This math class may well be the most applicable math class you will ever have. Some lessons for life we learned today include:

- If you have an infinite number of things to do, don't try to do them all at once. You'll go crazy! Narrow it down to doing something specific to one thing.

- Be careful about terms and definitions (in class, we emphasized that an open set and an open interval don't mean the same thing).

We finished section 2.2 and also reviewed a corrected proof or two from 2.1. We also talked about how big the rational numbers are (they are countably infinite), and discovered how to list them out.

There are several things for next time:

- We are making the last half of the midterm a take-home exam. I've graded problems 1-4. Problems 5-9 are due on Monday at the start of class. You may not use any resources in working on the problems on the exam—just as if you were taking the exam in class. Just you and your plain pencil/pen. You may not work together or discuss the problems. As a hint, you might try approaching the problem involving $a^2+b^2=c^2$ using even vs. odd arguments.
- I posted the next two sections. Section 2.3 starts with a lot of explanation and asks you to do some straightforward exercises, followed by two proofs similar to what we have done. Please prepare the problems in section 2.3 for discussion on Monday (i.e., problems 2.50-2.60).
- Please continue thinking about listing out all of the elements in $P(\mathbb{N})$. Is it possible? Note that from our discussion in class, your reasoning for why it is not possible should not apply to the rational numbers, since it is possible to list them out.

We talked a bit about the history of set theory. Here is a good article about its development and the discovery of the paradoxes that we've talked about.

We discussed 1.65-1.75, and had a great discussion about when it is equivalent to switch the order of various quantifiers.

For Wednesday, do 1.76-1.88.

We also talked about the Banach-Tarski paradox. It seems like it's like creating chocolate out of nothing, but the paradox is more fundamental than that. The paradox deals with the fundamental question, “what is the size of a set?” You might enjoy reading a non-technical explanation of the paradox.

We discussed 1.56-1.64, and had great proofs to show for it. I loved how we collectively came up with some really nice proofs by contradiction—good job everyone! We spent some time talking about quantifiers a bit more too.

We didn't turn in the problems today, but make sure to typeset your proof of Theorem 1.58 in the Sage Cloud system before class on Monday. Please prepare problems 1.68–1.75 to discuss and turn in on Monday.

We also talked a bit about Paul Erdős and the breaking news of the 13 gigabyte claimed proof of his discrepancy conjecture. For fun and math culture, we talked a bit about the Erdős number (see also the Erdős number project). Here is also a collection of stories and a collection of problems from him.

Much of Erdős' legacy comes from his amazing ability to come up with good problems. As was attributed to him in Some of my favorite problems and results, “Problems have always been an essential part of my mathematical life. A well chosen problem can isolate an essential difficulty in a particular area, serving as a benchmark against which progress in this area can be measured. An innocent looking problem often gives no hint as to its true nature. It might be like a 'marshmallow,' serving as a tasty tidbit supplying a few moments of fleeting enjoyment. Or it might be like an 'acorn,' requiring deep and subtle new insights from which a mighty oak can develop [….] In this note I would like to describe a variety of my problems which I would classify as my favorites. Of course, I can't guarantee that they are all 'acorns' but because many have thwarted the efforts of best mathematicians for many decades (and have often acquired a cash reward for their solutions), it may indicate that new ideas will be needed, which can in turn, lead to more general results, and naturally, to further new problems. In this way, the cycle of life in mathematics continues forever.”

Happy President's day! We talked about negation and had great presentations of 1.46–1.53. I thought Exercise 1.53, where we took the complicated tautology and rewrote it using implications in various ways, was a great exercise. We also covered a few common Latex issues I noticed while grading problems. We talked about proof by contradiction, and how it often comes up when you want to prove that a situation exists, even if we can't show how to construct it (like the Brouwer fixed-point theorem). We finished by introducing quantifiers.

For Wednesday, do 1.56–1.64 (get the updated pdf above, which includes the next section, section 1.4).

We were talking about computer proofs the other day, as well as SAT solvers. Just today, someone announced a proof that relied on a computer using a SAT solver to generate an example. The data is about 13 gigabytes, which is bigger than all of wikipedia. See arxiv or this writeup.

The Brouwer fixed-point theorem implies the swishing water-bottle fact. Francis Su has an interesting writeup of how the Borsuk-Ulam theorem implies the fixed point theorem.

The 3-SAT problem is the NP-complete problem we talked about.

- Here is the TeX source for our problem notes
- I am constantly referencing The Short Math Guide For Latex.
- Here is the TeX source for our problem notes
- detexify will help you find latex symbol names based on just drawing their picture.
- Use Web Equation to convert handwriting to equations
- http://www.macrotex.net/texbooks/ - a nice collection of Tex and Latex resources.

\documentclass[11pt]{article} \usepackage{amssymb,amsmath,amsthm} \usepackage{hyperref} \usepackage[lmargin=1in,rmargin=2.5in]{geometry} \usepackage{setspace} \doublespacing \theoremstyle{definition} \newtheorem*{theorem}{Theorem} \newtheorem*{corollary}{Corollary} \newtheorem*{lemma}{Lemma} \newtheorem*{conjecture}{Conjecture} \newtheorem*{definition}{Definition} \newtheorem*{example}{Example} \title{Math 101, Spring 2014} \author{YOUR NAME} % change to your name \date{ASSIGNMENT DUE DATE} % change to the date \begin{document} \maketitle \begin{theorem}[THEOREM NUMBER] THEOREM STATEMENT \end{theorem} \begin{proof} YOUR PROOF \end{proof} \end{document}

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported