Proof Writing Practice

This is a universal conditional statement. One symbolic form is

Using divisibility notation, it can also be written as

Negate the quantifiers in reverse order:

In words, there is a real number that is greater than or equal to every real number.

You must prove both directions:

Proving both directions is exactly what makes the statement an equivalence.

Since $m$ and $n$ are even, write

for some integers $a$ and $b$. Then

Because $a+b$ is an integer, $m+n$ is even.

Since $m$ and $n$ are odd, write

for some integers $a$ and $b$. Then

Factor out a 2 from the even part:

This has the form $2k+1$, so $mn$ is odd.

Since $a \mid b$, there is an integer $k$ such that $b = ak$.

Since $a \mid c$, there is an integer $\ell$ such that $c = a\ell$.

Then

Because $k+\ell$ is an integer, $a \mid (b+c)$.

Let $x \in A \cap B$. By definition of intersection, $x \in A$ and $x \in B$.

In particular, $x \in A$. Since every element of $A \cap B$ is an element of $A$, we have

Assume $f(x_1) = f(x_2)$. Then

Add $2$ to both sides:

Divide by $5$:

Therefore $f$ is injective.

Let $y \in \mathbb{R}$ be arbitrary. Choose

Then

So every real number has a preimage under $g$, and $g$ is surjective.

Choose

It is rational, and

So a rational number between $1$ and $2$ exists.

We prove both inclusions.

First let $x \in A \cap (B \cup C)$. Then $x \in A$ and $x \in B \cup C$. So $x \in B$ or $x \in C$.

If $x \in B$, then $x \in A \cap B$. If $x \in C$, then $x \in A \cap C$. In either case,

Now let $x \in (A \cap B) \cup (A \cap C)$. Then either $x \in A \cap B$ or $x \in A \cap C$.

In the first case, $x \in A$ and $x \in B$, so $x \in A \cap (B \cup C)$.

In the second case, $x \in A$ and $x \in C$, so $x \in A \cap (B \cup C)$.

Thus the two sets are equal.

Reflexive: for any integer $a$,

is even, so $aRa$.

Symmetric: if $aRb$, then $a-b$ is even. Since

and the negative of an even integer is even, $bRa$.

Transitive: if $aRb$ and $bRc$, then

for some integers $k,\ell$. Adding gives

so $a-c$ is even. Hence $aRc$.

We prove the contrapositive: if $n$ is odd, then $n^2$ is odd.

If $n$ is odd, then $n = 2k+1$ for some integer $k$. Squaring gives

This has the form $2m+1$, so $n^2$ is odd.

Therefore the contrapositive is true, and so the original statement is true.

Assume, for contradiction, that

for integers $a,b$ in lowest terms, with $b \ne 0$. Then

So $a^2$ is even, which means $a$ is even. Write $a = 2k$. Then

So $b^2$ is even, hence $b$ is even. That means both $a$ and $b$ are even, contradicting that $\frac{a}{b}$ was in lowest terms.

Therefore $\sqrt{2}$ is irrational.

Consider two cases.

If $n$ is even, then $n = 2k$ for some integer $k$. So

If $n$ is odd, then $n = 2k+1$ for some integer $k$. Then

In either case, $n^2 \equiv 0$ or $1 \pmod{4}$.

Base case: when $n=1$,

So the formula is true for $n=1$.

Inductive hypothesis: assume for some $k \ge 1$ that

Inductive step: then

Factor out $k+1$:

This is exactly the desired formula with $n = k+1$. Therefore the statement holds for all $n \ge 1$.

Solve the equation:

So $x=6$ is a solution, which proves existence.

If $x_1$ and $x_2$ both satisfy $3x - 7 = 11$, then each must equal $6$, so $x_1 = x_2$. Thus the solution is unique.

To show injectivity, assume

Then

For real numbers, this implies $x_1 = x_2$, so $f$ is injective.

To show surjectivity, let $y \in \mathbb{R}$ be arbitrary. Choose

Then

So every real number has a preimage, and $f$ is surjective. Therefore $f$ is bijective.

First show injectivity. If $f(x_1) = f(x_2)$, then

Adding $1$ and dividing by $4$ gives

So $f$ is injective.

Now show surjectivity. Let $y \in \mathbb{R}$ be arbitrary. Solve

for $x$:

This choice gives $f(x)=y$, so $f$ is surjective.

Therefore $f$ is bijective.

Let $x \in A$. Since $A \cap B = A$, the element $x$ is also in $A \cap B$.

By definition of intersection, $x \in B$.

Because every element of $A$ is an element of $B$, we conclude

Every integer is either even or odd.

If $n$ is even, then $n = 2k$ for some integer $k$, so

is odd.

If $n$ is odd, then $n = 2k+1$ for some integer $k$, so

is even.

So in either case, exactly one of $n$ and $n+1$ is even.

Base case: for $n=1$,

So the statement is true for $n=1$.

Inductive hypothesis: assume for some $k \ge 1$ that

Inductive step: then

Simplify:

So the formula holds for $k+1$. Therefore it holds for all $n \ge 1$.

Assume, for contradiction, that there is an integer $n$ with $n^2=2$.

Then $n^2$ is even, so $n$ must be even. Write $n=2k$ for some integer $k$. Substituting gives

But the left-hand side is even, while the right-hand side is odd, which is impossible.

Therefore no integer $n$ satisfies $n^2=2$.

Take the domain to be the real numbers and let

Then $\forall x\, \exists y\, P(x,y)$ is true, because for each real number $x$ we can choose $y = x+1$.

But $\exists y\, \forall x\, P(x,y)$ is false, because no single real number $y$ is greater than every real number $x$.

This shows that the order of the quantifiers matters.

First assume $A \subseteq B$. To show $A \cap B = A$, prove both inclusions.

If $x \in A \cap B$, then $x \in A$, so $A \cap B \subseteq A$.

If $x \in A$, then $x \in B$ as well, since $A \subseteq B$. So $x \in A \cap B$, and hence $A \subseteq A \cap B$.

Therefore $A \cap B = A$.

Now assume $A \cap B = A$. Let $x \in A$. Then $x \in A \cap B$, so $x \in B$.

Thus every element of $A$ is an element of $B$, which means $A \subseteq B$.

Let $y \in \mathbb{R}$ be arbitrary.

Since $f$ is surjective, there exists some $x$ such that

So a solution exists.

To show uniqueness, suppose $f(x_1)=y$ and $f(x_2)=y$. Then

Since $f$ is injective, it follows that

Therefore the equation $f(x)=y$ has exactly one solution.

Assume, for contradiction, that $\sqrt{2}$ is rational. Then we can write

for integers $a,b$ in lowest terms, with $b \ne 0$.

Squaring both sides gives

so

Thus $a^2$ is even, so $a$ is even. Write $a=2k$ for some integer $k$. Then

So $b^2$ is even, which means $b$ is even. That contradicts the assumption that $\frac{a}{b}$ was in lowest terms.

Therefore $\sqrt{2}$ is irrational.