Logic and Proofs, An Introduction

Introduction

Ask someone to define logic, and they will probably tell you that it is "A process, a way of thinking, where each step follows logically from the previous steps." This is of course circular reasoning. We fall into this trap because logical thought is difficult to define. In fact, logical thought is impossible. Unless we are adding fractions, or performing some other purely mechanical task, we are always guided by our emotions, our experience, and other subconscious processes beyond our control or comprehension. Indeed, even skeptical scientists are beginning to recognize the value of intuition. So, if you're trying to decide whether to get married, you're not going to be 100% logical about the whole thing, though a certain amount of logic is appropriate if you want the marriage to last.

In the world of mathematics, pure logic does exist, and it is surprisingly close (in spirit) to the circular definition given above. Consider the following, as a first approximation.

Logic is a sequence of statements, where each statement conforms to a certain syntax, and each statement can be constructed from the earlier statements using rules of inference.

We choose these rules of inference carefully, so that a batch of true statements only produces true statements. For example, a rule might say that you can put any two statements together with "and" between them. If statement 7 says "The earth is round", and statement 9 says "Water contains hydrogen", we can put them together to make statement 23: "The earth is round and water contains hydrogen."

This is all well and good, but logic needs a place to start. The very first statement can't be inferred. Instead, the first few statements are called axioms, and are assumed to be true without question. Subsequent statements are then derived from these axioms.

Some axioms are basic - you can't get along without them - but other axioms are arbitrary. For example, most mathematicians accept the axiom of choice, because we like the resulting theorems, but this is a matter of taste. You can deny the axiom of choice, declaring it false instead of true, and a new batch of theorems appears.

In summary, logic is a system of inferring new statements, based on prior statements and specific rules of inference. The rules and the axioms must be specified at the outset, just like the rules of a grammar.

A proof is a sequence of inferences that starts with the axioms, and leads to the particular statement you wish to prove. This is similar to a "derivation", which "proves" that a word is generated by a grammar, and is part of the corresponding language.