Math 2710-001, Spring 2012
Now that you know the basic Boolean connectives, you can start checking sentences to see if they are equivalent (if they have the same truth values on each line of a truth table). You might want to start by checking "P implies Q" and "not Q implies not P." Remember that the second is called the contrapositive of the first. Then you could go on and compare "Q implies P" to the other two: this is called the converse of "P implies Q" and is not equivalent to it. If you'd like a quick cheat sheet on Boolean connectives (and quantifiers, which we'll get to on Thursday), I've got one here.
|Week ||Sections in text (estimated) ||Quiz/Test ||Administrivia|
|Week 1: Jan. 17-20 || 1.2-1.6
|Week 2: Jan. 23-27 || 2.1, 2.2
|Week 3: Jan. 30 - Feb. 3 || 2.3, 2.5
|| ||Monday: last day to drop without a "W" |
or choose the P/F option
|Week 4: Feb. 6-10 ||2.5, 3.1, 3.3
|Week 5: Feb. 13-17 ||3.4-3.6
|Week 6: Feb. 20-24 ||7.4, 4.1
||Midterm #1 |
|Week 7: Feb. 27 - March 2 ||4.1-4.3
|Week 8: March 5-9 ||5.1, 5.2, sequences and series
|Week 9: March 12-16 || none
|| ||Spring break!|
|Week 10: March 19-23||6.1-6.3
||Midterm #2 |
|Week 11: March 26-30 ||6.4-6.6
|| ||Monday: last day to drop |
or choose to get a letter grade
|Week 12: April 2-6 ||8.1-8.4
|Week 13: April 9-13 ||8.5-8.8
|Week 14: April 16-20 ||9.1-9.3
|Week 15: April 23-27 ||9.3, review
I encourage you to read section 1.1 on your own, though I won't talk about it in class. It introduces some very basic mathematical vocabulary.
A note about "there exists" and uniqueness: I made a point in class of saying that "there exists a book in the UConn library" doesn't imply that there is only one book in the UConn library. On the other hand, it doesn't imply that there is more than one, either. All it means is that there is at least one book. This means that I can say "there exists a postdoc in the math department at UConn" and "there exists a postdoc in the math department at UConn who normally uses two middle initials professionally." The first could be any one of nine people, the last describes someone uniquely.
Please take a look at Proof Methods 1.56-1.59. We'll use these techniques in class, and they will be far more intuitive if you think about why they work in advance. You should also read the proof of Proposition 2.11(iii). We won't be using it as much as the other parts of this proposition in the future, but developing the habit of reading mathematics makes writing it much easier.
I recommend that you go through the proof of the GCD Characterization Theorem carefully. Take this opportunity to think about the relationship between an implication, its converse, and its contrapositive: what are the converse and the contrapositive of the GCD Characterization Theorem? Can you find a counterexample to one of them?
Today was a very algorithmic day. The only way to get used to the Extended Euclidean Algorithm is to do it repeatedly, so pick different pairs of numbers and try it. What happens if you run it on a and b and then on b and a (in the opposite order)?
I also suggested that you read the proof of Prop. 2.27. I'll assume the results in class, but I do expect you to read the proof on your own. Please see me if you have questions about it!
Remember the steps for finding the solutions of an equation ax+by=c:
The main proof I suggested you read is the proof of Theorem 2.53 (this is the first time I've asked you to look at a proof of a result of the form P->(Q OR R)). If you're having a hard time sorting out why the proof in the book works, look at Proof Method 1.56. I also mentioned the results of Theorems 2.57-59 with almost minimal proof, so reading through those proofs might not be a bad idea either...
- Does gcd(a,b) divide c? If not, there are no solutions. If it does, then...
- Find one solution. If the numbers are pleasant, you can do this by observation. If not, use the Extended Euclidean Algorithm to solve ax+by=gcd(a,b) and then use this to find a solution of ax+by=c.
- Apply the formula from class: x = x_0 + (b/d)n and y = y_0 - (a/d)n for all integers n, where x_0, y_0 is the solution you just found and d=gcd(a,b).
I decided not to ask you to expand the book's proof of Prop. 3.12 on the homework assignment. Instead, please just read it. It might also be useful for you to try to find relations on the integers with every possible combination of the three properties we talked about in class.
If you're interested in finding out how the divisibility tests work, I suggest you read Section 3.2.
If you aren't quite comfortable with addition and multiplication of congruence classes, try working out the tables for some larger integers. Z6 would probably be a very good exercise. You could also try to prove that if n is composite, then not every nonzero element in Zn has a multiplicative inverse.
Today we talked about solving linear congruences and found that if x_0 is one solution to ax=c(mod m), then we can write the complete solution as either x=x_0(mod m/d) or x=x_0, x_0+m/d,...,x_0+(d-1)m/d (mod m). Think about why these give you the same solution.
We ended class today with a congruence that looks difficult to solve. What tricks do you know for simplifying congruences to make them easier to solve?
You've taken a test and deserve something amusing. How about this collection of proof techniques? Note that we'll be working on proofs by induction next week. :)
If you'd like to know more about the issues with RSA I talked about in class today, I'd recommend this blog post.
You should read the proofs by induction in the book. Make sure you can identify the base base, the induction case, and the induction hypothesis for each of them. Take a look at Example 4.14: you have to prove an inequality. After you do that, try proving that
1/1^2 + 1/2^2 + 1/3^2 + ... + 1/n^2 <= 2 - 1/n
for all positive integers n. (I didn't do it in class today because it's a problem on a takehome exam for another class...)
I'm not going to cover Section 4.3 in class, but I encourage you to read it! It will teach you some basic combinatorics (ways of counting things), and you'll get some practice with induction as well.
Today we managed to code the rational numbers using the integers by defining each rational number q as the set of all ordered pairs (a,b) such that q=a/b. On Thursday, we'll ask the corresponding question for the real numbers: if we have the integers and the rational numbers, how can we use them to code the real numbers?
Today we talked about the differences between rational numbers and irrational numbers and introduced the idea of transcendental numbers. I also started talking about Cauchy sequences. We'll use these to talk about limits of rational sequences in a couple of weeks. Enjoy your break!
If you need some diversion for your break, here's a video from the show that introduced me to the Fibonacci numbers many, many years ago.
I only talked a little bit about Dedekind cuts. If you'd like to know more, the information on this site is pretty good.
I left you with a challenge at the end of class: find a function from the reals to the reals that is surjective but not injective.
A couple years ago, the New York Times ran a very nice series about mathematical concepts. Here's the last article in the series: it explains some of the proofs we did in class today and provides a nice picture of the Hilbert Hotel.
We know that the cardinality of R is greater than the cardinality of P (and thus of Q). What can you say about the cardinality of the set of irrational numbers? Is it the same as the cardinality of Q? Why or why not?
Today I left you with a puzzle. We have a geometric meaning for addition of complex numbers: we just add the vectors they define. We have a way of assigning a geometrically meaningful real number to any complex number: we take the length of the vector it defines and call it the modulus. We have a geometric meaning for taking the complex conjugate: we flip it over the real axis. What is the geometric meaning for multiplication?
We learned a new proof technique today with de Moivre's Theorem. We had to prove that a formula was true for all integers n. Instead of letting n be an arbitrary integer and then proving the formula, we divided the proof into cases. First, we proved that it was true for all positive n using induction. Then we proved that it was true for all negative n using the fact that it was true for all positive n. Then we checked the case n=0. This might be a trick to keep in mind!
I touched on this in class today, but not explicitly. What is the geometric meaning of finding all the nth roots of a complex number?
I recommend very strongly that you go through the book's proof of the Fundamental Theorem of Algebra and take a look at Example 8.82. The pictures on p. 217 give a nice demonstration of the convergence of a loop to a point that I talked about at the end.
Make sure you understand why the base case of an induction proof based on induction on the degree of a polynomial can be so complicated!
We went over the last new material for the term. Section 9.3 will not be on the final, but the Rational Roots Theorem is so pretty that I wanted to tell you about it. Section 9.2 is fair game, though.
Today was just review: formal logic, Cauchy sequences, cardinality, and a quick discussion about how to get started on a proof. Good luck studying, and I'll see you for the final!