Instructions – please read carefully

• 2 out of 4 problems from this problem bank will appear as-is on the exam

• You may discuss the problems with other students. Furthermore, you can ask the in- structor and TA clarifying questions. If you are really stuck, you can ask the instructor and TA for hints to get you started.  However, do not ask for, or share, either partial or full solutions.

• You will not be permitted any reference material during the exam. I advise against rote memorization: as the saying goes, the easiest way to memorize something is to understand it.

• You can use any result proved in the course text, in class, or on a previous homework question provided you mention that you are using a result.  You do not need to mention the exact name or reference for the result if you forget it – the purpose is to demonstrate that you are aware you are using a non-trivial result in your proof.

1. Fix some set X . In this question we we will show how ⊂ is ‘kind of like’≤ by talking about “upper bounds” and “lower bounds” of collections of subsets of X .

Recall that the powerset P(X) is the set of all subsets of X . C ∈ P(X) means that C ⊂ X .  Furthermore, a subset A ⊂ P(X) has elements of the form B ∈ A, where B ⊂ X . In other words, A is a collection of sets.

(a) Let C ∈ P(X), and let A ⊂ P(X). We say C is an upper bound of A if B ⊂ C

for all B ∈ A.

Given B1 ,B2    ∈  P(X),  show that B1  n B2    ∈  P(X) is an upper bound of {B1 ,B2 } ⊂ P(X).

(b) We say an upper bound S of A ⊂ P(X) is a least upper bound if for all upper

bounds C of A, S ⊂ C .

Given B1 ,B2   ∈ P(X), show that if C is an upper bound of {B1 ,B2 }, then B1 n B2  ⊂ C . Use this with your result in (a) to show that B1 n B2  is the unique least upper bound of {B1 ,B2 }.

(Hint: For the second part, first show that B1 nB2  is a least upper bound. Then, show that if S is another least upper bound, S = B1 n B2 )

(c) Write down a corresponding definition for some C ∈ P(X) to be a lower bound of A ⊂ P(X). Use it to prove that B1 ∩ B2  is a lower bound of {B1 ,B2 }.

(d) Show that P(X) an analogue to the least upper bound property:  every non- empty collection A ⊂ P(X) has a least upper bound S .

You may find the following to be helpful: given a collection of sets A ⊂ P(X),

you can define a set which is the union over this collection,

n B := {x ∈ X : x ∈ B for some B ∈ A} ∈ P(X)

B∈A

2. In the following, let S ⊂ R be non-empty and bounded above. In this problem, we will see an interesting connection between the supremum and infinite sets.

(a) Show that there exists a sequence {xn } with xn   ∈ S for all n  ∈ N such that

lim xn  = supS .

(Hint: Look at Q8 on HW1 and HW2)

(b) Suppose supS   S .  Show that there exists a strictly monotone increasing se-

quence {yn } with yn  ∈ S for all n ∈ N.

(Hint: You may want to approach this problem inductively.  Take some y1  ∈ S , and note that supS − y1  > 0 (why?).  Use this with HW1 Q8 to find y2 , etc... When doing induction, you may want to prove that sup S − yp  > 0 for all p ∈ N.)

(c) Suppose supS  S . Show that there exists a countably infinite subset E ⊂ S .    (Hint: Consider the set {yn  : n ∈ N} defined for the sequence {yn } in (b).  Can you find some bijection between this set and N?)

(d) Suppose supS  ∈ S .  Will there always be a countably infinite subset E  ⊂ S?

Either prove the statement, or give a counterexample.

(Note: finite sets are never countably infinite)

3. So far in the course, we have only talked about sequences which converge to some real number. In this problem, we will use the following definition:

A sequence (of real numbers) {xn } is said to diverge to  (positive) infinity if for all K ∈ R, there exists some M ∈ N such that for all n ≥ M , xn  > K . In this case, we abuse notation and write

lim xn  := +∞

(a) Write down a corresponding definition for a sequence  {xn } which  diverges  to negative infinity, and use it to show that  lim −n3  = −∞

n→∞

(b) Suppose {xn } is a sequence satisfying xn  > 0 for all n ∈ N, and furthermore

lim  1  = 0

n→∞ xn

Show that {xn } diverges to positive infinity.

(c) Show that a sequence {xn } is unbounded above (i.e.  the set {xn   : n  ∈ N} is unbounded above) if and only if {xn } has a subsequence {xnk} which diverges to positive infinity.

(Hint: The ( ⇐= ) direction is easier, so you may want to start with that. For the ( =⇒ ) direction, I’d recommend splitting the proof into parts:

(i) prove that if {xn } is unbounded, then every p-tail of {xn } is also unbounded. (ii) inductively construct a subsequence {xnk} which satisfies xnk     >  k  for all k ∈ N.

(iii) prove that this subsequence does what you want it to do.)