All Problems

Please Login to access more options.

Today

Problem 1: (Another Way To Express Two)

You've seen the number $1.99\bar9$ before. Does this number equal 2, or is it different than 2? Prove your answer.

Problem 2: (Between Any Two Real Numbers Is Another Real Number)

Suppose $a$ and $b$ are real numbers with $a<b$. Prove that there exists a real number $c$ with $a<c<b$.

Here are some common symbols we use for standard number systems. We use

• $\mathbb{N}=\{1,2,3,\ldots\}$ for the natural numbers,
• $\mathbb{W}=\{0,1,2,3,\ldots\}$ for the whole numbers,
• $\mathbb{Z}=\{\ldots, -3,-2,-1,0,1,2,3,\ldots\}$ for the integers,
• $\mathbb{Q}=\{\frac{p}{q}\mid \text{ $p$ and $q$ are integers with $q\neq 0$}\}$ for the rational numbers, and
• $\mathbb{R}=(-\infty,\infty)$ for the real numbers.

We'll spend most of the semester looking at collections of real numbers, and these symbols will appear quite often.

Definition (Lower Bound, Upper Bound, Bounded)

Let $S$ be a collection of real numbers (written $S\subseteq \mathbb{R}$, or $S$ is a subset of the real numbers).

• A lower bound for $S$ is a real number $m$ such that $m\leq x$ for every $x\in S$. We say that $S$ is bounded below if it has a lower bound.
• An upper bound for $S$ is a real number $m$ such that $m\geq x$ for every $x\in S$. We say that $S$ is bounded above if it has an upper bound.
• We say that $S$ is bounded if has both a lower and upper bound.

Problem 3: (Practice With Bounded Definitions)

Consider the set $S=[0,4) = \{x\in\mathbb{R}\mid 0\leq x \text{ and } x< 4\}$.

1. Show that $S$ is bounded below by giving a lower bound. Prove that the number you gave is a lower bound, and then state another lower bound different than the one you gave.
2. Of all possible lower bounds, which is the greatest lower bound. In other words, produce a lower bound $m$ so that if $m'$ is any lower bound, then we must have $m'\leq m$. Prove your answer.
3. Show that $S$ is bounded above by giving an upper bound. Justify your answer.
4. Of all possible upper bounds, which is the least upper bound?

Problem 4: (Practice With Bounded Definitions 2)

Let $S$ be the set $S=\left\{\frac{1}{n}\mid n\in\mathbb{N}\right\}=\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\ldots\} $.

1. Give two different upper bounds for $S$. Then give the supremum of $S$.
2. Give two different lower bounds for $S$. Then give $\inf S$.

Remember, any time you make a claim, you must prove that your claim is correct.

In mathematics there are some ground rules that we cannot prove, rather they are just accepted as true without proof. We call these axioms. The following axiom just gives words to a fact that you may think is pretty obvious (something axioms tend to be).

Axiom (The Completeness Axiom)

Every nonempty set of real numbers that is bounded above has a least upper bound.

Problem 5: (Using The Completeness Axiom)

Consider the solutions to the inequality $x^2<2$. We can write this using set builder notation as $S=\{ x\mid x^2<2\}$.

1. Is $S$ bounded above? Prove your claim.
2. What does the completeness axiom say about this set?
3. Give $\sup S$, or explain why there is no supremum of $S$.

One of the skills we need to develop as mathematicians is the ability to encounter a new definition and from that definition start drawing conclusions. As the semester progresses, we'll have lots of opportunities to practice this. The beginnings of analysis and calculus are directly related to the next definition, that of a limit point of a set of real numbers.

Definition (Limit Point Of A Set Of Real Numbers)

Let $S$ be a set of real numbers. We say that a point $p$ is a limit point of $S$ if every open interval $I=(a,b)$ that contains $p$ also contains a point $x$ in $S$ with $x\neq p$.

Problem 6: (A Limit Point Of An Open Interval)

Let $S=(0,1)$ which is the open interval from 0 to 1 that does not include the end points. Prove that $p=1$ is a limit point of $S$. Then state another limit point of $S$.

Problem 7: (A Set With One Limit Point)

Let $\ds S=\left\{\frac{1}{n}\mid n\in \mathbb{N}\right\}$, the collection of fractions of the form $\frac{1}{n}$ where $n$ is a natural number. Prove that $p=0$ is a limit point of $S$.

In the work above, we saw several sets of real numbers. We've used sets our whole life to group together objects that have some common property. That is precisely what a set it, a group of things that share something in common.

Definition (Set, Subset, Equality Of Sets)

A set $S$ is a collection of elements that have been grouped together.

• We use brackets $\{$ and $\}$ to enclose elements of sets.
• We'll write $x\in S$ to say that $x$ is an element of $S$ or $x$ is in $S$. Similarly, we'll write $x\notin S$ to say that $x$ is not in $S$.
• We say that a set $B$ is a subset of the set $S$, and we write $B\subseteq S$, if every element in $B$ is also an element of $S$. We also read $A\subseteq B$ as "$A$ is contained in $B$." We'll often write $B\supseteq A$ instead of $A\subseteq B$, and read $B\supseteq A$ as either "$B$ is a super set of $A$" or "$B$ contains $A$."
• We say that $B$ is a proper subset of $S$ if $B\subseteq S$ but there is an element of $S$ that is not in $B$.
• We say that two sets $A$ and $B$ are equal if $A\subseteq B$ and $B\subseteq A$.

There are two general ways to express elements of a set. We can use the roster method where we list the elements of a set, as in $\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\ldots\}$. The roster method requires the reader to guess the remaining elements of the set, and hence can sometimes lead to unclear proofs. To avoid this potential confusion, we use set builder notation. With set builder notation, we express how to obtain the elements, as in $\{\frac{1}{n}\mid \in\mathbb{N}\}$. Any time you see $\{x\mid P(x)\}$ you can read this as the set of $x$ such that $P(x)$ holds.

There are many different ways we can use set builder notation to describe the exact same set, and we need to be able to show when two different ways are equal. For an example, consider the interval $I=(5,9] $. Let $S$ be the collection of upper bounds of $I$, which we can write in set builder notation as $$S=\{x\mid x \text{ is an upper bound of } I\}.$$ I claim that $S=\{x\mid x\geq 9\} $. Halt. This is a claim that two sets, namely $S$ and the set $A=\{x\mid x\geq 9\} $ are equal. From the definition above about equality of sets, to prove this claim is true we must prove that $S\subseteq A$ and that $A\subseteq S$. That's precisely what the next problem has you prove.

Problem 8: (First Proof That Two Sets Are Equal)

Let $I=(5,9] $. Consider the sets $S=\{x\mid x \text{ is an upper bound of } I\}$ and $A=\{x\mid x\geq 9\} $. Prove that $S=A$.

• Start by proving that $S\subseteq A$. So show that every element of $S$ is an element of $A$.
• Then prove that $A\subseteq S$.

Problem 9: (Second Proof That Two Sets Are Equal)

Let $I=(5,9] $. Consider the sets $T=\{x\mid x \text{ is a lower bound of } I\}$ and $B=\{x\mid x\leq 5\} $. Prove that $T=B$.

An important set that will show up often throughout the semester is the set with nothing in it, which we call the empty set.

Definition (Empty Set)

The empty set is the set $\emptyset = \{\}$ that contains no elements. If we think of a set as a box with elements in it, then the empty set is a box with nothing in it.

Here is another axiom that you have probably used many times in your life without ever realizing it.

Axiom (Well Ordering Principle)

Every nonempty subset $S$ of the natural numbers has a least element. By least element, we mean that there is a natural number $m$ which is an element of $S$ such that $m\leq x$ for every $x$ in $S$.

Problem 10: (Which Dominoes Remain Standing)

Suppose that Jon has set up an infinite number of dominoes, with the dominoes numbered $1,2,3, \ldots$. The dominoes are set up so that if the $k$th domino falls, then the $(k+1)$st domino will also fall. So if the 7th domino falls, then the 8th must fall as well. Jon knocks down the first domino, which starts causing other dominos to fall. Which dominos fall? Which dominoes remain standing? Make sure you prove your result. The well ordering principle will come in handy.

Suggestion: Use set builder notation to help you, so let $F=\{n\in \mathbb{N}\mid \text{domino $n$ fell}\}$ and $S=\{n\in \mathbb{N}\mid \text{domino $n$ remains standing}\}$. Then make some claims and prove they are correct.

Definition (Statement And Open Sentence)

• A statement is a sentence that can be classified as either true or false (but not both). The truth value of a statement is either "True" or "False." For a sentence to be a statement, it is not necessary that we know the truth value, but it must be clear that the value is either "True" or "False."
• Some sentences involve a variable, and the truth value of the sentence cannot be determined until the value of the variable is specified. An open sentence is a sentence involving a variable whose truth value cannot be determined until the variables in the sentence are specified, at which point the open sentence becomes a statement.

Exercise (Recognizing Statements And Open Sentences)

Classify each sentence below as a statement, an open sentence, or neither. Make sure you justify each answer.

1. Every integer is either even or odd.
2. Today is Thursday.
3. $x^2-9=0.$
4. The second coming will occur in 2050.
5. Sunsets are beautiful.
6. Have you read the first book in the Harry Potter series?
7. $\cos^2(x)+\sin^2(x)=1$.

Definition (Negation, Conjunction, Disjunction Of Statements)

Let $P$ and $Q$ be statements or open sentences.

• The negation of $P$, written $\sim P$, is the statement or open sentence which is true precisely when $P$ is false. We often read $\sim P$ as "It is not the case that $P$."
• The conjunction of $P$ and $Q$, written $P\wedge Q$, is the statement or open sentence "$P$ and $Q$." A conjunction is true only when both $P$ and $Q$ are true. So a conjunction is false unless both $P$ and $Q$ are true.
• The disjunction of $P$ and $Q$, written $P\vee Q$, is the statement or open sentence "$P$ or $Q$." A disjunction is true when $P$ is true, or $Q$ is true, or both are true. So a disjunction is true unless both $P$ and $Q$ are false.

Definition (Truth Table)

Let $P_1, P_2, \ldots, P_n$ be $n$ statements or open sentences that are used to make the compound sentence $P$. A truth table for this compound sentence is a table that keeps track of all possible truth values for the compound sentence based upon the possible truth values for each of $P_1, P_2, \ldots, P_n$.

Exercise (A Truth Table For A Conjunction Its Negation)

Construct a truth table for $P\wedge Q$ and $\sim(P\wedge Q)$.

Definition (Logically Equivalent)

We say two statements or open sentences are logically equivalent if they have the same truth value for all possible values of their component statements.

Problem 11: (De Morgan's Laws With Truth Tables)

Let $P$ and $Q$ be statements or open sentences. Start by completing the truth table below to give the truth values for $P\vee Q$, $\sim (P\vee Q)$, $(\sim P)\vee (\sim Q)$, and $(\sim P)\wedge (\sim Q).$ $$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\vee Q&\sim(P\vee Q) &\sim P&\sim Q &(\sim P)\vee (\sim Q) & (\sim P)\wedge (\sim Q)\\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

1. Use your truth table to prove that $\sim (P\vee Q)$ and $(\sim P)\wedge (\sim Q)$ are logically equivalent.
2. Construct a similar truth table to prove that $\sim (P\wedge Q)$ and $(\sim P)\vee (\sim Q)$ are logically equivalent .

In other words, when you have finished this problem you will have shown that

Problem 12: (Associativity Laws With Truth Tables)

Let $P$, $Q$, and $R$ be statements or open sentences. Use truth tables to prove each of the following.

1. Prove that $(P\wedge Q)\wedge R$ is equivalent to $P\wedge (Q\wedge R)$.
2. Prove that $(P\vee Q)\vee R$ is equivalent to $P\vee (Q\vee R)$.
3. Is $(P\vee Q)\wedge R$ equivalent to $P\vee (Q\wedge R)$.

Problem 13: (Distributive Laws With Truth Tables)

Let $P$, $Q$, and $R$ be statements or open sentences. Use truth tables to prove each of the following.

1. Prove that $(P\wedge Q)\vee R$ is equivalent to $(P\vee R)\wedge (Q\vee R)$.
2. Prove that $(P\vee Q)\wedge R$ is equivalent to $(P\wedge R)\vee (Q\wedge R)$.

Problem 14: (Creating A Truth Table For An Implication)

Suppose your teacher tells you the following "If you pass the final, then you pass the class." This sentence contains a construction of the form "If $P$, then $Q$."

1. There are four different scenarios that might occur as you may or may not pass the final, and you may or may not pass the class. List the four scenarios and decide in each scenario if the teacher lied.
2. Suppose that $P$ and $Q$ are statements. Use your answer to the previous part to construct a truth table for the statement "If $P$ then $Q$."

Definition (Implication)

If $P$ and $Q$ are statements or open sentences, then an implication, written symbolically as $P\implies Q$, is the sentence "If $P$, then $Q$" or equivalently "$P$ implies $Q$". There are several equivalent ways to express this sentence such as "$Q$ if $P$" or "$P$ only if $Q$." The implication $P\implies Q$ is true unless $P$ is true and $Q$ is false.

Definition (Converse, Inverse, And Contrapositive)

Consider the implication $P\implies Q$. From this implication we can define 3 other implications.

• The converse of $P\implies Q$ is the implication $Q\implies P$.
• The inverse of $P\implies Q$ is the implication $(\sim P)\implies (\sim Q)$.
• The contrapositive of $P\implies Q$ is the implication $(\sim Q)\implies (\sim P)$.

Problem 15: (Practice With Converse Inverse And Contrapositive)

Let $A=[3,7)$. Consider the implication "If $x\geq 8$ then $x$ is an upper bound of $A$."

1. Is this implication true or false?
2. Write the converse of this implication and determine the truth value of the converse.
3. Write the inverse of this implication and determine the truth value of the inverse.
4. Write the contrapositive of this implication and determine the truth value of the contrapositive.

Remember to always justify any claims you make.

Problem 16: (What Is Logically Equivalent To An Implication)

Consider the implication $P\implies Q$.

1. Construct a truth table that contains the possible values for this implication, the converse, the inverse, and the contrapositive. Feel free to use the table at the end of this problem to complete your work.
2. Which of these sentences are logically equivalent?

$$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\implies Q&Q\implies P &\sim P&\sim Q &(\sim P)\implies (\sim Q) & (\sim Q)\implies (\sim P)\\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

Problem 17: (Creating Examples Of Implications)

Give an example of each of the following, or explain why it cannot be done. Make sure you justify your claims (as always).

1. An implication that is true, and the converse is true.
2. An implication that is false, but the converse is true.
3. An implication that is true, but the contrapositive is false.

Problem 18: (The Negation Of An Implication Is A Conjunction)

In this problem we want to find the negation of $P\implies Q$.

1. In a truth table for an implication $P\implies Q$, how many of the 4 rows contain the truth value $T$?
2. In a truth table for a conjuction $P\wedge Q$, how many of the 4 rows contain the truth value $T$?
3. In a truth table for a disjunction $P\vee Q$, how many of the 4 rows contain the truth value $T$?
4. In a truth table for the negation of the implication $P\implies Q$, how many of the 4 rows contain the truth value $T$? Based off this answer alone, explain why you expect the negation of an implication to be a conjunction.
5. Complete the truth table below, and use your answer to determine which statement is logically equivalent to $\sim(P\implies Q)$.

$$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\implies Q&\sim(P\implies Q) &P \wedge Q &P \wedge (\sim Q) & (\sim P) \wedge Q& (\sim P) \wedge (\sim Q) \\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

Problem 19 (Proof By Contrapositive Versus Proof By Contradiction)

Let $a$ and $b$ be real numbers with $a<b$. Consider the set $S=(a,b)=\{x\in \mathbb{R}\mid a<x<b\}$. We know $b$ is an upper bound for this set as if $x\in S$, then by definition of $S$ we have $x<b$, which clearly implies $x\leq b$. To show that $b$ is the supremum of $S$, we must show "If $m$ is an upper bound of $S$, then $b\leq m$." This is an implication of the form "If $P$, then $Q$."

1. State the contrapositive of this implication.
2. State the negation of this implication.
3. Prove that the implication is true by proving that the contrapositive is true.
4. Now, instead, prove that the implication is true by proving that the negation is false.

As a corollary to this problem, similar reasoning shows that if $S$ is an interval (of the form $(a,b)$, $ [a,b)$, $(a,b] $, or $ [a,b] $), then we have $\sup S=b$ and $\inf S=a$. You may use those facts now without proof.

Definition (Union And Intersection Of Sets)

Let $A$ and $B$ be sets.

• The intersection of $A$ and $B$, written $A\cap B$, is a new set whose elements are those that are in $A$ and in $B$. Using set builder notation, we can write the intersection as $$A\cap B = \{x\mid x\in A \text{ and } x\in B\}.$$
• The union of $A$ and $B$, written $A\cup B$, is a new set whose elements are those that are in $A$ or in $B$ (or both). Using set builder notation, we can write the union as $$A\cup B = \{x\mid x\in A \text{ or } x\in B\}.$$

Problem 20: (Intersection Of Two Intervals)

Suppose that $a,b,c,d\in \mathbb{R}$ and that $a<b<c<d$. Consider the intervals $ A=(a,c) $ and $ B=[b,d] $. Prove that $A\cap B = [b,c) $. (Remember this means you need to prove that $A\cap B \subseteq [b,c) $ and $ [b,c)\subseteq A\cap B$.

Problem 21: (Union Of Two Intervals)

Suppose that $a,b,c,d\in \mathbb{R}$ and that $a<b<c<d$. Consider the intervals $ A=(a,c) $ and $ B=[b,d]$. Prove that $ A\cup B = (a,d] $.

Problem 22: (The Empty Set Is A Subset Of Every Set)

Prove or disprove. The empty set is a subset of every set. In other words, If $S$ is a set, then we have $\emptyset\subseteq S$.

Here are three more limit point problems to work on, one with a solution provided.

Exercise (Points In An Intervals Are Limit Points)

Let $a,b\in \mathbb{R}$, with $a<b$. Let $M=[a,b]$. Prove that if $p\in M$, then $p$ is a limit point of $M$.

Problem 23: (Points Not In A Closed Interval Are Not Limit Points)

Let $a,b\in \mathbb{R}$, with $a<b$. Let $M=[a,b]$. Prove that if $p\notin M$, then $p$ is not a limit point of $M$.

Problem 24: (Limit Points Of Subsets Are Limit Points Of The Larger Set)

Suppose that $A$ and $B$ are subsets of the real numbers. Prove that if $A\subseteq B$ and $p$ is a limit point of $A$, then $p$ is a limit point of $B$.

We have seen that the truth value of many sentences cannot be determined without an appropriate context. This requires that we quantify any possible variable in the sentence. Do we consider all possible values of the variable over some range, or should we consider just one possible instance of the variable. Consider the open sentence "$x^2+5x+6=0$." Two ways we can quantify what the variable $x$ represents are given below.

• For all real numbers $x$, we have $x^2+5x+6=0$.
• There exists a real number $x$ such that $x^2+5x+6=0$.

The first sentence is false (since when $x=0$ we do not have $6= 0$), and the second is true (let $x=-2$). We'll see the phrases "for every" and "there exists" quite often in mathematical writing. Because they occur so often, mathematicians have agreed upon some shorthand symbols for writing these phrases.

Exercise

Are the statements "It is not true that P implies Q" and "P does not imply Q" logically equivalent? Prove that they are, or provide a counter example.

Definition (The Quantifiers $\forall$ and $\exists$)

• We'll use $\forall$ as shorthand in place of the phrases "for every," "for all," "for each," or any equivalent expression that suggest for every possible case. We call $\forall$ the universal quantifier.
• We'll use $\exists$ as shorthand in place of the phrases "there exists," "there is at least one," or any equivalent expression that suggest there is at least one possible case. We call $\exists$ the existential quantifier.

These symbols are used often in open discussions, presentations, and informal work. However, when publishing formal papers, it is common practice to avoid using these symbols and instead just write the words.

Problem 25: (The Order Of Quantifiers Matters)

Translate each of the following into an English sentence. Then determine the truth value of each statement.

1. $\forall x \in \mathbb{R}, \exists y\in\mathbb{R}$ such that $y+1>x$.
2. $\exists y \in \mathbb{R}$ such that $\forall x \in \mathbb{R}$, we have $y+1>x$.

Problem 26: (Negating Quantifiers)

Rewrite each statement below using the quantifiers $\forall$ and/or $\exists$. Then write the negation of each statement.

1. For each $x\in\mathbb{N}$ we have $x>4$.
2. There exists $y\in \mathbb{R}$ such that $y\in (-3,4)$.
3. For every $\varepsilon>0$, there exists a $\delta>0$ such that $0<|x-c|<\delta$ implies $\left|f(x)-L\right|<\varepsilon$.

Problem 27: (Practice Finding Truth Values With Universal Quantifiers)

Determine the truth value of each statement below. Be prepared to justify your claim.

1. $\forall x\in \mathbb{R}$ and $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $x+y=z$.
2. $\forall x\in \mathbb{R}$ and $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $xz=y$.
3. $\forall x\in \mathbb{R}$, $\exists y\in \mathbb{R}$ such that $\forall z\in \mathbb{R}$, $z>y$ implies $z>x+y$.
4. $\exists x\in \mathbb{R}$ such that $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $z>y$ implies $z>x+y$.

The following problem gets at the heart of what it means to be a limit point.

Problem 27.5: (Limit Points Of A Singleton Set)

Let $a\in \mathbb{R}$. Suppose $S=\{a\}$, so a set with a single number. What are the limit points of $S$? Prove your claim.

Definition (Maximum and Minimum)

Let $S\subseteq \mathbb{R}$.

• We say $m$ is a minimum of $S$ if $m$ is a lower bound for $S$ and $m\in S$. We write $\min S$ for the minimum of $S$.
• We say $m$ is a maximum of $S$ if $m$ is an upper bound for $S$ and $m\in S$. We write $\max S$ for the maximum of $S$.

Problem 28: (Minimums And Maximums Are Unique)

Prove that a minimum of set $S$, if it exists, is unique. In other words, prove that if $m_1$ and $m_2$ are both minimums of $S$, then we must have $m_1=m_2$. A similar proof will show that maximums are unique.

Problem 29: (Relation Between Minimums And Infimums)

Suppose $S$ is a set of real numbers.

• If $m$ is the minimum of $S$, must $m$ be the infimum of $S$? Prove your claim.
• If $m$ is the infimum of $S$, must $m$ be the minimum of $S$? Prove your claim.

(Similar facts hold true for the maximum and supremum of a set.)

Problem 29.5 (Proving A Set Has No Minimum)

Let $S=(3,7] $. Prove that $S$ has no minimum.

The next theorem lists several facts about set unions and intersections that we would like to refer to from here on out.

Theorem (Union And Intersection Properties)

Let $A,B,C$ be sets. Then the following facts are true.

1. $A\subseteq A$ (Every set is a subset of itself.)
2. $A\subseteq A\cup B$ (A set is a subset of the union of itself and another set.)
3. $A\cap B\subseteq A$ (The intersection of two sets is a subset of the first set.)
4. $A\cup B = B\cup A$ (Set unions are commutative.)
5. $A\cap B = B\cap A$ (Set intersections are commutative.)
6. $A\cup (B\cup C)=(A\cup B)\cup C$ (Set unions are associative.)
7. $A\cap (B\cap C)=(A\cap B)\cap C$ (Set intersections are associative.)
8. $A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$
9. $A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$

The last two we call the distributive laws for unions and intersections.

Take some time to prove that each of the statements above is true. The next exercise includes several of the proofs. I'll leave some for you to prepare for class.

Exercise (Union And Intersection Properties)

Prove the statements in the Union and Intersection Properties theorem.

Problem 30: (Associative Laws For Set Unions And Intersections)

Let $A$, $B$, and $C$ be sets.

1. Prove that $A\cup (B\cup C) = (A\cup B)\cup C$.
2. Prove that $A\cap (B\cap C) = (A\cap B)\cap C$.

Problem 31: (The Integers Have No Limit Points)

There are three parts to this problem.

• Start by writing the definition of a limit point $p$ of a set $S$ using the quantifiers $\forall$ and $\exists$. Feel free to use set operations $\cup$ and/or $\cap$ in your definitions.
• Then write, using these quantifiers, what it means to not be a limit point.
• Finish by proving that if $p\in\mathbb{R}$, then $p$ is not a limit point of $\mathbb{Z}$. In other words, prove that $\mathbb{Z}$ has no limit points.

Problem 32: (Periodic Functions And Practice With Quantifiers)

Consider the following definition:

1. Rewrite the definition above using the symbols $\exists$ and $\forall$.
2. Prove that $y=\sin(x)$ is periodic over the reals.
3. Finish the following: "We say that a function $y=f(x)$ is not periodic over the reals if ..."
4. Prove that $y=x^2$ is not periodic over the reals.

Problem 33: (First Induction Problem)

For each $n\in \mathbb{N}$ consider the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ This is infinitely many statements. How do we prove infinitely many statements are true? What follows is a proof that all of these statements are true. The proof relies on the domino problem done earlier in the semester. Part way through the proof are several different versions of how to proceed. Your job is to read the proof and the different versions, and then decide for each version if it is logically sound and clear.

We'll have a discussion in class about your answers. Now for the proof.

To simplify our writing below, for each $n\in \mathbb{N}$ let $S_n$ be the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ We will prove that for each $n\in \mathbb{N}$, we know that $S_n$ is a true statement. To do this, we'll refer to the domino problem we proved earlier in the semester. Imagine for a minute that we have an infinite collection of dominos numbered $1, 2, 3, \ldots$. The first domino has the statement $1=\frac{1(2)}{2}$ on it, the second domino has the statement $1+2=\frac{2(3)}{2}$ on it, the third domino has the statement $1+2+3=\frac{3(4)}{2}$ on it, and so on. For each $n\in \mathbb{N}$, domino $n$ has the statement $S_n$ on it. We now have an infinite collection of dominos, one for each natural number $n$. We will now knock over each domino when we know the statement written on that domino is true. If we can knock over every domino, then $S_n$ is true for every $n\in \mathbb{N}$.

In the domino problem, two important things happened. First, note that Jon knocked over the first domino. Second, we knew that "if the $k$th domino falls, then it knocks over the $(k+1)$st domino." We will verify these two facts are true about our dominos. The first domino clearly falls, as the statement on the first domino is $1=\frac{1(2)}{2}$, which is true. We now must prove the second condition is true, namely "if the $k$th domino falls, then it knocks over the $(k+1)$st domino."

We conclude by referring to the domino problem. Since the first domino was knocked over, and since the $k$th domino falling implies the $(k+1)$st domino falls, then we know that every domino falls (the conclusion of the domino problem). This means that $S_n$ is a true statement for every $n\in\mathbb{N}$.

After reading the previous problem and analyzing several different proofs, we are ready to make a formal statement what we call "The principle of Mathematical Induction." The next problem asks you to prove this. If your proof looks very similar to the domino problem, then you are doing this correctly.

Theorem (The Principle Of Mathematical Induction)

If $S$ is a subset of the natural numbers such that

• 1 is an element of S, and
• if $k\in S$, then $k+1\in S$

then we must have $S=\mathbb{N}$.

Problem 34: (Proof Of Mathematical Induction)

Use the well ordering principle to prove the principle of mathematical induction.

Problem 35: (Induction With The Sum Of The Squares Of The First $n$ Natural Numbers)

Use induction to prove that $\ds 1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}$ for every $n\in \mathbb{N}$.

Exercise (Implications Versus Universal Quantifiers)

Consider the two statements below.

1. For every $x\in \mathbb{N}$, we have $x\geq 4$.
2. If $x\in \mathbb{N}$, then we have $x\geq 4$.

Are these two statements logically equivalent? Explain.

Definition (Set Complement And Cartesian Product)

Let $A$ and $B$ be sets.

• The complement of $B$ in $A$ is the set of elements in $A$ that are not in $B$. We can write this in set builder notation as $$A\setminus B = \{x\mid x\in A \text{ and }x\notin B\}.$$
• The Cartesian product (or cross product, or product) of $A$ and $B$ is the set of ordered pairs $(a,b)$ where $a\in A$ and $b\in B$. We can write the product in set builder notation as $$A\times B = \{(a,b)\mid a\in A\text{ and }b\in B\}.$$

Theorem (Rules For Set Complements)

Let $A$, $B$, and $C$ be sets. Then the following statements are true.

1. $A\setminus A = \emptyset$
2. $A\setminus \emptyset = A$
3. $A\setminus(B\cap C) = (A\setminus B)\cup(A\setminus C)$
4. $A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$
5. $A\setminus(B\setminus C) = (A\setminus B)\cup(A\cap C)$

Problem 36: (Set Complements Rules 1 And 2)

Prove rules 1 and 2 of Theorem (Rules For Set Complements).

Problem 37: (Set Complements Rules 3 And 4)

Prove rules 3 and 4 of Theorem (Rules For Set Complements).

Problem 38: (Set Complements Rule 5)

Prove rule 5 of Theorem (Rules For Set Complements).

Problem 39: (Distribution With Cartesian Products)

Let $A$, $B$, and $C$ be sets. Prove or disprove each statement.

1. $(A\cap B)\times C = (A\times C)\cap(B\times C)$
2. $(A\cup B)\times C = (A\times C)\cup(B\times C)$

Problem 40: (Practice Finding Truth Values With Universal Quantifiers 2)

For each statement below, first write the negation. Then determine whether the statement or the negation is true, and justify your claim. In your work below, assume that $f(x)=x^2$.

1. $\forall x\in \mathbb{R}$, $\exists y\in \mathbb{R}$ such that $\forall z\in \mathbb{R}$ we have $x+y=z$.
2. $\forall x,y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $x+z=y$.
3. $\exists x\in \mathbb{R}$ such that $\forall y\in \mathbb{Z}$, $x<y$ implies $f(x)<f(y)$.
4. $\forall x,y\in \mathbb{R}$, if $f(x)=f(y)$ then $x=y$.

Problem 41 (More Practice With Universal Quantifiers)

For each $n\in \mathbb{N}$, define $\ds a_n = \frac{n-1}{n}$. Only one of the statements below is true. Rewrite each statement using the quantifiers $\forall$ and $\exists$. Then determine which statement is true, prove that statement is true, and then prove the other statement is false.

1. For each real number $\varepsilon>0$, there exists $N\in \mathbb{N}$ such that for every $n\in \mathbb{N}$, if $n>N$ then $\ds \left|a_n-0\right|<\varepsilon$.
2. For each real number $\varepsilon>0$, there exists $N\in \mathbb{N}$ such that for every $n\in \mathbb{N}$, if $n>N$ then $\ds \left|a_n-1\right|<\varepsilon$.

We use Cartesian products all the time without realizing it. When we look for relationships between two groups, we are looking at a subset of a Cartesian product. Family history involves looking at a Cartesian product. For example, we could let $A$ and $B$ both be the set of all humans that have lived on the planet. In our family tree, we often care to know when person $x$ descends from person $y$. One goal of family history is to determine all the pairs $(x,y)$ where person $x$ descends from person $y$. This is a subset of $A\times B$. Similarly, any time we start grouping objects together from two sets, we're formally stating a relationship between the two sets and looking for a subset of the Cartesian product. We call these subsets relations.

Definition (Relation Between Two Sets)

Let $A$ and $B$ be sets. A relation $\mathrm{R}$ between $A$ and $B$ is a subset of $A\times B$, so $\mathrm{R}\subseteq A\times B$. Given $a\in A$ and $b\in B$, we write $(a,b)\in\mathrm{R}$ precisely when $a$ is related to $b$.

A function is one important kind of relation that we've been studying since middle school. Here's a formal definition.

Definition (Function)

Let $A$ and $B$ be sets. A function $f$ from $A$ into $B$, written $f:A\to B$, is a relation between $A$ and $B$ (so $f\subseteq A\times B$) such that for every $x\in A$, there exists a unique $y\in B$ such that $(x,y)\in f$. When $f$ is a function from $A$ into $B$, we'll use the notation $y=f(x)$ or $f(x)=y$ rather than the more cumbersome notation $(x,y)\in f$ used for sets.

Problem 42: (Which Relations Are Functions)

In each number below, you are given a relation $\mathrm{R}$ between a set $A$ and a set $B$. Prove that the relation is a function from $A$ into $B$ or give a counter example to show that the relation is not a function from $A$ into $B$.

1. Let $\mathrm{R}$ be the relation between $\mathbb{N}$ and $\mathbb{Z}$ given by $(n,m)\in \mathrm{R}$ if and only if $n^2=m$.
2. Let $\mathrm{R}$ be the relation between $\mathbb{N}$ and $\mathbb{Z}$ given by $(n,m)\in \mathrm{R}$ if and only if $n=m^2$.
3. Let $\mathrm{R}$ be the relation between $\mathbb{R}\times\mathbb{R}$ and $\mathbb{R}$ given by $((x,y),z)\in \mathrm{R}$ if and only if $x+y=z$.
4. Let $\mathrm{R}$ be the relation between $\mathbb{R}\times\mathbb{R}$ and $\mathbb{R}$ given by $((x,y),z)\in \mathrm{R}$ if and only if $x/y=z$.

Definition (Domain And Codomain)

Let $A$ and $B$ be sets and let $f$ be a function from $A$ into $B$, so we have $f:A\to B$.

• We call the set $A$ the domain of $f$.
• We call the set $B$ the codomain of $f$.

Definition (Injective, Surjective, And Bijective)

Let $D$ and $R$ be sets and let $f$ be a function from $D$ into $R$, so we have $f:D\to R$.

• We say that $f$ is injective (or one-to-one) if and only if for every $a,b\in D$ we have $f(a)=f(b)$ implies $a=b$.
• We say that $f$ is surjective (or onto) if and only if for every $y\in R$ there exists an $x\in D$ such that $y=f(x)$.
• We say that $f$ is bijective if and only if the function $f$ is both injective and surjective.

Problem 43: (Practice With Injective And Surjective)

For each function below, state the domain and codomain, determine if the function is injective, and then determine if the function is surjective.

1. Let $f:\mathbb{R}\to\mathbb{R}$ be defined by $f(x)=x^2$.
2. Let $f:[0,\infty)\to\mathbb{R}$ be defined by $f(x)=x^2$.
3. Let $f:\mathbb{R}\to [0,\infty)$ be defined by $f(x)=x^2$.
4. Let $f:[0,\infty)\to[0,\infty)$ be defined by $f(x)=x^2$.

As always, remember to justify each claim you make.

Exercise (Induction With The Sum Of Cubes)

Prove that for every $n\in \mathbb{N}$, we have $$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2.$$

Problem 44: (Induction With Sum Of Odds)

Notice that $$ \begin{align} 1&=1 \\ 1+3&=4 \\ 1+3+5&=9 \\ 1+3+5+7&=16 \\ 1+3+5+7+9&=25. \end{align} $$ Make a conjecture about the sum of odd numbers by giving a general formula for what you see above. Then prove that your formula is valid by using mathematical induction.

Problem 45: (Relationships Between Subsets, Infimums, And Supremums)

Suppose that $S$ and $T$ are nonempty bounded subsets of $\mathbb{R}$ and that $S\subseteq T$. Prove that $$\inf T \leq \inf S \leq \sup S\leq \sup T.$$

Definition (Epsilon Neighborhoods And Deleted Neighborhoods)

Given $\varepsilon>0$, an $\varepsilon$-neighborhood of the real number $x$ is the interval $$N_{\varepsilon}(x) = (x-\varepsilon,x+\varepsilon) = \{y\in \mathbb{R}\colon |x-y|<\varepsilon\}.$$ A deleted $\varepsilon$-neighborhood of $x$ is the same interval minus the point $x$, which we'll write as $$N^*_{\varepsilon}(x) = N_{\varepsilon}(x)\setminus\{x\} = (x-\varepsilon,x)\cup(x,x+\varepsilon) = \{y\in \mathbb{R}\colon 0<|x-y|<\varepsilon\}.$$

Problem 46: (Practice With Neighborhoods)

Consider the interval $S=(1,8)$.

1. Find real numbers $x$ and $\varepsilon$ so that $S=N_\varepsilon(x)$.
2. Find real numbers $x$ and $\varepsilon$ so that $N_\varepsilon(x)$ is a proper subset of $S$.
3. For every $x\in S$, give a formula for $\varepsilon$ so that $N_\varepsilon(x)\subseteq S$. Your choice of $\varepsilon$ will depend on $x$.

Definition (Interior Point, Open Set, Closed Set)

Let $S\subseteq \mathbb{R}$.

• We say that $x$ is an interior point of $S$ if and only if there exists an $\varepsilon>0$ such that $N_\varepsilon(x)\subseteq S$.
• The interior of $S$ is the collection of interior points of $S$.
• We say that $S$ is an open set if and only if for every $x\in S$ there exists an $\varepsilon>0$ such that $N_\varepsilon(x)\subseteq S$ (so every point in $S$ is an interior point, or equivalently $S$ equals the interior of $S$).
• We say that $S$ is a closed set if and only if the complement $\mathbb{R}\setminus S$ is open.

Problem 47: (Open Intervals Are Open Sets)

Prove that if $a$ and $b$ are real numbers such that $a<b$, then the interval $S=(a,b)$ is an open set.

Problem 48: (Closed Intervals Are Closed Sets)

Prove that if $a$ and $b$ are real numbers such that $a<b$, then the interval $ S=[a,b] $ is a closed set.

Definition (Sequence)

A sequence of real numbers is a function $a:\mathbb{N}\to\mathbb{R}$.

• We'll often use the notation $a_n$ rather than $a(n)$ to denote the value of the sequence at $n$. We call $a_n$ the $n$th term of the sequence.
• We may refer to the sequence by writing $(a_n)$ or by writing $(a_1,a_2,\ldots)$.
• We may change the domain from $\mathbb{N}$ to $\mathbb{N}\cup \{0\}$ by adding in $0$, or we might remove several of the first entries from the sequence. When we do this, we'll use the notation $(a_n)_{n=m}^{\infty}$ where $m$ is the first term we want to consider.

Definition (Convergent Sequence)

Let $(a_1,a_2,\ldots)$ be a sequence of real numbers.

• We say that $(a_n)$ converges to $L$ and write $(a_n)\to L$ if and only if for every $\varepsilon>0$, there exists a real number $M$ such that for every $n\in \mathbb{N}$ we have $n> M$ implies $|a_n-L|<\varepsilon$.
• When $(a_n)$ converges to $L$, we call $L$ the limit of $(a_n)$.
• We say that $(a_n)$ is a convergent sequence if and only if $(a_n)$ converges to $L$ for some real number $L$.
• We say that $(a_n)$ is a divergent sequence if and only if $(a_n)$ is not a convergent sequence.

Problem 49: (Showing A Sequence Converges)

Consider the sequence $\ds (a_n)=\left(\frac{n+1}{n}\right)$. Prove that $(a_n)$ converges to $L=1$.

You can get the list of definitions using this download.

• Midterm Exam Definitions

How do we determine if two sets have the same number of elements? If both sets are finite, the answer is simple as you can count the number of elements. However, what if both sets have infinitely many elements? The sets $\mathbb{Z}$ and $\mathbb{N}$ both have infinitely many elements. How do we compare the size of these sets?

• We could say there more than two times as many integers as there are natural numbers. This is because we can see an injection $f:\mathbb{N}\to\mathbb{Z}$ defined by $f(n)=n$, and this injection misses all the negative integers and zero.

To help us build some intuition, let's examine a classical fun way to look at this issue. It involves a rather strange hotel that has infinitely many rooms.

Problem: The Hilbert Hotel

Sally owns a rather strange hotel. This hotel has infinitely many rooms which are numbered 1, 2, 3, 4, .... Business has been good, and Sally manages to fill the entire hotel. Frank, Sally's brother, shows up at the main lobby and asks to get a room. The front clerk says, "Sorry, we're full." Luckily Sally overhears this comment and interrupts by saying, "Frank, I think we can find a room for you. We may have to ask some people to switch around rooms, but we can fit you in." Sally comes to you and asks you to find a room for Frank.

1. Prepare new room assignments for every single occupant in Sally’s hotel so that after each occupant has moved to their new room, there will be an empty room available for Frank. In other words, if someone is currently in room $k$, which room do you want them to move to, and in which room will you put Frank. You’re allowed to move as many people in the hotel as you want, but you can’t make anyone share rooms.
2. If George, who is Sally's cousin, had shown up at the same time as Frank, how could you have prepared the room assignments to make space for two empty rooms?
3. If $n$ people show up to Sally's full hotel, how can you make room for $n$ extra people?

Definition: Cardinality

Suppose $A$ and $B$ are two sets. The cardinality of $A$ is written $|A|$.

• We say that the cardinality of $A$ is finite if $A$ has finitely many elements. Otherwise, we say that the cardinality of $A$ is infinite.
• If $A$ has finitely many elements, say $n$ elements, then we write $|A|=n$.
• If there is an injection $f:A\to B$, then we write $|A|\leq |B|$.
• If there is a surjection $g:A\to B$, then we write $|A|\geq |B|$.
• If there is a bijection $h:A\to B$, then we write $|A|=|B|$. Two sets have equal cardinalities if and only if there is a bijection between the two sets.

Problem: Several Countably Infinite Sets

What does the Hilbert Hotel Problem tell us about the cardinality of $\mathbb{N}$ and $\mathbb{N}\cup \{0\}$? What about the cardinality of $\mathbb{N}$ and $\mathbb{N}\cup \{0,-1,-2,-3,-4\}$? Which has a greater cardinality, or are they the same? Why?

Definition: Countably Infinite, Countable, Uncountable

Let $A$ be a set.

• We say that $A$ is countably infinite if $|A|=|\mathbb{N}|$.
• We say that $A$ is countable if either $A$ is a finite set or $A$ is countably infinite.
• We say that $A$ is uncountable if $A$ is not countable.

What happens when you start combining sets whose cardinality is infinite? Some might call the results below strange, while others might call them beautiful.

Problem: Finite Products of Countable Sets

Business has been really good for Sally, so her brother Frank decides to open another hotel across town, next to the river. Both Sally and Frank manage to fill their hotels completely every night (really good business). However, a week of excessive rain causes the river to flood, and Frank has to find lodging for all of his hotel guests (quite a feat). Frank calls Sally (whose hotel is full) and he tells her about the problem. Sally immediately says, ``Oh, I've got room for all your guests. Bring them over.'' Since you were the one who figured out how to make room for Frank, George, and $m$ friends, Sally figures you can find a way to fit in an extra infinite number of guests. She asks you to prepare the room assignments for all of Franks guests. Not wanting to disappoint her, you accept the challenge.

1. Prepare new room assignments for every single occupant of both hotels. If someone is currently in room $k$ in your hotel, which room should they move to? If someone was in room $j$ of Frank's hotel, which room will you give them in your hotel? You can't make anyone share rooms. Sally would also like you to make sure the hotel is still full when you're done (if there are vacancies, it might look bad, we have to keep up appearances).
2. George, remember Sally's cousin, decides to open a hotel as well (he puts it next to a lake). A month later, severe flooding causes both Frank and George to vacate their hotel. All three of Sally, Frank, and George have completely full hotels, but Sally tells the boys to bring all their guests over and she'll fit them all into the hotel. She then tells you to make room assignments.

Problem: Countable Products of Countable Sets

One night, Sally decides to take her hotel plan and sell the concept to potential investors. The idea is quite popular, and she fills each room in her hotel with someone who wants to build a hotel just like hers. For sake of ease, we'll name the new entrepreneurs $p_1, p_2, p_3, \ldots.$ Every entrepreneur goes out and opens a new hotel (businessman $p_k$ opens hotel $H_k$) that is just like Sally's. After a few months, every single hotel $H_k$ is filled to capacity. The business men $p_k$ decide to have a party in recognition of Sally, and as part of the party they decide that everyone should bring all their occupants to Sally's hotel on the same night (so there will be an infinite number of hotels, each bringing infinitely many guests). Sally decides to clear her hotel of all guests for the day, so her hotel is empty to start with. She asks you to prepare room assignments for all the inhabitants of all the hotels. Sally insists that you can do this.

• Your job is clear. When each guest arrives, they tell you which hotel $H_k$ they came from, and then they tell you which room number $j$ they were occupying at hotel $H_k$. How will you make the room assignments so that you can fill every single room in Sally's hotel with exactly one occupant? Which room will you assign guest $(j,k)$ to ($j$ was their old room assignment in hotel $H_k$)?

Problem: An uncountable set

One day, an alien space ship lands next to Sally's hotel. They had heard about her hotel and its amazing feats from an intergalactic newspaper. The alien ship is quite full, and Sally is having a hard time remembering names. She discovers that you can name all the aliens if you name them $a_x$ for each $x\in \mathbb{R}$. The aliens want to all stay in Sally's hotel, so Sally asks you to prepare room assignments for them all. You tell her it can't be done. She insists that it can be done, but you are firm in your convictions and tell her that it can't be done (you're not discriminating against aliens, rather you are just stating a fact). Sally doesn't believe you, so she prepares the room assignments herself. She brings you a list that says which alien should be in room 1, which alien to put in room two, etc. Before she takes it to the ship, she ask you to look over the list to make sure she hasn't missed anyone.

• Your job is clear. Show Sally why her room assignment plan is missing an alien. In other words, give her a counterexample that proves here list is incomplete.

When you complete this problem, you'll show that the cardinality of the real numbers is larger than the cardinality of the natural numbers. This proves that $\mathbb{R}$ is an uncountable set. There are different sizes of infinity.

Definition (Cardinality Of A Finite Set)

If $A$ is a finite set, then the cardinality of $A$, written $|A|$, is the number of distinct elements of $A$.

Problem 50: (Induction And Cardinality Of Cartesian Products)

If $A$ and $B$ are finite sets, then we have discussed in class why the cardinality of $A\times B$ is given by $$|A\times B|=|A|\cdot |B|.$$ Use induction to prove that for every $n\in \mathbb{N}$ if $A_1, A_2, \ldots, A_n$ are finite sets, then we have $$|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|.$$

Definition (Accumulation Point Of A Set)

Let $S$ be a set of real numbers. We say that a real number $a$ is an accumulation point of $S$ if for every $\varepsilon>0$, we have $N_\varepsilon^*(a)\cap S \neq \emptyset$.

The definition of accumulation point should look very similar to the definition of limit points. The next problem has you make this precise. You'll see a statement of the for "$P$ if and only if $Q$" in the problem below. This is shorthand for writing both "$P$ if $Q$" (so $Q\implies P$) and "$P$ only if $Q$" (so $P\implies Q$), which is the same as proving the two statements are logically equivalent.

Practice.ProvingSomethingIsAnAccumulationPoint

We learned a new definition. Let's practice using it.

1. Prove that 0 is an accumulation point of the set $S=\{\frac{1}{n}\mid n\in\mathbb{N}$.
2. Prove that 3 is an accumulation point of the set $S = [2,7)$.
3. Prove that 0 is not an accumulation point of the set $S = [2,7)$.
4. Prove that 2 is an accumulation point of the set $S = [2,7)$.
5. Prove that 7 is an accumulation point of the set $S = [2,7)$.

Problem 51: (Accumulation Points Are The Same As Limit Points)

Let $S$ be a set. Prove that $a$ is an accumulation point of $S$ if and only if $a$ is a limit point of $S$. In other words, prove both of the following:

• If $a$ is an accumulation point of $S$, then $a$ is a limit point of $S$.
• If $a$ is a limit point of $S$, then $a$ is an accumulation point of $S$.

Let's now examine a problem related to limits of sequences. Some of you noticed in the definition of a limit of a sequence that we used the word "a" instead of "the." What we will prove now is that when a sequence converges, we can talk about "the" limit of the sequence instead of just "a" limit of the sequence.

Problem 52: (A Convergent Sequence Has A Unique Limit)

Let $(a_n)$ be a convergent sequence of real numbers. Prove that $(a_n)$ converges to a unique real number.

We now turn our attention to open sets. How does the union and intersection set operation behave when working with two open sets?

Practice.Open Set Practice

Complete the following

1. Let $U_1 = (-3,2)$ and $U_2=(5,9)$. Prove that $U_1\cup U_2$ is open.
2. Let $U_1 = (-3,2)$ and $U_2=(5,9)$. Prove that $U_1\cap U_2$ is open.
3. Prove that $\{4\}$ is a closed set.
4. Give a set that is both open and closed.

Problem 53: (Unions And Intersections Of Two Opens Sets Are Open)

Let $U_1$ and $U_2$ be open sets. Show that $U_1\cup U_2$ and $U_1\cap U_2$ are open sets.

Now that we've seen that unions and intersections of two open sets are open, what happens if we have more than two open sets? We need a formal definition of how to create a union and intersection of any collection of sets.

Definition (Unions And Intersections Of Arbitrarily Many Sets)

Suppose we have a large collection of sets. Each set has been given a name of the form $A_j$ where $j$ is an element of some nonempty set $J$. We call the collection $\mathrm{A} = \{A_j\mid j\in J\}$ an indexed family of sets with index set $J$. The union and intersection of all the sets in $\mathrm{A}$ are the sets given by $$\bigcup_{j\in J}A_j = \{x\mid x\in A_j \text{ for some } j\in J\}\text{ and } \bigcap_{j\in J}A_j = \{x\mid x\in A_j \text{ for every } j\in J\}.$$ When $J=\mathbb{N}$, then we'll often write the union and intersection using the notation $$\bigcup_{n\in \mathbb{N}}A_n = \bigcup_{n=1}^\infty A_n = A_1\cup A_2\cup A_3\cup\cdots\text{ and } \bigcap_{n\in \mathbb{N}}A_n = \bigcap_{n=1}^\infty A_n = A_1\cap A_2\cap A_3\cap\cdots.$$

Problem 54: (Unions And Intersections Of Nested Sets)

Let $n$ be a natural number and suppose that $A_1,A_2,\ldots, A_n$ are sets. Suppose also that $A_1\supseteq A_2\supseteq A_3\supseteq \cdots \supseteq A_n$.

1. Prove that $\ds\bigcup_{i=1}^n A_i = A_1$.
2. Make a conjecture that simplifies $\ds\bigcap_{i=1}^n A_i$. Then prove your conjecture.

Exercise (Induction With The Sum Of Cubes)

Prove that for every $n\in \mathbb{N}$, we have $$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2.$$

The formal principle of induction allows us to show that a set $S$ equals $\mathbb{N}$. This requires that we show $1\in S$ and if $k\in S$, then $k+1\in S$. What if the statement we wish to show is not true for every natural number, but is true for every natural number past some base case. So suppose we know that $4\in S$ and if $k\in S$ with $k\geq 4$, then $k+1\in S$. Can we conclude that $S$ contains every natural number greater than or equal to 4? If you examine the proof we used for induction, you'll find the quick answer to this question is "yes." So we now have a new form of induction.

Problem 55: (Induction And $2^n\geq n^2$)

Use induction to prove that for every $n\in \mathbb{N}$ except for $n=3$ we have $2^n\geq n^2$.

When we have shown that something holds true for two objects, we can often use induction to prove the same fact holds true for any finite collection of those objects. The next problem has you do this.

Problem 56: (Unions And Intersections Of Finitely Many Opens Sets Are Open)

Use induction to prove for each $n\in \mathbb{N}$ if $U_1$, $U_2$, ..., $U_n$ are open sets, then $\ds \bigcup_{i=1}^n U_i$ is an open set.

Let's now return to studying functions.

Definition (Image $f(A)$ and Preimage $f^{-1}(B)$)

Consider the function $f:X\to Y$. Let $A$ be a subset of the domain $X$ and let $B$ be a subset of the codomain $Y$.

• The image of $A$ under $f$ is the subset of $Y$ defined by $$ \begin{align} f(A) &=\{y\in Y\mid y=f(a) \text{ for some }a\in A\}\\ &=\{f(a)\mid a\in A\} .\end{align}$$ This means that $y\in f(A)$ if and only if $y=f(a)$ for some $a\in A$.
• The preimage (or inverse image) of $B$ under $f$ is the subset of $X$ defined by $$ \begin{align} f^{-1}(B) &=\{x\in X\mid f(x)=b \text{ for some }b\in B\}\\ &=\{x\in X\mid f(x) \in B\} .\end{align}$$ This means that $x\in f^{-1}(B)$ if and only if $f(x)=b$ for some $b\in B$ if and only if $f(x)\in B$. Note that when the set $B$ contains a single element, then we write $f^{-1}(b)$ rather than $f^{-1}(\{b\})$.

We were just introduced to a new definition. We should try to apply this definition to a function we understand. The next problem has you do this.

Problem 57: (Function Notation With Sine)

Consider the function $f:\mathbb{R}\to\mathbb{R}$ defined by $f(x)=\sin x$.

1. What are the sets $f(\mathbb{R})$ and $f([0,\pi/2))$?
2. What are the sets $f^{-1}(0)$ and $f^{-1}([0,\pi/2))$?
3. Find a set $A\subseteq \mathbb{R}$ so that $g:A\to \mathbb{R}$ defined by $g(x)=\sin(x)$ is injective.
4. Find a set $B\subseteq \mathbb{R}$ so that $h:A\to B$ defined by $h(x)=\sin(x)$ is surjective.

The following theorem lists many facts that we could prove about the image and preimage of a function. We'll take some time to prove a few of them, but not all of them in class. You should be able to prove each of them for the final exam.

Theorem (Image And Preimage Properties)

Consider the function $f:X\to Y$.

1. If $A\subseteq X$, then we have $A\subseteq f^{-1}(f(A))$.
2. If $B\subseteq Y$, then we have $f(f^{-1}(B))\subseteq B$.
3. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.
4. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cup A_2)=f(A_1)\cup f(A_2)$.
5. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2)$.
6. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$.
7. We have $f(A)\subseteq B$ if and only if $A\subseteq f^{-1}(B)$.
8. If $A_1\subseteq A_2\subseteq X$, then we have $f(A_1)\subseteq f(A_2)$.
9. If $B_1\subseteq B_2\subseteq Y$, then we have $f^{-1}(B_1)\subseteq f^{-1}(B_2)$.
10. If $B\subseteq Y$, then $f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$.

Problem 58: (Image And Preimage Properties 1 And 2)

Prove properties 1 and 2 for images and preimages. So prove for a function $f:X\to Y$ both of the following.

1. If $A\subseteq X$, then $A\subseteq f^{-1}(f(A))$.
2. If $B\subseteq Y$, then $f(f^{-1}(B)\subseteq B$.

Then give an example of a function $f:X\to Y$ and subsets $A\subseteq X$ and $B\subseteq Y$ where $A\neq f^{-1}(f(A))$ and $B\neq f(f^{-1}(B))$.

Problem 59: (Image And Preimage Property 3)

Prove property 3 for images. So let $f:X\to Y$. Then prove that

• If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.

Finish by proving that if $f$ is injective, then equality holds.

Problem 60: (Image And Preimage Property 6)

Prove property 6 for preimages. So let $f:X\to Y$. Then prove that

• If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$.

Problem 61: (Image And Preimage Property 7)

Prove property 7 for preimages. So let $f:X\to Y$. Then prove that

• We have $f(A)\subseteq B$ if and only if $A\subseteq f^{-1}(B)$.

Problem 62: (The Union And Intersection Of Infinitely Many Open Sets)

For each $n\in\mathbb{N}$, let $A_n = \left(0,1+\frac{1}{n}\right)$.

1. What are the sets $\ds \bigcup_{n=1}^\infty A_n$ and $\ds \bigcap_{n=1}^\infty A_n$?
2. Prove your claims.

Exercise (Unions And Intersections Of Opens Sets)

Prove each of the following:

1. The union of any collection of open sets is open.
2. The intersection of finitely many open sets is open.

Problem 63: (The Union And Intersection Of Infinitely Many Closed Sets)

For each $x$ such that $3<x<4$, let $A_x = [2,x]$.

1. State an interval that equals each of $\ds \bigcup_{3<x<4} A_x$ and $\ds \bigcap_{3<x<4} A_x$.
2. Prove your claims.

Definition (Function Composition)

Consider the functions $f:A\to B$ and $g:C\to D$. When $B\subseteq C$, then we know for each $a\in A$ that $f(a)\in B\subseteq C$. Since $f(a)\in C$, we can compute the quantity $g(f(a))$. If $B\subseteq C$, then we define the composition of $g$ and $f$ to be the new function $g\circ f : A\to D$ defined by $$(g\circ f)(a) = g(f(a)).$$

Problem 64: (The Composition Of Surjective Functions Is Surjective)

Let $A$, $B$, and $C$ be sets, and consider the functions $f:A\to B$ and $g:B\to C$. Prove that if both $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Problem 65: (The Composition Of Injective Functions Is Injective)

Let $A$, $B$, and $C$ be sets, and consider the functions $f:A\to B$ and $g:B\to C$. Prove that if both $f$ and $g$ are injective, then $g\circ f$ is injective.

Problem 66: (Triangle Inequality)

For any real numbers $u$ and $v$, let $d(u,v)$ be the distance between $u$ and $v$, which means $d(u,v)=|u-v|=|v-u|$.

1. Let $a,b,c\in\mathbb{R}$. Prove that $d(a,b)\leq d(a,c)+d(c,b)$.
2. Let $x,y\in\mathbb{R}$. Use the previous result to prove that $|x+y|\leq |x|+|y|$.

Problem 67: (Proving A Quotient Of Two Linear Sequences Converges)

Prove that $\left(\frac{2n+1}{3n+4}\right)$ converges to $\frac{2}{3}$.

Hint: Given $\varepsilon>0$, solve the equality $|a_M-L|=\varepsilon$ for $M$, which should help you find a value $M$ you can choose to satisfy the definition of converges. So start by solving $\left|\frac{2M+1}{3M+4} - \frac{2}{3}\right|=\varepsilon$ for $M$.

Problem 68: (Limit Of A Sum Equals Sum Of Limits)

Suppose $(a_n)$ converges to $A$ and $(b_n)$ converges to $B$. Prove that $(a_n+b_n)$ converges to $A+B$. The triangle inequality should help.

Definition (Invertible Function)

We say that a function $f:D\to C$ is invertible if there exists a function $g:C\to D$ such that $f(g(c))=c$ for every $c\in C$ and $g(f(d))=d$ for every $d\in D$. If such a function $g$ exists, then we use the notation $f^{-1}$ as the name for the function $g$.

Problem 69: (Functions Are Invertible Iff Bijective)

Prove that a function $f:D\to C$ is invertible if and only if $f$ is bijective.

Problem 70: (Proving A Quotient Of Two Quadratic Sequences Converges)

Prove that $\left(\frac{n^2}{n^2+1}\right)$ converges.

Hint: Given $\varepsilon>0$, solve the equality $|a_M-L|=\varepsilon$ to find a value $M$ you can choose to satisfy the definition of converges.

Definition (Image Of A Function)

Let $f:X\to Y$. The image of $f$ is the set $f(X)$.

Exercise (A Function Is Surjective Iff Codomain And Image Are Equal)

Prove that a function is surjective if and only if the codomain of $f$ and the image of $f$ are equal.

Exercise (The Composition Of Surjective Functions Is Surjective Take 2)

Suppose both $f:A\to B$ and $g:B\to C$ are surjective. Prove that $g\circ f:A\to C$ is surjective.

Definition (The Image Of A Sequence Is A Set)

Given a sequence $(a_n)$ of real numbers, note that the image of the sequence, namely $a(\mathbb{N}) = \{a_n\mid n\in\mathbb{N}\}$, is a subset of the real numbers. Because the image of the sequence is a set of real numbers, we can use any of our previous words that we defined on sets of real numbers, and now apply them to a sequence. Here are some examples:

• We say a sequence is bounded if the image of the sequence is a bounded set.
• A lower bound for a sequence is a lower bound for the image of the sequence.
• The supremum of a sequence is the supremum of the image of the sequence.
• A limit point of a sequence is a limit point of the image of the sequence.

Problem 71: (Convergent Sequences Are Bounded)

Prove that if a sequence of real numbers converges, then the sequence is bounded.

Problem 72: (Limit Of Product Equals Product Of Limits)

Suppose $(a_n)$ converges to $A$ and $(b_n)$ converges to $B$. Prove that $(a_nb_n)$ converges to $AB$. The triangle inequality should help, along with the fact that convergent sequences are bounded.

Problem 73: (Limits Of Sequences And Limit Points Of Images)

Is a limit point of the image of a sequence equal to the limit of that sequence?

• Give an example of a sequence $(a_n)$ that converges to $L$, such that $L$ is a limit point of the image of the sequence.
• Give an example of a sequence $(a_n)$ that converges to $L$, such that $L$ is not a limit point of the image of the sequence.
• Make a conjecture about when limits of sequences and limit points of images of sequences are equal.
• Give an example of a sequence $(a_n)$ that does not converge, yet the image of the sequence has one (or more) limit points.

Problem 74: (Converges To L Can Be Written As Converges To 0)

Let $(a_n)$ be a sequence of real numbers, and $A$ a real number. Prove that $(a_n)$ converges to $A$ if and only if the sequence $(a_n-A)$ converges to $0$. This will simplify proving that some sequences converge.

Problem 75: (Proving A Rational Sequence Converges)

Consider the sequence $\ds (s_n)=\left(\frac{4n^3-2n^2-7n}{5n^3-3n^2+2n-1}\right)$. In this problem, your job is to prove that $s_n\to 4/5$. You may assume that for all natural numbers, we have $5n^3-3n^2+2n-1>0$.

1. Show that $\ds(s_n-4/5)= \left(\frac{2 n^2-43 n+4}{5 \left(5 n^3-3 n^2+2 n-1\right)}\right).$
2. Find a $k_1>0$ and $M_1$ so that $|2 n^2-43 n+4|\leq k_1 n^2$ for all natural numbers $n>M_1$.
3. Find a $k_2>0$ and $M_2$ so that $|5 \left(5 n^3-3 n^2+2 n-1\right)|\geq k_2 n^3$ for all natural numbers $n>M_2$.
4. Prove that $(s_n)$ converges to $4/5$.

Problem 76: (Limit Of Quotient Equals Quotient Of Limits)

Suppose $(a_n)$ converges to $A$ and $(b_n)$ converges to $B\neq 0$, and also suppose $b_n\neq 0$ for every natural number $n$. Prove that $(a_n/b_n)$ converges to $A/B$.

Definition (Increasing Decreasing Monotonic Sequences)

Let $(a_n)$ be a sequence of real numbers.

• We say that $(a_n)$ is (strictly) increasing if $a_n<a_{n+1}$ for every $n\in\mathbb{N}$.
• We say that $(a_n)$ is (strictly) decreasing if $a_n>a_{n+1}$ for every $n\in\mathbb{N}$.
• We say that $(a_n)$ is nonincreasing if $a_n\geq a_{n+1}$ for every $n\in\mathbb{N}$.
• We say that $(a_n)$ is nondecreasing if $a_n\leq a_{n+1}$ for every $n\in\mathbb{N}$.
• We say that $(a_n)$ is monotonic if $(a_n)$ is either nonincreasing or nondecreasing.

You should notice that a strictly decreasing sequence is nonincreasing, and a strictly increasing sequence is nondecreasing.

Problem 77: (Monotonic Sequences Converge If And Only If Bounded)

Let $(a_n)$ be a monotonic sequence. Prove that $(a_n)$ converges if and only if $(a_n)$ is bounded.

Definition (Diverges To Infinity)

Let $(a_n)$ be a sequence of real numbers. We say that $(a_n)$ diverges to infinity if for every $V$, there exists $H$ such that for every $n\in \mathbb{N}$ we know $n>H$ implies $a_n>V$. When $(a_n)$ diverges to infinity, we write $(a_n)\to \infty$.

Problem 78: (A Sequence Diverges To Infinity)

Prove that the sequence $(n^2)$ diverges to $+\infty$.

Problem 79: (Diverges To Negative Infinity)

Construct a definition of what it means to diverge to $-\infty$, by appropriately modifying the definition of diverges to $\infty$. Then prove that the sequence $(-n^3+2n)$ diverges to $-\infty$.

Problem 80: (DeMorgan's Laws For Sets)

Suppose that for each $j$ in some nonempty set $J$ that $A_j$ is a set, and also suppose that $B$ is a set. Pick one of the statements below and prove that it is true. The other is very similar.

• $\ds B\setminus \left(\bigcup_{j\in J}A_j\right) = \bigcap_{j\in J}\left(B\setminus A_j\right) $
• $\ds B\setminus \left(\bigcap_{j\in J}A_j\right) = \bigcup_{j\in J}\left(B\setminus A_j\right) $

Problem 81: (Additional Properties Of Cartesian Products)

Let $A$, $B$, $C$, and $D$ be sets. Prove or disprove each statement.

1. $(A\times B)\cap(C\times D) = (A\cap C)\times(B\cap D)$
2. $(A\times B)\cup(C\times D) = (A\cup C)\times(B\cup D)$

Definition (Interior And Closure)

Let $A$ be a subset of the real numbers.

• We use the notation $A'$ to denote the set of limit points of $A$.
• The closure of $A$, written $\text{cl}(A)$, is the union of $A$ and its limit points, so $\text{cl}(A) = A\cup A'$.
• The interior of $A$, written $\text{int}(A)$, is the collection of interior points of $A$.

Problem 82: (The Closure of $A$ Is a Closed Set.)

Let $A$ be a set. Prove that the closure of $A$ is a closed set.

Problem 83: (The Interior Is The Union Of Every Open Set Inside A Set)

Let $S^\circ$ be the union of every open set contained in $S$. Prove that $\text{int} (S)=S^\circ$.

Problem 84: (The Closure Is The Intersection Of Every Closed Set Containing A Set)

Let $\bar A$ be the intersection of every closed set that contains $A$. Prove that $\bar A=\text{cl}(A)$.

Exercise.Standard Induction Argument

We have proven many facts this semester about how to combine two things to obtain something new. There is a very standard induction argument that allows you to take a statement, like any of the ones below, and make the statement true for any finite number of things.

1. If $f$ and $g$ are surjective, then $f\circ g$ is surjective.
2. If $f$ and $g$ are injective, then $f\circ g$ is injective.
3. If $U$ and $V$ are open, then $U\cap V$ is open.
4. If $U$ and $V$ are closed, then $U\cap V$ is closed.
5. If $U$ and $V$ are open, then $U\cup V$ is open.
6. If $U$ and $V$ are closed, then $U\cup V$ is closed.
7. If $(a_n)$ converges to $A$ and $(b_n)$ converges to $B$, then $(a_n+b_n)$ converges to $A+B$.
8. If $(a_n)$ converges to $A$ and $(b_n)$ converges to $B$, then $(a_nb_n)$ converges to $AB$.
9. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.
10. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cup A_2)=f(A_1)\cup f(A_2)$.
11. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2)$.
12. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$.
13. If $x,y\in\mathbb{R}$ then $|x+y|\leq |x|+|y|$.
14. If $A,B,C$ are sets, then $(A\cap B)\times C = (A\times C)\cap(B\times C)$.
15. If $A,B,C$ are sets, then $(A\cup B)\times C = (A\times C)\cup(B\times C)$.
16. If $A,B,C$ are sets, then $A\setminus(B\cap C) = (A\setminus B)\cup(A\setminus C)$.
17. If $A,B,C$ are sets, then $A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$.
18. If $A,B,C$ are sets, then $A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$.
19. If $A,B,C$ are sets, then $A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$.

For more problems, see AllProblems