May

Please Login to access more options.

Today

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.

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$.

One of you asked the following question in your report. It's a great question, that gets at the heart of what it means to be a limit point. I decided to add it to the problem set.

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.)

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.

For more problems, see AllProblems