Module 1: Propositional/Predicate Calculus Review #

We start with the logical connectives and truth tables which interpret the connnectives. These are really to come back to.

Logical Connectives #

(\(\neg, \land, \lor, \Rightarrow, \Leftrightarrow\))

Comment: In truth tables, I will use 0 for False, and 1 for True.

NOTE: We will use \(\rightarrow\) and \(\Rightarrow\) which ARE DIFFERENT. \(\Rightarrow\) is “implies” while \(\rightarrow\) is just an arrow.

Comment: Here, note that false for P says nothing about Q. For example, the statement
"if you eat the cheeseburger, you will be full" says nothing about the scenario where you don’t eat the cheeseburger. In the cases where we can say nothing, the if statement “defaults” to true.

Comment: Note that every true/false pair is present. That is, we have every combination of P and Q being true/false. We have precisely \(2^n\) cases where n is the number of elements in the \( \{ \bold{P},\bold{Q} \dots \} \) set.

Tautologies & Contradictions #

A formula is said to be a tautology when its column in a truth table only consists of “trues”.

Example:

Tautology

A formula is said to be a contradiction when its column in a truth table only consists of “falses”.

Example:

Contradiction

Comment: Most formulas are neither tautologies nor contradictions.

Equivalent Formulas

We say that formulas \(\phi\) and \(\psi\) are equivalent when \((\phi \Leftrightarrow \psi)\) is a tautology. This is the case exactly when the columns in the truth tables for \(\phi\) and \(\psi\) match*.

*With the caveat that the tables contain the same propositional symbols.

Example:

  P and \(\neg \neg P\) are equivalent.

Example:

\((\neg P \land \neg Q)\) and \(\neg (P \lor Q)\) are equivalent.

\((\neg P \Rightarrow (Q \land \neg Q))\)

P and \((\neg P \Rightarrow (Q \land \neg Q))\) are equivalent.

Predicates v. Propositions A proposition is a statement/sentence that is either true or false and has no (free) variables.

Examples:

• \(\pi\) is an irrational number. (True)
• 13 is the sum of two perfect squares. (True: \(2^2 + 3^2\))
• 7587 is a prime number. (False: \(3^3 \cdot 281\))
• 14 is the best number. - Ambiguous/not well defined/not true/false (not a proposition)
• \(x^2 > 15\) — Free variable \(x\), truth value depends on \(x\), not a proposition.
• \(x^2 \geq 0\) — Free variable \(x\), not a proposition.
• For every real number \(x\), \(x^2 \geq 0\). (True: Here \(x\) is not a free variable, this is a proposition).
• There is a natural number \(x\) such that \(x^2 = 17\). (False)

Comments: In formulas, we use capital letters to represent propositions, and we can “build” more complex propositions by combining them using the logical connectives.

Using some algebra, show that \((P \Rightarrow Q)\) where

• P: “1=0”
• Q: “1=1”

Notice that in the third line, we used that Q is true. This might seem ambiguous right now, and that’s because it kind of is. In the future, we’ll use an equivalent statement known as the contrapositive which will verify the third line in a cleaner manner.

Also Notice we can show any two integers are equal if 0=1.

HOWEVER, we can make everything fall apart and very quickly. Assume we know there are two numbers that aren’t equivalent.

Assume that you know that \( 17 \not= 3 \)

R: “17=3”

\( \bold{\neg R: “17\not=3”}\)

It turns out there are many ways to come to a contradiction, but one way is to show \( (P \land Q \land R) \) is a contradiction.

Note: This choice of statement is often a problem in itself. There are equivalent statements to prove the same thing.

  A predicate is a statement with zero or more (free) variables that becomes a proposition when each (free) variable is assigned a value.

Examples: “\(\pi\) is an integer.” (Predicate with zero free variables/Proposition) (Also false)

“\(x^2 = 4\)” (Predicate with one variable: If \(x = 2\), true. If \(x = 17\), false.)

“\(x+y=7\)” (Predicate with two variables: If \(x = 1, y = 6\), true. If \(x=2, y=19\), false.)

Comments: We often use a “function-like” notation for predicates, using capital letters followed by the free variables in parentheses to represent predicates: e.g. \(P, R(x), Q(x,y),…\)

Common Sets: #

\(\emptyset = \{\}\) The Empty Set

\(\mathbb{N} = \{1, 2, 3, 4, 5, \dots\}\) The Natural Numbers

\(\omega = \{0, 1, 2, 3, 4, 5, \dots\}\) The Whole Numbers

\(\mathbb{Z} = \{\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots\}\) The Integers

\( \mathbb{Q} = \{ \frac{p}{q} \mid p \text{ and } q \text{ are integers and } q \neq 0 \} \) The Rational Numbers

\(\mathbb{P}\) The Irrational Numbers

\(\mathbb{R}\) The Real Numbers

\(\mathbb{C}\) The Complex Numbers

Comment: Only the value of a number determines what set(s) it is in, not how it is written. For example, the positive of \(\sqrt{16}\) is equal to 4, so it is in \(\mathbb{N}, \omega, \mathbb{Z}, \mathbb{Q}, \mathbb{R}\) and \(\mathbb{C}\).

Example:

\(\mathbb{Z}[i]\) “Gaussian integers” \(= \{ a + bi \mid a, b \text{ are integers} \} \)

• \(4 + 5i\) is in \(\mathbb{Z}[i]\)
• \(6 + \pi i\) is not in \( \mathbb{Z}[i] \)
• \(\frac{1}{2} - 3i\) is not in \( \mathbb{Z}[i] \)
• \(-2 + 3i\) is a Gaussian integer.

Intervals #

Intervals: Intervals are special types of sets of real numbers.

We will use the following as our definitions:

• \( (a,b) = \{x \in \mathbb{R} \mid a < x < b\} \)
• \( [a,b) = \{x \in \mathbb{R} \mid a \leq x < b\} \)
• \( (a,b] = \{x \in \mathbb{R} \mid a < x \leq b\} \)
• \( [a,b] = \{x \in \mathbb{R} \mid a \leq x \leq b\} \)
• \( (-\infty, b) = \{x \in \mathbb{R} \mid x < b\} \)
• \( (-\infty, b] = \{x \in \mathbb{R} \mid x \leq b\} \)
• \( (a, \infty) = \{x \in \mathbb{R} \mid a < x\} \)
• \( [a, \infty) = \{x \in \mathbb{R} \mid a \leq x\} \)
• \( (-\infty, \infty) = \mathbb{R} \)

Ex: \((1,5]\) has infinitely many elements, including 2,3,4,5, but also 1.036, \(\pi, \sqrt{2}, 2.7, 4.5,…\)

Also order matters:

\( [3,1) = \{x \in \mathbb{R} \mid 3 \leq x < 1 \} = \emptyset \)

vs

\( (1,3] = \{x \in \mathbb{R} \mid 1 < x \leq 3\}\) (Which is not the emptyset)

On the number line, \((1,3]\) is:

More examples:

\( [2,2] = \{x \in \mathbb{R} \mid 2 \leq x \leq 2\} = \{2\} \)

\( (2,2] = \{x \in \mathbb{R} \mid 2 < x \leq 2\} = \emptyset\)

Set Operations: #

Union: \(A \cup B = \{x \mid x \in A \lor x \in B\}\)

Intersection: \(A \cap B = \{x \mid x \in A \land x \in B\}\)

Difference: \(A \setminus B = \{x \mid x \in A \land x \notin B\}\)

Comment: While the union symbol “\(\cup\)” looks like the letter, it is not the same

(\(U\) is \(\underline{\text{not}}\) the union symbol)

Truth sets of Predicates #

Let \(P(x)\) be a predicate and let \(A\) be a set. The truth set of \(P(x)\) in \(A\) is:

\( TS_A(P(x)) = \{x \in A \mid P(x) \text{ is true}\} \)

This is the set of every value in the set \(A\) that makes \(P(x)\) true.

Example: Consider \(P(x)\) to be “\(-2 < x \leq 5\)”

\( TS_{\mathbb{N}}(P(x)) = \{1, 2, 3, 4, 5\} \)
\( TS_{\mathbb{W}}(P(x)) = \{0, 1, 2, 3, 4, 5\} \)
\( TS_{\mathbb{Z}}(P(x)) = \{-1, 0, 1, 2, 3, 4, 5\} \)
\( TS_{\mathbb{R}}(P(x)) = (-2, 5] \)
\( TS_{\emptyset}(P(x)) = \emptyset \)
\( TS_{\text{Primes}}(P(x)) = \{2, 3, 5\} \)
\( TS_{x^2 + 3x + 2 = 0}(P(x)) = \{ -1 \} \)

Notice that to be in \(TS_A(P(x))\), a value both needs to be in the set \(A\) and needs to make \(P(x)\) true.

Although we have different intervals that would yield the same evaluations, they are not the same. For example, when evaluating \( TS_{\mathbb{W}}(P(x))\) for \((-2,5] \text{ and } [-1,5]\), we get the same set, however, \((-2,5] \not= [-1,5]\)

An obvious observation.

Quantifiers #

A different manner in which we can convert a predicate into a proposition is by “bounding/quantifying” the free variables.

The Universal Quantifier #

The Universal Quantifier (\(\forall\))

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\forall x \in A) (P(x))\) is read “For every (all) \(x\) in \(A\), \(P(x)\).” and is true exactly when: \(TS_A (P(x)) = A\).

Example: \((\forall x \in \mathbb{N}) (x \geq 1)\) is true because: \(TS_{\mathbb{N}} (x \geq 1) = \mathbb{N}\)

\((\forall x \in \omega) (x \geq 1)\) is false because \(TS_{\omega} (x \geq 1) = \{1, 2, 3, …\} \neq \omega\)

Recall: The whole numbers have 0.

The Existential Quantifier #

The Existential Quantifier (\(\exists\))

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\exists x \in A) (P(x))\) is read “There exists/is an \(x\) in \(A\) such that \(P(x)\).”

and is true exactly when: \(TS_A (P(x)) \neq \emptyset\)

Example: \((\exists x \in \mathbb{N}) (x < 1)\) is false because \(TS_{\mathbb{N}} (x < 1) = \emptyset\)

\((\exists x \in \omega) (x < 1)\) is true because \(TS_{\omega} (x < 1) = \{0\} \neq \emptyset\)

\(TS_{\mathbb{N}}(x \geq 1) = \{1, 2, 3, \dots\} = \mathbb{N} \)
\(TS_{\omega}(x \geq 1) = \{1, 2, 3, \dots\} \neq \omega \)
\(TS_{\mathbb{N}}(x < 1) = \emptyset \)
\(TS_{\omega}(x < 1) = \{0\} \neq \emptyset\)

The Unique Existential Quantifier #

The Unique Existential Quantifier “\(\exists!\)”

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\exists!x \in A)(P(x))\) is read “There exists (is) a unique \(x\) in \(A\) such that \(P(x)\)”.

and is true exactly when \(|T S_A(P(x))| = 1\), i.e., when \(T S_A(P(x))\) has exactly one element.

Example: \((\exists!x \in \mathbb{N})(x < 1)\) is false because \(|T S_{\mathbb{N}}(x < 1)| = |\emptyset| = 0 \neq 1\)

\((\exists!x \in \omega)(x < 1)\) is true because \(|T S_\omega(x < 1)| = |\{0\}| = 1\)

\((\exists!x \in \mathbb{Z})(x < 1)\) is false because \(|T S_{\mathbb{Z}}(x < 1)| = |\{…, -2, -1, 0 \}| \neq 1\)

\((\exists!x \in \mathbb{N})(x < 4)\) is false because \(|T S_{\mathbb{N}}(x < 4)| = |\{1, 2, 3 \}| = 3 \neq 1\)

Comment: There are other quantifiers that can be used in addition to \(\forall\), \(\exists\), and \(\exists!\)

\(\exists!\) can be written using only \(\exists\) and \(\forall\):

\((\exists!x \in A)(P(x))\) is equivalent to:

\(\left( (\exists x \in A)(P(x)) \wedge (\forall x \in A)(\forall y \in A)((P(x) \wedge P(y)) \Rightarrow x = y)) \right)\)

An Interesting Case

For any predicate \(P(x)\), notice that: \(TS_\emptyset(P(x)) = \emptyset\).

This means that we have: \((\forall x \in \emptyset) (P(x))\) is true (no matter \(P(x)\))

and that we have: \((\exists x \in \emptyset) (P(x))\) is false (no matter \(P(x)\))

For example:

\((\forall x \in \emptyset) (x \neq x)\) is true

\((\exists x \in \emptyset) (x = x)\) is false

In any other universe/set \(A\):

\((\forall x \in A) (x \neq x)\) is false

\((\exists x \in A) (x = x)\) is true

Terminology: We say that \((\forall x \in \emptyset) (P(x))\) is vacuously true

\((\forall x \in \emptyset) (P(x)) \text{ is True}\)

\((\exists x \in \emptyset) (P(x)) \text{ is False}\)

\((\forall x \in \mathbb{Z}) (x \neq x)\)??

\(TS_{\mathbb{Z}}(x \neq x) = \emptyset \neq \mathbb{Z} \text{so False}\)

\((\exists x \in \mathbb{Z}) (x = x) \text{True}\)

\(TS_{\mathbb{Z}} (x = x) = \mathbb{Z} \neq \emptyset\)

Notation Comments:

In cases where the universe of discourse \(U\) is “understood” we may use the following notation:

\((\forall x \in U)(P(x))\) may be written: \((\forall x)(P(x))\) (Suppressing the \(U\))

\((\exists x \in U)(P(x))\) may be written: \((\exists x)(P(x))\)

As a general rule, avoid this shorthand especially when using multiple quantifiers bounding over different sets and when the universe isn’t clear.

Equivalencies: Let \(A \subseteq B\). Then, the following equivalencies hold:

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x \in B)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x \in B)(x \in A \land P(x))\)

As \(A \subseteq A\) for any set:

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x \in A)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x \in A)(x \in A \land P(x))\)

If we have an understood universe \(U\), and \(A \subseteq U\):

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x)(x \in A \land P(x))\)

Multiple Quantifiers #

Many statements will have multiple quantifiers. When this is the case, it is important to be very careful with the order.

To examine this idea:

\(P(x, y)\) is a predicate with two free variables \( x \text{ \& } y\)

\((\exists y \in B) (P(x, y))\) is a predicate with one free variable \((x)\)

\((\forall x \in A) (\exists y \in B) (P(x, y))\) is a proposition/predicate with no free variables.

Please note that \(\hat{x}\) is just another variable name like x or y or whatever.

\((\forall x \in A) (\exists y \in B) (P(x, y))\) is true exactly when:

\(TS_A \left( (\exists y \in B) (P(x, y)) \right) = A\)

That is, when:

\(\left\{ x \in A \mid (\exists y \in B) (P(x, y)) \right\} = A\)

so that for every \(\hat{x} \in A\), we have that \((\exists y \in B) (P(\hat{x}, y))\) is true,

and that for every \(\hat{x} \in A\), we have that:

\(TS_B \left( P(\hat{x}, y) \right) \neq \emptyset\).

This means if we choose some \(\hat{x} \in A\), we will be able to find a value of \(y \in B\) that makes \(P(\hat{x}, y)\) true. (And the choice of \(\hat{x} \in A\) doesn’t matter)

\(TS_A (\exists y \in B)(P(x,y)) \rightarrow\) The set of all \(x \in A\) for which \((\exists y \in B)(P(x,y))\) is true.

Notice that we just said the same statement like 5 times. Also, if you didn’t follow, it might be good to take a break at this point. Come back, and try again.

An Observation: Order Matters

\((\forall x \in \mathbb{R})\ (\exists y \in \mathbb{R})\ (x+y=0) \rightarrow True\)

\(x=4 \rightarrow y=-4\)

\(x=17.2 \rightarrow y = -17.2\)

\((\exists y \in \mathbb{R})\ (\forall x \in \mathbb{R})\ (x+y=0) \rightarrow False\)

To show

\((\exists y \in \mathbb{R})\ (\forall x \in \mathbb{R})\ (x+y=0) \rightarrow False\)

• Consider \(y=7\)

\((\forall x \in \mathbb{R})\ (x+7=0)\)

This is false.

• Consider \(y=0\)

\((\forall x \in \mathbb{R})\ (x+0=0)\)

This is false.

Indeed, for any y, x + y does not HAVE TO equal 0.

Reading the statement in English. “There exists a number (y) such that any (\(\forall\)) other number (x) satisfies x + y = 0”.

Notice we just flipped the statement order. That is, order matters. \((\forall x \in \mathbb{R})\ (\exists y \in \mathbb{R})\ (x+y=0) \rightarrow True\)

\((\exists y \in \mathbb{R})\ (\forall x \in \mathbb{R})\ (x+y=0) \rightarrow False\)

More examples

\((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x \leq y^2)\)

Consider \(x=1\)

\((\forall y \in \mathbb{R}) (1 \leq y^2) \rightarrow \text{False}\)

Consider \(x = -1\)

\((\forall y \in \mathbb{R}) (-1 \leq y^2) \rightarrow \text{True.}\)

This tells us that \(x = -1\) is in \(TS_{\mathbb{R}} ((\forall y \in \mathbb{R}) (x \leq y^2))\)

Thus, the truth set \(TS \neq \emptyset\)

\((\forall x \in \mathbb{R}) (\exists! y \in \mathbb{R}) (x+y=0) \rightarrow \text{True}.\)

\(\text{Next: } (\exists x \in A) (\forall y \in B) (P(x,y)) \text{ is true exactly when:}\) $$TS_A((\forall y \in B)(P(x,y))) \neq \emptyset$$ \(\text{That is, when there is at least one value of } x \in A \text{ such that }\) $$(\forall y \in B) (P(x,y)) \text{ is true.}$$ \(\text{Let } \hat{x} \in A \text{ be one of such values, i.e., so that } (\forall y \in B) (P(\hat{x},y)) \text{ is true. }\) This means that: $$TS_B (P(\hat{x},y)) = B$$ That is: $$\{y \in B \mid P(\hat{x},y) \} = B$$

\(\text{This means that for } \hat{x} \in A, \text{ we have that } P(\hat{x},y) \text{ is true for every } y \in B.\)

We will again consider:

\((\forall x \in \mathbb{R})\ (\exists y \in \mathbb{R})\ (x+y=0)\)
and
\((\exists y \in \mathbb{R})\ (\forall x \in \mathbb{R})\ (x+y=0)\)

• \((\forall x \in \mathbb{R})(\exists y \in \mathbb{R})(x+y=0)\) will be true if for every/any \(\hat{x} \in \mathbb{R}\) we can find a value \(y \in \mathbb{R}\) such that \(x+y=0\).

  ---

  • This is the case: For any \(\hat{x} \in \mathbb{R}\), we can let \(y = -\hat{x}\). Note that as \(\hat{x} \in \mathbb{R}\), \(-\hat{x}\) is also real so \(y \in \mathbb{R}\). Also: \(\hat{x} + y = \hat{x} + (-\hat{x}) = \hat{x} - \hat{x} = 0\).

    ---

    • e.g. If \(\hat{x} = 3\), we let \(y=-3\). If \(\hat{x} = -10.5\), we let \(y=10.5\).

• \((\exists y \in \mathbb{R})(\forall x \in \mathbb{R})(x+y=0)\) will be true if we can find some \(\hat{y} \in \mathbb{R}\) such that every \(x \in \mathbb{R}\) will make \(x + \hat{y} = 0\).

  ---

  • This is not the case! No matter what \(\hat{y} \in \mathbb{R}\) we choose, there is only one value of \(x\) that will give \(x + \hat{y} = 0\) (so we will not have \(x + \hat{y} = 0\) for every real number \(x\)).

    ---

    • e.g. If we tried letting \(\hat{y} = 3\), it will not be the case that \((\forall x \in \mathbb{R})(x + 3 = 0)\) will be true.

Checking an equivalence with a truth table #

The equivalence \(A\) is equiv. to \((\neg A \Rightarrow (B \wedge \neg B))\) (listed below, and used later for proofs by contradiction) can be verified directly: the columns for \(A\) and for \((\neg A \Rightarrow (B \wedge \neg B))\) match.

Example:

A. \((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y)\)
vs
B. \((\forall y \in \mathbb{R}) (\exists x \in \mathbb{R}) (x + y = y)\)

A.

• \((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y) \text{ is true:}\)

  ---

  • Notice that: \(TS_{\mathbb{R}}(0 + y = y) = \mathbb{R}\)

    ---

    • so that: \((\forall y \in \mathbb{R}) (0 + y = y) \text{ is true.}\)

      ---

This means that when \(x = 0\), \((\forall y \in \mathbb{R}) (x + y = y) \text{ is true.}\) \(x=0\) is in the truth set or satisfies \((\forall y \in \mathbb{R}) (x + y = y)\).

This tells us that \(TS_{\mathbb{R}}((\forall y \in \mathbb{R}) (x + y = y)) \neq \emptyset\), so that:

\((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y) \text{ is } \underline{\text{true}}.\)

B.

• \((\forall y \in \mathbb{R}) (\exists x \in \mathbb{R}) (x + y = y) \text{ is also true:}\)
  • No matter what value of \(\hat{y} \in \mathbb{R}\) that we choose, notice that \(0 + \hat{y} = \hat{y},\)
    • so that \(0\) is in \(TS_{\mathbb{R}} (x + \hat{y} = \hat{y})\), so that \(TS_{\mathbb{R}} (x + \hat{y} = \hat{y}) \neq \emptyset\).

This gives us that \((\exists x \in \mathbb{R}) (x + \hat{y} = \hat{y}) \text{ is true.}\)

As the choice of \(\hat{y} \in \mathbb{R}\) didn’t matter, and \(\hat{y}\) is in the truth set of \((\exists x \in \mathbb{R})(x + y = y)\),

we have that \(TS_{\mathbb{R}}((\exists x \in \mathbb{R})(x + y = y)) = \mathbb{R}\), and:

\((\forall y \in \mathbb{R}) (\exists x \in \mathbb{R})(x + y = y) \text{ is } \underline{\text{true}}\).

Less formally, from left to right, for any y \((\forall y \in \mathbb{R}) \), choose x = 0 \((\exists x \in \mathbb{R})\) and the equation is true.

A Few Important Equivalencies #

• \((A \Rightarrow B)\) is equiv. to: \((\neg B \Rightarrow \neg A)\) (the contraposition)

  • and also: \((\neg A \vee B)\)

• \(\neg (A \vee B)\) is equiv. to: \((\neg A \wedge \neg B)\) } De Morgan’s Laws

• \(\neg (A \wedge B)\) is equiv. to: \((\neg A \vee \neg B)\) } De Morgan’s Laws

• \(A \wedge (B \vee C)\) is equiv. to: \(((A \wedge B) \vee (A \wedge C))\) } Distribution

• \(A \vee (B \wedge C)\) is equiv. to: \(((A \vee B) \wedge (A \vee C))\) } Distribution

• \(\neg (A \Rightarrow B)\) is equiv. to: \((A \wedge \neg B)\)

• \((\neg A \Rightarrow (B \wedge \neg B))\) is equiv. to: \(A\)

• \(A \Rightarrow (B \vee C)\) is equiv. to: \((A \wedge \neg B) \Rightarrow C\)

• \((A \vee B) \Rightarrow C\) is equiv. to: \((A \Rightarrow C) \wedge (B \Rightarrow C)\)

• \(A \Rightarrow (B \wedge C)\) is equiv. to: \((A \Rightarrow B) \wedge (A \Rightarrow C)\)

• \(A \Rightarrow (B \Rightarrow C)\) is equiv. to: \((A \wedge B) \Rightarrow C\)

• \(\neg (\forall x \in A)(P(x))\) is equiv. to: \((\exists x \in A)(\neg P(x))\)

• \(\neg (\exists x \in A)(P(x))\) is equiv. to: \((\forall x \in A)(\neg P(x))\)

• \(\neg \neg A\) is equiv. to: \(A\) (Double negation)

A computation of a negation #

A computation of a negation

\( \neg (\forall x \in A) (P(x) \Rightarrow Q(x)) \)
\( \left(\exists x \in A\right) \left(\neg \left(P(x) \Rightarrow Q(x)\right)\right) \)
\( \left(\exists x \in A\right) \left(P(x) \wedge \neg Q(x)\right) \)

Notice we use the equivalency of: \( \neg (A \Rightarrow B) \) and \((A \wedge \neg B)\).

Breakdown

\( \neg (\forall x \in A) (P(x))\) is true exactly when \( (\forall x \in A) (P(x)) \text{ is false.} \)
 \(\text{is true exactly when | } TS_A (P(x)) \neq A\)
 \(\text{is true exactly when | there is some value } \hat{x} \in A \text{ s/t } P(x) \text{ is not true.}\)
 \(\text{is true exactly when | there is some value } \hat{x} \in A \text{ s/t } P(x) \text{ is false} \)
 \(\text{is true exactly when | } \text{ there is some } \hat{x} \in A \text{ s/t } \neg P(x) \text{ is true.}\)
 \(\text{is true exactly when | } \text{ there is some } \hat{x} \in A \text{ is } TS_A (\neg P(x)).\)
 \(\text{is true exactly when | } TS_A (\neg (P(x))) \neq \emptyset \)
 \( \text{is true exactly when | } (\exists x \in A) (\neg P(x)) \text{ is true.}\)

As well, \( \neg (\exists x \in A) (P(x)) \) and \((\forall x \in A) (\neg P(x))\) are equivalent.

Simplifying Denials/Negations. #

Goal: We want the only instances of the negation symbol “\(\neg\)” immediately preceding the predicate/propositional symbols.

Example:
\(\neg (\forall x \in A)(\forall y \in B)(\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z)))\)

\((\exists x \in A)(\neg (\forall y \in B)(\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\neg (\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\forall z \in C)(\neg ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\forall z \in C)((P(x) \vee Q(y)) \wedge \neg R(x, y, z))\)

Example:
\(\neg (\exists a \in A)(\forall b \in B)(\exists c \in C)(\neg P(a) \vee (R(b) \Rightarrow S(c)))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(\neg(\neg P(a) \vee (R(b) \Rightarrow S(c))))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(\neg \neg P(a) \wedge \neg (R(b) \Rightarrow S(c)))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(P(a) \wedge (R(b) \wedge \neg S(c)))\)

Example: We will find/simplify a denial/negation of
\((\exists! x \in A) (P(x))\)

\(\neg (\exists! x \in A) (P(x))\) is equivalent to: \(\neg \left( (\exists x \in A) (P(x)) \wedge (\forall y \in A) (\forall z \in A) ((P(y) \wedge P(z)) \Rightarrow y=z) \right) \) *
\(\neg (\exists x \in A) (P(x)) \vee \neg (\forall y \in A) (\forall z \in A) ((P(y) \wedge P(z)) \Rightarrow y = z) \)
\((\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) \neg ((P(y) \wedge P(z)) \Rightarrow y = z) \)
\((\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) ((P(y) \wedge P(z)) \wedge \neg (y = z)) \)
\((\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) (P(y) \wedge P(z) \wedge y \neq z))\)
* We used this in the first step.

In english, the statement is: “Either every \( x \in A\) makes \(P(x)\) false or there are two values (or more) that make \(P\) true that are different.”

Comment (Associativity & Commutativity):
\((A \wedge B) \wedge C\) is equiv. to \(A \wedge (B \wedge C)\) and \(A \wedge B \wedge C\)
\((A \vee B) \vee C\) is equiv. to \(A \vee (B \vee C)\) and \(A \vee B \vee C\) (Associativity)
\(A \wedge B\) is equiv. to \(B \wedge A\)
\(A \vee B\) is equiv. to \(B \vee A\) (Commutativity)

Short Exercises: #

Verify that an implication \((A \Rightarrow B)\) and the converse \((B \Rightarrow A)\) are not equivalent.

In this section you have to show that when you have 0 = 1, 1=1, you can’t have 17 = 3. Give another statement that if proved, would show such a thing.

Show that \((\forall x \in \mathbb{R}) (\exists! y \in \mathbb{R}) (x+y=0) \rightarrow \text{True}\) from this section.

Show the equivalency of: \( \neg (A \Rightarrow B) \) and \((A \wedge \neg B)\) from this section.

Module 2: Equivalent Statements & Proofs #

A (mathematical) theorem is a statement/sentence that describes a relationship/pattern between mathematical objects & structures.

A theorem will be a proposition (i.e., a statement that is either true or is false), and can then be written in a “Logical Form” (LF) using predicate calculus.

(* Generally a “theorem” is known to be true and has a “proof” as justification)

Examples:

“\(\sqrt{2}\) is irrational”
L.F.: P (P is “\(\sqrt{2}\) is irrational”)

“There are real numbers \(x\) and \(y\) such that \(x+y = 10\)."
L.F.: \((\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(P(x,y))\) (\(P(x,y)\) is “\(x+y = 10\)”)

“There are (two) whole numbers whose product is 15."
L.F.: \((\exists a \in \mathbb{W})(\exists b \in \mathbb{W})(P(a,b))\) (\(P(a,b)\) is “\(ab = 15\)”)

“Let \(a\) be a real number. Either \(a^2 > 0\) or \(a = 0\)."
L.F.: \((\forall a \in \mathbb{R})(P(a) \lor Q(a))\)
P(a) is \(“a^2 > 0”\)
Q(a) is “a = 0”

“Every natural number greater than or equal to 11 can be written in the form \(2s + 5t\) for some natural numbers \(s\) and \(t\)."
L.F.: \((\forall n \in \mathbb{N})(P(n) \implies (\exists s \in \mathbb{N})(\exists t \in \mathbb{N})(Q(n, s, t)))\)
P(n) is \(“n \geq 11” \)
Q(n, s, t) is \(“2s + 5t = n”\)

Proofs #

A proof is a logical justification/verification of the truth of a theorem.

Our proofs will be written in full (English) sentences with proper grammar and punctuation.

• This means in paragraph form and not as a bulleted list. (Some “mathese”/math notation will (usually) appear.)

Our proofs will be stand-alone:

• The reader should be able to begin reading at the start of the proof, not needing to know any prior information, and understand what is being proved.

Every proof must begin with: “Proof:”

Every proof must end with one of the following in the bottom right:

\(\blacksquare, \square, \triangle, QED\)

“Quod Erat Demonstrandum”

General Structure/Outline:
Proof:
(Set-up/un-weaving” quantifiers)
(Get to a point where you are needing to show/prove a “quatifier-free” statement)
(Logical Reasoning/Definitions to show statement)
(Re-weave quantifiers)
(Conclude with original/full statement of theorem.
\(\blacksquare, \square, \triangle, QED\) at the end.

Example: We will prove \((\forall x \in \mathbb{Z})(\exists y \in \mathbb{Z})(x + y = 0)\).

Proof: Let \(x\) be an arbitrary integer. Let \(y = -x\). As \(-x = (-1)(x)\) and \(-1\) and \(x\) are integers, and the integers are closed under multiplication, \(-x\) is an integer, so \(y\) is an integer. Now: \(x + y = x + (-x) = x - x = 0\). Hence \(x + y = 0\). As \(y\) is an integer, there exists an integer \(y\) such that \(x + y = 0\). As \(x\) was arbitrary, for all integers \(x\), there exists an integer \(y\) such that \(x + y = 0\). QED.

In a proof, the following are always allowed:

• State an axiom/postulate (i.e., statements that are given to be true without needing additional justification)

  • For example: “Closure” Properties of \(\mathbb{N}, \mathbb{W}, \mathbb{Z}, \mathbb{Q} \) and \(\mathbb{R}\)
    “Lower Bound” Properties of \(\mathbb{N}\) and \(\mathbb{W}\)

• State tautologies

  • For example (if U = Z): “Either x is odd or x is not odd” \((P \vee \neg P)\)

• State any assumptions that you are making

  • “Assume that…”
  • “Suppose that…"
    Note: Make sure you don’t assume what you want to show.

• State something you wrote earlier in the proof (possibly in a different but equivalent way).

• Use algebraic manipulation to re-write equations/inequalities/expressions/etc… in equivalent ways.

• State a “previously proven result.”

• Use a definition to re-write a statement in an equivalent way.

  • (A definition is a statement/predicate that gives a precise/unambiguous meaning to a concept/term.)

• Use “Modus Ponens” to make deductions.

  • If you have both A and (A \(\implies\) B), then you may conclude/state you have B.

When writing a proof of a theorem:

• Determine/write the logical form (in predicate calculus) of the theorem.
• This form should have no free-variables. If a quantifier is “hidden”/“isn’t clearly stated”, it is most likely the universal quantifier “\(\forall\)”.

“Identifying Phrases”:

• “\(\forall\)”: Every, All, Each, Let \(x\) be, …
• “\(\exists\)”: There is, There exists, For some, …

Key Idea: “The structure of a proof of a theorem will follow the structure of the logical form or of an equivalent logical form of the theorem.”

To Show/Prove \((\forall x \in \mathcal{U}) (P(x))\):

• “Let \(x\) in \(\mathcal{U}\) be arbitrary.” or “Fix an arbitrary \(x\) in \(\mathcal{U}\).”
• Show/Prove \(P(x)\).

To Show/Prove \((\exists x \in \mathcal{U}) (P(x))\):

• Use scratch work to find a value of \(x\) in \(\mathcal{U}\) that makes \(P(x)\) true.
• “Let \(x = \) (the value you found in scratch work).” or “Define \(x\) to be the value you found in scratch work).”
• Show/State that \(x\) is in \(\mathcal{U}\).
• Show/Prove \(P(x)\)

To Show/Prove \((A \Rightarrow B)\):

• “Assume A.” OR “Suppose A.”
• Show B.

Note: If we are assuming/supposing a statement, we take it as true and do not need to show/prove it.

• If we assume \((\forall x \in \mathbb{U})(P(x))\), then any \(x\) in \(U\) will make \(P(x)\) true.
• If we assume \((\exists x \in \mathbb{U})(P(x))\), then we can let \(\hat{x}\) be some element of \(U\) that makes \(P(x)\) true (we say \(\hat{x}\) is a “witness”).

Example Outline: \((\forall x \in \mathbb{R})(\forall y \in \mathbb{R}) (x < y \Rightarrow (\exists w \in \mathbb{R})(x < w < y))\)

Proof: Let \(x\) and \(y\) be arbitrary real numbers. Suppose \(x < y\).

Let \(w = \dots\) (found in scratch work). Notice that \(\dots\) so that \(w\) is a real number.

Now, \(\dots\)

“Weaving” back to the full theorem.
Hence, \(x < w < y\). Therefore, as \(w\) is a real number, there exists a real number \(w\) such that \(x < w < y\). Hence, if \(x < y\), then there exists a real number \(w\) such that \(x < w < y\). As \(x\) and \(y\) were arbitrary, for all real numbers \(x\) and \(y\), if \(x < y\), there exists a real number \(w\) such that \(x < w < y\). \(\square\)

Example Outline: \((\exists x \in \omega) (\forall y \in \omega) (x \leq y)\)

Proof: Let \(x = \dots\) (Found in scratch work). Note that \(\dots\), so we have that \(x\) is a whole number. Let \(y\) be an arbitrary whole number.

Now \(\dots\):

Hence, \(x \leq y\). As \(y\) was arbitrary, for all whole numbers \(y\), \(x \leq y\).

As \(x\) was a whole number, there exists a whole number \(x\) such that for all whole numbers \(y\), \(x \leq y\) . \( \square\)

Example Outline: \((\forall x \in \mathbb{Q}) (\exists y \in \mathbb{Q}) (x + y = 0)\)

Proof: Let \(x\) be an arbitrary rational number. Let \(y = \dots\) (Found in scratch work and may “depend” on \(x\)). Note that \(\dots\), so we have that \(y\) is rational.

Now, \(\dots\):

Hence, \(x + y = 0\). As \(y\) is a rational number, there exists a rational number \(y\) such that \(x + y = 0\). As \(x\) was arbitrary, for all rational numbers \(x\), there exists a rational number \(y\) such that \(x + y = 0\).\( \square\)

“Divides” Definition & Notation #

(for integers / \(\mathbb{Z}\))

Divisibility is a classical problem in number theory and in general.

Let \(a\) and \(b\) be integers.

We say “\(a\) divides \(b\)” and we write \(a|b\) exactly when there is an integer \(k\) such that \(b=ak\).

Logical Form: \(a|b\) iff \((\exists k \in \mathbb{Z}) (b=ak)\)

We say \(b\) is even iff \(2|b\) iff \((\exists k \in \mathbb{Z}) (b=2k)\)

We say “\(a\) does not divide \(b\)” and write \(a\nmid b\) exactly when there is an integer \(k\) and a natural number \(r\) such that \(r<a\) and such that \(b=ak+r\). (\(r\) is called the remainder.)

Logical form: \(a\nmid b\) iff \((\exists k \in \mathbb{Z}) (\exists r \in \mathbb{N}) (r<a \wedge b=ak+r)\)

Comment: We can “break” this up by either:

\((\exists k \in \mathbb{Z}) (b=ak+1 \vee b=ak+2 \vee \dots \vee b=ak+(a-1))\)

\((\exists k \in \mathbb{Z}) (b=ak+1) \vee (\exists k \in \mathbb{Z}) (b=ak+2) \vee \dots \vee (\exists k \in \mathbb{Z}) (b=ak+(a-1))\)

We say \(b\) is odd iff \(b\) is not even iff \(2 \nmid b\) iff \((\exists k \in \mathbb{Z}) (b=2k+1)\)

Example: We will prove the theorem “If \(3|x\), then \(3|x^{2}\)”.

• As we have a “hidden” quantifier, we will use the universal for \(x\). (we cannot have a free variable in our logical form)

• The “divides” notation indicates \(x\) will be an integer. (Note: This notation could be used for subsets of \(\mathbb{Z}\), such as \(\mathbb{N}\) and \(\mathbb{W}\), but without specification, it is assumed to be on integers)

Logical Form: \((\forall x \in \mathbb{Z}) (3|x \Rightarrow 3|x^{2})\)

Our Outline: Proof: Let \(x\) be an arbitrary integer. Assume that \(3|x\).

Now, … (We need to fill this part in.)

Hence, \(3|x^2\). Thus, if \(3|x\), then \(3|x^2\). As \(x\) was arbitrary, for all integers \(x\), if \(3|x\), then \(3|x^2\). QED.

Strategy: We have that \(3|x\) and need to get to \(3|x^2\). By using the definition of divides we can rewrite these in different but equivalent ways:
\(3|x\) iff there is some integer \(k\) such that \(x = 3k\)
\(3|x^2\) iff there is some integer \(j\) such that \(x^2=3j\)

This means we need to get from \(x = 3k\) to \(x^2 = 3j\). Also, as we have assumed \(3|x\), we know that there is an integer \(k\) such that \(x = 3k\).
For \(3|x^2\), we need to find an integer \(j\) such that \(x^2 = 3j.\)

Some examples of the “divides” / “does not divide” definitions:

Now, as we have \(x = 3k\) (for some integer \(k\)), we will use this to “examine” \(x^2\):

\(x^2 = (3k)^2 = 9k^2 = 3(3k^2)\)

\( \uparrow \text{ This is the “j” we need. }\)

If we set \(j = 3k^2\), then we have \(x^2 = 3j\). However: We need \(j\) to be an integer.

Closure Properties: \(\mathbb{Z}\) is closed under addition, subtraction, and multiplication. This means that if \(a\) and \(b\) are integers, \(a + b\), \(a - b\), and \(ab\) are all also integers. (\(\mathbb{Z}\) is not closed under division).

As \(3\) is an integer and as \(k\) is an integer, \(3k^2\) is also an integer as the integers are closed under multiplication. (Hence, we do have that \(j\) is an integer.)

We can now put the whole proof together:

Proof: Let \(x\) be an arbitrary integer. Assume that \(3 | x\). Now, there exists an integer \(k\) such that \(x = 3k\). Now: \(x^2 = (3k)^2 = 9k^2 = 3(3k^2)\).

As \(3\) and \(k\) are integers and as the integers are closed under multiplication, \(3k^2\) is an integer. Let \(j = 3k^2\). Notice that \(x^2 = 3j\) and that \(j\) is an integer by our previous comments. Hence, \(3 | x^2\). Thus, if \(3 | x\), then \(3 | x^2\). As \(x\) was arbitrary, for all integers \(x\), if \(3 | x\), then \(3 | x^2\). QED.

In many cases, the “logical reasoning” portion of a proof / the part that needs to be filled in after forming the outline could be very difficult. In these cases it may be helpful to find an equivalent statement to prove instead of the original. (as equivalent statements are true exactly at the same time, if you have shown one, you have also shown the other.)

Contraposition: #

Recall that (\(A \Rightarrow B\)) is equivalent to (\(\neg B \Rightarrow \neg A\))

To Prove \(A \Rightarrow B\) by contraposition:

• Assume/suppose \(\neg B\) (i.e., that B is false)
• Show/prove \(\neg A\) (i.e., that A is false)
• Conclude “If \(\neg B\), then \(\neg A\).”
• State that by contraposition, if \(A\), then \(B\).

Example: We will prove “If \(x^2\) is even, then \(x\) is even.”

Logical Form: \((\forall x \in \mathbb{Z}) (2 | x^2 \Rightarrow 2 | x)\)

Initial Outline Attempt: Proof: Let \(x\) be an arbitrary integer. Suppose \(x^2\) is even.

Now,…

Hence \(x\) is even. Thus, if \(x^2\) is even, then \(x\) is even.

As \(x\) was arbitrary, for all integers \(x\), if \(x^2\) is even, then \(x\) is even. QED.

For this attempt, we have that \(x^2 = 2k\) for some integer \(k\) (such a value does exist as we assume \(x^2\) is even). We need to show that there is an integer \(j\) such that \(x=2j\) (we’ll need to find this value).

If we had \(x = 2j\), then we could use substitution to write \(x^2 = (2j)^2\), but here we have \(x^2 = 2k\) and we need to somehow get \(x\) from this.

\(\frac{k}{x}\) need not be in \(\mathbb{Z}\) as \(\mathbb{Z}\) not closed under division, and don’t know that \(x\neq 0\).

\(\sqrt{\frac{k}{2}}\) may not be in \(\mathbb{Z}\) (\(\mathbb{Z}\) not closed under division nor under square roots).

Essentially, we can’t guarentee the set inclusion and proving that the square root is in the integers is too much trouble.

Instead, we can use contraposition:

\((\forall x\in \mathbb{Z})(2 \nmid x^2 \implies 2\nmid x)\) is equivalent to: \((\forall x \in \mathbb{Z})(2 \mid x \implies 2\mid x^2)\).

Outline: Proof: Let \(x\) be an arbitrary integer. Suppose \(x\) is not even. Now,… . Hence, \(x^2\) is not even. Thus, if \(x\) is not even, then \(x^2\) is not even. By contraposition, if \(x^2\) is even, then \(x\) is even. As \(x\) was arbitrary, for all integers \(x\), if \(x^2\) is even, then \(x\) is even. QED.

With this outline, our assumption is now that \(x\) is not even (is odd), so we know that there is an integer \(k\) such that \(x = 2k+1\).

We need to show that \(x^2\) is not even, i.e., that \(x^2\) is odd, i.e., that there is some integer \(j\) such that \(x^2 = 2j+1\). (Goal: Find this integer \(j\))

As \(x = 2k+1\):

\((2k^2 + 2k)\) will be the \(j\) that we need.

If \(j = 2k^2 + 2k\), we have that \(x^2 = 2j + 1\). We still need to confirm/show that \(j\) is an integer. As both 2 and \(k\) are integers, and as the integers are closed under multiplication and addition, \(2k^2 + 2k\) is an integer, so that \(j\) is an integer.

Putting this together:

Proof: Let \(x\) be an arbitrary integer. Suppose \(x\) is not even. Then \(x\) is odd so that there is some integer \(k\) such that \(x=2k+1\). Now:

As 2 and \(k\) are integers and as the integers are closed under multiplication and addition, \(2k^2 + 2k\) is an integer. Let \(j = 2k^2 + 2k\). Notice that \(x^2 = 2j+1\) and that \(j\) is an integer by our previous comments. Hence, \(x^2\) is odd, and is therefore not even. Thus, if \(x\) is not even, then \(x^2\) is not even. By contraposition, if \(x^2\) is even, then \(x\) is even. As \(x\) was arbitrary, for all integers \(x\), if \(x^2\) is even, then \(x\) is even. QED.

To Show/Prove (\(A \land B\)):

• Show/Prove A
• Show/Prove B
• Conclude (\(A \land B\))

To Show/Prove (\(A \iff B\)): We generally use the equivalence:

• (\(A \iff B\)) is equivalent to: ((\(A \implies B\)) \(\land\) (\(B \implies A\)))

By this equivalence:

• Show (\(A \implies B\)):

  • Assume \(A\), then show/prove \(B\).
  • Use contrapositive: (\(\neg B \implies \neg A\)).

• Show (\(B \implies A\)):

  • Assume \(B\), then show/prove \(A\).
  • Use contrapositive: (\(\neg A \implies \neg B\)).

• “We have shown both directions of the biconditional, hence A iff B.”

To show or prove that \(A \iff B\), we typically show both implications: Note: There is another method, a “biconditional proof”, that is a string of equivalent statements: \(A\) iff \(A_1\) iff \(A_2\) iff \(A_3\) iff … iff \(B\). This method is not generally recommended initially as it is much easier to have an error.

Outline: Proof: (Set-up)

• (\(\implies\)) Suppose A. Now… Hence, B. Therefore, if A, then B.
• (\(\impliedby\)) Suppose B. Now… Hence, A. Therefore, if B, then A.

We have proven both directions of the biconditional, hence A iff B. \(\Box\)

Example: We will prove “\(2|n \iff 2|n^2\)”.

Logical Form: \((\forall n \in \mathbb{Z}) (2|n \iff 2|n^2)\)

This is equivalent to: \((\forall n \in \mathbb{Z})((2|n \implies 2|n^2) \land (2|n^2 \implies 2|n))\)

In our previous example, we used contraposition to show \((2|n^2 \implies 2|n)\), so we will do the same here, and we will use the following equivalent form.

\((\forall n \in \mathbb{Z}) ((2|n \implies 2|n^2) \land (2 \nmid n \implies 2 \nmid n^2))\)

Proof: Let \(n\) be an arbitrary integer.

\((\implies)\) Suppose \(2|n\). Then \(n = 2k\) for some integer \(k\). Now:

\(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\).

As 2 and \(k\) are integers, and as the integers are closed under multiplication, \(2k^2\) is an integer. Let \(j = 2k^2\). Notice that \(n^2 = 2j\) and that \(j\) is an integer by our previous comments. Hence \(2|n^2\). Thus, if \(2|n\), then \(2|n^2\).

\((\impliedby)\) Now, suppose \(2 \nmid n\). Then, there is some integer \(k\) such that \(n = 2k + 1\). Now:

\(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\).

As 2 and \(k\) are integers and as the integers are closed under multiplication and addition, \(2k^2 + 2k\) is an integer. Let \(j = 2k^2 + 2k\). Notice that \(n^2 = 2j + 1\) and that \(j\) is an integer by our previous comments. Hence, \(2 \nmid n^2\). Thus, if \(2 \nmid n\), then \(2 \nmid n^2\). By contraposition, if \(2|n^2\), then \(2|n\).

We have shown both directions of the biconditional, hence \(2|n\) iff \(2|n^2\). As \(n\) was arbitrary, for all integers \(n\), \(2|n\) iff \(2|n^2\). QED

Contradiction #

Now, recall the equivalence:

\(A\) is equivalent to (\(\neg A \Rightarrow (B \land \neg B)\))

In many cases, if we are trying to prove/show a theorem A, it may be easier to prove the above equivalent statement.

This is called a proof by contradiction (Notice that \((B \land \neg B)\) is a contradiction)

To Prove A by Contradiction:

• Assume \(\neg A\), i.e., assume A is false.
• Show/prove B
• Show/prove \(\neg B\) (i.e., that B is false)
• “This is a contradiction, hence A (is true).”

Comments: This method is often used if the logical form is just “A” (without any logical connectives)

• If A is more “complex” this method still can be used.

Suppose A is of the form \((X \Rightarrow Y)\):

\(A\) is equiv. to: \((\neg A \Rightarrow (B \land \neg B))\)

is equiv. to: \((\neg (X \Rightarrow Y) \Rightarrow (B \land \neg B))\)

is equiv. to: \(((X \land \neg Y) \Rightarrow (B \land \neg B))\)

Here, to assume \(\neg A\), we assume \(X\) is true and \(Y\) is false.

• It may take some work/playing around to determine the “B” that will give you the contradiction.

Example: We will prove the theorem: “\(\sqrt{2}\) is irrational”

The logical form of this theorem is just: \(P\)

We will prove the equivalent: \((\neg P \implies (B \land \neg B))\)

Initial Proof Outline:

Proof: Suppose \(\sqrt{2}\) is not irrational. Then \(\dots\)
\(\vdots\)

Hence, \(B\) (which we still need to determine)
\(\vdots\)

Thus, \(\neg B\).

This is a contradiction. Therefore, \(\sqrt{2}\) is irrational. \(\square\)

For this example, we will use the following:

• Every rational number can be written in the form \(\frac{p}{q}\) where \(p\) and \(q\) are integers (with \(q \neq 0\)) and \(p\) and \(q\) have no common factors greater than 1 (i.e., \(\frac{p}{q}\) is in lowest terms).

• “Our previous result”: \((\forall n \in \mathbb{Z}) (2 \mid n^2 \iff 2 \mid n)\)

Proof: Towards a contradiction, suppose that \(\sqrt{2}\) is not irrational. Then, we have that \(\sqrt{2}\) is rational, so that there exist integers \(a\) and \(b\), with \(b \neq 0\), such that

and \(a\) and \(b\) have no common factors greater than 1. Now, as \(\sqrt{2} = \frac{a}{b}\), we have that \(b\sqrt{2} = a\), so that \((b\sqrt{2})^2 = a^2\), and \(2b^2 = a^2\). As \(b\) is an integer, and as the integers are closed under multiplication, \(b^2\) is an integer. Hence, \(2|a^2\). By our previous result, as \(a\) is an integer and \(2|a^2\), we have that \(2|a\). Hence, there is some integer \(k\) such that \(a=2k\).

Now, as \(2b^2 = a^2\) and \(a=2k\), we have that \(2b^2 = (2k)^2\) so that \(2b^2 = 4k^2\), and \(b^2 = 2k^2\). As \(k\) is an integer, and as the integers are closed under multiplication, \(k^2\) is an integer. Hence, \(2|b^2\). Again, by our previous result, as \(b\) is an integer and \(2|b^2\), we have that \(2|b\). Notice that we have that \(2|a\) and \(2|b\). Hence, \(a\) and \(b\) have a common factor, greater than 1 (namely 2). This is a contradiction; hence, we have that \(\sqrt{2}\) is irrational.

\(\blacksquare\)

Proof By Cases: #

Recall that we have the following equivalence:

Note: This can be extended:

etc…

For some theorems of the form \((A \Rightarrow B)\), we may be able to “break-up” the antecedent \(A\) into “more precise” propositions connected by “\(\lor\)” (OR)

For example:

• (n is an integer) can be written: (n is even) \(\lor\) (n is odd)
• (x is a real number) can be written: (x is a positive real number) \(\lor\) (x = 0) \(\lor\) (x is a negative real number)

If we can rewrite \((A \Rightarrow B)\) as \(((A_1 \lor A_2) \Rightarrow B)\), then we can prove the equivalent: \(((A_1 \Rightarrow B) \land (A_2 \Rightarrow B))\):

• Prove/Show \(A_1 \Rightarrow B\)
• Prove/Show \(A_2 \Rightarrow B\)

Comment: As \(A_1\) & \(A_2\) are more precise, when you are assuming them, you will have more information to work with.

Using these equivalencies is called a “Proof by Cases”

Outline: If (\(A \Rightarrow B\)) can be written as ((\(A_1 \lor A_2 \lor A_3\)) \(\Rightarrow\) B) : Here we have three “cases”

Proof: Suppose A. We will consider (three) cases.

• Case 1 (\(A_1\)): Suppose \(A_1\). Then…. Hence, B.

  • Therefore, if \(A_1\), then B.

• Case 2 (\(A_2\)): Suppose \(A_2\). Then…. Hence, B.

  • Therefore, if \(A_2\), then B.

• Case 3 (\(A_3\)): Suppose \(A_3\). Then…. Hence, B.

  • Therefore, if \(A_3\), then B. These cases are exhaustive. Hence, B. Therefore, if A then B.

\(\boxtimes\)

Comment: Recall we mentioned that (\(\forall x \in \mathcal{U}\))(P(x)) is equivalent to

(\(\forall x \in \mathcal{U}\))(\(x \in \mathcal{U} \Rightarrow P(x)\)).

If we can break-up \(x \in \mathcal{U}\) into cases, we can use this method here as well.

Example: We will prove the theorem: \((\forall n \in \mathbb{Z}) (3 \nmid n \implies 3 \nmid n^2)\)

Recall that we have \(3 \nmid n\) is equivalent to/defined to be:

\(\big( (\exists k \in \mathbb{Z}) (n = 3k + 1) \lor (\exists k \in \mathbb{Z}) (n = 3k + 2) \big)\) Case 1 or Case 2 respectively.

Proof: Let \(n\) be an arbitrary integer. Suppose \(3 \nmid n\). We will consider two cases.

• Case 1 \(((\exists k \in \mathbb{Z}) (n = 3k + 1))\): Suppose \(n = 3k + 1\) for some integer \(k\). Now:

\(n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3 (3k^2 + 2k) + 1\).

As \(2, 3\) and \(k\) are integers and as the integers are closed under multiplication and addition, \(3k^2 + 2k\) is an integer. Hence, \(3 \nmid n^2\). Thus, if \(n = 3k + 1\) for some integer \(k\), then \(3 \nmid n^2\).

• Case 2 \(((\exists k \in \mathbb{Z}) (n = 3k + 2))\): Suppose \(n = 3k + 2\) for some integer \(k\). Now:

\(n^2 = (3k + 2)^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3 (3k^2 + 4k + 1) + 1\).

As \(1, 3, 4\), and \(k\) are integers and as the integers are closed under multiplication and addition, \(3k^2 + 4k + 1\) is an integer. Hence, \(3 \nmid n^2\). Thus, if \(n = 3k + 2\) for some integer \(k\), then \(3 \nmid n^2\).

These cases are exhaustive. Hence, \(3 \nmid n^2\). Therefore, if \(3 \nmid n\), then \(3 \nmid n^2\).

As \(n\) was arbitrary, for all integers \(n\), if \(3 \nmid n\), then \(3 \nmid n^2\). QED.

Equivalence: \((A \Rightarrow (B \lor C))\) is equivalent to: \(((A \land \neg B) \Rightarrow C)\)

If we need to prove a statement of the form: \((A \Rightarrow (B \lor C))\)

We often prove the above equivalent statement.

To prove/show \((A \Rightarrow (B \lor C))\) using this equivalence:

• Assume/suppose both \(A\) is true and \(B\) is false (i.e., assume \(A\) and \(\neg B\))
• Show/Prove \(C\)
• Conclude “Therefore, if \(A\), then \(B\) or \(C\).”

Comments: Showing a disjunction \((B \lor C)\) is difficult, so this equivalence avoids this.

We could also prove \((A \Rightarrow (B \lor C))\) by contraposition!

\((\neg (B \lor C) \Rightarrow \neg A)\)

\(((\neg B \land \neg C) \Rightarrow \neg A)\)

Assume both \(B\) and \(C\) are false, then show/prove that \(A\) must also be false.

Example: “Let \(x\) be a real number. If \(x^2 + 7x = 9x + 15\), then \(x \leq 2\) or \(\frac{x-4}{x-3} > 0\).”

Logical Form: \((\forall x \in \mathbb{R})(P(x) \Rightarrow (Q(x) \vee R(x)))\)

Equivalent Form: \((\forall x \in \mathbb{R})((P(x) \wedge \neg Q(x)) \Rightarrow R(x))\)

where

Proof: Let \(x\) be an arbitrary real number. Suppose we have that \(x^2 + 7x = 9x + 15\) and that \(x \neq 2\). Then, we have that \(x^2 - 2x - 15 = 0\) and that \(x > 2\). As \(x^2 - 2x - 15 = 0\), we have that \((x-5)(x+3) = 0\) so that either \(x-5 = 0\) or that \(x+3 = 0\). Then, we have \(x=5\) or \(x = -3\). As \(x > 2\) and either \(x = 5\) or \(x=-3\), we must have that \(x=5\). (If we had \(x=-3\), we would have \(x \nless 2\), which would contradict \(x > 2\)). Now:

Hence, \(\frac{x-4}{x-3} > 0\). Therefore, we have that if \(x^2 + 7x = 9x + 15\), then either \(x \leq 2\) or \(\frac{x-4}{x-3} > 0\). As \(x\) was arbitrary, for any real number \(x\), if \(x^2 + 7x = 9x + 15\), then either \(x \leq 2\) or \(\frac{x-4}{x-3} > 0\). QED.

Review :

We’re going to use a negation to show how the negation changes the statement. \[ \begin{aligned} & \left(\forall n \in \omega \right) \left(n \leq 129^{(37^{100})}\right) \leftarrow \text{False} \\ & \neg \left( \left(\exists n \in \omega\right) \left(n > 129^{(37^{100})}\right) \right) \leftarrow \text{Same and still False}\\ & \left(\exists n \in \omega \right) \left(n \leq 129^{(37^{100})}\right) \leftarrow \text{True} \\ & \left(\exists n \in \omega \right) \left(n > 129^{(37^{100})}\right) \leftarrow \text{Same and still True} \end{aligned} \]

Example: For any integers \(x\) and \(y\), if 6 divides \(xy\), then either 2 divides \(x\) or 2 divides \(y\).

Logical Form: \((\forall x \in \mathbb{Z})(\forall y \in \mathbb{Z}) (6|xy \Rightarrow (2|x \vee 2|y))\)

Equivalent Form: \((\forall x \in \mathbb{Z})(\forall y \in \mathbb{Z})((6|xy \wedge 2 \nmid x) \Rightarrow 2|y)\)

Assuming more & showing less

Proof: Let \(x\) and \(y\) be arbitrary integers. Suppose that 6 divides \(xy\) and that 2 does not divide \(x\). Then, there are integers \(k\) and \(j\) such that \(xy = 6k\) and \(x = 2j + 1\). Now:

As 3, \(k\), \(j\) and \(y\) are integers, and as the integers are closed under multiplication and subtraction, \(3k - jy\) is an integer. Thus, 2 divides \(y\).

Hence, if 6 divides \(xy\), then either 2 divides \(x\) or 2 divides \(y\). As \(x\) and \(y\) were arbitrary, for any integers \(x\) and \(y\), if 6 divides \(xy\), then either 2 divides \(x\) or 2 divides \(y\). QED.

Proving (\(\forall x \in U\)) (P(x)) is False by Counter Example:

If we are proving a universal statement is false, then we are proving that the negation is true. Recall that: \(\neg (\forall x \in U) (P(x))\) is equivalent to: \((\exists x \in U) (\neg P(x))\). This gives us the following outline:

Proof: Let \(x\) = (found in scratch work). Now,… Hence we have \(x\) is in U.

Now: …

Thus we have that P(x) is false. As \(x\) is in U, it is not the case that every \(x\) in U makes P(x) true. QED.

Example: We will prove that \((\forall x \in \omega) (x^2 + x + 41 \text{ is prime})\) is false by counter example.

Proof: Let \(x = 41\). Notice that \(x\) is a whole number. Now:

\(x^2 + x + 41 = 41^2 + 41 + 41 = 41(41 + 1 + 1) = 41(43)\).

As \(x^2 + x + 41 = 41(43)\) and both \(41\) and \(43\) are integers greater than 1, we have that \(x^2 + x + 41\) is a composite number, that is, \(x^2 + x + 41\) is not prime.

As \(x\) is a whole number, it is not the case that \(x^2 + x + 41\) is prime for all whole numbers. QED.

Note: In these proofs, the value of \(x\) that we find is called a “counter example.”

Cool Proof #

Another cool “proof” of irrationality of square roots of primes in general.
Proof: Let n be a prime integer. Toward contradiction, suppose that \(\sqrt{n}\) is rational. Then, we have that \(\sqrt{n}\) is rational, so that there exist integers \(a\) and \(b\), with \(b \neq 0\), such that \(\sqrt{n} = \frac{a}{b}\) and a and b have no common factors greater than 1 (i.e., \(\frac{a}{b}\) is in lowest terms). Now, as \(\sqrt{n} = \frac{a}{b}\), we have that \(b\sqrt{n} = a\), so that \((b\sqrt{n})^2 = a^2\), and \(nb^2 = a^2\). That is, \(nb^2\) is a perfect square. Using the factorization of \(nb^2\), we see that \(n\) is a perfect square. As a perfect square greater than 1 cannot be prime, we have a contradiction. Hence, \(\sqrt{n}\) is irrational. \(\blacksquare\)

Module 3: Relations, Functions, Injections, Surjections, Bijections #

Let \(A\) and \(B\) be two sets.

The (Cartesian) product \(A \times B\) is defined to be:

“\((a, b)\)” is the ordered pair with “a” as the first component and “\(b\)” as the second.

Notation: We may write \(A^2\) to mean \(A \times A\) (e.g., \(\mathbb{R}^2\), \(\mathbb{Z}^2\), etc.).

If \(C \subseteq A \times B\), we say that \(C\) is a relation from \(A\) to \(B\) (i.e., if \(C\) is a set of ordered pairs whose 1st components come from \(A\) and whose 2nd components come from \(B\)).

If \(C \subseteq A^2\), we say that \(C\) is a relation on \(A\).

“Idea”: A relation is a set of ordered pairs.

Let \(F \subseteq A \times B\) such that the following two properties hold:

(i). \((\forall a \in A)(\exists b \in B)((a, b) \in F)\)
(ii). \((\forall a \in A)(\forall b_1 \in B)(\forall b_2 \in B)[((a, b_1) \in F \land (a, b_2) \in F) \Rightarrow b_1 = b_2]\)

In this case, we write \(F: A \rightarrow B\) and we say “\(F\) is a function from \(A\) to \(B\)”.

If (i) doesn’t hold, but (ii) does, we write \(F : A \rightharpoonup B\) (with a “harpoon” arrow) and say “\(F\) is a partial function from \(A\) to \(B\).”

Examples: Let \(A = \{0, 1, 2, 3, 4\}\) and let \(B = \{0, 2, 4, 6, 8\}\)

\(F_0 = \{(0, 8), (1, 6), (2, 4), (3, 2), (4, 0)\}\) \(F_0 : A \to B\)

\(F_1 = \{(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)\}\) \(F_1 : A \to B\)

\(F_2 = \{(0, 0), (1, 2), (2, 4), (3, 6), (4, 8), (0, 2)\}\)
\(F_2\) is not a function from \(A\) to \(B\): ii. fails: \((0, 0)\) & \((0, 2)\) in \(F_2\) but \(0 \neq 2\). In other words, the first component “0” goes to two different second values (0 & 2).

\(F_3 = \{(0, 2), (1, 4), (2, 6), (3, 8)\}\) \(F_3 : A \to B\)

i. fails as there is no b such that \((4,b) \in F\).

\(F_4 = \{(0, 0), (2, 1), (4, 2), (6, 3), (8, 4)\}\)
\(F_4\) is not a function from \(A\) to \(B\) as \(F \nsubseteq A \times B\)

(However: \(F_4 : B \to A\)). That is, it defines a function from \(B\) to \(A\).

If \(F : A \to B\):

• \(A = \text{dom}(F)\) “The domain of \(F\).”
• \(B = \text{cod}(F)\) “The codomain of \(F\).”
• Im\((F) = \text{ran}(F) = \{b \in B \mid (\exists a \in A) ((a, b) \in F) \}\)
    “The image (or range) of \(F\).”

For \(F_0\): dom\((F_0) = A\), cod\((F_0) = B\), ran\((F_0) = B\)

For \(F_1\): dom\((F_1) = A\), cod\((F_1) = B\), ran\((F_1) = \{2\}\)

Another example: Let \(A = \{5, 7, 9, 11\}\) and \(B = \{0, 2, 4, 6, 8, 10\}\), so that \(F, G \subseteq A \times B\) where

F: is a function, and
\(F: A \rightarrow B\)

G: is a function, but not a function from \(A\) to \(B\) as (i) fails. (The “top dot” in \(A\) doesn’t correspond to a pair in \(G\).) We do have \(G\) is a partial function from \(A\) to \(B\).
\(G: A \rightarrow B\)

H: Is a function, and
\(H: A \rightarrow B\)

J: is not a function from \(A\) to \(B\) (as \(J \not\subseteq A \times B\)), though \(J\) is a function by using different sets \(\hat{A}\) and \(\hat{B}\) for the domain & codomain, say \(\hat{A}\) and \(\hat{B}\). Then, we could have \(J: \hat{A} \rightarrow \hat{B}\).

K: is not a function as (ii) fails as one point in \(A\) “goes to” different values in \(B\).

Comment: I will often refer to property (ii) as the “VLT” (the “Vertical Line Test”).

A relation drawn in the plane fails the VLT when some vertical line \(x = a\) meets it twice, i.e., \((a, b_1)\) and \((a, b_2)\) are both in the relation with \(b_1 \neq b_2\):

Defining Functions: When we are writing out/defining a function there are three important parts we need to identify:

• The Domain
• The Co-domain
• The Ordered Pairs in the function.

If the domain is finite, we can list out all of the ordered pairs in the function, if the domain is large or infinite, we may try to identify a rule to describe which pairs are in the function.

Notation: We may write \(f(a) = b\) to mean \((a, b) \in f\). This also gives us: \((a, f(a)) \in f\) for each \(a\) in the domain.

Example: \(f: \mathbb{N} \to \mathbb{N}\) where \(f(n) = 2n - 1\) for each \(n \in \mathbb{N}\).

Example: \(f: \mathbb{R} \to \mathbb{R}\) where \(f(x) = x^2\) for each \(x \in \mathbb{R}\).

Alternate Rule Notation “maps to”: \(a \mapsto b\) means \((a, b) \in f\), i.e., \(f(a) = b\).

Example: \(f: \mathbb{N} \to \mathbb{Z}\) where \(n \mapsto (-1)^n (2n - 1)\) for each \(n \in \mathbb{N}\).

Example (a Cartesian product):

Additional Comments: Most of the functions that we will be looking at will be subsets of \(\mathbb{R}^2\). If just the “rule” is specified, we assume the domain to be as “large as possible” in \(\mathbb{R}\).

Example: Consider \(f(x) = \frac{x+2}{x-7}\). We assume that \(f: \mathbb{R} \to \mathbb{R}\) (as domain & codomain were not stated).

The only value that can’t be in dom\((f)\) is 7 (can’t divide by zero). So we have:

\(f:\mathbb{R} \setminus \{7\} \to \mathbb{R}\)

One reason that we specify the codomain instead of the image/range is that it often is difficult to determine the actual range.

(In the above example, the range is actually \(\mathbb{R} \setminus \{1\}\), but this takes additional work).

Three main rules for domain:

• Can’t divide by zero \(\frac{A}{x} \implies x \neq 0\)
• Can’t take a square root (or other even root) of a negative value \(\sqrt[2n]{x} \implies x \geq 0\)
• Can’t take a log of a non-positive value \(\log(x) \implies x > 0\)

Converse Relations/Functions

Suppose that \(R \subseteq A \times B\). The converse of \(R\) is \(\hat{R} \subseteq B \times A\) and is defined by:

“Idea”: The converse is just the collection of all “flipped”/reversed ordered pairs.

Example: If \(R = \{(0, 0), (1, 2), (2, 4), (3, 0)\}\), then:

We will define a property to determine when the converse of a function is itself a (partial) function.

Preview (from class): here is the outline and algebra for a proof that \(F(x) = \frac{x+2}{x-7}\) is one-to-one. The definition this uses is given right after. \[ \begin{aligned} &\text{L.F} (\forall a \in \mathbb{R}\setminus\{7\} \ \forall b \in \mathbb{R}\setminus\{7\} \ (F(a)=F(b) \implies a=b)) \\ &\text{Proof: Let } F: \mathbb{R}\setminus\{7\} \to \mathbb{R} \text{ be the function defined by} \\ &F(x) = \frac{x+2}{x-7} \text{ for all } x \text{ in the domain of } F. \\ &\text{Let } a \text{ and } b \text{ be arbitrary in } \mathbb{R}\setminus\{7\} \\ &\text{Assume } F(a) = F(b) \\ & \vdots (\text{show } a=b) \\ &\text{Hence, } a=b. \text{ Thus, if } F(a) = F(b), \text{ then } a=b. \\ &\text{As } a \text{ and } b \text{ were arbitrary, } F \text{ is one-to-one.} \end{aligned} \]

In our example, the reason that \(R\) wasn’t a (partial) function was that in \(R\), two values (0 & 3) both went to 0 (so “flipping” the pairs results in 0 mapping to two different values).

This means that to ensure that the converse of \(R: A \to B\) is also a function any different values in the domain must go to different values in the codomain:

By contraposition, this is equivalent to:

Definition: Let \(F: A \to B\). We say that \(F\) is 1-1 (one-to-one) or an injection, and we write: \(F: A \overset{1-1}{\longrightarrow} B\) provided:

Outline of a proof that \(F: A \to B\) is an injection:

Proof: Set-up (Introduce / define \(F\)). Let \(a\) and \(b\) be arbitrary in \(A\). Suppose \(F(a) = F(b)\).

Now, …

Hence, \(a=b\). Thus, if \(F(a) = F(b)\), then \(a=b\). As \(a\) and \(b\) were arbitrary in \(A\) (in the domain), \(F\) is an injection (one-to-one).

Example: Let \(F: \mathbb{R} \setminus \{7\} \to \mathbb{R}\) be defined by \(x \mapsto \frac{x+2}{x-7}\) for all \(x \in \mathbb{R} \setminus \{7\}\). We will prove that \(F\) is an injection.

Proof: Let \(F: \mathbb{R} \setminus \{7\} \to \mathbb{R}\) be the function defined by \(x \mapsto \frac{x+2}{x-7}\) for all \(x \in \mathbb{R} \setminus \{7\}\). Let \(a\) and \(b\) be arbitrary in \(\mathbb{R} \setminus \{7\}\). Suppose \(F(a) = F(b)\). Now:

Hence, \(a=b\). Therefore, if \(F(a) = F(b)\), then \(a=b\). As \(a\) and \(b\) were arbitrary in the domain of \(F\), \(F\) is one-to-one.

Example: Let \(g : \mathbb{Z} \to \omega\) be defined by \(n \mapsto n^2\) for all \(n \in \mathbb{Z}\). Prove that \(g\) is not one-to-one.

Logical Form: \(\neg (\forall a \in \mathbb{Z}) (\forall b \in \mathbb{Z}) (g(a) = g(b) \Rightarrow a=b)\)

We prove this using a counter example by the equivalence: \((\exists a \in \mathbb{Z}) (\exists b \in \mathbb{Z}) (g(a) = g(b) \land a \neq b)\).

Scratch Work: We need \(g(a) = g(b)\) and \(a \neq b\), i.e., we need \(a^2 = b^2\) and \(a \neq b\).

One case where this will happen is when \(a=13\) and \(b=-13\).

Proof: Let \(g : \mathbb{Z} \to \omega\) be the function defined by \(n \mapsto n^2\) for all integers \(n\). Let \(a = 13\) and let \(b = -13\). Note that both \(a\) and \(b\) are integers. Now:

\(g(a) = a^2 = 13^2 = 169 = (-13)^2 = b^2 = g(b)\).

Hence, we have that \(g(a) = g(b)\). Also, note that \(a = 13 \neq -13 = b\), so \(a \neq b\).

Thus, we have that \(g(a) = g(b)\) and \(a \neq b\). As \(a\) and \(b\) are integers, there are integers \(a\) and \(b\) such that \(g(a) = g(b)\) and \(a \neq b\). Therefore, \(g\) is not one-to-one.

Prove: \(f: \mathbb{R} \rightarrow \mathbb{R}, \ x \mapsto 7-3x\) for all \(x \in \mathbb{R}\) is 1-1.

L.F. \((\forall a \in \mathbb{R})(\forall b \in \mathbb{R})(f(a) = f(b) \Rightarrow a=b)\)

Proof: Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be the function defined by \(x \mapsto 7-3x\) for all \(x \in \mathbb{R}\). Let \(a\) and \(b\) be arbitrary real numbers.

Suppose \(f(a) = f(b)\). Now:

Hence, \(a = b\). Therefore, if \(f(a) = f(b)\), then \(a = b\).

As \(a\) and \(b\) were arbitrary, \(f\) is an injection.

Example: a relation that is not a function, with its domain and image:

Comments/Definitions in the following proof:

i) Provided the VLT property holds for a relation, the relation will be a function for appropriate sets as the domain and codomain.

↪ This means to show that \(\hat{F}\) is a function, we only need to show the VLT for \(\hat{F} \subseteq B \times A\):

\((\forall b \in B) (\forall a_1 \in A) (\forall a_2 \in A) [((b, a_1) \in \hat{F} \land (b, a_2) \in \hat{F}) \Rightarrow a_1 = a_2]\)

ii) If \(X\) and \(Y\) are sets, we say \(X = Y\) exactly when:

\((X \subseteq Y \land Y \subseteq X)\)

iii) If \(X\) and \(Y\) are sets we have \(X \subseteq Y\) exactly when:

\((\forall x)(x \in X \Rightarrow x \in Y)\)

iv) The domain of a Function/Relation \(R \subseteq A \times B\) can be defined by:

\(\text{dom}(R) = \{a \in A \mid (\exists b \in B)((a,b) \in R)\}\)

Example: Let \(F = \{(0,1), (1,1), (2,1)\}\), so \(F : \{0,1,2\} \to \{1\}\) is a function that is not one-to-one. Its converse is \(\hat{F} = \{(1,0), (1,1), (1,2)\}\), which fails the VLT (the single input \(1\) goes to \(0\), \(1\) and \(2\)), so \(\hat{F}\) is not a function.

Theorem: Let \(F: A \to B\), and let \(\hat{F} \subseteq B \times A\) be the converse of \(F\). Then

Furthermore, \(\text{dom}(\hat{F}) = \text{ran}(F)\) and \(\text{ran}(\hat{F}) = \text{dom}(F)\).

Proof: Let \(F: A \to B\) and let \(\hat{F} \subseteq B \times A\) be the converse of \(F\).

(\(\implies\)) Suppose that \(\hat{F}\) is a function. Let \(a\) and \(b\) be arbitrary in the domain of \(F\) and suppose \(F(a) = F(b)\). Denote the value of \(F(a) = F(b)\) by \(c\) (i.e., \(F(a) = c\) and \(F(b) = c\)). Now, we have that both \((a,c) \in F\) and \((b,c) \in F\). By the definition of the converse, we have that \((c,a) \in \hat{F}\) and \((c,b) \in \hat{F}\). As \(\hat{F}\) is a function, we have that \(a = b\). Thus, if \(F(a) = F(b)\), then \(a = b\). As \(a\) and \(b\) were arbitrary, \(F\) is one-to-one. Thus, if \(\hat{F}\) is a function, then \(F\) is one-to-one.

(\(\impliedby\)) Now, suppose \(F\) is one-to-one. Let \(b \in B\) be arbitrary and let \(a_1\) and \(a_2\) be arbitrary in \(A\). Suppose that \((b, a_1) \in \hat{F}\) and that \((b, a_2) \in \hat{F}\). By the definition of the converse, we have \((a_1, b) \in F\) and \((a_2, b) \in F\), i.e., that \(F(a_1) = b\) and \(F(a_2) = b\). Hence, \(F(a_1) = F(a_2)\). As \(F\) is one-to-one, we have that \(a_1 = a_2\). Therefore, if \((b, a_1) \in \hat{F}\) and \((b, a_2) \in \hat{F}\), then \(a_1 = a_2\). As \(b, a_1\), and \(a_2\) were arbitrary, \(\hat{F}\) is a function. Thus, if \(F\) is one-to-one, then \(\hat{F}\) is a function.

We’ve shown both directions of the biconditional. Hence, \(\hat{F}\) is a function iff \(F\) is one-to-one.

(dom (\(\hat{F}\)) = ran(\(F\))): Let \(x \in \text{dom}(\hat{F})\) be arbitrary. Then, there is some \(y \in A\) such that \((x,y) \in \hat{F}\). By the definition of the converse, \((y,x) \in F\). As \(y \in A\) and \((y,x) \in F\), we have that \(x \in \text{Ran}(F)\). As \(x\) was arbitrary, \(\text{dom}(\hat{F}) \subseteq \text{Ran}(F)\).

Now, let \(x \in \text{Ran}(F)\) be arbitrary. Then, there is some \(y \in A\) such that \((y,x) \in F\). By the definition of the converse, \((x,y) \in \hat{F}\). Hence, \(x \in \text{dom}(\hat{F})\). As \(x\) was arbitrary, \(\text{Ran}(F) \subseteq \text{dom}(\hat{F})\).

Thus, we have \(\text{dom}(\hat{F}) = \text{Ran}(F)\).

(ran(\(\hat{F}\)) = dom(\(F\))): Let \(x \in \text{ran}(\hat{F})\) be arbitrary. Then, there is some \(y \in B\) such that \((y,x) \in \hat{F}\). This implies that \((x,y) \in F\). Hence, \(x \in \text{dom}(F)\). As \(x\) was arbitrary, \(\text{ran}(\hat{F}) \subseteq \text{dom}(F)\).

Now, let \(x \in \text{dom}(F)\) be arbitrary. Then, there is some \(y \in B\) such that \((x,y) \in F\). This implies that \((y,x) \in \hat{F}\). As \(y \in B\), we have that \(x \in \text{ran}(\hat{F})\). As \(x\) was arbitrary, \(\text{dom}(F) \subseteq \text{ran}(\hat{F})\).

Thus, we have \(\text{ran}(\hat{F}) = \text{dom}(F)\).

Scratch work for the next theorem: suppose \(f(x) = f(y)\) for \(f(x) = \frac{ax+b}{cx+d}\). Cross-multiplying and simplifying leads to \((ad-bc)(x-y) = 0\), so if \(ad - bc \neq 0\) we get \(x - y = 0\):

Theorem: Let \(a, b, c,\) and \(d\) be real numbers with \(c\) and \(d\) not both equal to zero.

Let \(f : \mathbb{R} \setminus \{-\frac{d}{c}\} \to \mathbb{R}\) be the function defined by \(x \mapsto \frac{ax+b}{cx+d}\) for all \(x \in \text{dom}(f)\).

Then, \(f\) is \(1-1\) iff \(ad - bc \neq 0\).

For the proof of this theorem, we will use the “Zero Product Property” of the real numbers:

Logical Form: \((f \text{ is } 1-1) \iff (ad - bc \neq 0)\)

(Comment: The above form has the quantification of \(a, b, c, d\) (and \(f\)) suppressed. For \(a, b, c, d\) (and \(f\)) the universal quantifier would be used.)

Equivalent Forms:

“Full” / Quantified Logical Form:

Additional Comment: In the case where \(c=0\) (and \(d \neq 0\)), we have that \(f : \mathbb{R} \to \mathbb{R}\) (as \(-\frac{d}{c}\) is not defined / not a real number so that \(\mathbb{R} \setminus \{ -\frac{d}{c} \} = \mathbb{R}\)).

The set-up of our proof will still follow this quantified form with one minor adjustment:

We won’t use the key-word “arbitrary” when introducing the function \(f\). This is due to the fact that we are defining a specific function. (We could still use the word “arbitrary” in the proof here, it just isn’t needed.)

Proof: Let \(a, b, c\) and \(d\) be arbitrary real numbers with \(c\) and \(d\) not both equal to zero. Then, let \(f: \mathbb{R} \setminus \{-\frac{d}{c}\} \to \mathbb{R}\) be the function defined by \(x \mapsto \frac{ax+b}{cx+d}\) for all \(x\) in the domain of \(f\).

\((\Rightarrow)\) Now, suppose \(ad - bc = 0\). Let

If \(c \neq 0\): as \(1, c\) and \(d\) are real and as the reals are closed under addition, subtraction and division by non-zero values, \(-\frac{d}{c} + 1\) is real, so that \(x\) is real. We will show that \(x \neq -\frac{d}{c}\). Towards a contradiction, suppose \(x = -\frac{d}{c}\). Then, as \(x = -\frac{d}{c} + 1\), we have that \(-\frac{d}{c} = -\frac{d}{c} + 1\), so that \(0 = 1\). As \(0 \neq 1\), we have a contradiction. Hence, \(x \neq -\frac{d}{c}\). Therefore, \(x \in \mathbb{R} \setminus \{-\frac{d}{c}\}\), i.e., \(x\) is in the domain of \(f\).

If \(c = 0\), then we have \(x = 1\), so that \(x\) is real. When \(c = 0\), \(\mathbb{R} \setminus \{-\frac{d}{c}\} = \mathbb{R}\), so that \(x\) is in the domain of \(f\).

Now, let \(y = x + 1\). As \(x\) is real and \(1\) is real and the reals are closed under addition, \(x + 1\) is real, so that \(y\) is real. If \(c \neq 0\), we have that \(y = -\frac{d}{c} + 2\). As was the case with \(x\), we have that \(y \neq -\frac{d}{c}\), so that \(y\) is in the domain of \(f\). If \(c = 0\), we have that the domain of \(f\) is \(\mathbb{R}\) and \(y\) is thus in the domain.

Next, we show that \(x \neq y\). If \(c \neq 0\), we have \(x = -\frac{d}{c} + 1\) and \(y = -\frac{d}{c} + 2\). Note that \(1 \neq 2\), so that \(-\frac{d}{c} + 1 \neq -\frac{d}{c} + 2\), and \(x \neq y\). If \(c = 0\), we have \(x = 1 \neq 2 = y\).

We now will show that we do have that \(f(x)=f(y)\). Note that:

Thus, we have \(f(x) = f(y)\). As \(x \neq y\) and \(f(x) = f(y)\), and \(x\) and \(y\) are in the domain of \(f\), we have that \(f\) is not one-to-one. Thus, if \(ad-bc = 0\) then \(f\) is not one-to-one. Hence, by contraposition, if \(f\) is one-to-one, then \(ad-bc \neq 0\).

\((\Leftarrow)\) Now, suppose \(ad-bc \neq 0\). Let \(x\) and \(y\) be arbitrary in the domain of \(f\).

Suppose \(f(x)=f(y)\). Now:

\(\frac{ax+b}{cx+d} = \frac{ay+b}{cy+d}\)

\((ax+b)(cy+d) = (ay+b)(cx+d)\)

\(acxy + adx +bcy +bd = acxy + ady+bcx + bd\)

\(adx +bcy - ady - bcx = 0\)

\(adx-bcx + bcy-ady = 0\)

\((ad-bc)x - (ad-bc)y = 0\)

\((ad-bc)(x-y) = 0\).

By the zero product property, we must either have that \(ad-bc=0\) or that \(x-y=0\). As \(ad-bc\neq0\), this implies that \(x-y=0\), so that \(x=y\). Thus, if \(f(x) = f(y)\), then \(x=y\). As \(x\) and \(y\) were arbitrary, for all \(x\) and \(y\) in the domain of \(f\), if \(f(x) = f(y)\), then \(x=y\). Hence, \(f\) is one-to-one. Thus, if \(ad-bc \neq 0\), then \(f\) is one-to-one.

We have shown both directions of the biconditional, hence \(f\) is 1-1 iff \(ad-bc\neq0\). As \(a, b, c,\) and \(d\) were arbitrary, for any real numbers \(a, b, c\) and \(d\) with \(c\) and \(d\) not both equal to zero, for \(f : \mathbb{R}\setminus\{-\frac{d}{c}\} \rightarrow \mathbb{R}\) defined by \(x \mapsto \frac{ax+b}{cx+d}\) for every \(x\) in the domain, we have that \(f\) is an injection iff \(ad - bc \neq 0\). \(\blacksquare\)

Consider the function \(f : \mathbb{R} \to \mathbb{R}\) defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\).

Note #1: \(f\) is not one-to-one because we can find two different values in the domain that \(f\) maps to the same value. E.g. \(-4 \neq 4\) (both in the domain), but \(f(-4) = 16 = f(4)\). Visually, this is because \(f\) fails the “Horizontal Line Test” (HLT).

Note #2: This is an example of a function whose codomain and image/range are not the same.

If we “changed” the codomain and considered \(\hat{f} : \mathbb{R} \to [0, \infty)\) defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\), then we would have that the codomain and the image/range would be equal / the same.

If a function is such that the codomain and image are equal (the same), i.e., if \(\text{Cod}(f) = \text{Im}(f)\), we say that the function is onto or is a surjection.

In this case, we may write: \(f : A \xrightarrow{\text{onto}} B\).

Surjections / Onto Functions #

A function \(f: A \to B\) is onto / a surjection when \(\text{Cod}(f) = \text{Im}(f)\).

This “means” that everything in \(B\) needs to be mapped to by at least one value in \(A\) (the domain).

Notice that being 1-1 & onto are unrelated (one doesn’t imply / give the other).

The Logical Form of the Definition of Onto

A function \(f: A \rightarrow B\) is onto/a surjection iff:

“For every value \(b\) in \(Cod(f) = B\), we can find a value \(a\) in \(Dom(f) = A\), such that \(f\) maps/takes \(a\) to \(b\).”

“Outline” of a proof that \(f: A \rightarrow B\) is a surjection:

Proof: (Introduce the function)
Let \(b\) be arbitrary in \(B\).
Let \(a = \text{(value found in scratch work)}\).
(Show \(a \in A\))*
Now: \(f(a) = \dots = b\). (“calculation”)
Thus, \(f(a) = b\). As \(a \in A\), there exists an \(a\) in \(A\) such that \(f(a) = b\).
As \(b\) was arbitrary, for all \(b\) in \(B\), there is an \(a\) in \(A\) such that \(f(a) = b\). Thus, \(f\) is a surjection/is onto.

*In many cases this is done by contradiction & closure properties.

Example: We will prove that \(f: \mathbb{R} \to \mathbb{R}\), defined by \(f(x) = 2x - 7\) is onto.

Logical Form: \((\forall b \in \mathbb{R}) (\exists a \in \mathbb{R}) (f(a) = b)\)

Scratch Work: We need \(f(a) = b: 2a - 7 = b \implies 2a = b + 7 \implies a = \frac{b+7}{2}\).

Proof: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by \(x \mapsto 2x - 7\) for all \(x \in \mathbb{R}\).

Let \(b\) be an arbitrary real number. Let \(a = \frac{b+7}{2}\). Notice that \(2\), \(7\), and \(b\) are real numbers, so that as the reals are closed under addition and division by non-zero values, \(\frac{b+7}{2}\) is real. Hence, we have that \(a\) is real, i.e., that \(a\) is in the domain of \(f\).

Now:

Hence, we have that \(f(a) = b\). As \(a\) is real, there is a real number \(a\) such that \(f(a) = b\). As \(b\) was arbitrary, for all real numbers \(b\), there exists a real number \(a\) such that \(f(a) = b\). Hence, \(f\) is a surjection.

Example: We will prove that \(f: \mathbb{R} \setminus \{7\} \to \mathbb{R} \setminus \{5\}\) defined by \(x \mapsto \frac{5x-2}{x-7}\) is onto.

Logical Form: \(\left(\forall b \in \mathbb{R} \setminus \{5\}\right) \left( \exists a \in \mathbb{R} \setminus \{7\} \right) \left( f(a) = b \right)\)

Scratch Work: Need to find \(a \in \mathbb{R} \setminus \{7\}\) such that \(f(a) = b\): \(\frac{5a-2}{a-7} = b\)

\(\Rightarrow (5a-2) = b(a-7) \Rightarrow 5a-2 = ab - 7b \Rightarrow 5a - ab = 2 - 7b\)

\(\Rightarrow a(5-b) = 2-7b \Rightarrow a = \frac{2-7b}{5-b}\).

Closure properties of \(\mathbb{R}\) (and that \(b \neq 5\)) will give us \(a \in \mathbb{R}\).

We will use a contradiction to show \(a \neq 7\). (Assume \(a = 7\) and get a false statement).

Proof: Let \(f: \mathbb{R} \setminus \{7\} \to \mathbb{R} \setminus \{5\}\) be the function defined by \(f(x) = \frac{5x-2}{x-7}\) for all \(x\) in \(\mathbb{R} \setminus \{7\}\). Let \(b\) be in \(\mathbb{R} \setminus \{5\}\) be arbitrary. Let \(a = \frac{2-7b}{5-b}\). Note that \(b \neq 5\), so that \(5-b \neq 0\). As, 2, 5, 7 and \(b\) are real, and as \(5-b \neq 0\), we have that as the reals are closed under subtraction, multiplication and division by non-zero values, \(\frac{2-7b}{5-b}\) is real, i.e., \(a\) is real.

We claim that \(a \neq 7\). Towards a contradiction, suppose \(a=7\). Now:

Now, we have that \(35 = 2\). As \(35 \neq 2\), we have a contradiction, hence \(a \neq 7\), as claimed. Thus, \(a \in \mathbb{R} \setminus \{7\}\), that is a is in the domain of \(f\).

Now, notice:

Hence, \(f(a) = b\). As \(a \in Dom(f)\), then is an \(a \in Dom(f)\) such that \(f(a) = b\). As \(b \in Cod(f)\) was arbitrary, for all \(b \in Cod(f)\), there is an \(a \in Dom(f)\) such that \(f(a) = b\). Hence, \(f\) is onto.

Example: We will prove that \(f: \mathbb{R}\setminus\{\frac{9}{8}\} \rightarrow \mathbb{R}\) defined by \(x \mapsto \frac{2x+1}{8x-9}\) is not a surjection.

Logical Form: \(\neg (\forall b \in \mathbb{R})(\exists a \in \mathbb{R}\setminus \{\frac{9}{8}\}) (f(a)=b)\)

Equivalent Form (simplified): \((\exists b \in \mathbb{R}) (\forall a \in \mathbb{R}\setminus\{\frac{9}{8}\}) (f(a) \neq b)\)

We need to find a real number \(b\) that nothing in the domain maps to.

We will examine \(f(a) = \frac{2a+1}{8a-9}\)

Now: \(f(a) = \frac{2a+1}{8a-9} = \frac{1}{4} + \frac{\frac{13}{4}}{8a-9}\)

This means that \(f(a)\) can’t equal \(\frac{1}{4}\) (this is the value of \(b\) we were looking for)

(Never equals zero (\(\frac{A}{B} = 0\) iff \(A=0\) & \(B\neq0\)))

Comment: We could also look at the graph, which has a horizontal asymptote at \(y = \frac{1}{4}\), which the curve doesn’t cross.

Proof: Let \(f: \mathbb{R} \setminus \{\frac{9}{8}\} \to \mathbb{R}\) be the function defined by \(f(x) = \frac{2x+1}{8x-9}\) for all \(x \in \mathbb{R} \setminus \{\frac{9}{8}\}\). Let \(b = \frac{1}{4}\). Note that \(b \in \mathbb{R}\), so that \(b\) is in the codomain of \(f\). Now, let \(a \in \mathbb{R} \setminus \{\frac{9}{8}\}\) be arbitrary. We will show that \(f(a) \ne b\). Towards a contradiction, suppose \(f(a) = b\). Now:

Now, we have \(4 = -9\). As \(4 \ne -9\), we have a contradiction. Hence, \(f(a) \ne b\). As \(a\) was arbitrary, for every \(a\) in the domain, \(f(a) \ne b\). As \(b\) is in the codomain, there is a \(b\) in the codomain, such that for all \(a\) in the domain, \(f(a) \ne b\). Hence, \(f\) is not a surjection.

Bijections #

As we noted earlier, functions can be either 1-1 or onto or both or neither. If \(f: A \to B\) is both 1-1 and onto, we write \(f: A \overset{1-1}{\underset{onto}{\to}} B\) and we say that \(f\) is a bijection (or a one-to-one correspondence).

To prove that \(f: A \to B\) is a bijection, we prove both that it is 1-1 and is onto and then conclude that \(f\) is a bijection.

Example: We will prove \(f: \mathbb{R} \to \mathbb{R}\), defined by \(x \mapsto x-7\) is a bijection.

Proof: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by \(f(x) = x-7\) for all \(x \in \mathbb{R}\).

(1-1): Let \(a\) and \(b\) be arbitrary in the domain, and suppose that \(f(a) = f(b)\). Now:

Hence, \(a=b\). Thus, if \(f(a) = f(b)\), then \(a = b\). As \(a\) and \(b\) were arbitrary, for all \(a\) and \(b\) in the domain, if \(f(a) = f(b)\), then \(a = b\). Thus, \(f\) is an injection.

(Onto): Let \(b\) be arbitrary in the codomain. Let \(a = b+7\). As \(b\) is in the codomain, \(b\) is real. As \(7\) and \(b\) are real, and as the reals are closed under addition, \(b+7\) is real, i.e., \(a\) is real and is in the domain of \(f\). Now:

Thus, \(f(a) = b\). As \(a\) is in the domain, there is an \(a\) in the domain such that \(f(a) = b\). As \(b\) was arbitrary, for all \(b\) in the codomain, there is an \(a\) in the domain such that \(f(a) = b\). Hence, \(f\) is a surjection.

As \(f\) is both an injection and a surjection, \(f\) is a bijection.

We will now “construct” a surjection \(f: \mathbb{N} \to (0, \infty) \cap \mathbb{Q}\).

Visually, we “weave” through the lattice points \((a,b)\) with \(a, b \in \mathbb{N}\), starting at \((1,1)\), going along the diagonals \(a + b = 2, 3, 4, \dots\):

• This “weaving” pattern will hit every ordered pair of positive integers;
• This means that we will get every fraction of positive integers.
• As every positive rational number can be written as \(\frac{a}{b}\) for \(a,b\) positive integers, \(f\) will be onto \((0,\infty) \cap \mathbb{Q}\).

We “associate” an ordered pair \((a,b)\) with the rational number equal to \(\frac{a}{b}\).

We “map” each natural number to the rational number associated with the corresponding dot/point.

A bijection between two finite sets of the same size, \(A = \{0,1,2,3,4,5\}\) and \(B = \{2,6,8,10,12,16\}\) (so \(|A| = 6 = |B|\)):

Here \(f(0) = 2\), \(f(1) = 6\), \(f(2) = 8\), \(f(3) = 10\), \(f(4) = 12\) and \(f(5) = 16\).

The function \(f : \mathbb{N} \to (0,\infty) \cap \mathbb{Q}\) that we just described is not an injection (not 1-1).

In fact, every positive rational number will be mapped to by infinitely many values from the domain.

We already have that \(f(1) = f(5)\) (both equal 1) with \(1 \neq 5\). (We also will have \(f(13) = 1\)).

Any time the “path” hits \((n,n)\), the output will be 1.

While \(f\) is not 1-1, we can use it to “build” a bijection between \(\mathbb{N}\) and \((0,\infty) \cap \mathbb{Q}\).

The “idea” will be to “skip over” values we already have mapped to.

We will have \(g: \mathbb{N} \xrightarrow[\text{onto}]{1-1} (0, \infty) \cap \mathbb{Q}\)

• As \(f\) was onto, \(g\) still will be.
• As we skip “duplicate” values, \(g\) will be 1-1.

Cardinality of Sets

Two sets \(A\) and \(B\) are said to have the same cardinality if there is a bijection \(f : A \xrightarrow[onto]{1-1} B\).

In this case, we write: \(|A| = |B|\)

If a set is finite, then we write \(|A| = n\) where \(n\) is the number of elements in \(A\).

If \(|A| = |\mathbb{N}|\), i.e., if there is a bijection \(f : \mathbb{N} \xrightarrow[onto]{1-1} A\), we say that \(A\) is denumerable, and we write \(|A| = \aleph_0\).

Example: Our last function \(g : \mathbb{N} \xrightarrow[onto]{1-1} (0, \infty) \cap \mathbb{Q}\), so we have that:

\(|(0, \infty) \cap \mathbb{Q}| = \aleph_0\)

Example: Consider \(f : \mathbb{N} \xrightarrow[onto]{1-1} \omega\) defined by \(n \mapsto n-1\) for all \(n \in \mathbb{N}\). As this is a bijection, we have \(|\omega| = \aleph_0\)

Example: Consider \(h : \mathbb{N} \xrightarrow[onto]{1-1} \mathbb{N}\) defined by \(n \mapsto n\) for all \(n \in \mathbb{N}\). (h is the identity function on \(\mathbb{N}\)). Thus, we have \(|\mathbb{N}| = \aleph_0\).

When \(f : A \xrightarrow[\text{onto}]{1-1} B\), every arrow can be reversed, giving \(f^{-1} : B \xrightarrow[\text{onto}]{1-1} A\):

Example: \(|\mathbb{N}| = |\mathbb{Z}|\). We want to find \(f : \mathbb{N} \xrightarrow[\text{onto}]{1-1} \mathbb{Z}\).

A first attempt, \(1 \mapsto 1,\ 2 \mapsto -1,\ 3 \mapsto 2,\ 4 \mapsto -2,\ \dots\), i.e.

is \(1\)-\(1\) but is not onto (it misses \(0\)). Shifting the odd values down by one fixes this:

(For \(n\) odd we can write \(n = 2k+1\) with \(k = \frac{n-1}{2}\), and we send \(n \mapsto k\).)

Example: Consider \(j : \mathbb{N} \to \mathbb{Z}\) defined by

This gives us that \(|\mathbb{Z}| = \aleph_0\).

A set \(A\) is said to be countable if either \(A\) is finite or if \(A\) is denumerable.

In other words, \(A\) is countable if either \(|A| = \aleph_0\) or if there is some \(n \in \mathbb{N}\) such that \(|A| = n\).

Fact: A set \(A\) is countable exactly when there is a surjection from \(\mathbb{N}\) to \(A\), i.e., there is some \(f : \mathbb{N} \twoheadrightarrow A\).

Aside: if \(A = \{1,2,3,4,5\}\) (so \(|A| = 5\)), \(A\) is countable, so there should be a surjection \(f: \mathbb{N} \xrightarrow{\text{onto}} A\). For example: \(1 \mapsto 1,\ 2 \mapsto 2,\ 3 \mapsto 3,\ 4 \mapsto 4,\ 5 \mapsto 5,\ 6 \mapsto 1,\ 7 \mapsto 2,\ 8 \mapsto 3,\ 9 \mapsto 4, \dots\) (cycling through \(A\)).

We will show that the interval (0,1) (of real numbers) is not countable.

To do this, we will show that every function \(f:\mathbb{N} \rightarrow (0,1)\) is not onto.

This means that there will always be a value in (0,1) that is not in the image/range of the function.

Fact we will use: Every real number in (0,1) can be written in the form:

\(y = \sum_{n=1}^\infty \frac{y_n}{10^n}\) where each \(y_n \in \{0,1,2,3,4,5,6,7,8,9\}\)

(This is the listing of all the digits in y in the decimal expansion)

For example: If \(y=\frac{1}{13}\), we have \(y=0.0769230769230…\)

Here: \(y_1=0\), \(y_2=7\), \(y_3=6\), \(y_4=9\), \(y_5=2\), \(y_6=3\), \(y_7=0\), …

Comment: The decimal expansion may not actually be unique. This won’t matter for us right now, but it’s important to be aware (In the actual proof, it will come up)

Example: If \(y=\frac{23}{100}\) we have both: \(y = 0.23000000…\) and \(y = 0.22999999…\)

The expansions can be made unique by not allowing the “tailing” 9’s.

Let \(f: \mathbb{N} \to (0,1)\) be an arbitrary function. We will show \(f\) is not onto by finding a value \(b \in (0,1)\) which is not in the range/image of \(f\).

Logical Forms: \(\neg\) (\(f\) is onto)

\( \neg (\forall b \in (0,1)) (\exists a \in \mathbb{N}) (f(a)=b)\)

\( (\exists b \in (0,1)) (\forall a \in \mathbb{N}) (f(a) \neq b)\)

We don’t know what \(f\) maps values to precisely, however, we can write the following:

\(f(1) = y_1 = \sum_{n=1}^{\infty} \frac{y_{1n}}{10^n} = 0.y_{11} y_{12} y_{13} y_{14} y_{15} y_{16} \dots\)

\(f(2) = y_2 = \sum_{n=1}^{\infty} \frac{y_{2n}}{10^n} = 0.y_{21} y_{22} y_{23} y_{24} y_{25} y_{26} \dots\)

\(f(3) = y_3 = \sum_{n=1}^{\infty} \frac{y_{3n}}{10^n} = 0.y_{31} y_{32} y_{33} y_{34} y_{35} y_{36} \dots\)

\(\vdots\)

\(f(m) = y_m = \sum_{n=1}^{\infty} \frac{y_{mn}}{10^n} = 0.y_{m1} y_{m2} y_{m3} y_{m4} y_{m5} y_{m6} \dots\)

Comment: Notationally it would be better to put a comma ‘,’ between the subscripts (and necessary for larger values).

We now will define/create a number \(b\) as follows:

Where:

Idea: We look at the \(n^{th}\) digit of \(f(n)\) and change it to something different.

Example: Suppose \(f\) gave us the following:

\(f(1) = 0.6 \boxed{9} 54405\ldots\)
\(f(2) = 0.4 \boxed{0} 86829\ldots\)
\(f(3) = 0.69 \boxed{6} 1720\ldots\)
\(f(4) = 0.998 \boxed{5} 129\ldots\)
\(f(5) = 0.986 \boxed{0} 307\ldots\)
\(f(6) = 0.78896 \boxed{3} 6\ldots\)
\(f(7) = 0.395945 \boxed{6}\ldots\)

The \(n^{th}\) digit of \(f(n)\) is boxed.

This allows us to begin to write \(b = 0.3333773…\)

Notice that \(b\) only has 3’s & 7’s, so it can’t have trailing 9’s, nor will it terminate (i.e., trailing 0’s).

As \(b\) will not have trailing 9’s nor 0’s, the representation is unique, i.e., there is no other decimal expansion for the same value.

This means that if \(b=a\), every digit in the decimal expansions must match/be the same.

(i.e., \(b_1=a_1, b_2=a_2, b_3=a_3, b_4=a_4\), etc…)

Now:

• \(b \neq f(1)\) as \(b_1 \neq y_{11}\) (the first digits are different)
• \(b \neq f(2)\) as \(b_2 \neq y_{22}\) (the second digits are different)
• \(b \neq f(3)\) as \(b_3 \neq y_{33}\) (the third digits are different)
• \(\vdots\)
• \(b \neq f(m)\) as \(b_m \neq y_{mm}\) (the \(m^{th}\) digits are different)
• \(\vdots\)

This tells us that no matter what \(n \in \mathbb{N}\) we plug in, we will not get \(b\).

In other words, \(b\) is not in the range (but \(b\) is in \((0,1)\), the codomain).

Thus, \(f\) is not onto. (\(Cod(f) \neq Range(f)\))

As \(f\) was arbitrary, any function \(f: \mathbb{N} \to (0,1)\) will not be a surjection.

Comment: The “b” will be different for each \(f: \mathbb{N} \to (0,1)\), but we find such a “b” using the same process.

We’ve just seen that any function \(f: \mathbb{N} \to (0,1)\) cannot be onto, so that any function \(f: \mathbb{N} \to (0,1)\) cannot be a bijection.

This means that \(|\mathbb{N}| \neq |(0,1)|\) (Different Cardinalities), so that \(|(0,1)| \neq \aleph_0\).

We also know that \((0,1)\) is not finite, so that \((0,1)\) is not countable.

Aside: While \(f: \mathbb{N} \to (0,1)\) cannot be onto, it is possible for \(f\) to be 1-1.

For example, consider:

\(f: \mathbb{N} \to (0,1)\) defined by \(n \mapsto \frac{1}{n+1}\) for all \(n \in \mathbb{N}\).

The same type of process also gives us that any function \(f: \mathbb{N} \to \mathbb{R}\) cannot be onto (just make \(b \in \mathbb{R}\) such that \(b\) “disagrees” with the \(n^{\text{th}}\) digit of \(f(n)\).)

This means that \(|\mathbb{N}| \neq |\mathbb{R}|\) and \(|\mathbb{R}| \neq \aleph_0\).

\((0,1)\) vs \(\mathbb{R}\): can we find a bijection \(f : (0,1) \to \mathbb{R}\)? Some functions \((0,1) \to \mathbb{R}\) are \(1\)-\(1\) but not onto, and some are onto but not \(1\)-\(1\):

Now, consider the function:

From the graph of \(f\), we see that \(f\) does “pass” the HLT, so \(f\) is 1-1. We also see that the range/image of \(f\) is in fact all of \(\mathbb{R}\), so \(f\) is onto.

This means we will have \(f\) is a bijection, so that:

Previously, we saw that:

We will consider a (new) function \(F: \mathbb{N} \longrightarrow [0, \infty) \cap \mathbb{Q}\) defined by:

Factor out all powers of 2. Remaining odd part.

Examples:

It is clear that this function is not 1-1 (We already have \(f(1)=f(3)=0\)).

It is also easy to see that this function is onto:

Choose any non-negative rational number, \(q\).

As \(q\) is non-negative and rational, we can write \(q\) in the form \(q = \frac{a}{b}\)

where \(a \in \mathbb{W}\) and \(b \in \mathbb{N}\).

Notice that:

\(2^{a}(2b-1)\) will be natural (this takes a little work to verify).

• When \(a \in \mathbb{W}\), \(2^{a}\) will be natural (\(2^{0} = 1 \in \mathbb{N}\), and for \(a>1\), \(2^a\) is natural by the closure of \(\mathbb{N}\) under multiplication, and for \(a=1\), \(2^1 = 2 \in \mathbb{N}\).)
• As \(b \in \mathbb{N}\), \(2b-1\) is an integer (closure of \(\mathbb{Z}\) under multiplication and subtraction). Also, \(b \geq 1\), so \(2b \geq 2\), and \(2b - 1 \geq 1\). As \(2b - 1 \geq 1\) and \(2b - 1 \in \mathbb{Z}\), we have that \(2b-1 \in \mathbb{N}\).
• As \(2^a \in \mathbb{N}\) and \((2b-1) \in \mathbb{N}\), by closure of \(\mathbb{N}\) under multiplication, \(2^a(2b-1) \in \mathbb{N}\), so \(2^a(2b-1)\) is in the domain of \(f\).

Then, we have: \(f(2^{a}(2b-1)) = \frac{a}{b} = q\). As \(q \in [0, \infty) \cap \mathbb{Q}\) was arbitrary, \(f\) is a surjection.

We now have \(f: \mathbb{N} \xrightarrow{onto} [0, \infty) \cap \mathbb{Q} (2^a(2b-1) \mapsto \frac{a}{b})\)

We can use this function to “build”/define a bijection \(g: \mathbb{N} \xrightarrow{onto} [0, \infty) \cap \mathbb{Q}\)

To do this, we use the same “skipping” idea that we used previously.

\(f(1) = 0 = g(1)\)
\(f(2) = 1 = g(2)\)
\(f(3) = 0 \text{ (skip)}\)
\(f(4) = 2 = g(3)\)
\(f(5) = 0 \text{ (skip)}\)
\(f(6) = \frac{1}{2} = g(4)\)
\(f(7) = 0 \text{ (skip)}\)
\(f(8) = 3 = g(5)\)
\(f(9) = 0 \text{ (skip)}\)
\(f(10) = \frac{1}{3} = g(6)\)
\(f(11) = 0 \text{ (skip)}\)
\(f(12) = 1 \text{ (skip)}\)
\(f(13) = 0 \text{ (skip)}\)
\(f(14) = \frac{1}{2} \text{ (skip)}\)
\(f(15) = 0 \text{ (skip)}\)
\(f(16) = 4 = g(7)\)
\(f(17) = 0 \text{ (skip)}\)
\(f(18) = \frac{1}{5} = g(8)\)
\(f(19) = 0 \text{ (skip)}\)
\(f(20) = \frac{2}{3} = g(9)\)
\(f(21) = 0 \text{ (skip)}\)
\(f(22) = \frac{1}{6} = g(10)\)
\(f(23) = 0 \text{ (skip)}\)
\(f(24) = \frac{3}{2} = g(11)\)
\(f(25) = 0 \text{ (skip)}\)
\(f(26) = \frac{1}{7} = g(12)\)
\(f(27) = 0 \text{ (skip)}\)

Again, by only skipping repeats, we still will be onto, but we now will pass the “HLT” and we have a 1-1 function.

This tells us that we have:

\(| \mathbb{N} | = | [0, \infty) \cap \mathbb{Q} | = \aleph_0\)

Example (a surjection \(\mathbb{R} \to \mathbb{N}\)): \(f: \mathbb{R} \xrightarrow{\text{onto}} \mathbb{N}\) defined by \(x \mapsto \lfloor |x| \rfloor + 1\). For instance \(0 \mapsto 1\), \(\pi \mapsto 4\), \(4.3 \mapsto 5\), \(1 \mapsto 2\).

Exercise: Can you find \(f:(0,1] \xrightarrow[\text{onto}]{1-1} (0,1)\) to show that \(|(0,1]| = |(0,1)|\)?

Example: \(f: \omega \xrightarrow[\text{onto}]{1-1} \mathbb{N}\), \(n \mapsto n+1\) (\(0 \mapsto 1,\ 1 \mapsto 2,\ 2 \mapsto 3, \dots\)) shows \(|\omega| = |\mathbb{N}| = \aleph_0\).

Notation Detour: Consider a (partial) function \(f: A \rightharpoonup B\) (i.e., \(f \subseteq A \times B\) and \(f\) satisfies the VLT.)

Input Domain of \(f = A\)

Domain of \(f = \{x \in A \mid (\exists y \in B)((x, y) \in f)\} = \text{Dom}(f)\) *

\(f\) is a total function when \(\text{Dom}(f) = A\) (and we write \(f: A \rightarrow B\))

Codomain of \(f = B = \text{Cod}(f)\)

Range/Image of \(f = \{y \in B \mid (\exists x \in A)((x, y) \in f)\} = \text{Range}(f) = \text{Im}(f)\) *

Graph of \(f\) is the set of all ordered pairs in the function (often denoted just by \(f\))

* In the definition of \(\text{Dom}(f)\) and \(\text{Range}(f)\), we are referring to the graph of \(f\).

Technicality: Two functions may have the same graph, but not be the same,

i.e., exactly the same ordered pairs but either the input domains differ, or the codomains differ (or both differ).

Examples:

• \(f_1: \mathbb{R} \rightharpoonup \mathbb{R}\) with \(x \mapsto \sqrt{x}\)
• \(f_2: \mathbb{R} \rightharpoonup [0, \infty)\) with \(x \mapsto \sqrt{x}\)
• \(f_3: [0, \infty) \rightarrow \mathbb{R}\) with \(x \mapsto \sqrt{x}\)
• \(f_4: [0, \infty) \rightarrow [0, \infty)\) with \(x \mapsto \sqrt{x}\)

\(f_1, f_2, f_3\) and \(f_4\) all have the same graph, but are different functions.

Domain Restrictions: Consider a (partial) function \(f: A \rightharpoonup B\) and a set \(C\).

We can “create” a new function \(f|_C\) by “restricting the domain of \(f\) to \(C\)”:

• \(f|_C: (A \cap C) \rightharpoonup B\) (New Input Domain)
• The graph of \(f|_C\) is given by: \(f|_C = \{(x,y) \in f \mid x \in C \}\)

(We make the domain smaller to only include values in \(C\).)

Example: Consider \(f: \mathbb{R} \rightarrow \mathbb{R}\) defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\).

Note: \(C\) need not be a subset of \(A\). If \(C\) has “extra” values/values not in \(A\), they are ignored.

E.g., let \(g : \omega \rightarrow \mathbb{Z}\) be defined by \(n \mapsto (-1)^n \cdot n^2\) for all \(n \in \omega\).

Set Images: Consider a (partial) function \(f: A \rightarrow B\) and a set \(C\).

The image of \(C\) under \(f\) is defined to be the set of all “output” values when elements from \(C\) are “inputted” into \(f\):

This is just \(\text{Im}(f|_C)\).

Notation: The image of \(C\) under \(f\) is denoted by: \(f’‘C\)

Example: Consider \(f: \mathbb{R} \rightarrow \mathbb{R}\) defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\).

The image of a set is always defined; \(f(i)\) is undefined here, so \(f’’\{i\} = \emptyset\).

Why the notation matters: let \(g: \{ \emptyset, \{ \emptyset \} \} \rightarrow \mathbb{R}\) with \(g(\emptyset) = 17\) and \(g(\{ \emptyset \}) = \pi\). Then

so \(g(\emptyset) \neq g’’\emptyset\) and \(g(\{ \emptyset \}) \neq g’’\{ \emptyset \}\): “plugging in” a set and “taking the image of” a set are different operations.

Consider \(f: A \to B\) and a set \(C\). We denote the image of \(C\) under \(f\) by either \(\text{Im}(f(C))\) or \(f’‘C\). Sometimes people write \(f(C)\). This notation can be problematic.

Consider a function whose input domain consists of sets which is defined by:

\(A \mapsto A \cup \{A\}\). (\(S(A) = A \cup \{A\}\))

Now: \(S(\emptyset) = \emptyset \cup \{\emptyset\} = \{\emptyset\}\)
\(S(\{\emptyset\}) = \{\emptyset\} \cup \{\{\emptyset\}\} = \{\emptyset, \{\emptyset\}\}\)
\(S(\{\emptyset, \{\emptyset\}\}) = \{\emptyset, \{\emptyset\}\} \cup \{\{\emptyset, \{\emptyset\}\}\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\)

\(S’’\emptyset = \emptyset\)
\(S’’\{\emptyset\} = \{S(\emptyset)\} = \{\{\emptyset\}\}\)
\(S’’\{\emptyset, \{\emptyset\}\} = \{S(\emptyset), S(\{\emptyset\})\} = \{\{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\)

Notice: \(S(\emptyset) \neq S’’\emptyset\)
\(S(\{\emptyset\}) \neq S’’\{\emptyset\}\)
\(S(\{\emptyset, \{\emptyset\}\}) \neq S’’\{\emptyset, \{\emptyset\}\}\)

``\(f’‘C\) is defined for every set \(C\) (if \(C\) is not a set, undefined)

\(f(C)\) is defined for every \(C \in \text{Dom}(f)\) (if \(C \notin \text{Dom}(f)\), undefined)

Concerning Domain Restrictions & Changing Codomains

If \(f: A \rightarrow B\) is a partial function, \(f|_{\text{dom}(f)}: \text{dom}(f) \rightarrow B\) is a total function.

If \(f: A \rightarrow B\) is a function, we can find some set \(\hat{A} \subseteq A\) such that

\(f|_{\hat{A}} : \hat{A} \rightarrow B\) is an injection.

E.g. \(f: \mathbb{R} \rightarrow \mathbb{R}\), defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\).

\(f|_{[0, \infty)}: [0, \infty) \mapsto \mathbb{R}\) defined by \(x \mapsto x^2\) for all \(x \in [0, \infty)\) is an injection.

If \(f: A \rightarrow B\) is a function, we can change the codomain to create a new function

\(f: A \xrightarrow{\text{onto}} \text{Im}(f)\) that is a surjection.

E.g. \(f: \mathbb{R} \rightarrow \mathbb{R}\), defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\)

\(f: \mathbb{R} \xrightarrow{\text{onto}} [0, \infty)\), defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\) is a surjection.

Comment: Let \(f: A \rightarrow B\) be a function. Range\((f) = \text{Image}(f) = f’‘A\).

(If \(f: A \rightarrow B\), Range\((f) = \text{Im}(f) = f’‘A = f’’\text{dom}(f)\).)

Inverse Set Images
Let \(f: A \to B\), and let \(C\) be a set.
The inverse image of \(C\) under \(f\) is denoted by \(f^{-1}(C)\) and is defined by:

``Idea": \(f^{-1}(C)\) is the set of all values in the domain of \(f\) that map to something in \(C\).

``Notes": \(f^{-1}(C)\) is defined for every set \(C\) (only undefined if \(C\) is not a set)

\(f^{-1}(B) = f^{-1}(\text{Range}(f)) = \text{Dom}(f)\)

Example: Consider \(f: \mathbb{R} \to \mathbb{R}\) defined by \(x \mapsto x^2\) for all \(x \in \mathbb{R}\).

More examples (same \(f\)):

(The class notes write the inverse image as \(f^{-1}{}‘‘C\), to match the \(f’‘C\) notation.)

Aside: why \(0.\overline{9} = 1\) (this came up when discussing non-unique decimal expansions): \[ \begin{aligned} x &= 0.\overline{9} \\ 10x &= 9.\overline{9} \\ x &= 0.\overline{9} \\ \hline 9x &= 9 \\ x &= \frac{9}{9} = 1 \end{aligned} \]

Exercises #

1. Show that \(F : \mathbb{Q} \to \mathbb{R}\) “defined” by \(\frac{a}{b} \mapsto a + b\) does not satisfy (ii), \((\forall a \in A)(\forall b_1 \in B)(\forall b_2 \in B)[((a, b_1) \in F \land (a, b_2) \in F) \Rightarrow b_1 = b_2]\), and thus is not a function.

2. Prove that \(f: \mathbb{R} \setminus \{7\} \to \mathbb{R} \setminus \{5\}\), \(x \mapsto \frac{5x-2}{x-7}\), is a bijection (the “onto” half was done above; do the “1-1” half).

3. Find \(f’’[-1, 2)\) and \(f^{-1}([-4, 1))\) for \(f: \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\).

Module 4: Towards the Definition of a Limit #

Consider the function \(f:\mathbb{R}\to\mathbb{R}\) defined by

(For \(x \neq 3\), \(\frac{x^2-9}{x-3} = \frac{(x+3)(x-3)}{x-3} = x + 3\).)

Notice that:

\(\text{Im}(f|_{(1,5)}) = f’’(1,5) = (4,8) \cup \{9\}\)
↪ \((1,5) = (3-2, 3+2)\) is an (open) interval about \(3\).

Goal: We want to create/find a definition of the limit, i.e., we want to find a predicate/formula \(\varphi_{\lim}(f, a, L)\) which will be true exactly when \(\lim_{x \to a} f(x) = L\).

Notice that we can “remove” \(9\) from the image by excluding \(3\) from the set we are finding the image of:

\(\text{Im}(f|_{(1,5)\setminus\{3\}}) = f’’((1,5)\setminus\{3\}) = (4,8)\setminus\{6\}\)

\((1,5) \setminus \{3\}\) is a “punctured” open interval about \(3\).

Notice that \((4,8)\setminus\{6\} \subseteq (4,8)\) and \((4,8)\) is an interval that contains \(6\), the value that we would like to be the limit as \(x\to3\).

Some intervals from class (for \(L = 4\), which will turn out not to be the limit): Player I (see the game below) might play \((2,6)\) (\(e=2\)), \((3,5)\) (\(e=1\)) or \((3.9, 4.1)\) (\(e=0.1\)); Player II might answer with \((2,4)\setminus\{3\}\) (\(d=1\)) or \((1,5)\setminus\{3\}\) (\(d=2\)).

I’m going to describe a “game” for a number L.

In this game, there are two Players: I & II, and Player I always goes first.

I plays an open interval about L, i.e., an interval of the form \((L-e, L+e)\) for some positive (real) number \(e\).

II plays a “punctured” open interval about 3, i.e., an interval of the form \((3-d, 3+d)\setminus\{3\}\) for some positive (real) number \(d\).

Player II wins the game if \(f’’(3-d, 3+d) \setminus\{3\}) \subseteq (L-e, L+e)\)

Example Game #1: (\(L = 9\)) Player I gives/plays \((9-4, 9+4) = (5, 13)\)

Player II Attempts: \(f’’((1, 5)\setminus\{3\}) = (4, 8)\setminus\{6\} \nsubseteq (5, 13) (d=2)\) \(f’’((2, 4)\setminus\{3\}) = (5, 7)\setminus\{6\} \subseteq (5, 13) (d=1)\)

Player II can play to win!

(If Player II uses any \(d \in (0, 1)\), they’ll win)

Example Game #2: (\(L=9\)) Player I gives/plays \((9-1, 9+1) = (8,10)\)
Player II Attempts : \(f’’((1,5)\setminus\{3\}) = (4,8) \setminus\{6\} \nsubseteq (8,10)\) (\(d=2\))
\(f’’((2,4)\setminus\{3\}) = (5,7)\setminus\{6\} \nsubseteq (8,10)\) (\(d=1\))

Notice that as Player II decreases \(d\), the image will stay disjoint from \((8, 10)\), so the image will never be a subset. As \(d\) increases, the image will still have values that are not in \((8,10)\).
Player II can’t play to win.

Example Game #3: (\(L=6\)) Player I gives/plays \((6-1, 6+1) = (5,7)\)
Player II can play \((2,4)\backslash\{3\}\) to win:
\(f’’((2,4)\backslash\{3\}) = (5,7)\backslash\{6\} \subseteq (5,7)\)

Example Game #4: (\(L=6\)) Player I gives/plays \((6-0.01, 6+0.01) = (5.99, 6.01)\)
Player II can play \((2.99, 3.01) \backslash \{3\}\) to win:
\(f’’((2.99, 3.01)\backslash\{3\}) = (5.99, 6.01) \backslash\{6\} \subseteq (5.99, 6.01)\)

Notice that in the games where L=9, Player I could play to win (in Game #2), by making e small enough. However, when L=6, no matter how small Player I made e, Player II could make d small enough to still win. It turns out that for any other value of L (other than 6) Player I can win (This will actually give us lead us to a definition of the limit.)

Play the game yourself: drag the sliders. Player I picks \(L\) and \(e\) (the blue horizontal band is \((L-e, L+e)\)); Player II picks \(d\) (the green vertical band is the punctured interval \((3-d, 3+d)\setminus\{3\}\)). Player II wins when the orange graph over the green band stays inside the blue band. Try \(L = 9\) and \(L = 6\).

“No matter what Player I chooses for \(e\), Player II can find a \(d\) such that \(f’’((3-d, 3+d)\setminus\{3\}) \subseteq (6-e, 6+e)\)” determines who “wins” the game.

Let \(\varphi_{\lim} (f, 3, 6)\) be the formula/predicate:

“For every positive value of \(\epsilon\), there exists a positive value of \(\delta\) such that \(f’’( (3-\delta, 3+\delta) \setminus \{3\} ) \subseteq (6-\epsilon, 6+\epsilon)\). "

We can more formally write this as follows: (Using \(\epsilon\) (epsilon) for \(\epsilon\) and \(\delta\) (delta) for \(\delta\))

\((\forall \epsilon > 0) (\exists \delta > 0) (f’’( (3-\delta, 3+\delta) \setminus \{3\} ) \subseteq (6-\epsilon, 6+\epsilon)) (\varphi_{\lim}(f,3,6))\)

Notation: \((\forall \epsilon > 0)\) is shorthand for \((\forall \epsilon \in (0, \infty))\)

\((\exists \delta > 0)\) is shorthand for \((\exists \delta \in (0, \infty))\)

Generalization:

\((\forall \epsilon > 0) (\exists \delta > 0) (f’’((a-\delta, a+\delta) \setminus \{a\}) \subseteq (L-\epsilon, L+\epsilon)) (\varphi_{\lim}(f, a, L))\)

Unpacking the subset condition. Recall \(A \subseteq B\) iff \((\forall \alpha)(\alpha \in A \Rightarrow \alpha \in B)\). Also, \(\alpha \in f’’((a-\delta, a+\delta) \setminus \{a\})\) exactly when \(\alpha = f(x)\) for some \(x \in \text{Dom}(f)\) with \(x \in (a-\delta, a+\delta) \setminus \{a\}\). So

(If \(x \notin \text{Dom}(f)\) the antecedent is false, so the implication is true and such \(x\) cause no trouble.)

For the last step we used that for real numbers \(\beta, A\) and \(b > 0\):

In our “Limit Games”, Player I plays an interval around a value \(L\), then Player II plays a punctured interval around a value \(a\). Player II wins if whenever we take \(x\) from II’s punctured interval, \(f(x)\) stays in Player I’s interval. More symbolically, Player II wins if:

(Removing \(x = a\) from consideration “punctures” II’s interval.)

We say that \(\lim_{x \to a} f(x) = L\) exactly when II can always play to win, no matter what Player I plays:

Playing the Game Algebraically #

Let \(f(x) = (x-5)^2\). We claim \(\varphi_{\lim}(f, 5, 0)\), i.e., that \(\lim_{x \to 5} f(x) = 0\). (\(f: \mathbb{R} \to \mathbb{R}\))

If this is in fact the case, Player II can always play to win.

Let’s say I plays \(\epsilon = 2\). Player II needs to find/play a value \(\delta\) such that whenever \(x \in (5-\delta, 5+\delta) \setminus \{5\}\) we have \(f(x) \in (0-2, 0+2)\).

We work backwards from what we want:

\(f(x) \in (-2, 2)\)

\(-2 < f(x) < 2\)

\(-2 < (x-5)^2 < 2\)

Any real squared is greater than or equal to zero. \(0 \le (x-5)^2 < 2\)

As \((x-5)^2 \ge 0\), the square root is defined. \( 0 \le |x-5| < \sqrt{2} \) If \(|A| < B\), then \(-B < A < B\). Also: \(\sqrt{A^2} = |A|\).

\(-\sqrt{2} < x - 5 < \sqrt{2}\)

\(5 - \sqrt{2} < x < 5 + \sqrt{2}\)

\(x \in (5 - \sqrt{2}, 5 + \sqrt{2})\)

This suggests that we can let \(\delta = \sqrt{2}\) (or any smaller value.)

(Recall: \(\sqrt{A^2} = |A|\), and \(|A| < B\) is equivalent to \(-B < A < B\). E.g. \(|A| < 17\) means \(-17 < A < 17\). Likewise \(|x - a| < \delta\) is equivalent to \(a - \delta < x < a + \delta\).)

Generalizing: (Still consider \(f(x)=(x-5)^2\), \(a=5\), \(L=0\))

We know I will play some \(\epsilon > 0\), with this information, let’s see if we can determin II’s play (\(\delta > 0\)) based off of what value I chooses for \(\epsilon\).

Again, we’ll work backwards from what we want:

Player II needs to use \(\delta = \sqrt{\epsilon}\) (or a smaller value) to win.

Comment: \(x \in (a-\delta, a+\delta)\) is equivalent to \(|x-a| < \delta\), and

\(f(x) \in (L-\epsilon, L+\epsilon)\) is equivalent to \(|f(x)-L| < \epsilon\), so we can write \(\varphi_{\lim}(f, a, L)\) by:

\((\forall \epsilon > 0)(\exists \delta > 0) (\forall x \in \text{Dom}(f) \setminus \{a\})( |x-a| < \delta \implies |f(x) - L| < \epsilon)\)

Now, consider

We will again claim \(\varphi_{\lim}(f, 5, 0)\).

We again will try to find II’s move \(\delta\) for given moves \(\epsilon > 0\) that Player I makes.

Player I Plays \(\epsilon = \frac{1}{2}\): Need: \(|f(x) - 0| < \frac{1}{2}\) (i.e., \(f(x) \in (0 - \frac{1}{2}, 0 + \frac{1}{2})\))

For the “replacement”, we know we are excluding 5, but we’ll also want to make \(\delta\) small enough not to include 4 nor 6, as we only want to consider \(f(x)\) near \(x=5\), so that we only use \((x-5)^2\).

This means we’ll need \(\delta \le 1\).

With this restriction:

(\(\sqrt{\frac{1}{2}} < 1\), so this is fine!)

Player I Plays \(\epsilon = 4\): Need \(|f(x) - 0| < 4\), i.e. \(-4 < f(x) < 4\).

Again, we’ll need to require \(\delta \leq 1\) so that we only are using \((x-5)^2\) (which is what \(f(x)\) is equal to “close” to \(a = 5\)).

As we need \(\delta \leq 1\) and \(\delta \leq 2\), we take the minimum, and we let \(\delta = 1\) (or smaller).

Generalizing: Need \(|f(x) - 0| < \epsilon\), i.e. \(-\epsilon < f(x) < \epsilon\). When \(\delta \leq 1\), we will have \(f(x) = (x-5)^2\):

As \(\delta \leq 1\) and \(\delta \leq \sqrt{\epsilon}\), we let \(\delta = \min(1, \sqrt{\epsilon})\) (or smaller).

• Proof Outline:
• Proof:
• Introduce the function \(f\) (Domain, Codomain, “rule”).
• Let \(\epsilon > 0\) be arbitrary.
• Let \(\delta = \dots\) (found in scratch work) \(\implies\) Work backwards from \(|f(x) - L| < \epsilon\), to get \(|x-a| < \delta\). \(\delta\) can be based on/depend on \(\epsilon\).
• Show/State \(\delta > 0\) (and is real). May need to set \(\delta\) equal to a minimum of multiple values.
• Let \(x \in \text{Dom}(f) \setminus \{a\}\) be arbitrary.
• Assume/Suppose \(|x-a| < \delta\).
• Show \(|f(x) - L| < \epsilon\). \(\implies\) This will generally be the scratch work in reverse, or very similar with explanations added.
• “Hence, if \(|x-a| < \delta\), then \(|f(x) - L| < \epsilon\).”
• “As \(x\) was arbitrary, for all \(x \in \text{Dom}(f) \setminus \{a\}\), if \(|x-a| < \delta\), then \(|f(x) - L| < \epsilon\).”
• “As \(\delta > 0\), there exists a \(\delta > 0\) such that for all \(x \in \text{Dom}(f) \setminus \{a\}\), if \(|x-a| < \delta\), then \(|f(x) - L| < \epsilon\).”
• “As \(\epsilon > 0\) was arbitrary, for all \(\epsilon > 0\), then exists a \(\delta > 0\) such that for all \(x \in \text{Dom}(f) \setminus \{a\}\), if \(|x-a| < \delta\), then \(|f(x) - L| < \epsilon\).”
• “Therefore, \(\lim_{x \to a} f(x) = L\).”
• QED/End Proof Symbol.

For \(f: \mathbb{R} \rightarrow \mathbb{R}\), defined by \(f(x) = (x-5)^2\), we will prove \(\lim_{x \to 5} f(x) = 0\).

Proof: Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be the function defined by \(f(x) = (x-5)^2\) for all \(x \in \mathbb{R}\). Let \(\varepsilon > 0\) be arbitrary. Let \(\delta = \sqrt{\varepsilon}\). As \(\varepsilon > 0\), we have that \(\delta > 0\). Now, let \(x \in \mathbb{R} \setminus \{5\}\) be arbitrary. Suppose \(|x - 5| < \delta\). Now:

As \((x - 5)^2 \geq 0\), \(|(x - 5)^2| = (x - 5)^2\), so we have:

Hence, \(|f(x) - 0| < \varepsilon\). Thus, if \(|x - 5| < \delta\), then \(|f(x) - 0| < \varepsilon\). As \(x\) was arbitrary, for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x - 5| < \delta\), then \(|f(x) - 0| < \varepsilon\). As \(\delta > 0\), then exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x - 5| < \delta\), then \(|f(x) - 0| < \varepsilon\). As \(\varepsilon > 0\) was arbitrary, for all \(\varepsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x - 5| < \delta\), then \(|f(x) - 0| < \varepsilon\). Therefore, \(\lim_{x \to 5} f(x) = 0\).

Recall that \(\varphi_{\lim}(f, a, L)\) is the predicate:

\((\forall \epsilon > 0)(\exists \delta > 0)(\forall x \in \text{Dom}(f)\setminus\{a\})(|x - a| < \delta \implies |f(x) - L| < \epsilon)\)

We write \(\lim_{x \to a} f(x) = L\) exactly when \(\varphi_{\lim}(f, a, L)\) is true.

Warm Up: We will prove that \(\lim_{x \to 1} (2x + 7) = 9\). (\(f(x) = 2x + 7\), \(f: \mathbb{R} \to \mathbb{R}\))

“Scratch Work”: \(|f(x) - 9| < \epsilon\) (work backwards)

\(|(2x + 7) - 9| < \epsilon\)

\(|2x - 2| < \epsilon\)

\(2|x - 1| < \epsilon\)

\(|x - 1| < \epsilon/2\) (We set \(\delta = \epsilon/2\))

We can now write the proof.

Proof: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by \(f(x) = 2x + 7\) for all real values of \(x\).

Let \(\epsilon > 0\) be arbitrary. Now, let \(\delta = \epsilon/2\). Notice that as \(\epsilon > 0\), we have \(\delta > 0\).

Now, let \(x \in \mathbb{R} \backslash \{1\}\) be arbitrary, and suppose \(|x - 1| < \delta\). Now:

\(|x - 1| < \epsilon/2\)

\(2|x - 1| < \epsilon\)

\(|2x - 2| < \epsilon\)

\(|(2x + 7) - 9| < \epsilon\)

\(|f(x) - 9| < \epsilon\).

Hence, we have \(|f(x) - 9| < \epsilon\). Therefore, if \(|x-1| < \delta\), then \(|f(x) - 9| < \epsilon\). As x was arbitrary, for all \(x \in \mathbb{R} \setminus \{1\}\), if \(|x-1| < \delta\), then \(|f(x) - 9| < \epsilon\). As \(\delta > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{1\}\), if \(|x-1| < \delta\), then \(|f(x) - 9| < \epsilon\). As \(\epsilon > 0\) was arbitrary, for all \(\epsilon > 0\), then exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{1\}\) if \(|x-1| < \delta\), then \(|f(x) - 9| < \epsilon\). Hence, we have \(\lim_{x \to 1} f(x) = 9\).

Now, consider \(f : \mathbb{R} \to \mathbb{R}\) defined by

Here, we still have that \(\lim_{x \to 1} f(x) = 9\), and the proof is almost identical:

• When we introduce the function at the start, we would introduce this function instead.

• In the “calculation” portion, after we have \(|(2x+7) - 9| < \epsilon\), we would note that as \(x \neq 1\), \(f(x) = 2x+7\), so that we can write \(|f(x) - 9| < \epsilon\). (Recall \(x \in \mathbb{R} \setminus \{1\}\) was arbitrary, so \(x \neq 1\))

Now, consider \(f:\mathbb{R}\rightarrow \mathbb{R}\) defined by

We will show/prove \(\varphi_{\lim} (f, 5, 0)\), i.e., \(\lim_{x\to 5} f(x) = 0\).

Logical Form: \((\forall \epsilon > 0) (\exists \delta > 0) (\forall x \in \text{Dom}(f)\setminus\{5\}) (|x-5| < \delta \implies |f(x) - 0| < \epsilon)\)

Previously: If we just had \(f(x) = (x-5)^2\), we needed to set \(\delta = \sqrt{\epsilon}\). This won’t quite work for us here.

Recall the “game”: If Player I plays \(\epsilon = 4\), Player II will need to find a value of \(\delta\) that will keep the function values in \((0-4, 0+4)\), i.e., between -4 and 4.

If II plays \(\sqrt{\epsilon} = \sqrt{4} = 2\), we are keeping \(x\) between \(5-2=3\) and \(5+2 = 7\), i.e., in the interval: \((3,7) \setminus \{5\}\).

This will be fine for any \(x\) that is not an integer, however, notice that if \(x=4\) or \(x=6\), we have \(f(x) = 9\), which is not in \((-4, 4)\).

(So Player II would lose)

Instead, Player II needs to make \(\delta\) small enough to avoid these values.

As long as Player I keeps \(\delta \leq 1\), there will be no other integers in \((5-\delta, 5+\delta) \setminus \{5\}\) so the case when \(x \in \mathbb{Z}\) won’t come up, and we just will have \(f(x) = (x-5)^2\).

Key Fact: The minimum of a collection of values is less than or equal to each of the values:

(E.g. \(\min(1, 3, 2, 17) = 1\), which is \(\le 1\), \(\le 3\), \(\le 2\) and \(\le 17\).) We will also use that if \(a < b\) and \(b \leq c\), then \(a < c\).

Also, when Player II is playing a \(\delta\), any value less than a “winning” \(\delta\) will also win.

In our case, we will set \(\delta = \min(\sqrt{\epsilon}, 1)\). (Note: A min. of positive numbers is positive.)

Proof: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by

Let \(\epsilon > 0\) be arbitrary and let \(\delta = \min(\sqrt{\epsilon}, 1)\). As \(\epsilon > 0\), we have that \(\delta > 0\), as both \(\sqrt{\epsilon} > 0\) and \(1 > 0\). Now, let \(x \in \mathbb{R} \setminus \{5\}\) be arbitrary, and suppose that \(|x - 5| < \delta\).

As \(\delta = \min(\sqrt{\epsilon}, 1)\), we have that \(\delta \leq 1\), so that \(|x - 5| < \delta \leq 1\) and \(|x - 5| < 1\).

From this, \(-1 < x - 5 < 1\) and \(4 < x < 6\). As \(x \neq 5\) and \(4 < x < 6\), we have that \(x \notin \mathbb{Z}\). Hence, we have that \(f(x) = (x - 5)^2\).

Now, as \(\delta = \min(\sqrt{\epsilon}, 1)\), we also have that \(\delta \leq \sqrt{\epsilon}\), so \(|x - 5| < \delta \leq \sqrt{\epsilon}\) and \(|x - 5| < \sqrt{\epsilon}\).

Now:

As \((x-5)^2 \geq 0\), \(|(x-5)^2| = (x-5)^2\), so we have:

As we found \(f(x) = (x-5)^2\), we have that \(|f(x) - 0| < \epsilon\). Thus, if \(|x-5| < \delta\), then \(|f(x)-0|<\epsilon\).

As \(x\) was arbitrary, for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x-5| < \delta\), then \(|f(x) - 0| < \epsilon\).

As \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x-5| < \delta\), then \(|f(x) - 0| < \epsilon\).

As \(\epsilon\) was arbitrary, for all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{5\}\), if \(|x-5| < \delta\), then \(|f(x) - 0| < \epsilon\).

Therefore, \(\lim_{x \to 5} f(x) = 0\). \(\square\)

Example: Consider \(f: \mathbb{R} \to \mathbb{R}\) defined by

We will show \(\varphi_{\lim}(f,0,6)\), i.e., \(\lim_{x \to 0} f(x) = 6\).

There are four different “parts” of the domain of \(f\):

Cases:

• (i) \(x < -2\)
• (ii) \(-2 \leq x < 0\)
• (iii) \(x=0\)
• (iv) \(x > 0\)

We choose \(x \in \mathbb{R} \setminus \{0\}\), so this case won’t come up.

If we have \(\delta \leq 2\), we will have \(-2 < x < 2\), so case (i) won’t be relevant.

(This means we will set \(\delta = \min(2, \dots)\))

For case (ii): \(-2 \leq x < 0\). Here: \(f(x) = 3(x+2)\) as \(-2 \leq x < 0\) implies \(x+2 \geq 0\), so \(|x+2| = x+2\). Also, \(0 \leq x+2 < 2\), so

For case (iv): Here: \(f(x) = 7x^2 + 6\).

\(|f(x) - 6| < \epsilon\)
\(|7x^2 + 6 - 6| < \epsilon\)
\(|7x^2| < \epsilon\)
\(7|x^2| < \epsilon\)
\(|x^2| < \frac{\epsilon}{7}\)
\(|x| < \sqrt{\frac{\epsilon}{7}}\)

We need: \(|x - 0| < \sqrt{\frac{\epsilon}{7}} \implies \delta \leq \sqrt{\frac{\epsilon}{7}}\), so \(\delta = \min(2, \frac{\epsilon}{3}, \sqrt{\frac{\epsilon}{7}})\)

Proof: Let \(f:\mathbb{R}\rightarrow \mathbb{R}\) be the function defined by

Let \(\epsilon > 0\) be arbitrary. Define \(\delta = \min(2, \frac{\epsilon}{3}, \sqrt{\frac{\epsilon}{7}})\). As \(\epsilon > 0\), we have \(\frac{\epsilon}{3} > 0\) and \(\sqrt{\frac{\epsilon}{7}}>0\). As \(2>0\) as well, we have \(\delta>0\). Let \(x \in \mathbb{R} \setminus \{0\}\) be arbitrary, and suppose \(|x - 0| < \delta\). We will consider two cases, either \(x < 0\) or \(x > 0\).

Case 1: Suppose \(x < 0\). As \(x < 0\), we have that \(f(x) = 3|x + 2|\). As \(\delta \leq 2\) and \(|x - 0| < \delta\), we have that \(|x - 0| < 2\) so that \(|x| < 2\) and \(-2 < x < 2\). Hence, \(0 < x + 2 < 4\). As \(x + 2 > 0\), we have that \(|x + 2| = x + 2\), so that \(f(x) = 3(x + 2)\). Also, as \(\delta \leq \frac{\epsilon}{3}\), we have \(|x - 0| < \frac{\epsilon}{3}\).

Now: \(|x-0| < \frac{\epsilon}{3}\)

As \(f(x) = 3(x+2)\), we have \(|f(x)-6|<\epsilon\).

Case 2: Now, suppose \(x>0\). Thus, we have that \(f(x)=7x^2+6\). As \(\delta \leq \sqrt{\frac{\epsilon}{7}}\) and \(|x-0|<\delta\), we have that \(|x-0|<\sqrt{\frac{\epsilon}{7}}\). Now:

As \(f(x) = 7x^2+6\), we have that \(|f(x)-6|<\epsilon\).

These cases are exhaustive, hence, \(|f(x)-6|<\epsilon\). Thus, if \(|x-0|<\delta\), then \(|f(x)-6|<\epsilon\). As \(x\) was arbitrary, for all \(x \in \mathbb{R} \setminus \{0\}\), if \(|x-0|<\delta\), then \(|f(x)-6|<\epsilon\).

As \(\delta > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{0\}\), if \(|x-0|<\delta\), then \(|f(x)-6|<\epsilon\). As \(\epsilon\) was arbitrary, for all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{0\}\), if \(|x-0|<\delta\), then \(|f(x)-6|<\epsilon\). Therefore, \(\lim_{x \to 0} f(x) = 6\).

\(\square\)

Example: Let \(f: \mathbb{R} \to \mathbb{R}\) be defined by

For instance \(f(\sqrt{2}) = 0\), \(f(0) = 0\), \(f(4) = 16\), \(f(\pi) = 0\) and \(f(\sqrt{9}) = 9\). We claim \(\lim_{x \to 0} f(x) = 0\), i.e.

\((\forall \epsilon > 0)(\exists \delta > 0)(\forall x \in \mathbb{R} \setminus \{0\})(|x - 0| < \delta \Rightarrow |f(x) - 0| < \epsilon)\).

Scratch work, by cases on \(x\):

So \(\delta = \sqrt{\epsilon}\) works for both cases.

\(\varphi_{\lim}(f, a, L)\) iff \((\forall \epsilon > 0)(\exists \delta > 0)(\forall x \in \text{Dom}(f)\setminus\{a\})(|x-a|<\delta \implies |f(x) - L| < \epsilon)\)

Let’s examine the function \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) defined by \(f(x) = x^2\) for all \(x \in \mathbb{Z}\). (E.g. \(f(5) = 25\), \(f(-2) = 4\), \(f(1) = 1\), \(f(0) = 0\), while \(f(\frac{1}{2})\) is undefined as \(\frac{1}{2} \notin \mathbb{Z}\).)

We’ll take a look at the formula \(\varphi_{\lim}(f, 2, 4)\):

\((\forall \epsilon > 0)(\exists \delta > 0)(\forall x \in \mathbb{Z}\setminus\{2\})(|x-2| < \delta \implies |f(x)-4| < \epsilon)\)

In the “Game”, if Player II plays any \(\delta \leq 1\), \(|x-2| < \delta\) will just be false:

As \(x \in \mathbb{Z}\setminus\{2\}\), there are no values of \(x\) which satisfy \(1 < x < 3\).

This makes the implication (trivially) true, so \(\varphi_{\lim}(f, 2, 4)\) is true.

For the same reasoning/logic, \(\varphi_{\lim}(f, 2, 17)\) will also be true.

Using our limit notation, we would write both

We don’t want this sort of issue to come up, we want the limit to be well defined & unique.

The issue/problem in this example was that the punctured open interval \((2-\delta, 2+\delta) \setminus \{2\}\) was disjoint from the domain of the function, i.e.,:

In other words, the issue is that we could find an open interval that isolates 2 from the domain of \(f\).

Let’s consider a similar, but different function:

Where

Listing a few of the elements of \(D\) by \(m\):

“Picture” of \(D\):

For example, zooming in near \(1\) and \(2\):

Now let \(f : D \to \mathbb{R}\) be defined by \(x \mapsto x^2\) for all \(x \in D\). For this function \(\varphi_{\lim}(f, 2, L)\) will be true if \(L = 4\), but will be false for any \(L \neq 4\):

• For \(L = 4\), whatever Player I chooses for \(\epsilon > 0\), Player II can “win” by playing \(\delta = \min(2, \frac{\epsilon}{6})\).
• For \(L \neq 4\), Player I can find a value of \(\epsilon > 0\) small enough that Player II cannot play to win.

Definition (Accumulation Point) Let \(D \subseteq \mathbb{R}\). We say that \(a \in \mathbb{R}\) is an accumulation point of \(D\) iff

Equivalent to:

or

Definition (Condensation Point) Let \(D \subseteq \mathbb{R}\). We say that \(a \in \mathbb{R}\) is a condensation point of \(D\) iff

Equivalent to:

or

Examples. Let \(D = (0, 1] \cup \{2\}\).

• \(-17\): \((-18, -16) \cap D = \emptyset\), which is not infinite, so \(-17\) is not an accumulation point of \(D\).
• \(0\): \((-1, 1) \cap D = (0, 1)\), \((-0.1, 0.1) \cap D = (0, 0.1)\), \((-0.01, 0.01) \cap D = (0, 0.01)\), … always infinitely many (in fact uncountably many) elements, so \(0\) is an accumulation point (and a condensation point) of \(D\).
• \(0.5\): \((0.4, 0.6) \cap D = (0.4, 0.6)\) is uncountable, so \(0.5\) is an accumulation and condensation point of \(D\).
• \(1\): \((-1, 2) \cap D = (0, 1]\), \((0.001, 1.1) \cap D = (0.001, 1]\), \((0.9999, 1.00001) \cap D = (0.9999, 1]\), … so \(1\) is an accumulation (and condensation) point.
• \(1.5\): \((0.5, 1.6) \cap D = (0.5, 1]\) is infinite, but \((1, 2) \cap D = \emptyset\) is not. As we need every open interval about \(1.5\) to meet \(D\) in infinitely many points, \(1.5\) is not an accumulation point of \(D\).
• \(2\): \((1.9, 2.1) \cap D = \{2\}\), so \(2\) is not an accumulation point of \(D\) (even though \(2 \in D\)).
• \(3\): \((2.9, 3.1) \cap D = \emptyset\), so \(3\) is not an accumulation point of \(D\).

Example. Let \(D = \{0, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, 1\}\). Then \((0.249, 0.251) \cap D = \{\frac{1}{4}\}\), so \(\frac{1}{4}\) is not an accumulation point. In fact a finite set has no accumulation points.

Example. Let \(B = \{0\} \cup \{\frac{1}{n+1} \mid n \in \mathbb{N}\} = \{0, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots\}\).

\((-0.5, 0.5) \cap B = \{0, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{6}, \dots\}\) is infinite, so \(0\) is an accumulation point of \(B\). However this set is countable: \(F: \mathbb{N} \to (-0.5, 0.5) \cap B\) with \(1 \mapsto 0\) and \(n \mapsto \frac{1}{n+1}\) for \(n \ge 2\) (\(2 \mapsto \frac{1}{3}, 3 \mapsto \frac{1}{4}, \dots\)) is a bijection, so the intersection is countable, not uncountable. Hence \(0\) is not a condensation point of \(B\).

Exercises. Find all accumulation points and all condensation points of:

1. \((0, 1)\)
2. \(D = (0, \tfrac{1}{2}) \cup (1, 1\tfrac{1}{3}) \cup (2, 2\tfrac{1}{4}) \cup (3, 3\tfrac{1}{5}) \cup (4, 4\tfrac{1}{6}) \cup \dots\)

With these “new” terms, let’s examine the sets \(\mathbb{Z}\) and \(D = \mathbb{Z} \cup \{m+\frac{1}{n} \mid m \in \mathbb{Z}, n \in \mathbb{N}\}\) (both \(\mathbb{Z} \subseteq \mathbb{R}\) and \(D \subseteq \mathbb{R}\)).

In \(\mathbb{Z}\):

Notice \(1.5\) & \(2.5\) are both real, \(1.5 < 2 < 2.5\), but \((1.5, 2.5) \cap \mathbb{Z} = \{2\}\) which is not infinite.

This tells us that \(2\) is not an accumulation point (nor a condensation point) of \(\mathbb{Z}\). For similar reasons, no value will be an accumulation (condensation) point of \(\mathbb{Z}\).

In \(D\): (drag \(c\) and \(d\))

Here, no matter what values of \(c\) & \(d\) are chosen with \(c < 2 < d\), there will be infinitely many points in \((c,d) \cap D\) (specifically the points will be to the right of \(2\)).

This tells us that \(2\) is an accumulation point of \(D\). Similarly, every integer will be an accumulation point of \(D\).

(Still Examining \(D\)) Zooming in on \((1.9, 2.3)\):

If we were to choose \(c = 1.9\) and \(d = 2.3\) (\(1.9 < 2 < 2.3\)), we can define \(f:\mathbb{N} \xrightarrow[\text{onto}]{1-1} ((1.9, 2.3) \cap D) \setminus \{2\}\) as follows:

As this function is a bijection, \(((1.9, 2.3) \cap D) \setminus \{2\}\) is denumerable / countable.

This tells us that 2 is not a condensation point of D. (In fact, every integer in D is not a condensation point).

Also notice that any non-integer value in D will not be an accumulation point.

Example: \([e, \pi]\). Every point of \([e, \pi]\) (e.g. \(2.8\), \(3\), \(3.1\)) is an accumulation point, and so are the endpoints \(e\) and \(\pi\); the set of accumulation points is \([e, \pi]\) (these are also all condensation points).

(Adjusted/Fixed) Definition:

Let \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\). Also, let \(f: D \to E\) and suppose \(a \in \mathbb{R}\) is an accumulation point of \(D\). Then:

\(\varphi_{\lim} (f, a, L) \text{ iff } (\forall \epsilon > 0)(\exists \delta > 0)(\forall x \in \text{dom}(f) \setminus \{a\})( |x-a| < \delta \Rightarrow |f(x) - L| < \epsilon)\)

With this additional requirement that \(a\) be an accumulation point of the domain, we avoid the issue of the antecedent being always false.

Theorem: Let \(D \subseteq \mathbb{R}\), \(E \subseteq \mathbb{R}\), \(f: D \to E\), and let \(a \in \mathbb{R}\) be an accumulation point of \(D\). Also, let \(L \in \mathbb{R}\) and \(\hat{L} \in \mathbb{R}\).

If \(\varphi_{\lim} (f, a, L)\) and \(\varphi_{\lim} (f, a, \hat{L})\), then \(L = \hat{L}\).

We will prove this theorem. This theorem tells us that the limit is unique (if it exists).

Another way to say it: Let \(D \subseteq \mathbb{R}\). A value \(a \in \mathbb{R}\) is an accumulation point of \(D\) iff

i.e., there are infinitely many points from \(D\) in the interval \((a-\beta, a+\beta)\), no matter how small \(\beta > 0\) is.

E.g. Consider \(D = \mathbb{Q}\), \(a = \pi\). Then \((\pi - 1, \pi + 1) \cap \mathbb{Q} = (2.141\ldots, 4.141\ldots) \cap \mathbb{Q}\) is infinite (\(|(\pi-1,\pi+1)\cap\mathbb{Q}| \ge \aleph_0\)), and so is \((\pi - 0.1, \pi + 0.1) \cap \mathbb{Q}\), etc. So \(\pi\) is an accumulation point of \(\mathbb{Q}\) (but not a condensation point, as \(\mathbb{Q}\) is countable).

Set-up for a proof by contradiction. The theorem has the form “\((A \land B) \Rightarrow C\)”, call it \(\Psi\). We will prove \(\Psi\) by contradiction: \(\Psi\) is equivalent to \((\neg \Psi \Rightarrow (D \land \neg D))\), and \(\neg \Psi\) is \(\neg((A \land B) \Rightarrow C)\), which is equivalent to \((A \land B) \land \neg C\). So we assume \(A\), \(B\) and \(\neg C\).

Two small facts we will use: if \(a \neq b\) then \(|a - b| > 0\) (e.g. \(|2 - 7| = 5\)); and \(\varphi_{\lim}(f, a, L)\) lets us pick any \(\epsilon > 0\) and get a corresponding \(\delta\). For example, for \(\epsilon = 15\) there is a \(\delta_L(15) > 0\) such that \((\forall x \in D \setminus \{a\})(|x - a| < \delta_L(15) \Rightarrow |f(x) - L| < 15)\); for \(\epsilon = 0.02\) there is a \(\delta_L(0.02) > 0\) such that \((\forall x \in D \setminus \{a\})(|x - a| < \delta_L(0.02) \Rightarrow |f(x) - L| < 0.02)\); and so on for \(\epsilon = 0.0000001\) or \(\epsilon = \frac{1}{4}|L - \hat{L}|\).

Logical Form of the Theorem

Shorthand: \((\forall D \subseteq \mathbb{R})(\forall E \subseteq \mathbb{R})\) means \((\forall D \in \mathcal{P}(\mathbb{R})) (\forall E \in \mathcal{P}(\mathbb{R}))\). \(\operatorname{Acc}(D)\) is the set of all accumulation points of \(D\). \(E^D\) is the set of all functions with domain \(D\) & codomain \(E\).

Recall the equivalences: \(\neg (A \Rightarrow B)\) and \((A \land \neg B)\) and: \(C\) and \((\neg C \Rightarrow (D \land \neg D))\)

We will do this proof by contradiction, so we assume:

i.e.:

And then, we will produce a contradiction: “(\(\Psi \land \neg \Psi\))”

“Idea” of the Proof:

For a given \(\epsilon\), there will be \(\delta\) & \(\hat{\delta}\) windows that keep the function inside the windows around \(\hat{L}\) & \(L\).

If the windows around \(\hat{L}\) & \(L\) are disjoint, and there are values in the domain in this \(\delta, \hat{\delta}\) windows we’ll have a contradiction (each corresponding point would need to be in both windows).

In our proof, we will be assuming the following (for a contradiction):

i) \(\lim_{x \to a} f(x) = L: (\forall \epsilon > 0) (\exists \delta > 0) (\forall x \in dom(f) \setminus \{a\} ) (|x - a| < \delta \Rightarrow |f(x) - L| < \epsilon)\)

ii) \(\lim_{x \to a} f(x) = \hat{L}: (\forall \epsilon > 0) (\exists \delta > 0) (\forall x \in dom(f) \setminus \{a\} ) (|x - a| < \delta \Rightarrow |f(x) - \hat{L}| < \epsilon)\)

iii) \(L \ne \hat{L}\)

We have these “facts” to work with (we’re assuming these); we don’t need to show them.

For (i) & (ii), this means that we can choose any \(\epsilon > 0\), and we can state that there is a corresponding \(\delta\) (for each \(L\) & \(\hat{L}\)).

In the proof we will use an \(\epsilon > 0\) that is small enough to make sure that the \(\epsilon\)-windows don’t overlap.

Proof: Let \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\) be arbitrary sets and let \(f:D\rightarrow E\) be an arbitrary function. Also, let \(a\) be an arbitrary accumulation point of \(D\). Finally, let \(L\) and \(\hat{L}\) be arbitrary real numbers.

We will show that if \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} f(x) = \hat{L}\), then \(L = \hat{L}\).

Towards a contradiction, suppose \(\lim_{x \to a} f(x) = L\), \(\lim_{x \to a} f(x) = \hat{L}\), and that \(L \neq \hat{L}\).

As \(L \neq \hat{L}\), we have that \(|L - \hat{L}| > 0\).

Define \(\hat{\varepsilon}\) to be \(\frac{1}{4} |L - \hat{L}|\), i.e., \(\hat{\varepsilon} = \frac{1}{4}|L - \hat{L}|\). Note that as \(|L - \hat{L}| > 0\), we have that \(\hat{\varepsilon} = \frac{1}{4}|L - \hat{L}| > 0\).

Since \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} f(x) = \hat{L}\), we have that:

\((\forall \varepsilon > 0)(\exists \delta_L > 0)(\forall x \in D \setminus \{a\})(|x - a| < \delta_L \Rightarrow |f(x) - L| < \varepsilon)\), and

\((\forall \varepsilon > 0)(\exists \delta_{\hat{L}} > 0)(\forall x \in D \setminus \{a\})(|x - a| < \delta_{\hat{L}} \Rightarrow |f(x) - \hat{L}| < \varepsilon)\).

In particular, as \(\hat{\varepsilon} > 0\), there exist \(\delta_L > 0\) and \(\delta_{\hat{L}} > 0\) such that:

\((\forall x \in D \setminus \{a\})(|x - a| < \delta_L \Rightarrow |f(x) - L| < \hat{\varepsilon})\), and (1)
\((\forall x \in D \setminus \{a\})(|x - a| < \delta_{\hat{L}} \Rightarrow |f(x) - \hat{L}| < \hat{\varepsilon})\). (2)

Let \(\delta = \min(\delta_L, \delta_{\hat{L}})\). Then, as \(\delta_L > 0\) and \(\delta_{\hat{L}} > 0\), we have that \(\delta > 0\).

Since \(\delta > 0\) and since \(a\) is an accumulation point of \(D\), we have that \(((a - \delta, a + \delta) \cap D) \setminus \{a\}\) is infinite, so that there is some \(\hat{x} \in ((a - \delta, a + \delta) \cap D) \setminus \{a\}\). As \(\delta = \min(\delta_L, \delta_{\hat{L}})\), we have \(\delta \le \delta_L\) and \(\delta \le \delta_{\hat{L}}\) so that:

From this, and as \(\hat{x} \in ((a - \delta, a + \delta) \cap D) \setminus \{a\}\), we have that:

Hence, we have that \(\hat{x} \in D \setminus \{a\}\) and that \(|\hat{x} - a| < \delta_L\) and \(|\hat{x} - a| < \delta_{\hat{L}}\).

By (1) and (2), we have that \(|f(\hat{x}) - L| < \hat{\varepsilon}\) and \(|f(\hat{x}) - \hat{L}| < \hat{\varepsilon}\). (3)

Now:

Now, \(|L - \hat{L}| < \frac{1}{2}|L - \hat{L}|\), so that \(\frac{1}{2}|L - \hat{L}| < 0\), and \(|L - \hat{L}| < 0\). As \(|L - \hat{L}| > 0\), we have a contradiction.

Hence, if \(\varphi_{\lim}(f, a, L)\) and \(\varphi_{\lim}(f, a, \hat{L})\), then \(L = \hat{L}\).

As \(D, E, f: D \to E, a, L\) and \(\hat{L}\) were arbitrary, for all \(D \subseteq \mathbb{R}\), \(E \subseteq \mathbb{R}\), \(f: D \to E\), and for all accumulation points \(a\) of \(D\) and any real numbers \(L\) and \(\hat{L}\), if \(\varphi_{\lim}(f, a, L)\) and \(\varphi_{\lim}(f, a, \hat{L})\), then \(L = \hat{L}\). \(\blacksquare\)

(The last step in detail, with \(A = |L - \hat{L}|\):)

The triangle inequality \(|A + B| \leq |A| + |B|\) in examples (equality when \(A\) and \(B\) have the same sign, strict inequality otherwise):

Worked example: \(\lim_{x \to 2} x^2 = 4\) #

Let \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\). We want, for a given \(\epsilon > 0\), a \(\delta > 0\) with \(|x - 2| < \delta \Rightarrow |f(x) - 4| < \epsilon\).

Scratch work:

The problem: the bound \(\frac{\epsilon}{|x+2|}\) depends on \(x\), and \(\delta\) may only depend on \(\epsilon\). The fix is to first insist that \(\delta \le 1\), which controls \(|x + 2|\):

Then \(|x-2|\,|x+2| < 5\,|x - 2|\), so it is enough to also have \(|x - 2| < \frac{\epsilon}{5}\). We let \(\delta = \min(1, \frac{\epsilon}{5})\).

Proof: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by \(f(x) = x^2\) for all \(x \in \mathbb{R}\). Let \(\epsilon > 0\) be arbitrary and let \(\delta = \min(1, \frac{\epsilon}{5})\). As \(1 > 0\) and \(\frac{\epsilon}{5} > 0\), we have \(\delta > 0\). Let \(x \in \mathbb{R} \setminus \{2\}\) be arbitrary and suppose \(|x - 2| < \delta\). As \(\delta \le 1\), \(|x - 2| < 1\), so \(-1 < x - 2 < 1\) and \(3 < x + 2 < 5\). Hence \(x + 2 > 0\), so \(|x + 2| = x + 2 < 5\). As \(\delta \le \frac{\epsilon}{5}\), \(|x - 2| < \frac{\epsilon}{5}\). Now:

Hence, \(|f(x) - 4| < \epsilon\). Thus, if \(|x - 2| < \delta\), then \(|f(x) - 4| < \epsilon\). As \(x\) was arbitrary, for all \(x \in \mathbb{R} \setminus \{2\}\), if \(|x - 2| < \delta\), then \(|f(x) - 4| < \epsilon\). As \(\delta > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{2\}\), if \(|x - 2| < \delta\), then \(|f(x) - 4| < \epsilon\). As \(\epsilon > 0\) was arbitrary, for all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in \mathbb{R} \setminus \{2\}\), if \(|x - 2| < \delta\), then \(|f(x) - 4| < \epsilon\). Therefore, \(\lim_{x \to 2} f(x) = 4\). \(\square\)

Other valid choices (from class): restricting to \(\delta \le 2\) gives \(2 < x + 2 < 6\), so \(\delta = \min(2, \frac{\epsilon}{6})\) also works; restricting to \(\delta \le \frac{1}{2}\) gives \(\frac{3}{2} < x + 2 < \frac{9}{2}\), so \(\delta = \min(\frac{1}{2}, \frac{2\epsilon}{9})\) works too. There are many winning moves for Player II.

Module 5: Limit Properties #

Example: Let \(f: \mathbb{R} \to \mathbb{R}\) be the function defined by \(f(x) = x^2\) for all \(x \in \mathbb{R}\). Let \(g: \mathbb{R} \to \mathbb{R}\) be the function defined by \(g(x) = x^3\) for all \(x \in \mathbb{R}\).

We can show that \(\varphi_{\lim}(f, 2, 4)\) and \(\varphi_{\lim}(g, 2, 8)\), i.e., that

(For a given \(\varepsilon > 0\), \(\delta_f = \min(1, \varepsilon/5)\) and \(\delta_g = \min(1, \varepsilon/19)\) will work in the proof of the above limits).

Question: Can we use this information to determine \(\lim_{x \to 2} (f(x) + g(x))\) ?

Can we use \(\delta_f\) & \(\delta_g\) to find the \(\delta\) for this “sum” limit?

From graphing (& our knowledge concerning limits) we should get that:

Definition / Notation: Suppose we have \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\), and functions \(f: D \to E\) and \(g: D \to E\).

We define a function \(f+g\) as follows:

\((f+g): D \to E\)

where: \(x \mapsto f(x) + g(x)\) for all \(x \in D\)

or: \((f+g)(x) = f(x) + g(x)\)

With this notation: We should have \(\lim_{x \to 2} (f+g)(x) = 12\)

Idea: \(|(f+g)(x) - 12| < \epsilon \implies \text{This is what we will need.}\)

\(|(f+g)(x) - 12| = |f(x) + g(x) - 12| = |(f(x) - 4) + (g(x) - 8)|\)

\(\leq |f(x) - 4| + |g(x) - 8| \text{(Triangle Inequality)}\)

If we have \(|f(x) - 4| < \epsilon/2\) and \(|g(x) - 8| < \epsilon/2\), then this “\(|f(x) - 4| + |g(x) - 8|\)” will be less than \(\frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon\).

This is what we need!

We know that \( \lim_{x \to 2} f(x) = 4 \), so for any \( \varepsilon > 0\), there is a \( \delta_f > 0 \) such that if \( |x-2| < \delta_f\), then \( |f(x) - 4 | < \varepsilon\).

As \( \frac{\varepsilon}{2} > 0\), there is a corresponding \( \hat{\delta_f} > 0 \) such that if \( |x-2| < \hat{\delta_f} \), then \( |f(x) - 4 | < \frac{\varepsilon}{2} \).

Similarly, we know that \( \lim_{x \to 2} g(x) = 8 \), so for any \( \varepsilon > 0\), there is a \( \delta_g > 0\) such that if \( |x-2| < \delta_g\), then \( |g(x) - 8 | < \varepsilon \).

As \( \frac{\varepsilon}{2} > 0\), there is a corresponding \( \hat{\delta_g} > 0 \) such that if \( |x-2| < \hat{\delta_g} \), then \( |g(x) - 8 | < \frac{\varepsilon}{2}\).

If \( \delta = \min(\hat{\delta_f}, \hat{\delta_g})\), then if \( |x-2| < \delta\), then both \( |x-2| < \hat{\delta_f}\) and \( |x-2| < \hat{\delta_g}\).

From this, we have: \( |f(x) - 4| < \frac{\varepsilon}{2} \) and \( |g(x) - 8 | < \frac{\varepsilon}{2}\)

Thus: \( |f(x) - 4 | + |g(x) - 8 | < \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon\)

Theorem: Let \(D \subseteq \mathbb{R}\), \(E \subseteq \mathbb{R}\). Also, let \(f: D \to E\) and \(g: D \to E\) be functions and let \(a \in \mathbb{R}\) be an accumulation point of \(D\). If \(L \in \mathbb{R}\) and \(M \in \mathbb{R}\) are such that \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} g(x) = M\), then

Proof: Let \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\) be arbitrary. Also, let \(f: D \to E\) and \(g: D \to E\) be arbitrary functions. Let \(a \in \mathbb{R}\) be an arbitrary accumulation point of \(D\). Finally, let \(L\) and \(M\) be arbitrary real numbers such that \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} g(x) = M\).

We need to show that \(\lim_{x \to a} (f+g)(x) = L + M\), i.e., that

Let \(\varepsilon > 0\) be arbitrary. As \(\lim_{x \to a} f(x) = L\) and as \(\frac{\varepsilon}{2} > 0\), there is some \(\delta_f > 0\) such that whenever \(x \in D \setminus \{a\}\) and \(|x-a| < \delta_f\), then \(|f(x) - L| < \frac{\varepsilon}{2}\).

Similarly, as \(\lim_{x \to a} g(x) = M\) and \(\frac{\varepsilon}{2} > 0\), there is some \(\delta_g > 0\) such that whenever \(x \in D \setminus \{a\}\) and \(|x-a| < \delta_g\), then \(|g(x) - M| < \frac{\varepsilon}{2}\).

Let \(\delta = \min(\delta_f, \delta_g)\). As both \(\delta_f > 0\) and \(\delta_g > 0\), we have \(\delta > 0\).

Now, let \(x \in D \backslash \{a\}\) be arbitrary, and suppose \(|x-a| < \delta\). As \(\delta = \min(\delta_f, \delta_g)\), we have that \(\delta \leq \delta_f\) and \(\delta \leq \delta_g\), so that as \(|x-a| < \delta\), we have both that \(|x-a| < \delta_f\) and \(|x-a| < \delta_g\).

As \(|x-a| < \delta_f\), we have \(|f(x) - L| < \epsilon/2\). Similarly, as \(|x-a| < \delta_g\), we have \(|g(x) - M| < \epsilon/2\).

Now:

By the triangle inequality:

Hence, we have:

Hence, \(|(f+g)(x) - (L+M)| < \epsilon\). Therefore, if \(|x-a| < \delta\), then \(|(f+g)(x) - (L+M)| < \epsilon\). As \(x \in D \backslash \{a\}\) was arbitrary, for all \(x \in D \backslash \{a\}\), if \(|x-a| < \delta\), then \(|(f+g)(x) - (L+M)| < \epsilon\). As \(\delta > 0\), there exists a \(\delta > 0\) such that for all \(x \in D \backslash \{a\}\), if \(|x-a| < \delta\), then \(|(f+g)(x) - (L+M)| < \epsilon\).

As \(\epsilon > 0\) was arbitrary, for all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in D \setminus \{a\}\), if \(|x-a| < \delta\), then \(|(f+g)(x) - (L+M)| < \epsilon\). Hence, we have that \(\lim_{x \to a} (f+g)(x) = L + M\). As, \(D, E, f, g, a, L\) and \(M\) were arbitrary, for any sets \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\), for any functions \(f: D \to E\) and \(g: D \to E\), any accumulation point \(a\) of \(D\) and any real numbers \(L\) and \(M\) such that \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} g(x) = M\), we have \(\lim_{x \to a} (f+g)(x) = L + M\). \(\blacksquare\)

Example (why the domain matters): Let \(f, g: [5, \infty) \to \mathbb{R}\) with \(f(x) = \sqrt{x-5}\) and \(g(x) = \sqrt{x-5}\,x\). Then \(fg: [5, \infty) \to \mathbb{R}\) and

Even though the formula \(x^2 - 5x\) makes sense at \(x = 0\), \((fg)(0)\) does not exist: \(0 \notin [5, \infty) = \text{Dom}(fg)\), and \((fg)(0)\) would have to equal \(f(0) \cdot g(0)\), which is undefined.

A familiar use of the product rule for limits (which we are about to prove):

The key idea for products will be to add and subtract \(L \cdot g(x)\):

Definition / Notation: Suppose we have \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\) and functions \(f: D \to E\) and \(g: D \to E\). We define a function \(fg\) as follows:

\((fg): D \to E\) where \(x \mapsto f(x) \cdot g(x)\) for all \(x \in D\), or: \((fg)(x) = f(x) \cdot g(x)\).

(On the left, \(fg\) is the “new” function; on the right, \(f\) and \(g\) are the “old”/original/given functions.)

Our next goal will be to prove the following theorem:

Theorem: Let \(D \subseteq \mathbb{R}\), \(E \subseteq \mathbb{R}\) and let \(f: D \to E\) and \(g: D \to E\) be functions. Let \(a \in \mathbb{R}\) be an accumulation point of \(D\). Let \(L \in \mathbb{R}\) and \(M \in \mathbb{R}\). If \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} g(x) = M\), then \(\lim_{x \to a} (fg)(x) = LM\).

As per usual, we will need to find \(\delta\) such that if \(|x-a| < \delta\), then \(|(fg)(x) - LM| < \epsilon\). In scratch work we start here & work backwards to find \(\delta = \delta(\epsilon)\).

“Scratch Work”:

Note: As \(\lim_{x \to a} f(x) = L\), there is a \(\delta_f > 0\) such that if \(|x-a| < \delta_f\), then \(|f(x)-L| < \epsilon\) (for any \(\epsilon > 0\)). As \(\lim_{x \to a} g(x) = M\), there is a \(\delta_g > 0\) such that if \(|x-a| < \delta_g\), then \(|g(x)-M| < \epsilon\) (for any \(\epsilon > 0\)).

① We’ll try to make \(|L| \cdot |g(x) - M|\) less than \(\frac{\epsilon}{2}\). As \(|L| < |L| + 1\):

As \(\frac{\epsilon}{2(|L|+1)} > 0\), the limit \(\lim_{x \to a} g(x) = M\) gives us a \(\delta_g = \delta_g\left( \frac{\epsilon}{2(|L|+1)} \right)\) that makes this happen. (Dividing by \(|L| + 1\) rather than \(|L|\) avoids the case \(L = 0\).)

② We’ll try to get \(|g(x)|\,|f(x)-L| < \frac{\varepsilon}{2}\).

We’ll use a similar idea as in ①, but \(|f(x)-L| < \frac{\varepsilon}{2(|g(x)|+1)}\) won’t work as this changes based on \(x\) (so \(\delta_f\) would as well).

Instead: we will want \(|g(x)| \leq M_g\), some positive constant. If we get this, then:

As \(\frac{\varepsilon}{2M_g} > 0\), we get \(\delta_f = \delta_f\left( \frac{\varepsilon}{2M_g} \right)\) from \(\lim_{x \to a} f(x) = L\).

Notice: As \(1 > 0\), we can find a \(\delta_1 > 0\) such that if \(|x-a|<\delta_1\), then \(||g(x)|-|M||<1\). In particular, if \(|x-a|<\delta_1\), then \(|g(x)| < |M|+1 = M_g\).

(We will need to prove that if \(\lim_{x\to a} g(x) = M\), then \(\lim_{x\to a} |g(x)| = |M|\). For now, we will assume this fact.)

“Idea” so far: We will three upper limits for \(\delta\):

This will give \(|g(x)| < |M| + 1\)

This will give \(|g(x)| |f(x) - L| < \frac{\varepsilon}{2} \)

This will give \(|L||g(x) - M| < \frac{\varepsilon}{2} \)

Putting this together: We let \(\delta = \min(\delta_1, \delta_f, \delta_g)\). For \(|x-a| < \delta\):

As \(|x-a| < \delta_1\), we have \(| |g(x)| - |M| | < 1\), so \(-1 < |g(x)| - |M| < 1\), and \(|M| - 1 < |g(x)| < |M| + 1\), so \(|g(x)| < |M| + 1\).

As \(|x-a| < \delta_f\), we have \(|f(x) - L| < \frac{\varepsilon}{2(|M|+1)}\), so \((|M|+1) |f(x) - L| < \frac{\varepsilon}{2}\).

As \(|g(x)| < |M| + 1\), \(|g(x)| |f(x) - L| < (|M|+1) |f(x) - L|\). Hence, \(|g(x)||f(x) - L| < \frac{\varepsilon}{2}\)

As \(|x-a| < \delta_g\), we have \(|g(x) - M| < \frac{\varepsilon}{2(|L|+1)}\), so \((|L|+1) |g(x) - M| < \frac{\varepsilon}{2}\).

As \(|L| < |L|+1\), \(|L||g(x) - M| < (|L|+1)|g(x) - M|\). Hence, \(|L||g(x) - M| < \frac{\varepsilon}{2}\).

(We will prove “if \(\lim_{x \to a} g(x) = M\), then \(\lim_{x \to a} |g(x)| = |M|\)” below.)

Putting this together: as \(|g(x)f(x) - LM| = |g(x)f(x) - Lg(x) + Lg(x) - LM| \leq |g(x)(f(x) - L)| + |L(g(x) - M)|\) (by the triangle inequality), we have:

For the proof: Set-up/introduce D, E, f and g. Introduce a, L, M. Assume \(\lim_{x \to a} f(x) = L\) and \(\lim_{x \to a} g(x) = M\). Let \(\epsilon > 0\) be arbitrary.

• Use these assumed limits to define \(\delta_f\) (for \(\frac{\epsilon}{2(|M| + 1)}\)), \(\delta_g\) (for \(\frac{\epsilon}{2(|L| + 1)}\)), and \(\delta_1\) (for 1).
• Set \(\delta = \min(\delta_f, \delta_g, \delta_1)\) and explain why \(\delta > 0\).
• Let \(x \in D \setminus \{a\}\) be arbitrary and suppose \(|x - a| < \delta\).
• Show \(|(fg)(x) - LM| < \epsilon\). (Using the above arguments)
• Conclude the proof (building back up to quantified statement).

Proof: Let \(D \subseteq \mathbb{R}, E \subseteq \mathbb{R}\). Let \(g: D \rightarrow E\) be a function and let \(a \in \mathbb{R}\) be an accumulation point of \(D\). Also, let \(M \in \mathbb{R}\) and suppose \(\lim_{x \rightarrow a} g(x) = M\).

We will prove that \(\lim_{x \rightarrow a} |g(x)| = |M|\).

Let \(\epsilon > 0\) be arbitrary. As \(\lim_{x \rightarrow a} g(x) = M\), there is a \(\tilde{\delta} > 0\) such that for any \(x \in D \setminus \{a\}\), if \(|x - a| < \tilde{\delta}\), then \(|g(x) - M| < \epsilon\).

We will consider three cases.

Case 1: Suppose \(M = 0\). Then, let \(\delta = \tilde{\delta}\). As \(\tilde{\delta} > 0\), \(\delta > 0\). Let \(x \in D \setminus \{a\}\) be arbitrary, and suppose \(|x - a| < \delta\). Then, we have that \(|x - a| < \tilde{\delta}\) so that \(|g(x) - M| < \epsilon\). In this case: \(|g(x) - 0| < \epsilon\), so \(|g(x)| < \epsilon\), and \(||g(x)|| < \epsilon\). From this, \(||g(x)| - |0|| < \epsilon\), and \(||g(x)| - 0|| < \epsilon\), so that \(||g(x)| - |M|| < \epsilon\). Hence, if \(|x - a| < \delta\), then \(||g(x)| - |M|| < \epsilon\).

As \(x \in D \setminus \{a\}\) was arbitrary, for any \(x \in D \setminus \{a\}\), if \(|x - a| < \delta\), then \(||g(x)| - |M|| < \epsilon\). As \(\delta > 0\), there exists \(\delta > 0\) such that for all \(x \in D \setminus \{a\}\), if \(|x - a| < \delta\), then \(||g(x)| - |M|| < \epsilon\).

Case 2: Suppose \(M > 0\). Note that \(\frac{M}{2} > 0\) so that as \(\lim_{x \to a} g(x) = M\), there is a \(\hat{\delta} > 0\) such that for any \(x \in D \setminus \{a\}\), if \(|x-a| < \hat{\delta}\), then \(|g(x) - M| < \frac{M}{2}\). Let \(\delta = \min(\hat{\delta}, \tilde{\delta})\). As \(\tilde{\delta} > 0\) and as \(\hat{\delta} > 0\), we have \(\delta > 0\). Now, let \(x \in D \setminus \{a\}\) be arbitrary, and suppose \(|x-a| < \delta\). Then \(|x-a| < \hat{\delta}\) so that:

As \(\frac{M}{2} < g(x)\) and \(\frac{M}{2} > 0\), we have that \(g(x) > 0\), so that \(|g(x)| = g(x)\). As \(M > 0\), we have that \(|M| = M\).

Now, as \(|x-a| < \delta \le \tilde{\delta}\), we have that \(|g(x) - M| < \epsilon\), so that \(||g(x)| - |M|| = |g(x) - M| < \epsilon\).

Hence, \(||g(x)| - |M|| < \epsilon\). Thus, if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \epsilon\). As \(x \in D \setminus \{a\}\) was arbitrary, for any \(x \in D \setminus \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \epsilon\). As \(\delta > 0\), there exists \(\delta > 0\) such that for all \(x \in D \setminus \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \epsilon\).

Case 3: Suppose that \(M < 0\). Note that \(\frac{|M|}{2} > 0\) so that as \(\lim_{x \to a} g(x) = M\), there is a \(\hat{\delta} > 0\) such that for any \(x \in D \backslash \{a\}\), if \(|x - a| < \hat{\delta}\), then \(|g(x) - M| < \frac{|M|}{2}\). Let \(\delta = \min(\hat{\delta}, \tilde{\delta})\). As \(\hat{\delta} > 0\) and \(\tilde{\delta} > 0\), we have \(\delta > 0\). Now, let \(x \in D \backslash \{a\}\) be arbitrary, and suppose \(|x-a| < \delta\). Then, we have that \(|x-a| < \hat{\delta}\) so that:

As \(M < 0\), \(|M| = -M\), so that:

Thus, \(g(x) < \frac{M}{2}\). As \(M < 0\), \(\frac{M}{2} < 0\) so that \(g(x) < 0\). Thus, \(|g(x)| = -g(x)\).

Now, as \(|x-a| < \delta\), we have \(|x-a| < \tilde{\delta}\) so that \(|g(x) - M| < \varepsilon\). Notice:

Hence, \(||g(x)| - |M|| < \varepsilon\). Thus, if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \varepsilon\). As \(x \in D \backslash \{a\}\) was arbitrary for any \(x \in D \backslash \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \varepsilon\). As \(\delta > 0\), there exists \(\delta > 0\) such that for all \(x \in D \backslash \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \varepsilon\).

These cases are exhaustive. Hence, there exists a \(\delta > 0\) such that for all \(x \in D \setminus \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \epsilon\). As \(\epsilon > 0\) was arbitrary, for all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x \in D \setminus \{a\}\), if \(|x-a| < \delta\), then \(||g(x)| - |M|| < \epsilon\). Therefore, \(\lim_{x \to a} |g(x)| = |M|\).

As \(D, E, g, a\) and \(M\) were arbitrary, for any \(D \subseteq \mathbb{R}, E \subseteq \mathbb{R}\) and any function \(g: D \to E\) and any accumulation point \(a \in \mathbb{R}\) of \(D\) and any \(M \in \mathbb{R}\), if \(\lim_{x \to a} g(x) = M\), then \(\lim_{x \to a} |g(x)| = |M|\).

The Triangle Inequality: For all real numbers \(x\) and \(y\), \(|x+y| \leq |x| + |y|\).

Proof: Let \(x\) and \(y\) be arbitrary real numbers. We will consider four cases.

Case 1: Suppose \(x < 0\) and \(y < 0\). Then, \(|x| = -x\) and \(|y| = -y\). Also, \(x+y < 0\), so \(|x+y| = -(x+y)\). Now:

\(|x+y| = -(x+y) = -x - y = (-x) + (-y) = |x| + |y|\).

Hence, \(|x+y| = |x| + |y|\), so that \(|x+y| \leq |x| + |y|\).

Case 2: Suppose \(x < 0\) and \(y \geq 0\). Then, \(|x| = -x\) and \(|y| = y\). We will consider two subcases.

Subcase 2.1: Suppose \(x+y \geq 0\). Then, \(|x+y| = x+y\). Now:

\(|x+y| = x+y \leq 2|x| + x + y = -2x + x + y = -x+y = |x| + |y|\).

Subcase 2.2: Suppose \(x+y < 0\). Then \(|x+y| = -(x+y)\). Now:

\(|x+y| = -(x+y) = -x -y \leq -x-y + 2|y| = -x-y+2y=-x+y = |x|+|y|\).

These subcases are exhaustive, so we have that \(|x+y| \leq |x| + |y|\).

Case 3: Suppose \(x \geq 0\) and \(y < 0\). Notice that \(|x+y| = |y+x|\), so by Case 2, we have \(|y+x| \leq |y| + |x| = |x| + |y|\). Hence, \(|x+y| \leq |x| + |y|\).

(Here we used that if \(a = b = c < d = e = f\), then \(a < f\): a chain of equalities with one strict inequality gives a strict inequality.)

Case 4: Suppose \(x \geq 0\) and \(y \geq 0\). Then \(|x| = x\) and \(|y| = y\). Also \(x+y \geq 0\) so that \(|x+y| = x+y\). Now:

Thus, \(|x+y| = |x|+|y|\), so that \(|x+y| \leq |x|+|y|\). These cases are exhaustive, hence \(|x+y| \leq |x|+|y|\). As \(x\) and \(y\) were arbitrary, for all real numbers \(x\) and \(y\), \(|x+y| \leq |x|+|y|\). \(\square\)

The Reverse Triangle Inequality: For all real numbers \(x\) and \(y\), we have that:

Proof: Let \(x\) and \(y\) be arbitrary real numbers. We will consider four cases.

Case 1: Suppose \(x < 0\) and \(y < 0\). Then, \(|x| = -x\) and \(|y| = -y\). Now:

Hence, we have \(||x| - |y|| = |x-y|\), so that \(||x| - |y|| \leq |x-y|\).

Case 2: Suppose \(x < 0\) and \(y > 0\). Then, \(|x| = -x\) and \(|y| = y\). Now:

By the triangle inequality, \(|x+y| \leq |x|+|y|\), so we have:

Hence, we have \(||x|-|y|| \leq |x-y|\).

Case 3: Suppose \(x \geq 0\) and \(y < 0\). Then, note that by case 2, \(| |y| - |x| | \leq |y-x|\). Also, we have that: \(| |x| - |y| | = | -(|x| - |y|) | = | |y| - |x| |\), and also that: \(|x-y| = |-(x-y)| = |y-x|\). Hence, we have that \(||x|-|y|| \leq |x-y|\).

Case 4: Suppose \(x \geq 0\) and \(y \geq 0\). Then \(|x| = x\) and \(|y| = y\). Now: \(||x|-|y|| = |x-y|\). Thus, \(||x|-|y|| \leq |x-y|\).

These cases are exhaustive, hence: \(||x|-|y|| \leq |x-y|\). As \(x\) and \(y\) were arbitrary, for all real numbers \(x\) and \(y\), \(||x|-|y|| \leq |x-y|\).

By the Reverse Triangle Inequality:

Comment: The Reverse Triangle Inequality greatly simplifies the proof that

As \(||g(x)| - |M|| \leq |g(x) - M|\), when \(|g(x) - M| < \varepsilon\), we also have that \(||g(x)| - |M|| < \varepsilon\).

Definition/Notation: Suppose we have \(D \subseteq \mathbb{R}\) and \(E \subseteq \mathbb{R}\) and functions

We define a function \(\left(\frac{f}{g}\right): D \setminus \{x \in D \,|\, g(x) = 0\} \to E\) by:

Our next ``goal" will be to show that: \(\displaystyle \lim_{x\to a} \left(\frac{f}{g}\right)(x) = \lim_{x\to a} \frac{f(x)}{g(x)} = \frac{\displaystyle\lim_{x\to a} f(x)}{\displaystyle\lim_{x\to a} g(x)} = \frac{L}{M}\)

Note: In order for this to make sense, we will need \(\displaystyle \lim_{x \to a} g(x) = M \neq 0\) (can’t divide by zero).

As we have \( \lim_{x \to a} f(x) = L \) and \( \lim_{x \to a} g(x) = M \), we try to get expressions of the form \(|f(x) - L|\) and \(|g(x) - M|\).

We already have \(M \neq 0\), but we’ll need \(|g(x)| \neq 0\) on some \(\delta\)-window around \(a\). As \(\lim_{x \to a} g(x) \neq 0\), this will be possible.