11 - Existence proofs and counterexamples

Focusing on proving there exists statements.

Constructive existence proofs

Find an element in the set. When working with existence qualifiers, use "fix", "put", or "set" instead of "let" - which is used for an arbitrary value.

!Screenshot 2023-10-01 at 7.25.06 PM.png

Intermediate value theorem

If $f : [a, b] \to R$ is continuous, then for any $y$ satisfying $f (a) < y < f (b)$ or $f (b) < y < f (a)$ , there exists $c \in (a, b)$ such that $f (c) = y$ .

Nonconstructive existence proofs

Uniqueness

It's common to write $\exists! x \in S, R (x)$ .

In class practice

Proposition. Every odd integer is the sum of two consecutive integers.

Proof. Let $a \in O D D$ . Thus $a = 2 k + 1$ for some $k \in Z$ . That is $a = k + (k + 1)$ , and so $a$ is the sum of two consecutive integers $k$ and $k + 1$ . $◻$

Proposition. The equation $2 x^{3} + 2 x - 3 = 0$ has a solution in the interval (0, 1).

Proof. The function $f (x) = 2 x^{3} + 2 x - 3$ is a polynomial, and thus continuous everywhere. We find that $f (0) = - 3$ and $f (1) = 1$ . By the intermediate value theorem, we know that $f$ must take the intermediate value 0 for some $x \in (0, 1)$ . $◻$

HW 11

Ben Finch

E 11.1
a) Fix $a = 1, b = 2$ . Then $a, b \in Q$ . We have $1^{2} = 1 \in Q$ . $◻$

b) Fix $a = 2$ , $b = \frac{1}{2}$ . Then $a, b \in Q$ . We have $2^{(\frac{1}{2})} = \sqrt{2} \in R - Q$ . $◻$

c) $HW_11_1c 1.jpg$

d) Fix $a = 0, b = \sqrt{2}$ . Then $a \in Q$ and $b \in R - Q$ . We have $0^{\sqrt{2}} = 0 \in Q$ . $◻$

e) Fix $a = 2, b = \sqrt{2}$ . Then $a \in Q$ and $b \in R - Q$ . We have $a^{b} = 2^{\sqrt{2}}$ .

f) Fix $a = \sqrt{2}, b = 2$ . Then $a \in R - Q$ and $b \in Q$ . We have ${\sqrt{2}}^{2} = 2 \in Q$ . $◻$

g) Fix $a = \sqrt{2}, b = 1$ . Then $a \in R - Q$ and $b \in Q$ . We have ${\sqrt{2}}^{1} = \sqrt{2} \in R - Q$ . $◻$

E 11.2
Disproof. Fix $x = 0$ and $y = \sqrt{2}$ . We have $x y = 0 \notin R - Q$ . $◻$

E 11.3
Disproof. Fix $6 s - 3 = - 3$ . Thus $s = 0 \notin O D D .$ $◻$

E 11.4
Disproof. Let $x \in Z$ . We work directly. There are two cases:

Case 1: Suppose $x$ is odd. Thus $x = 2 k + 1$ for some $k \in Z$ . We find

\begin{aligned} x^{2} + x & = (2 k + 1)^{1} + 2 k + 1 \\ = 4 k^{2} + 4 k + 1 + 2 k + 1 \\ = 2 (2 k^{2} + 3 k + 1) \end{aligned}

is even.

Case 2: Suppose $x$ is even. Thus $x = 2 k$ for some $k \in Z$ . We find

\begin{aligned} x^{2} + x & = (2 k)^{2} + 2 k \\ = 4 k^{2} + 2 k \\ = 2 (2 k^{2} + k) \end{aligned}

is even.

Hence we have for all cases that $\forall x \in Z$ , if $x$ is odd, then $x^{2} + x$ is even. $◻$

E 11.5

Lemma. We are trying to prove that a non-zero rational number times an irrational number is irrational. Let $x \in Q$ and $y \in R - Q$ where $x \neq 0$ . Thus $x = \frac{m}{n}$ for some nonzero $m, n \in Z$ . Assume by way of contradiction that $x y \in Q$ . Thus $x y = \frac{j}{k}$ for some $j, k \in Z$ . We find

\begin{aligned} x y & = \frac{j}{k} \\ \frac{m}{n} (y) & = \frac{j}{k} \\ y & = \frac{j n}{m k} \end{aligned}

Since $m, n, j, k \in Z$ , $\frac{j n}{m k} \in Q$ which contradicts our original assumption that $y \in Q$ . Thus a nonzero rational number times and irrational number is irrational. $◻$

Proof. We work directly. Assume $a$ is a positive rational number. We can break this into two cases:

Case 1: $a > \sqrt{2}$ . Thus a possible $x = \sqrt{2}$ which is irrational.

Case 2: $a < \sqrt{2}$ . Let $x = \frac{a}{\sqrt{2}} = a (\frac{1}{\sqrt{2}})$ . Per the lemma, $a (\frac{1}{\sqrt{2}})$ is irrational. Also, $\frac{a}{\sqrt{2}}$ is less than $\sqrt{2}$ .

Thus in all cases, we have $x \in R - Q$ . $◻$

E 11.6

Proposition. Given any two real numbers $x$ and $y$ such that $x < y$ , we want to show that there exists a rational number in the interval $(x, y)$ .

Proof.

Let $x, y \in R$ . Let $y - x > 0$ . We can express $y - x$ in decimal form as $d_{k} d_{k - 1} . . . d_{1} d_{0} . d_{- 1} d_{- 2} d_{- 3} . . .$ . Since $y - x > 0$ , there exists at least one decimal digit that is non-zero; let the first one be $d_{l}$ . Thus the value contributed by $d_{l}$ to $y - x$ is at least $d_{l} \cdot 10^{l - 1}$ . Since $d_{l}$ is non-zero, we have $d_{l} \geq 1$ .

So $y - x > 10^{l - 1}$ .

Multiplying the inequality by $10^{- (l - 1)}$ gives us $10^{- (l - 1)} (y - x) > 1$ .

Denoting $10^{- (l - 1)} y$ as $Y$ and $10^{- (l - 1)} x$ as $X$ , we obtain $Y - X > 1$ .

Since $X$ and $Y$ are more than 1 apart, there exists an integer $n$ such that $X < n < Y$ .

Given that $X = 10^{- (l - 1)} x$ and $Y = 10^{- (l - 1)} y$ , we have $10^{- (l - 1)} x < n < 10^{- (l - 1)} y$ .

Rewriting this as $x < 10^{l - 1} n < y$ and denoting $10^{l - 1} n$ as $q$ , we find that $x < q < y$ , where $q$ is rational since $10^{l - 1} n$ is a product of an integer and a rational number.

Hence, for all real numbers $x$ and $y$ such that $x < y$ , there exists a rational number $q$ in the interval $(x, y)$ . $◻$