Introduction to Proofs: An Active Exploration of Mathematical Language

Section1.1What is a Proof?

In this course we want to understand how to read and write mathematics as mathematicians. We would hope to eventually use these skills to generate our own mathematics. Before we can do that, we need to be familiar with how mathematicians convey ideas.

Definition1.1.1.

An integer is a whole number. It can be positive, negative, or zero.
Before we can prove statements about integers, we need to have a common understanding of them. Note that this definition relies on us understanding other mathematical terms, such as positive and negative.
It is assumed that you bring some mathematical understanding with you to this course. But it is not assumed that that understanding is necessarly precise. One of the goals throughout this course will be to help make your current understanding more precise (or rigorous).

Activity1.1.1.Types of Integers.

Without being precise, you can probably determine whether an integer is positive, even, or prime.

(a)

List three positive, even integers.

(b)

Is 235823576 even or odd? How do you know? Write down as precise a rule as possible for determining whether an integer is even or odd.

(c)

List three prime numbers. How do you know they are prime?

(d)

Is 235823576 prime? How do you know?

(e)

Is 23582357 prime? How do you know? If you are unsure, what would it take to determine the answer?

Activity1.1.2.More General Integers.

Assume $$n$$ is an integer.

(a)

Is $$8n$$ even or odd? Does you rule from Activity 1.1.1 still work? If not, can you refine your rule?

(b)

Is $$3n$$ even or odd? Can it sometimes be even and sometimes be odd?

(c)

Can $$8n$$ ever be prime? What about $$3n\text{?}$$
For the time being, we will rely on our general understanding of whether an integer is even or odd, prime or not prime. But we will eventually want more formal definitions for these ideas, which we see in Section 3.1.
Now let's look at a more complicated mathematical statement. A conjecture is an uproven mathematical statement. Every mathematical theorem started out as a conjecture. You are encouraged to make your own mathematical conjectures throughout this course.
We would like to know if Goldbach's Conjecture is true. We can start by just trying several examples. We want to see if positive even integers greater than 2 (like 4, 6, 8, 10, 12) can be written as the sum of two prime numbers. For example, $$6=3+3$$ and $$12=5+7\text{.}$$ Now try to write 4, 8, and 10 as the sum of two primes. Note, 1 is NOT prime. We will see this later when we formally define primes.

Activity1.1.3.Verify Goldbach's Conjecture.

Verify Goldbach's Conjecture for 14, 16, 18, and 20. This means you want to show the conjecture is true for these even integers.
We have now verified Golbach's Conjecture for several examples. Does that mean it is true in general? How many examples would you need so that you were convinced it is true? How many examples do you think mathematicians would need to be convinced? What would it take to know that it is true for every even integer greater than 2?
In fact, althought it has been verified for integers up to at least $$4 \times 10^{18}\text{,}$$ it has not been proven. Goldbach first conjectured the statement in a letter to Euler in 1742, and mathematicians have been unable to give a full proof.

Activity1.1.4.Prime Number Generator.

Let's switch gears a bit and look for a way to find prime numbers.

(a)

Play around with different functions whose inputs are positive integers. See if you can find one whose outputs are an infinite set of prime numbers. For example, $$f(n)=n^2+1$$ gives us $$f(1)=2, f(2)=5, f(3)=10\text{.}$$ The first two are prime, but $$f(3)=10$$ is not prime, so $$f(n)=n^2+1$$ does not work.

(b)

Now try the function $$f(n)=n^2+n+41\text{.}$$ Find outputs for $$n$$ from 1 to 10. Are the outputs all prime?

(c)

Based on (b), have we found a function whose outputs are only prime numbers? What would we have to check to know this is true?

(d)

In fact, there are values of $$n$$ for which $$f(n)$$ is not prime. See if you can find one. Think carefully about what you would need to not be prime.
We have seen that in Goldbach's Conjecture, we will know the statement is true if we can find a proof that works for every even integer. On the other hand, we saw in Activity 1.1.4 that it only takes one example where the statement fails to show it is false. This is an idea we will return to many times in this course.
So what is a proof? How do we decide if a statement has been proven? Let's start with a definition and an example of a proof.

Definition1.1.4.

Let $$n$$ be an integer. Then $$n$$ is even if there exists an integer $$k$$ such that $$n=2k\text{.}$$
Before moving to the proof, check your rule for determining whether an integer is even from Activity 1.1.2. Is your rule similar to the formal definition? If it is different, can you see any advantages to using the more formal definition?
Let $$n$$ be an integer. Prove $$8n$$ is even.
We can rewrite $$8n$$ as $$8n=2(4n)\text{.}$$ Then let $$k=4n\text{.}$$ Since $$n$$ is an integer, $$4n$$ is an integer. Thus, $$8n=2k$$ for some integer $$k\text{.}$$
The proof shows that $$8n$$ is even for any $$n\text{,}$$ without need to check every possible integer $$n\text{.}$$
In writing a proof we can see that it helps to have precise definitions of the mathematical terms. Then we need to connect our statements in a logical way so that we are convinced that the statement we are proving follows from the steps. The ability to connect our staements in a logical way is the heart of writing a proof. We will start our proof-writing journey by first understanding logical structure.