14.1 Logic and Proof

Why Logic Matters in Mathematics

Logic is the “grammar” of mathematical thinking. It tells us what it means for a statement to be true, how statements can be combined, and how we can move from known truths to new conclusions.

In this chapter, the focus is not on any particular area of mathematics (like numbers or geometry), but on the way mathematical reasoning itself is structured. Later chapters in this part of the course will talk about specific kinds of propositions and specific proof techniques. Here, you will see the big picture: what logical reasoning is, what a proof is supposed to accomplish, and how they relate.

Mathematical Reasoning vs Everyday Reasoning

People use “logic” informally all the time:

• “If it’s raining, then the ground will be wet.”
• “Either I forgot my keys, or I left them in the car.”

Mathematical logic aims to:

• Remove ambiguity (no vague words like “sort of,” “roughly,” “usually”).
• Make the structure of reasoning explicit (you can see clearly what depends on what).
• Guarantee that if you follow the rules, you never reach a false conclusion from true assumptions.

Everyday arguments often appeal to feelings, authority, or incomplete evidence. Mathematical arguments are supposed to rely only on clearly stated assumptions and strict logical steps.

Statements, Reasoning, and Proofs

Later, a separate chapter will go into “Propositions” and “Logical equivalence.” Here you only need a very simple view:

• A mathematical statement (or proposition) is something that is either true or false, but not both.
• A proof is a careful logical explanation that shows why a statement must be true, starting from agreed-upon assumptions (definitions, axioms, previously proved results).

The goal of a proof is not just to convince you emotionally, but to give a chain of reasoning that any careful reader can check.

You will see specific proof methods later (direct proof, proof by contradiction, induction). For now, focus on what makes any argument count as a valid proof at all.

Structure of a Mathematical Argument

At an abstract level, a mathematical argument has:

1. Assumptions (Premises)
   These include:
• Definitions (what words mean in a precise way).
• Axioms or postulates (basic facts we accept without proof).
• Previously proved theorems.
2. Logical steps
   Each step must:
• Follow from earlier steps or assumptions, using valid logical rules.
• Be clear enough that a careful reader could reconstruct the reasoning.
3. Conclusion
   The statement you wanted to prove. When the last step is reached, you can say the conclusion follows from the assumptions.

A proof is valid if every step is justified and the conclusion really does follow from the premises. The truth of the conclusion depends on both the validity of the reasoning and the truth of the premises.

Deductive vs Inductive Thinking (In the Informal Sense)

The word “induction” will later refer to a specific proof technique (mathematical induction). Here we distinguish two general patterns of thinking:

• Deductive reasoning: Start from general rules and known facts, and derive specific conclusions that must be true if the premises are true.

Example pattern:

• All even numbers are divisible by $2$.
• $8$ is an even number.
• Therefore, $8$ is divisible by $2$.

• Inductive (informal) reasoning: Notice patterns in many specific cases and guess a general rule that might be true.

Example pattern:

• $1^2 = 1$
• $1^2 + 2^2 = 5$
• $1^2 + 2^2 + 3^2 = 14$
  You might look for a pattern and conjecture a formula for the sum of squares.

Mathematics often uses informal induction to create conjectures (educated guesses). But a conjecture does not count as a theorem until there is a deductive proof.

Validity and Soundness

Two different issues arise when we judge a mathematical argument.

1. Validity: Does the conclusion follow logically from the premises?

An argument is valid if, assuming all the premises are true, the conclusion would have to be true. Validity is about the form of the reasoning, not about whether the premises are actually true.

2. Soundness: Are the premises actually true, and is the reasoning valid?

An argument is sound if:

• It is valid.
• All its premises are in fact true.

In mathematics, we usually assume our basic axioms and definitions and focus on making each proof valid. The larger body of mathematics is then built to be sound with respect to those starting assumptions.

Common Patterns of Correct Reasoning

Later, you will learn specific logical operators and how to manipulate them systematically. Here are some basic patterns of reasoning that come up constantly in proofs.

Modus Ponens (Using an “If–Then” Statement)

Pattern:

• Premise: “If $P$, then $Q$.”
• Premise: $P$ is true.
• Conclusion: $Q$ is true.

In symbols, this has the form: from $P \to Q$ and $P$, conclude $Q$.

This is perhaps the most basic move in mathematical proof: once you know the condition $P$ holds, you are allowed to use all consequences $Q$ that follow from $P$.

Modus Tollens (Reasoning from a False Consequence)

Pattern:

• Premise: “If $P$, then $Q$.”
• Premise: $Q$ is false (not $Q$).
• Conclusion: $P$ is false (not $P$).

In symbolic form: from $P \to Q$ and $\lnot Q$, conclude $\lnot P$.

This pattern underlies proof by contradiction and contrapositive arguments, which will be treated carefully later.

Chain of Implications

Mathematical arguments frequently link several “if–then” statements:

• If $P$, then $Q$.
• If $Q$, then $R$.
• Therefore, if $P$, then $R$.

In symbols: from $P \to Q$ and $Q \to R$, conclude $P \to R$.

In a proof, you might show:

• Assuming $P$, some property $Q$ holds.
• From $Q$, another property $R$ holds.
• Therefore, assuming $P$ leads logically to $R$.

This is how longer proofs are built from shorter logical steps.

Common Logical Pitfalls

Because logic is strict, many arguments that sound convincing at first are actually incorrect. Knowing typical errors will help you both understand others’ proofs and avoid mistakes in your own.

Affirming the Consequent

Faulty pattern:

• Premise: “If $P$, then $Q$.”
• Premise: $Q$ is true.
• Incorrect conclusion: $P$ is true.

In symbols, from $P \to Q$ and $Q$, it is not valid to conclude $P$.

Example of why this is wrong (informally):
“If it is raining, the ground is wet.” The ground might be wet for other reasons (a sprinkler). So from “the ground is wet,” you cannot conclude that it is raining.

Denying the Antecedent

Faulty pattern:

• Premise: “If $P$, then $Q$.”
• Premise: $P$ is false (not $P$).
• Incorrect conclusion: $Q$ is false (not $Q$).

From $P \to Q$ and $\lnot P$, you cannot conclude $\lnot Q$.

Using the same example:
“If it is raining, the ground is wet.” From “it is not raining,” you cannot conclude “the ground is not wet.” There may be another cause.

Confusing “If” with “If and Only If”

An implication “If $P$, then $Q$” says that whenever $P$ occurs, $Q$ also occurs. It does not say that $Q$ occurs only when $P$ does.

An “if and only if” statement, often written “$P$ iff $Q$,” represents a stronger claim: $P$ implies $Q$ and $Q$ implies $P$.

In proofs, being careless about this difference can cause you to assume more than you have actually proved.

The Role of Definitions and Axioms

Logical reasoning operates on content. That content is provided by:

• Definitions: give precise meaning to terms (for example, what exactly counts as a “prime number”).
• Axioms (postulates): statements taken as basic truths for a given mathematical theory.

Logic itself doesn’t tell you which axioms to choose; it only tells you what follows once you have chosen them. Different areas of mathematics can start from different sets of axioms, but within each area, the same basic logical rules are used.

When proving something, you must:

• Use definitions correctly (do not assume more than the definition says).
• Use axioms and previously proved results as your starting points.

Proofs as Explanations, Not Just Verifications

A proof does more than check that something is true. It also explains why it is true by revealing how it depends on simpler facts.

Two different proofs of the same statement can give very different insights. For example:

• One proof may show how a statement fits into a general pattern.
• Another may show a surprising connection to a different part of mathematics.

Thus, learning logic and proof is not only about correctness; it is also about understanding.

How Logic and Proof Connect to the Rest of the Course

In this course:

• The chapter on Propositions will focus on the basic building blocks of logical statements and how to combine them.
• The chapter on Logical equivalence will show when two statements really say the same thing, even if they look different.
• The later Proof Techniques and Writing Proofs chapters will show you specific methods and styles for constructing clear, rigorous arguments.

This chapter prepares you by:

• Emphasizing that mathematical claims require justification.
• Highlighting the distinction between valid and invalid reasoning.
• Showing that proofs are formalized, checked chains of logical steps, not just persuasive stories.

As you progress, keep returning to this simple idea: a proof is a logically correct explanation of why a statement must be true, starting from clearly stated assumptions.