Proofs Perceived

I hope to impart some extremely awesome facts on the intrinsic elements of being a mathematician and knowing mathematics by explaining, broadly, the fundamentals of proofs. I will do this by first giving you the basics and then move to more interesting theorems/proofs. For simplicities’ sake all information contained in this blog post is from the book “The Nuts and Bolts of Proofs” by Antonella Cupillari and I have included the page numbers at the end of the sentences.

Let’s start with if/then statements. If/then statements are like statements of a scientist who happens to states his hypothesis when he first starts talking only to end on some conclusion that was dependent upon his hypothesis (11). The tricky part of proving if/then statements is that some of the information might not be explicitly stated (12). For instance, sometimes people will ask you how long it takes to get a college degree. The amount of fluctuation in the length of time it takes differs greatly because of different requirements and different people, but it is implied that the person is looking for average length of time. This implied part can slip you up when trying to do these proofs because you might need to use information that is implied. For example, let’s say you were given an assignment to prove that two is prime. The original statement if two satisfies the condition of being prime then it is prime, will very likely not state that you can use all the properties of real numbers. You could accidentally see things being implied that aren’t being implied. If/then statements are a basic statement in mathematics and fundamental to many theorems and proofs.

All proofs fall into one of two categories, or a mixture of these categories (12-29). The categories are indirect proof and direct proof. Direct proof is like performing a calculation or computing a problem in most math classes. You just carry out a series of logically valid calculations to come to a final answer. You are given a beginning claim that you want to show leads to some particular conclusion. Essentially, you want to move from point “A” to point “B”, and in order to do so in a direct proof you carry out a series of logical steps. Direct proofs are used when there is enough information in the hypothesis to come to the conclusion (12). Indirect proofs are a bit more complicated than direct proofs. Indirect proofs involve altering the hypothesis in order to prove a different statement that is logically equivalent to the original hypothesis (22). A specific example of indirect proof is proof by contradiction. Proof by contradiction is assuming the hypothesis to not be true, and if this leads to a contradiction, then the hypothesis must be true.

Negation of quantifiers is also fundamental to proofs. I will identify the quantifiers in bold followed by an example and another example of its negation. All of this information on quantifiers can be found on page twenty-five from the book “The Nuts and Bolts of Proofs” by Antonella Cupillari as previously mentioned earlier. There are six quantifier negations that you just have to know. The first is at least one, as in there is at least one mathematician in our class (Hint: Lamb). The negation of this statement would be none of our classmates are mathematicians. The second one you have to know is some. Today some new myths will be made. The number of new myths made today was none. If you assert that all birds in America drink water, the negation of this statement is there is at least one object in the collection that does not have that property. Specific to the example given, the negation would be there is at least one bird in America that doesn’t drink water.

The fourth quantifier that you need to know is none. None of the boys in Salt Lake City like to eat cake. There is at least one boy in Salt Lake City that likes to eat cake. Fifth is there is no unicorn. There is at least one unicorn. The sixth is every object in a collection has a certain property. Every book at the University of Utah is worth reading. There is at least one book in the University that is not worth reading.

Moving on to the theorems and special proofs. By special proofs I mean specific versions of direct and indirect proofs. Theorems are general truths that are proven to be true by a series of logical steps, hence their connection to proofs (50). Existence proofs involve either an algorithm as a proof or an argument that proves the existence of the object in question and are often in the category of theorem (58). Just in case anyone doesn’t know what an algorithm is, it is a series of steps that are carried out sequentially. Also, an argument is a claim that is usually supported by reason and evidence, but as religion has shown, neither reason nor evidence is needed to argue—just some claim that causes controversy is necessary.

Another special type of proofs is the uniqueness proof, which shows that the steps/algorithms to show that the object exists were unique (61). Or by assuming that the object isn’t unique and then showing that the other object with the same properties isn’t a different object, and by constructing a valid argument you are able to prove uniqueness (61).

If and only if proofs involve the proof of two separate if/then proofs in order to prove the if and only if statement (35). An example of this is necessary because it is difficult to explain in words. “I will checkout more books if and only if I can read the books I have” would require the proof of “if I will checkout more books then I can read the books I have” and the proof of “if I can read the books I have then I can checkout more books.” Once you have done this then you have proven the statement “I will checkout more books if and only if I can read the books I have.” This makes more sense when you think about the fact that both checking-out more books and reading the books I already have must both be true in order to get a true statement. If either is false then the statement is false but if both are false then the statement is true (35). In this relationship checking-out books and reading the books I already have must follow each other in their truth value in order to get a true statement (35).

Proof by induction is also another cool, interesting tool in the world of mathematics and it is of great utility. All information on mathematical inductive proofs can be found on pages 48-58.  The first step in a proof by induction is to prove that the hypothesis is true for the smallest base case. Then you assume that it is true for some arbitrary value. After that you deductively show that it is true for an arbitrary value plus an additional defined magnitude. If you said for any natural number there is always a number greater in magnitude, the first thing you would do is show that it is true for the smallest case. In this instance the smallest case is one with two being greater. Then you would assume that an arbitrary number represented by some variable, usually “n”, has the same property. After that you would show that your hypothesis is true for the “n” plus one case. The steps taken in a proof by induction are awesome because it gives you the ability to conquer the infinite with a logical domino effect.

You now know the basics of proofs—which are if/then statements, negations, direct proofs, indirect proofs, and quantifiers. You also know some more interesting aspects of proofs such as proof by induction, if and only if proofs, existence proofs, and uniqueness proofs. How is this information important to your life?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s