Proof by Contradiction

In this post we’ll learn one of the most elegant and beautiful logical weapons that mathematicians can wield.  Every mathematician develops a toolbox for proving theorems, and this is one of the most powerful.  Its Latin name is reductio ad absurdum, and its English name is proof by contradiction.

How it works

Suppose we’re trying to prove that a statement (call it A) is true.  Also suppose that there are other statements that have already been proven true.  It doesn’t really matter what these other statements are, except for the fact that they have already been proven completely true.

What we do is suppose that the statement A is false.  There is nothing wrong with supposing something, so long as we never confuse it with something that is proven false.  Now, from this supposition we can start to derive other “valid” statements (scare quotes here to remind us that the subsequent statements are valid only if the supposition is correct (i.e., if A is actually false)).  Using logical deductions from our supposition, we want to arrive at a conclusion that contradicts something else that we know is true.

For example, call one of our already-proven-true statements B, and then suppose that A is false.  If we can use this supposition to show that B is false, then we have a contradiction because B is both true (already proven true) and false (just proven false)!  This is clearly not okay, and it tells us that the initial assumption was wrong.  What was the initial assumption?  That A was false.  Thus, A must be true!  Think about this one, it’s important.  In the meantime, here is a very trivial example (a better example is the proof of infinity primes).

Example

Suppose it is already proven that 0=0, and 0 doesn’t equal anything else.  I.e., zero only equals zero.  (This is obvious, but remember that we’re just looking at the logic here, not the math).  Suppose it is also known that we can add and subtract numbers in the normal way.  We can now ask the following trivial question: does 1=2?  Clearly the answer is no, but how can we prove it?  (obviousness is not a mathematical proof).

First, we assume the opposite.  Suppose that 1=2.  If that’s the case, then let’s see what happens when we subtract 1 from both sides (there’s nothing wrong with doing that).  Then 0=1.  But, we already know that zero equals zero and nothing else!  Therefore the conclusion that we’ve drawn here, namely that 0=1, is a contradiction!  This means our supposition was impossible.  What was our supposition?  That 1=2.  Thus it is the case that 1 does not equal 2.

Yes, this is trivial, but we use this method all the time for proving cooler stuff.  For example, it’s used in lesson 13 for showing that there are, in fact, at least two fundamentally different kinds of infinities, and again in lesson 14 to show that there are infinitely many different kinds of infinity!

Posted in Mathematics | 2 Comments

Infinity Primes

Prerequisites: Prime numbers, proof by contradiction

Here’s an awesome, easy, super clever, and really beautiful theorem/proof combination (which I cannot take credit for (Euclid can, though)).  Once you’ve learned what a prime number is and how to use proof by contradiction, you’ll be good to go (seriously, that’s it).

The beginning of the list of primes goes as follows: \{2, 3, 5, 7, 11, 13, 17, 19, 23, ...\}.  You can write out a thousand more primes if you’d like, but I’m sure you get the picture.  The first natural question to ask is the following: does this list go on forever?  In other words, are there infinitely many primes?  It is clear that an equivalent question would be to ask if there is a largest prime (clearly there is a smallest prime (which is 2), so there is a finite list of primes if and only if there is a largest prime).

Now, there is no reason that there has to be an infinite amount of primes.  As numbers get bigger they become more and more divisible (i.e., there are more numbers that are smaller than them, and therefore more candidates for things that could divide them), so it might be plausible for there to be a cut-off point above which every number can be divided and is therefore not prime.

How might we go about proving a statement regarding infinity?  If the enemy listed a whole bunch of consecutive non-prime numbers, it might provide evidence for the fact that there is a “largest prime”, but that is in no way a proof.  For I could just take the largest number that the enemy gave me and multiply it by itself a hundred billion billion trillion times and tell him to prove that we didn’t “miss” any primes.  What do we do?

Proof by contradiction

We will suppose that there is a largest prime, and arrive at a contradiction.  This contradiction will force us to draw the opposite conclusion, thus proving our claim.  Here we go.

Theorem: There are infinitely many prime numbers.

Proof: Suppose there aren’t.  Then there is a “largest prime”.  We don’t know what this prime is, but we know it’s out there (because we just supposed it exists), so let’s call it P.  Then the entire list of primelooks something like \{2, 3, 5, 7, 11, ..., P\}.  This hypothetical list hypothetically contains all the primes.  If the enemy gives us this list, we can define a new number in the following way: Let N = (2\times 3\times 5\times 7\times 11...\times P)+1.  In other words, N is the number defined by multiplying all of the prime numbers together and then adding 1.  This number would be huge, but it is finite (because our assumption says that there are only a finite amount of primes).

Now we can ask whether or not N is prime.  Remember, it is one or the other, but not both and not neither.

Well, clearly it can’t be prime, because it’s larger than P and we supposed that P was the largest prime.  Thus if N were larger than P and prime, P wouldn’t be the largest prime, which is a contradiction!  So then P must be not prime.  Now if N is not prime, then N must be divisible by a prime number.  This is because N is divisible by something (because it’s not prime), and this something is then either prime or not prime.  If this something is prime, then we’ve shown that N is divisible by a prime.  If this something is not prime, then this something is in turn divisible by something else.  We now just apply the same logic to this “something else”, and eventually we’ll hit a prime.  Thus, since we know N is not prime, it must be divisible by a prime.

Recall though that all of the primes are in our list \{2, 3, 5, 7, ..., P\}.  If we divide N by any of these numbers, we’ll always get a remainder of 1 because N was defined to be the product of multiplying all of these numbers together, and then adding 1.  Thus none of these numbers divides N evenly, so N is not divisible by a prime.  Since we know that every non-prime number is divisible by a prime, N must not be non-prime (sorry for the double negative).  But this means that N is both not prime, and not not prime (double negative)!  This is impossible, since we already know that every number is either prime or not prime.  Thus we’ve reached a complete contradiction, which means that our initial supposition was wrong.  And what was our initial supposition?  It was that there was some largest prime P.  Thus, there can’t be such a “largest prime”, and the only way that this can be true is if the primes go on forever.  Thus there are infinitely many primes!

QED (which means “you just finished the proof and you’re a boss!” in Latin).

Posted in Mathematics | 3 Comments

What is abstract thought?

In various posts throughout this site we have discussed the notion of abstract thought.  Abstract thought is the primary tool that mathematicians use in practicing their art form.  In fact, one could reasonably say that mathematics is the art of pure abstract thought.  The only problem with this, however, is the potential circularity in the reasoning: math is abstract thought, and abstract thought is that which mathematicians do.  Thus, we need to try to attack abstract thought directly.  This is no easy task.

Generalizing: Driving your car = skydiving

Abstract thought is very closely related to the mental process of generalizing.  Another way to think of this is that abstract thought is that which explores what something really “is”.

For example, I am currently drinking a glass of water.  I can generalize this in an infinite number of different ways, but here are a few: I am drinking water, I am consuming water in some way, I am nourishing my body, and I am doing something.  In each of these cases, the statement “I am drinking water” is only a special case.  Namely, if I am drinking water, then I am certainly drinking, I am nourishing my body, I am consuming water in some way, and I am doing something.  The converse is not necessarily true.  For example, I could be drinking orange juice, in which case “I am drinking” is true, but “I am drinking water” is not.  Similar counter examples can be found for the other generalizations.

This generalization is nice because anything that I can say about drinking, or nourishing my body, or consuming water in some way, or doing something, will also be true in the case of drinking water.  For example, if I say “drinking is good,” then it will also be true that “drinking water is good”, because drinking water is a special case of drinking.  You can think up several different examples, and it’s usually pretty fun to do so.

More than just generalizing

Abstract thought also includes the act of appraising the value of a certain generalization.  In other words, it is possible to “over-generalize” and reach a point of generalization that is no longer fruitful.  In the above examples, “I am doing something” would be a point of over-generalization in my opinion.  This is because if I want to make a meaningful generalization of “I am drinking water,” then I don’t want to generalize to the point that “drinking water” and “fighting a gorilla” are both special cases of the same thing.

This is, of course, a matter of taste in this instance.  In mathematics, however, the extent to which an idea is generalized is immensely important for making meaningful progress.  For example, if I took an object that could be generalized to a group (which is a very special type of set, with some added structure) and “over-generalized” it to a generic set (because a group is a set, but a lot of sets are not groups), then I will have lost a lot of meaningful information about the object.  Yes, it is true that anything that I prove to be true about a set is true about a group, but there are likely many important things that I can prove about a group that I can’t prove about a set, and I therefore might not want to generalize everything to a set.

This is how abstract thought is more than mere generalization.  It is also the intangible knowledge of when to stop generalizing.  We will often see the power of this type of thought, and indeed it is abstract thought that makes all of math “go”.  For now, however, it might be fun to try to generalize everything in your life to an almost comical degree.  For example, driving your car is a special case of driving a vehicle, which is a special case of driving, which is a special case of transporting yourself.   Sky-diving is also a special case of transporting yourself (transporting yourself from a plane to the ground, quickly).  Thus, driving and skydiving are, in precisely this way, the same!

Posted in General, Mathematics | Leave a comment

What is a mathematical structure?

In the post “What is math?”, we described mathematics as the art of creating and exploring mathematical structures.  It is not unlikely, however, that the reader is slightly unfamiliar with the notion of a mathematical structure.  If this is the case, then our definition of mathematics is rather unsatisfying.  This post aims to rectify this.

Structures in general

When we think of a structure in the everyday sense, we might think of buildings, houses, and bridges.  We may also think of a structure as a more abstract object involving some form of complex organization.  The plot of a movie, a musical composition, and government bureaucracies all are structures in some sense.  All of these are instances in which small sub-structures are organized in ways to create larger, more complicated patterns.  A building is nothing but the complicated organization of smaller sub-structures such as bricks, cement, wood, and iron.  A musical composition is a complicated organization of melodies and harmonies, which are in turn complicated organizations of notes and rhythms.

Math Structures

Math is no different.  A mathematical structure is nothing but a (more or less) complicated organization of smaller, more fundamental mathematical substructures.  Numbers are one kind of structure, and they can be used to build bigger structures like vectors and matrices (the definitions for which will be posted in the future).

There are plenty of other kinds of mathematical structures that exist in a rather fundamental way, and that can be used to build other remarkably beautiful structures.  Sets and functions are both incredibly fundamental in mathematics, and they can be used to build crazy things like topological spaces (again, which haven’t been defined (yet) on this site, but will be soon).  Sets and functions can also be tools for exploring different types of infinities.

Building your castle

One of several mathematical castles that you can build for yourself!

Studying math is like building a castle in your head.  When building a castle, you first must learn to build a brick, and once that is mastered, you can use it to build a wall.  Once you can build a wall, you can build a tower.  Stronger bricks allow for higher walls and bigger towers.  Additionally, powerful tools allow you to build faster and more efficiently.

The beauty of a mathematical structure comes from its ability to have larger structures built from it.  Certain mathematical concepts allow for faster building than others.  For example, a mathematician will find a mathematical crane much more useful than a mathematical wheelbarrow.

While you were in high school, you likely only learned about one type of structure—those that could be built up from numbers.  Although some of this is interesting, the real beauty of math lies in the flexibility and deep interconnectedness of various kinds of mathematical structure.  We explore several of these structures throughout this site, and I believe that once you start on your castle, you’ll never want to stop.

Posted in Mathematics | Tagged , , , , , , | Leave a comment

What is mathematics?

Math isn’t what you thought it was.

You might think that math goes something like this:

Calculate or simplify the following expressions:

  1.  535\times 45
  2. 12^3
  3. the derivative of f(x)=3x^4 + 25x^3 + 5\mathrm{sin}(x)
  4. (x+5)^3

Well, that all sucks.  No one wants to do any of that.  From this, one might think that math is just remembering the right formula, or the right steps, and then having the patience and focus to follow these steps for several minutes without making a mistake.  It involves tediously writing numbers and letters all over the paper in exactly the way that your teacher told you would work.  We often have no real idea as to why we’re doing this, or any knowledge of the vast logical constructions that make it all possible—we’re just calculating.  This post will explain that there is another kind of math—one that focuses primarily on the abstract foundations and the deep logical reasoning that goes in to establishing the math that we’re used to doing every day.  To begin exploring this “other” type of math first-hand, head on over to the lessons!

Two types of math.

I am going to refer to the above kind of math as “calculation”.  I.e., when we’re answering questions 1-4 above, we’re not doing our “mathematics” homework, but rather our “calculation” homework.  I will reserve the term “real mathematics” for what I mean by this “other world” of math.

What is “real” mathematics?   There are volumes written about this question, and I will only spend a few sentences on it here.  As you spend time reading through the lessons and exposing yourself to what I call “real” math, you’ll form your own idea of what mathematics is.  We can, however, make a little progress right here and now.

“Real” mathematics (or just mathematics) is the art of creating, understanding, and exploring the relationships between various mathematical* structures.  Mathematics is the art of making mathematics, by exploring and  understanding mathematical structures.  (Numbers are one such structure, but there are infinitely many more.  We will explore mathematical structures more in depth later, and many examples of such structures can be found on this site.)

There is indeed a good amount of what I’m calling “real” mathematics hidden inside of a standard high school math curriculum, and those who like math tend to be drawn to these bits.  But these parts of the curriculum are often drowned out by the emphasis on memorization, rote learning, and repetition.  Questions 1-4 above lie on top of a very elegant logical framework, but we often completely ignore this in order to get on with our calculations.

What do mathematicians do?

A mathematician does not spend his day calculating 2+2 or “the derivative of f(x)=3x^4 + 25x^3 + 5\mathrm{sin}(x)”.  He or she instead thinks about why and precisely when it is the case that 2+2=4, or what a derivative really means and what it can be used for.  The more math you learn, the more you realize that 2+2 does not always equal 4 (this will be explained when we describe “clock arithmetic”).  The remarkable logical foundation on which the true statement “2+2=4” stands was built by mathematicians who were doing “real” mathematics.  The actual process of calculating the result of 2+2 (and other similar calculations) is important for students to learn, but it is not the kind of thinking that goes into much of mathematics.

Everyone, from high school students to professional mathematicians, hates calculating derivatives.  The difference is that professional mathematicians have been exposed to the logical and rigorous foundations that make these calculations possible.  They’ve studied what derivatives are, where they come from, and what they lead to, and these kinds of considerations are what keeps them in the business of studying math.  Additionally, they find a deeper and more subtle beauty in the calculations themselves.  This site aims to introduce its readers to this type of math—what I’m calling “real” (as opposed to calculational)—and to explore some of the gorgeous subtleties that come along with it.

*You might be worried that I used the term “mathematical” in the definition of mathematics, but I have reason to do this.  A mathematical structure is a thing, and I am using it to describe what mathematics is as an art form.  In other words, there would be no problem saying that “painting is the art of making paintings”, and that is essentially what I’ve done here.

So true.
Posted in Mathematics | Leave a comment