We started by highlighting one of the steps from the previous lecture: if f(x) tends to a limit as x tends to a, then f is bounded in a neighbourhood of a. We also restated the part of a previous theorem: if f(x) tends to a limit as x tends to a, and g(x) tends to a nonzero limit as x tends to a, and g(x) does not equal zero in some neighbourhood of a, then f(x) / g(x) tends to (lim f) / (lim g) as x tends to a.

We next turned to the squeeze theorem: if f, g, and h are three functions such that f(x) and h(x) tend to the same limit as x tends to a, and such that f(x) ≤ g(x) ≤ h(x) for all x in some neighbourhood of a, then the limit of g(x) as x tends a exists, and equals the limit of f(x). We first proved a special case of this: if 0 ≤ G(x) ≤ H(x) in some neighbourhood of a, and if H(x) tends to 0 as x tends to a, then G(x) tends to 0 as x tends to a. (The proof of this is not hard -- just follow the definition.) Surprisingly, applying this theorem to the choices G = g-f and H = h-f immediately yields the general version of the squeeze theorem.

We then turned to two other types of limits. First,
we considered the limit of f(x) as x tends "to infinity".
We say f(x) tends to L as x tends to infinity iff for any
ε > 0 there exists some number x_{0} such
that |f(x) - L| < ε for all x ≥ x_{0}.
Another way to think about this: f(x) is very close to L
whenever x is "sufficiently close to infinity".

Second, we looked at left-handed and right-handed limits. We say f(x) approaches L as x tends to a from the left iff for any ε > 0, there exists a δ > 0 such that |f(x) - L| < ε for all x ∈ (a-δ, a). Right-handed limits are the same, except the inequality holds for all x ∈ (a, a+δ).

Finally, we applied the squeeze theorem to prove that sin(x) / x tends to 1 as x tends to 0. (Note that this is ONLY true if x is in radians!) To do this, we considered the unit circle and various triangle sitting inside of it. An easy argument shows comparing the length of a segment to the length of part of the circle shows that sin(x) ≤ x. Constructing a perpendicular to the exterior of the circle, we used similar triangles to prove that the length of this new segment is tan(x). Comparing the area of a certain triangle to the area of the sector of the circle sitting inside the triangle, we proved that x ≤ tan(x). The final step: squeeze theorem FTW!

We spent most of the lecture proving that the limit of
a product is the product of the limits. Here, I will only
sketch the proof, omitting the details. To make it readable,
define L_{f} to be the limit (as x approaches a) of
f(x), and L_{g} to be the limit (as x approaches a)
of g(x). We wish to show that when x is close to (but not
equal to) a, f(x)g(x) is close to L_{f} L_{g}.
We used our ideas from last time to write

Now, |f - L_{f}| is small in a neighbourhood
of a, by definition of L_{f}. Also, g is bounded
in a neighbourhood of a, since the limit of g(x) exists
as x approaches a. Thus, the quantity g + L_{g}
is bounded in a neighbourhood of a. Combining these, we
see that the first term on the RHS of (*) is small in a
neighbourhood of a. A similar argument shows that the
second term is also small. Putting this together, we
conclude that the LHS is small in a neighbourhood of a,
which concludes the proof.

We finished lecture by stating the squeeze theorem, and giving a couple of simple applications.

We started by discussing what it means for a limit to not exist. As an example, we proved (by contradiction) that the function f(x) defined to be 0 when x is irrational and 1 when x is rational, does not tend to a limit as x tends to 3. We then stated a theorem that the limit of a sum of two functions is the sum of the limits of the functions, the limit of the product is the product of the limits, etc. We proved the first statement, and made some headway on proving the second.

We began with a practice problem: prove that x sin(1/x)
tends to 0 as x tends to 0. Note that the limit exists,
even though the function isn't defined at 0! Next, we
considered
a more difficult example: we proved that the function
(x+1)/x^{2} tends to 3/4 as x tends to 2. This,
and ensuing discussion, took us the rest of the lecture.

We started by setting up some alternative notations for
limits. In particular, we used the phrase `f(x) tends to L
as x tends to a', which indicates something fundamental
about limits: they don't care about the value of f(x)
*at* x = a. The only thing the limit reflects is the
behaviour of f(x) for values of x *near* a. In other
words, informally, we say L is the limit of f(x) as x
tends to a iff for all x close to a (aside from x = a itself),
f(x) is close to L.

This is, of course, unsatisfactory as a definition: what
does `close' mean? To get intuition for this, we considered
the function h(x) = 3x^{2} + 1. What is the limit of
h(x) as x tends to 2? The answer is clearly 13. But how do you
know? We checked that when x is within 1/10 of 2, then h(x) is
within 1.23 of 13. Actually, this isn't very convincing evidence
that h(x) is close to 13 when x is close to 2. We realized that
the natural question is the reverse: can we show that for all x
close to 2, h(x) is within 1/100 of 13? Sean showed that the
answer is yes: if x is within 1/1230 of 2, then h(x) is within
1/100 of 13. We then asked the more general question: what if
rather than asking for h(x) to be within 1/100, we want it to
be within ε of 13, where ε is some tiny positive
number. Is this true for all x close to 2?
After some work, and a trick with taking a minimum, we figured
out how to do this.

All this led us to give a formal definition: we say that L is the limit of f(x) as x tends to a iff for every ε > 0, there exists a δ > 0 such that |f(x) - L| < ε whenever 0 < |x - a| < δ. (Note that the condition that 0 < |x - a| is just a fancy way of saying that x does not equal a.) Finally, we proved that the function 1/x tends to 1/3 as x tends to 3.

We began the lecture with a more formal description of one-to-one correspondences. Recall that informally, given two sets A and B, we can compare their sizes by thinking of A as a collection of people, B as a collection of seats (in a theatre, say), and then trying to see if there's a way to seat everyone so that every seat is filled (and no one is left waiting for a seat). If there is such a seating arrangement, we said that A and B are in one-to-one correspondence (alternatively, A and B have the same size).

So how do we formalize this concept? The idea was to use the language of functions. We'll say that f is a one-to-one correspondence between two sets A and B if

(i) f : A → B is a function; and

(ii) for every b in B, there exists a unique a in A such that f(a) = b.

In terms of our informal notions, (i) says that everyone
is assigned a seat, and (ii) says that every seat is assigned
to precisely one person. We've called such an f a one-to-one
correspondence, but there's another fancy name for it: any f
satisfying (i) and (ii) is called a *bijection* from
A to B. Finally, we say that A and B have the same size iff
there exists a bijection from A to B.

When proving that a function f satisfies (ii), it is often useful to check this in two stages:

(ii)a. for every b in B, there exists an a in A such that f(a) = b; and

(ii)b. if f(a

In our informal picture, (ii)a. means that every seat is
assigned to somebody; (ii)b. means that two different people
are never assigned to the same seat. These two conditions also
have fancy names: any function f : A → B satisfying (ii)a.
is called a *surjection*; if instead it satisfies (ii)b.,
f is called an *injection*. Thus, a function f : A → B
is a bijection from A to B iff f is both a surjection and an
injection.

I next described an algorithmic way to think about
countable sets. Recall that a set A is countably infinite
iff A has the same size as ℕ. What this means is that
there exists an algorithm for going through the elements of
A such that, for any element you pick, the algorithm will get
to your element after a *finite* number of steps. Note
the the algorithm comes before your choice of element, i.e.
we're not allowed to adjust the algorithm depending on which
element you've picked. Thus a set A is uncountable means that,
no matter which algorithm you design, there will be some elements
of A which the algorithm will *never get to*. This is
quite a strong condition but, as we have seen, it does occasionally
arise.

We concluded the lecture by starting to discuss limits.
Informally, we say `a function f(x) approaches a limit L
as x tends to a' iff whenever x is really close to a,
f(x) is really close to L. We did an example with the linear
function f(x) = 3x+1; first, we saw that when x is close to 2,
f(x) is close to 7, and then we figured out how close x would
have to be to 2 in order for f(x) to be at most 1/100 away from
7. The answer was conjectured by Zim, and isn't entirely obvious;
however, once you have a guess, *verifying* that it's right
is very easy. This will be a recurring theme, as we'll see on
Thursday.

Today we continued our discussion of functions. We started by discussing why the informal definition of function isn't great. The main problem is that it is secretly circular: a function is a rule, which is what? An association... which is a function...

So, instead, we have a different definition for what a function is: it's a set of ordered pairs, satisfying the nice condition that whenever (a,b) and (a,c) belong to the function, then b and c must be equal. Really, this definition just formalizes what the graph of a function is; except that rather than drawing the graph, we list all the points and call the list, the function. We then discussed various examples and non-examples. We concluded the lecture by discussing composition of functions, and noting that functions (with respect to composition) and numbers (with respect to addition) have suspiciously similar properties. This connection is explored more deeply in MATC01 (group theory).

Today we discussed functions. We gave an informal definition: a function f from a set A to another set B is a rule which associates to every element of A an element of B. We introduced some notation for this, and considered many examples (including a the function we called G, which associates to any real number x the number of 7's appearing in the decimal expansion of x, if this is finite; if x has infinitely many 7's, then we defined G(x) to be 2. This is a function, even though nobody knows the value of G(π). We also defined (with some difficulty!) the sine function.

We started the lecture by clarifying the main step in the proof of the nested intervals theorem: we observed that for any natural numbers k and n, we have

Next, we continued discussing sizes of sets. We showed that the union of two countable sets is countable. We also proved that the set of positive rational numbers is countable. Then, somewhat unexpectedly, we proved that the set [0,1] is uncountable!

We concluded the lecture with a discussion of what it means for a function to be continuous. We concluded that it makes sense to discuss continuity at a single point, and identified what this might mean in terms of limits. Next week we will begin a more careful investigation of this important topic.

We started by proving the theorem on nested (closed!) intervals. The first part of this proof caused some confusion; make sure you sort out what's going on in the proof! Next, we began discussing how to compare different infinite sets. Inspired by the movie theatre example, we say that two sets have the same size of there exists a one to one correspondence between them. We showed that ℕ, 2ℕ, and ℤ all have the same size, and finished the lecture by considering whether ℕ and ℚ have the same size.

We reviewed the concepts of upper bound and supremum, and corrected an error (caught by Molly) in our proof that sup (0,1) = 1. Next, we discussed lower bounds and infimum, and briefly sketched why the completeness property implies that inf A exists for any nonempty set A which is bounded below.

We then proved that ℚ is dense in ℝ -- i.e. that between any two (distinct) real numbers there is a rational number. To do this, we began with two positive numbers x and y, with x < y. We wish to show that the interval (x,y) contains a rational number. First, by the Archimedean property, we know that we can stretch the interval to make it longer than a unit interval (i.e. we can find a natural number n s.t. (nx,ny) has length bigger than 1). I next claimed that any interval of length > 1 must contain an integer; we proved this by using the well ordering of ℕ. Thus, we were able to find an integer m with nx < m < ny. This concluded the proof.

After discussing intervals, we proved (up to some
details) the nested interval theorem: that if we have a
sequence of nested closed, nonempty intervals
[a_{n},b_{n}], then there exists a real
number which lives in all of these intervals simultaneously.
Recall that saying the intervals are nested means that

The idea of the proof is simple. Let A = {a_{n}}.
The first observation is that A is bounded above (by any one
of the
b_{n}'s). Thus, by completeness, sup A exists. Since
sup A is an upper bound of A, we see that

for every n. On the other hand,
since b_{n} is an upper bound of A for every n, we
see that

for every n (since sup A is the smallest upper bound of A). This concluded the proof. Finally we discussed why it's necessary to assume that all the intervals are closed, by considering the sequence of nested open intervals {(0,1/n) : n∈ℕ}.

We started by recalling the Completeness Property, and restating it
in the following (equivalent) form. Given a set A⊆ℝ, define
U_{A} to be the set of all upper bounds of A. Moreover, set
U_{∅} := ∅.

** The Completeness Property of ℝ:**
Given A⊆ℝ. If U

Note the similarity to the Well-Ordering Property of ℕ.

We next reviewed the proof of the existence of √2 from last lecture. We went over the formal definition of upper bound and supremum of a set, and considered two examples: sup [0,1] and sup (0,1). In both examples, the supremum was equal to 1, but proving this was more difficult in the second case than in the first. The general strategy to proving that the supremum is what you think it should be proceeds in two steps: first, prove that your guess is an upper bound; next, prove that every other upper bound is bigger. One important point from our examples: sup A might live in A, or it might not belong to A!

We concluded the lecture by proving the Archimedean Property. Although the statement is trivial, the proof is subtle -- make sure you understand it!

We started by discussing the definition of ℕ (1∈ℕ, and whenever n∈ℕ, n+1∈ℕ). We defined 2 := 1+1, 3 := 2+1, etc. We next briefly reviewed the triangle inequality and some corollaries.

Next, we attempted to prove that √2 exists. In other words, we
tried to prove that there exists some real number α > 0 such that
α^{2} = 2. Here's a sketch of our attempt. Let

and let B denote the set of all upper bounds of A. In other words,

Let α denote the least element of B. (In words: α is the
*least upper bound* of A; it is an upper bound of A, and is smaller
than every other upper bound of A. This is also called the *supremum*
of A, or sup A for short. I didn't use this word in lecture, but it's in the book.)

In any event, we have produced some positive real number α. I
claim that α^{2} = 2. To prove this, we first showed that
if α^{2} < 2, then there exists another number which is a little
larger than α, but whose square is still less than 2; this contradicts
α's being an upper bound of A. Next, we showed that if
α^{2} > 2, then there exists another number which is a little
smaller than α, but whose square is still larger than 2; this contradicts
α's being the *least* upper bound of A. By trichotomy, we conclude
that α^{2} must equal 2. So, the square root of 2 exists!

There's only one problem with this proof: how do we know that the set
A has a supremum? Actually, this is equivalent to the existence of √2: a little
thought shows that sup A exists iff √2 does. Thus, we have not dealing
with a problem in the proof, but rather with a philosophical dilemma: either
we live in a universe in which √2 does not exist, or we live in a universe
in which sets like A have a supremum. This inspired us to make one final
assumption about ℝ: the completeness property. This asserts that if a
nonempty subset
A⊂ℝ *has* an upper bound, then sup A exists. Note that the supremum
may or may not belong to A! We will discuss this further next week.

We started by answering a question of Scott: we proved that
if 0 < a < 1, then 0 < a^{2} < a. I also mentioned that
you cannot assume, without proving it yourself, that -1*a = -a.
From the properties, all you know about -a is that when you add
a to it, you get 0.

Next, we discussed whether there are any sets other than ℝ
which satisfy all the algebraic and order properties. One suggestion
(due to Slavik) came particularly close: ℤ. This satisfies all
the properties aside from one - M4 (multiplicative inverses). Inspired
by this near-success, we realized that ℚ satisfies
all of our properties. Since we'd earlier proved that √2 ∉
ℚ, we see that the *existence* of √2 cannot be proved from
the algebraic and order properties alone. This might sound crazy at first
-- how could √2 not exist? The point is that the symbol √2
is telling us what the number should *do* rather than what it *is*.
Essentially, when we write √2, we're saying: wouldn't it be nice if
there were a number whose square is 2? In the same spirit, we could talk
about √ORANGE,
the number whose square is ORANGE. As you can see,
the existence of such a number -- just as of √2 -- is questionable.
Nonetheless, we will be able to prove the existence of √2, once we
introduce one more property. In fact, this will be the final property we
need to completely define ℝ. We will discuss this property next
lecture.

For now, we discussed absolute value. After stating the definition, we talked about the triangle inequality and some corollaries.

Given a statement of the form A ⇒ B, the *converse* is the statement
B ⇒ A; this might be true or false. If both the implication and its converse
hold, then we write A ⇔ B. Or in words: A if and only if B. Or, in abbreviated
words: A iff B. For example: Well-Ordering of ℕ is true iff Induction is. Another
example: ab = 0 iff (a = 0 or b = 0).

The *contrapositive* of [A ⇒ B] is [(not B) ⇒ (not A)]. An implication and
its contrapositive are equivalent -- either both implications are true, or both are false.
Sometimes it's more convenient to prove the contrapositive of a statement rather than the
statement itself; the example we looked at was: if α is irrational, then √α
is as well.

We next discussed the 9 properties A1-A4, M1-M4, D; these don't define the real numbers,
because there are other sets (with weird addition and multiplication) which satisfy all
nine properties! We explored an example in class: the set S={0,1}, where

0 + 0 = 0,
0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0, 0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.

Even though I'm using the labels 0 and 1 for the elements
of S, it's better to think of them as abstract objects, rather than as numbers.

We then moved onto the order properties of the real numbers; there exists a subset *P*
of the reals which satisfies three nice properties (0 ∉ *P*, a ∉ *P* iff
-a ∈ *P*; a+b and ab are both in *P* whenever a,b ∈ *P*). We then
defined the symbols >, ≥, <, and ≤ (e.g. a > b iff a - b is in *P*). We noted that
given any two reals, exactly one of a = b, a > b, a < b holds; this property is called trichotomy.
I sketched a proof that if a > b, then a+c > b+c for any real number c.

Finally, we proved (up to a lemma) that if a non-negative real number is smaller than every positive real number, then it must be 0. This had a nice implication: 0.99999... = 1.

We began by discussing the difference between figuring out *how* to
prove something, and actually *writing* the proof. To figure out how to
prove a claim, it's often useful to reverse engineer, use intuition, and
make logical leaps. But when you write the proof, it should be precise, logical,
and easy to follow step by step. As examples, we (re)proved that 0*a = 0 for all
real numbers a, and also proved that if ab=0 then one of a or b must be 0.
(There were also two extra problems: prove that a+b+c+d is unambiguous for all
real a,b,c,d; and prove that
a_{1}+a_{2}+a_{3}+...+a_{n}
is unambiguous.

Next we discussed the dangers of proving things by starting with a statement and manipulating it (5=3 => 0=0). This led us to a discussion of: what is a mathematical statement? (Examples: "5+3=7" is a statement, "Leo's first language was English" is a statement, "MATA31 is awesome" is not a statement.) Given two statements A and B, one can form a new statement: A => B. We saw through examples (some more plausible than others) that the statement A => B is always true UNLESS A is true and B is false.

Click here for the lecture summary.

Click here for midterm solutions.

Today we gave two important applications of strong induction. The first was to prove that any natural number can be written in binary (i.e. as the sum of distinct powers of 2). The second application was to show that any natural number larger than 1 can be decomposed into a product of primes. In both cases, SI made the proofs rather simple. Unlike the Fibonacci example from last lecture, we only needed to check one base case for these examples. (You should makes sure you understand why this suffices here, but not in the Fibonacci example.)

We finished up lecture with the following puzzle. Suppose there are 99 boxes, each
containing some number of apples and bananas. Prove that it's possible to pick 50
boxes so that these 50 contain at least half of the total number of apples, *and
also* contain at least half the total number of bananas.

We continued discussing induction. We proved that any
2^{n} x 2^{n} chessboard can be tiled by L-shaped pieces in such
a way such that the only square left open is one of the middle four. Actually, this
was a corollary of a stronger theorem: that for any such board, and for any
given square on the board, we can tile the entire board by L-pieces, with only that
one square left untiled.

Next we proved that
1 + 1/2^{2} + 1/3^{2} + ... + 1/n^{2} < 2
for all natural numbers n. Again, this was a corollary of a stronger theorem: that
the sum is actually bounded by 2 - 1/n.

I then showed a ridiculous induction `proof' that n! < 0 for all natural numbers n. The problem was that I forgot to check whether 1 satisfies this.

The next topic was a flexible notion of induction, where one can start at 5
(say) rather
than at 1. We followed this up with strong induction (SI), and used SI to prove that
the n-th Fibonacci number is less than 2^{n}. A key step in the proof was that
we had to check that both 1 and 2 satisfy this hypothesis. Make sure you understand
why we need to check two cases, rather than just one as in all the previous
problems!

We reviewed induction. We still haven't proved the theorem (coming next lecture!),
but we gave two more applications. First, we proved the curious formula

Next we discussed a totally different question. Suppose you have a
2^{n} x 2^{n} chessboard, with a king in one of the four middle
squares. Is it possible to tile the rest of the board with L-shaped pieces? (An
L-shaped piece consists of three squares in the shape of an L.) We will return to
this question, as well as other applications and a proof of induction, during the
next lecture.

Recall that we had two proofs that √2 is irrational. In the first,
we defined a set

In the second proof, we worked with a set

Today we quickly proved that A=B. This allows us to restate our two proofs in a way which makes them look very similar:

__Proof 1:__
If n∈A then __Proof 2:__
If n∈A then n(√2 - 1)∈A. Thus A has no least element,
and must therefore be empty. QED

**Well-Ordering Property of ℕ**:
Every nonempty subset of ℕ has a least element.

We noted that this property can fail in other contexts; for example, the set
ℚ_{≥0} of non-negative rationals is *not* well-ordered.

Next, we wrote down one of the main theorems of the semester: induction. We didn't prove it (yet), but instead, used it to prove the following:

- 1+2+3+...+n = n(n+1)/2
- n < 4
^{n}.

Today we spent most of the lecture discussing various notation and clearing up some confusion. We talked about the definition of odd and even numbers, and proved that an odd times an odd gives an odd number. Here's the notation which came up during our discussion:

- ∀ means
*for all* - ∃ means
*there exists* - ∅ means the empty set, the set which doesn't contain anything
- A ⊆ B means A is a
*subset*of B (everything which lives in A also lives in B)

We also reconsidered the proof from last time that root 2 is irrational. Precisely, we rewrote the first proof in a way which made it look like the second proof (start with a set consisting of natural numbers, if it's empty we win, otherwise show that it has no smallest element -- which is impossible). We will see (on Thursday) that this point of view leads to some fundamental questions and ideas.

We began by discussing sets and set notation. In particular, a set doesn't care about the order in which its elements appear, e.g. {1,3,5} = {3,1,5}. Also, a set doesn't see repeated elements, e.g. {1,3,3} = {1,3}. We also discussed the notion of equality. If two sets are equal, that means they're not actually two different sets; they're the same set, which we've written down twice. Another (useful) way to describe this is that two sets A and B are equal if they have precisely all the same elements: all the elements of A also live in B, and vice versa.

We next discussed some examples of sets which will come up a lot in this
course. The *natural numbers*, denoted ℕ, is the set

Next we have the

Finally, we have the set ℚ of

This is annoyingly long, so (after several steps) we wrote it very briefly as

Some of you suggested other ways to represent the set ℚ. We proved that

You should make sure you understand why we need to be prove this; why can't we just

Next we discussed circles, the definition of π (it's **not**
3.1415926,
nor is it 22/7), and the discovery that the square-root of 2 is irrational.
The entire second half of the lecture was devoted to giving two proofs of this
fundamental fact; click below to read them.

We went over the syllabus. After intense negotiations, we decided that
although computers, cameras, e-readers, and phones are not allowed to be used
in the lecture hall, voice recorders and e-dictionaries are permitted.

We next discussed the following problem. Given a circle, draw N
points on the circumference, and connect each pair of points with a
straight line. If the N points are random, then we can (and will) assume
that no three lines intersect anywhere in the interior of the circle. (In other
words, every point formed inside the circle is the intersection of exactly two
lines.) Into how
many regions do these lines split the circle? For N = 1, 2, 3, 4, 5, the
answers were (respectively) 1, 2, 4, 8, 16 regions. But for N = 6, the answer
was 31. What's going on?! I left this as a question to ponder for next lecture.
*Do not look this up in books / the internet. Where's the fun in
that?*

Note: you do **not** need to bring your
textbook to lectures -- the whole point of the lecture is to cover
the material in a different way than is done in the book! However,
you may find it helpful to bring your textbook to tutorials.