Introduction to Proof & Discrete Math

Welcome to the very first idea in the whole course. Before we can write a single proof, we have to agree on what counts as a clear claim. That is what this lesson builds, and it starts from something you already do every day. Every time you say "the store is open" or "it will rain later," you make a claim that is either right or wrong. Logic is just the careful study of claims like these, and proofs are chains of such claims linked together.

The building block of all logic is the proposition. A proposition is a declarative sentence that makes a claim which is either true or false, and never both at once. That is the entire definition. Read it once more: a proposition has a definite truth value, true or false.

Let us look at real examples before any letters appear.

• "7 is a prime number" is a proposition. It makes a claim, and the claim is true.
• "The integer 12 is odd" is a proposition too. It makes a claim, and the claim happens to be false. Being false does not stop a sentence from being a proposition.
• "What time is it?" is not a proposition. A question does not assert anything, so it cannot be true or false.
• "Close the door" is not a proposition. A command asks for an action; it makes no claim.
• "x + 1 = 5" is not a proposition on its own. Until we know what x is, we cannot say whether it is true.

That last one is worth pausing on, because it returns later in the course. A sentence with an unknown in it sits in a kind of waiting room. Once we fill in the unknown, or say something about all of its possible values, it becomes a genuine proposition. We name propositions with capital letters like P, Q, and R, the same way algebra names a number x. The letter is shorthand for "some definite claim," so we can talk about its shape without rewriting the whole sentence.

Key idea: a proposition is a sentence with a definite truth value, true or false.

The five connectives

On their own, single claims are limited. The interesting statements combine several claims, the way "it is cold and it is raining" combines two. The words we use to join claims are called logical connectives. There are five to learn, and each one has a symbol and exactly one fixed meaning. We will read each symbol out loud in plain English the first time it appears.

• Negation ~P, read "not P." It flips the truth value. If P is true, then ~P is false, and the other way around. Example: if P is "5 is prime" (true), then ~P is "5 is not prime" (false).
• Conjunction P AND Q, read "P and Q." It is true only when both parts are true. If either part fails, the whole thing is false. Think of a two-item to-do list: you finished it only if you did both tasks.
• Disjunction P OR Q, read "P or Q." It is true when at least one part is true. In logic, "or" also allows both to be true. This is called the inclusive or, and it is the default meaning throughout mathematics.
• Conditional P => Q, read "if P then Q." This one behaves like a promise, and we will spend a whole section on it.
• Biconditional P <=> Q, read "P if and only if Q." It is true exactly when both parts have the same truth value, either both true or both false.

Here is a plain way to hold the first three in mind. "And" is demanding, it wants everything. "Or" is generous, it is happy with one. "Not" is a switch, it reverses whatever it touches. Those three pictures will carry you a long way.

A quick concrete check. Let P be "3 > 2" (true) and Q be "3 > 5" (false). Then P AND Q is false, because Q fails. But P OR Q is true, because P holds. And ~Q is true, because Q was false. Notice how you settle each one by looking only at the truth values of the parts, not at their meaning.

One caution about "or." In everyday speech we sometimes mean the exclusive or, as in "soup or salad," where you pick one and not both. Mathematics almost always uses the inclusive or, where "both" is allowed. Whenever this course writes P OR Q, read it as "at least one, and possibly both."

Key idea: "and" needs both parts true, "or" needs at least one, "not" flips the value.

Building bigger statements

Once you have the five connectives, you can stack them, and a little care with grouping keeps the meaning clear. Parentheses do the grouping, exactly as in arithmetic. Consider ~(P AND Q). The parentheses say "first form P and Q, then negate the result," so this reads "it is not the case that both P and Q hold." Compare it with ~P AND ~Q, which reads "P fails and Q fails." These two are genuinely different statements, and telling them apart is a skill we will sharpen next lesson.

Let us parse one compound statement slowly. Take (P AND Q) => R, read "if both P and Q hold, then R holds." Suppose P is "it is a weekday," Q is "it is before noon," and R is "the bakery is open." The whole statement claims: on any weekday morning, the bakery is open. To check it in a situation, first see whether the hypothesis P AND Q is true, and only then look at R. Reading from the inside out, one grouping at a time, is the habit that makes long statements manageable.

Key idea: parentheses set the order of operations for logic, so ~(P AND Q) and ~P AND ~Q can mean different things.

Understanding the conditional

The conditional P => Q trips up almost every beginner, so we will move slowly, and it will settle into place. Here P is called the hypothesis and Q is called the conclusion. The statement is a promise: it says "whenever P happens, Q happens too."

The one and only way to break a promise like this is for the hypothesis to come true while the conclusion fails. So P => Q is false in exactly one situation: P true and Q false. In every other case the promise counts as kept, so the conditional is true.

Let us make that concrete with an everyday promise. Suppose a friend says, "If it rains, I will bring an umbrella." There are four ways the day can go.

1. It rains, and they bring the umbrella. Promise kept. True.
2. It rains, and they forget the umbrella. Promise broken. False.
3. It does not rain, and they bring the umbrella anyway. Promise not broken. True.
4. It does not rain, and they carry no umbrella. Promise not broken. True.

Look hard at rows 3 and 4. The friend made no promise about dry days, so nothing they do on a dry day can break the promise. That is the idea behind a rule that sounds odd at first: when the hypothesis P is false, the conditional is automatically true. We call this vacuously true, meaning true because there was nothing to check.

Here is a mathematical example of vacuous truth: "if 3 is even, then the moon is made of cheese." The hypothesis "3 is even" is false, so the promise was never triggered, and the whole statement counts as true. It is common to find this rule surprising the first several times. The payoff is that it keeps logic free of exceptions, which is exactly what proofs need.

Where people get stuck: many readers expect P => Q to be false whenever P is false. It is the opposite. A false hypothesis makes the conditional true, because an untriggered promise is never broken. When in doubt, ask, "did we ever catch the promise being broken?" Only a true P paired with a false Q does that.

Key idea: P => Q is false only when P is true and Q is false; everything else is true.

Try it: kept or broken?

Let the conditional be "if a number ends in 0, then it is even." Decide its status for the number 30, and then for the number 7.

For 30: it ends in 0 (hypothesis true) and it is even (conclusion true). The promise is kept, so the conditional is true here. For 7: it does not end in 0 (hypothesis false), so the promise was never triggered, and the conditional is true no matter what. Nice work, you just applied the vacuous-truth rule on your own.

How mathematicians write these

Textbooks often use compact symbols for the connectives, and it helps to recognize them on sight. Negation is written ¬, read "not." Conjunction uses ∧, read "and." Disjunction uses ∨, read "or." The conditional uses an arrow →, read "implies" or "if...then," and the biconditional uses a double arrow ↔, read "if and only if." In this course we usually spell the connectives out as words, but the meaning is identical to these symbols, so you can move between the two notations freely.

Related conditionals

From any conditional P => Q we can build three close relatives. They look similar, which is exactly why they get confused, so we will define each and then test all three on one example.

• The converse is Q => P. Same parts, order swapped.
• The inverse is ~P => ~Q. Same order, both parts negated.
• The contrapositive is ~Q => ~P. Swapped and both negated.

Let us test them on a real sentence: "If it is raining, then the ground is wet." Here P is "it is raining" and Q is "the ground is wet."

1. Converse: "if the ground is wet, then it is raining." This need not be true, because a sprinkler could wet the ground with no rain at all.
2. Inverse: "if it is not raining, then the ground is not wet." Same problem, the sprinkler breaks it again.
3. Contrapositive: "if the ground is not wet, then it is not raining." This one must be true whenever the original is, because dry ground rules out rain.

There is a rule hiding in that example, and it is one of the most useful facts in the whole course. A conditional and its contrapositive always mean the same thing; they are true in exactly the same situations. But a conditional and its converse are not the same, as the rain example just showed. We will prove the contrapositive equivalence carefully in a later lesson and then lean on it constantly to write proofs.

Where people get stuck: the classic error is treating a statement and its converse as interchangeable. "Wet ground" does not force "rain," even though "rain" forces "wet ground." Whenever you meet a conditional, keep the arrow pointing the way it was written, and resist the pull to flip it.

Key idea: a conditional equals its contrapositive, but not its converse.

Reading and writing statements cleanly

A large part of proof-writing is stating claims precisely before you argue about them, and three small habits help from day one. First, decide whether your sentence is actually a proposition; if it carries a free unknown, either name a domain or attach a quantifier so it gains a definite truth value. Second, name the pieces: write out what P and Q stand for, in plain words, so a reader can follow your thinking. Third, when you write a conditional, place the hypothesis and conclusion in the intended order, because the arrow direction carries the meaning.

These habits feel slow at first, and that is expected. Every experienced proof-writer passed through the same careful stage. The precision you build now is what will make later proofs read as steady steps rather than mysterious leaps, so the time you spend here pays off across the entire course.

Recap

• A proposition is a sentence with a definite truth value, true or false.
• The five connectives are negation (not), conjunction (and), disjunction (inclusive or), the conditional (if...then), and the biconditional (if and only if).
• "And" needs both parts true; "or" needs at least one; "not" flips the value; parentheses control grouping.
• The conditional P => Q is false only when P is true and Q is false, and it is vacuously true whenever P is false.
• A conditional equals its contrapositive but not its converse; confusing a statement with its converse is the most common logic error.

Sources

1. OpenStax. (2023). 2.1 Statements and quantifiers. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 2.2 Compound statements. In Contemporary mathematics. Rice University. openstax.org
3. Hammack, R. (2018). Chapter 2: Logic. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
4. Levin, O. (n.d.). 0.2 Mathematical statements. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
5. Encyclopedia of Mathematics. (n.d.). Propositional calculus. European Mathematical Society. encyclopediaofmath.org
6. Weisstein, E. W. (n.d.). Implies. MathWorld: A Wolfram web resource. mathworld.wolfram.com
7. Weber, K. (2001). Student difficulty in constructing proofs: The need for strategic knowledge. Educational Studies in Mathematics, 48(1), 101-119. doi.org/10.1023/A:1015535614355

Last lesson we learned what the connectives mean, one at a time. This lesson gives us a tool that checks a whole statement in every possible case at once, with no guessing. That tool is the truth table. Once you can build one, questions that sound hard, like "are these two statements really the same?", turn into a calm, mechanical check you can always finish.

A truth table lists every possible combination of truth values for the parts of a statement, and then computes the value of the whole statement in each case. Think of it like testing a machine by trying every switch position. If a statement has n distinct simple propositions inside it, the table has 2^n rows, because each proposition can independently be true (T) or false (F). Two propositions give 4 rows, three give 8, and so on.

A statement built from P, Q, and R, for instance, needs 2^3 = 8 rows, one for every way to assign T or F to the three parts. The table grows fast, but it never leaves anything to chance.

Key idea: a truth table checks a statement in all 2^n cases, so it settles logic questions with certainty.

Building a truth table step by step

Let us build one together for the statement ~P OR Q, read "not P, or Q." We go one small column at a time.

1. Count the simple parts. Here they are P and Q, so n = 2 and we need 2^2 = 4 rows.
2. Write the input columns so every combination appears once. A tidy habit: P goes T, T, F, F down the column, and Q goes T, F, T, F. Now all four cases are covered.
3. Add a helper column for ~P. Wherever P is T, write F; wherever P is F, write T. So the ~P column reads F, F, T, T.
4. Now compute ~P OR Q in each row using the "or" rule: true if at least one of ~P or Q is true.

Working down the four rows: row 1 has ~P = F and Q = T, so the or is true. Row 2 has ~P = F and Q = F, so the or is false. Row 3 has ~P = T, so the or is true. Row 4 has ~P = T, so the or is true. The final column reads T, F, T, T.

Look at where that column is false: only in row 2, where P is true and Q is false. Keep that observation in your pocket. We will meet it again very soon, because it is no accident.

Let us do one more, this time P AND ~Q, read "P and not Q." Same four input rows for P and Q. First build the ~Q helper column: since Q is T, F, T, F, its negation ~Q is F, T, F, T. Now apply the "and" rule, which needs both parts true.

1. Row 1: P = T and ~Q = F, so the "and" is false.
2. Row 2: P = T and ~Q = T, so the "and" is true.
3. Row 3: P = F, so the "and" is false right away.
4. Row 4: P = F, so the "and" is false again.

The final column for P AND ~Q reads F, T, F, F, true only in row 2. That is the exact opposite of the conditional P => Q, which was false only in row 2. Seeing two statements come out as perfect opposites is a strong hint, and here it says something true: P AND ~Q is the negation of P => Q. We will use that fact when we set up proofs by contradiction.

Where people get stuck: the most common slip is missing a row or repeating one. The fix is the fixed pattern in step 2. Always fill the input columns in the same order, and the count will come out to exactly 2^n distinct rows every time.

The basic tables

Two tables are worth memorizing outright, the conditional and the biconditional. Here they are side by side.

P	Q	P => Q	P <=> Q
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

Read the conditional column with the promise idea from last lesson. The only F sits in the row where P is true and Q is false, the one case that breaks the promise. Every other row is T, including the two rows where P is false, which are the vacuously true cases.

Now read the biconditional column. It is T exactly in the rows where P and Q share the same truth value, rows one and four, and F where they disagree. That matches "P if and only if Q," which asks the two sides to march in step.

Key idea: the conditional is false in one row only; the biconditional is true only when both parts match.

Tautologies and contradictions

Some statements come out the same no matter what their inputs do, and these deserve names.

• A tautology is true in every row. The classic example is P OR ~P, read "P or not P." Whether P is true or false, at least one of P and ~P is true, so the whole thing is always true. This is called the law of the excluded middle.
• A contradiction is false in every row, such as P AND ~P, read "P and not P." No single value of P can make both P and ~P true at once, so it is always false.
• A statement that is true in some rows and false in others is called a contingency. Most statements you meet are contingencies.

Tautologies are the backbone of valid reasoning. When we say an argument form is correct, we mean its truth is guaranteed in every case, which is exactly what a tautology captures. Later, proving a statement will often amount to showing that a certain conditional is a tautology.

Key idea: a tautology is always true, a contradiction is always false, and everything in between is a contingency.

Logical equivalence

Two statements are logically equivalent when they have identical truth tables, matching in every single row. We write this with three bars, ===, read "is logically equivalent to." Equivalent statements are interchangeable: you may swap one for the other inside any argument without changing what is true. Two equivalences come up constantly, so we will look at both.

Conditional as disjunction. The conditional can be rewritten with no arrow at all: P => Q === ~P OR Q. Remember the truth table we built by hand a moment ago for ~P OR Q? Its final column was T, F, T, T, false only when P is true and Q is false. That is exactly the conditional's column. Since the two columns agree in all four rows, the statements are equivalent. This is a handy trick: whenever a conditional is awkward, you can trade it for an "or."

De Morgan's laws. These two laws tell you how a negation spreads across "and" and "or."

• ~(P AND Q) === ~P OR ~Q
• ~(P OR Q) === ~P AND ~Q

In plain words: the negation of "both hold" is "at least one fails," and the negation of "at least one holds" is "both fail." A picture helps. If someone claims "I have a cat and a dog," you can call them wrong by pointing out they lack a cat, or lack a dog. One failure is enough, which is precisely the "or" on the right side of the first law.

Let us verify the first law with a full truth table, computing each side and comparing.

P	Q	P AND Q	~(P AND Q)	~P OR ~Q
T	T	T	F	F
T	F	F	T	T
F	T	F	T	T
F	F	F	T	T

Read the last two columns, ~(P AND Q) and ~P OR ~Q. They match in all four rows: F, T, T, T. Because the columns are identical, the equivalence holds. That is a complete verification, and you could check the second law the very same way.

De Morgan's laws matter far beyond this lesson. When you set up a proof by contradiction, you first negate a complicated statement, and these laws are exactly what let you push the negation inward correctly. They return in the chapters on quantifiers and on sets, wearing slightly different clothes each time, so time spent here pays off repeatedly.

Where people get stuck: when negating P AND Q, it is tempting to write ~P AND ~Q, keeping the "and." That is wrong. The connective flips too: "and" becomes "or," and "or" becomes "and." Negate both parts and switch the connective, every time.

Substituting equivalent statements

Here is why logical equivalence is worth the effort: equivalent statements are fully interchangeable. If A === B, then any place A appears inside a larger statement, you may replace it with B without changing the overall truth value. This is called the replacement rule, and it is the engine that lets us simplify messy statements into clean ones.

A quick illustration. Suppose you face the statement ~(P => Q), read "not, P implies Q." Using the equivalence P => Q === ~P OR Q, rewrite the inside first to get ~(~P OR Q). Now apply De Morgan's law to the outer negation: it becomes ~(~P) AND ~Q. Finally, a double negation ~(~P) is just P, so the whole thing simplifies to P AND ~Q. That matches the truth-table fact we noticed earlier, that P AND ~Q is the negation of the conditional. Two different roads, same destination.

Key idea: equivalent statements can be swapped anywhere, so a chain of known equivalences turns a tangled statement into a simple one.

Try it: are these equivalent?

Decide whether P => Q is equivalent to its converse Q => P by comparing one telling row.

Take the row where P is true and Q is false. There the conditional P => Q is F, because a true hypothesis with a false conclusion breaks the promise. But the converse Q => P has hypothesis Q false, so it is vacuously true, T. The two disagree in that row, so they are not equivalent. Nicely done, that single mismatched row is a complete answer.

Recap

• A truth table has 2^n rows and checks a statement in every case.
• Fill the input columns in a fixed pattern so you get exactly the right rows, then compute helper columns before the final one.
• A tautology is always true, a contradiction always false, and a contingency is sometimes each.
• Two statements are logically equivalent (===) when their truth tables match in every row.
• P => Q === ~P OR Q, and De Morgan's laws flip both the parts and the connective under a negation.

Sources

1. OpenStax. (2023). 2.3 Constructing truth tables. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 2.4 Truth tables for the conditional and biconditional. In Contemporary mathematics. Rice University. openstax.org
3. OpenStax. (2023). 2.5 Equivalent statements. In Contemporary mathematics. Rice University. openstax.org
4. OpenStax. (2023). 2.6 De Morgan's laws. In Contemporary mathematics. Rice University. openstax.org
5. Hammack, R. (2018). Sections 2.5 to 2.6: Truth tables for statements; Logical equivalence. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
6. Weisstein, E. W. (n.d.). Truth table. MathWorld: A Wolfram web resource. mathworld.wolfram.com
7. Encyclopedia of Mathematics. (n.d.). De Morgan laws. European Mathematical Society. encyclopediaofmath.org

Propositional logic, from the last two lessons, handles fixed claims like "7 is prime." But it hits a wall the moment we want to say something about many objects at once, such as "every integer has a next one." That sentence talks about all integers together, and a single letter P cannot capture it. To go further we need predicate logic, which adds variables to our language. This is the step that lets us state real theorems.

Here is the everyday version of the idea. "She is a doctor" is not true or false until you know who "she" is. The sentence has a blank in it. Fill the blank with a specific person and it becomes a genuine claim. Predicates work exactly like this.

Predicates: statements with a slot

A predicate is a statement with one or more variables, whose truth depends on what you put in for those variables. We write something like P(x): "x > 0", read "P of x, meaning x is greater than 0." On its own P(x) has no truth value, because x is still a blank. But the moment you substitute a number, it becomes a real proposition.

• P(3) says "3 > 0," which is true.
• P(-1) says "-1 > 0," which is false.
• P(x) by itself is neither, until x is pinned down.

Every predicate carries a domain, also called the universe of discourse. The domain is the set of values the variable is allowed to take, such as the integers, or the real numbers, or the people in a room. Choosing the domain is part of stating the claim, not an afterthought, because the same predicate can be true over one domain and false over another. We will see that happen in a moment.

Key idea: a predicate is a sentence with a blank; fill the blank, or quantify it, and it gains a truth value.

Predicates with more than one slot

A predicate can have several blanks. For example, over the integers we might write Q(x, y): "x < y", read "Q of x and y, meaning x is less than y." This needs both slots filled to become a claim. So Q(2, 5) says "2 < 5," which is true, while Q(5, 2) says "5 < 2," which is false, and Q(4, 4) says "4 < 4," also false.

Multi-variable predicates are the natural home of relationships, like "divides," "is less than," or "is the parent of." They matter here for a specific reason: when we start attaching quantifiers, a two-slot predicate lets us build statements such as "for every x there is a larger y," which is where the interesting subtleties live. Hold that thought, because it returns at the end of the lesson.

The two quantifiers

A quantifier turns a predicate into a full proposition by saying how many elements of the domain make it true. There are two, and each has a symbol we will read aloud.

• The universal quantifier is written FORALL x, P(x), using the symbol ∀, read "for all x, P of x." It claims that P(x) is true for every x in the domain, with no exceptions.
• The existential quantifier is written EXISTS x, P(x), using the symbol ∃, read "there exists an x such that P of x." It claims that P(x) is true for at least one x in the domain.

A homely way to keep them apart: "for all" is a strong, sweeping claim about everyone, while "there exists" is a modest claim that at least one example is out there. The strong claim is harder to prove and easy to knock down; the modest claim is easy to prove and hard to knock down. We will make that precise next.

Let us look at concrete cases over the integers. The statement FORALL x, x^2 >= 0, read "for all x, x squared is at least 0," is true, because squaring any integer gives a value that is zero or positive. The statement EXISTS x, x^2 = 2, read "there exists an x with x squared equal to 2," is false, because no integer squares to 2.

Now watch the domain do its work. If we change the domain from the integers to the real numbers, then EXISTS x, x^2 = 2 becomes true, witnessed by the square root of 2, which is a real number. Same predicate, different domain, different truth value. This is why naming the domain is part of the claim.

How to prove or disprove each

The two quantifiers call for opposite proof strategies, and knowing which is which saves a lot of wasted effort.

• To prove FORALL x, P(x), you must handle every case at once with a general argument about an arbitrary x. Checking a few examples is not enough.
• To disprove FORALL x, P(x), a single counterexample suffices. One value of x where P(x) fails brings down the whole universal claim.
• To prove EXISTS x, P(x), you exhibit one witness, a specific x that makes P(x) true. That is the entire job.
• To disprove EXISTS x, P(x), you must rule out every element, showing P(x) fails for all of them.

Notice the pleasing symmetry. A universal claim is expensive to prove but cheap to refute; an existential claim is cheap to prove but expensive to refute. This is not a coincidence, and next lesson on negation will explain exactly why the two mirror each other.

Where people get stuck: a very common error is thinking that testing a universal statement on three or four values proves it. It does not. "Every odd number is prime" survives 3, 5, and 7, then dies at 9. One counterexample is a proof of falsehood, but a handful of successes is never a proof of truth for a universal claim.

Let us walk one disproof in slow motion. Claim: FORALL x, (x^2 > x) over the integers, read "for all x, x squared is greater than x."

1. To break a "for all," we hunt for a single x where the inside fails.
2. Try x = 1. Then x^2 = 1 and x = 1, so x^2 > x says "1 > 1," which is false.
3. We found one value where the predicate fails, so the universal claim is false.

That single value, x = 1, is the counterexample, and it is a complete disproof. Note that many other integers, like 5, do satisfy x^2 > x. Those successes are irrelevant once a counterexample exists, which is the whole lesson about how cheap it is to knock down a universal claim.

Key idea: disprove "for all" with one counterexample; prove "there exists" with one witness.

The shape most theorems take

It helps to know the pattern you will meet again and again. A great many theorems are a universal quantifier wrapped around a conditional: FORALL x, (P(x) => Q(x)), read "for all x, if P of x then Q of x." For instance, "for every integer n, if n is even then n squared is even" fits this mold, with P(x) being "x is even" and Q(x) being "x squared is even."

Reading a theorem in this form tells you how the proof will start. Because it is a "for all," you begin with an arbitrary x. Because the inside is a conditional, you assume P(x) and aim for Q(x). That single observation turns a mysterious statement into a clear plan of attack, and we will use it constantly once we reach direct proof in Module 4.

Nested quantifiers

Statements often stack two quantifiers, and here order matters in a way that changes meaning. Compare these two claims, both over the integers.

• FORALL x, EXISTS y, (x + y = 0), read "for all x, there exists a y such that x plus y equals 0."
• EXISTS y, FORALL x, (x + y = 0), read "there exists a y such that for all x, x plus y equals 0."

Let us reason through the first one carefully. It says: give me any integer x, and I can find an integer y that cancels it. Given x, choose y = -x. Then x + y = x + (-x) = 0. Since this works for whatever x you were handed, the statement is true. The key point is that y is chosen after x is known, so y is allowed to depend on x.

Now the second one. It says: there is one single integer y, fixed in advance, that cancels every x at the same time. That would need one number to be the negative of every integer simultaneously, which is impossible. So the second statement is false. The only change was swapping the two quantifiers, and it flipped a true statement into a false one.

An analogy makes the difference vivid. "Every person has a mother" is a FORALL x, EXISTS y claim, and it is true, with each person free to have a different mother. "There is one person who is the mother of everyone" is the EXISTS y, FORALL x version, and it is false. Same words, reordered, opposite truth.

Where people get stuck: the trap is reading a nested statement as if order did not matter. Always read left to right, and ask whether the inner witness is allowed to change as the outer variable changes. In FORALL x, EXISTS y it can; in EXISTS y, FORALL x it cannot, because the y is locked in first.

Key idea: in FORALL x, EXISTS y the y may depend on x; in EXISTS y, FORALL x a single y must work for all x.

Try it: which is true over the integers?

Decide the truth of FORALL x, EXISTS y, (y > x), and then of EXISTS y, FORALL x, (y > x).

The first says every integer has a larger one. Given x, take y = x + 1, which is larger, so it is true. The second says one fixed integer y is bigger than every integer, including itself, which is impossible, so it is false. That is the same pattern as before, and you handled it. Well done.

Recap

• A predicate P(x) is a statement with a variable slot and a stated domain; it gets a truth value once x is filled in or quantified.
• FORALL x, P(x) (∀, "for all") claims P holds for every element; EXISTS x, P(x) (∃, "there exists") claims it holds for at least one.
• Disprove a "for all" with one counterexample; prove a "there exists" with one witness.
• The domain is part of the claim: the same predicate can be true over the reals and false over the integers.
• With nested quantifiers, order matters: FORALL x, EXISTS y lets the witness depend on x, while EXISTS y, FORALL x demands one witness for all.

Sources

1. OpenStax. (2023). 2.1 Statements and quantifiers. In Contemporary mathematics. Rice University. openstax.org
2. Hammack, R. (2018). Section 2.7: Quantifiers. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
3. Levin, O. (n.d.). 3.1 Propositional logic. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
4. Encyclopedia of Mathematics. (n.d.). Quantifier. European Mathematical Society. encyclopediaofmath.org
5. Weisstein, E. W. (n.d.). Quantifier. MathWorld: A Wolfram web resource. mathworld.wolfram.com
6. Weisstein, E. W. (n.d.). Predicate. MathWorld: A Wolfram web resource. mathworld.wolfram.com
7. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu

Here is a skill that quietly decides whether many proofs succeed or stall: writing the exact negation of a statement. You need it to disprove a claim, and you need it even more to start a proof by contradiction, where the very first line is "suppose the opposite." If you negate the statement wrongly, the whole proof is built on sand. So we will slow down and get this exactly right.

Start with the everyday version, because the mistake is easy to make in plain English too. The opposite of "everyone passed the test" is not "everyone failed." It is "at least one person failed." Flipping a sweeping claim gives you a modest one, and flipping a modest claim gives you a sweeping one. That single idea is the heart of this lesson.

The negation rules

For quantified statements there are two clean rules. To negate a quantified statement, flip the quantifier and negate the predicate inside.

• ~(FORALL x, P(x)) === EXISTS x, ~P(x), read "not, for all x P of x, is the same as there exists an x with not P of x." In words: "not everything satisfies P" means "something fails P."
• ~(EXISTS x, P(x)) === FORALL x, ~P(x), read "not, there exists an x with P, is the same as for all x, not P." In words: "nothing satisfies P" means "everything fails P."

Both rules match common sense once you say them slowly. The claim "all swans are white" is false exactly when there exists a swan that is not white. You do not need every swan to be off-color; one gray swan is enough to sink it. Likewise, "some student failed" is false exactly when every student did not fail, that is, when all of them passed. Read each of those twice, matching the English to the symbols.

A short mantra captures both rules: flip the quantifier, negate the inside. A FORALL becomes an EXISTS, an EXISTS becomes a FORALL, and whatever predicate sat inside gets a "not" placed on it.

Key idea: negating a quantified statement flips FORALL to EXISTS (and back) and negates the predicate.

Why the two rules mirror each other

These rules are not arbitrary; they are De Morgan's laws in new clothing. Think about what a universal statement really claims over a domain like {1, 2, 3}. Saying FORALL x, P(x) is the same as saying P(1) AND P(2) AND P(3), a big "and" across all elements. By De Morgan, the negation of a big "and" is a big "or" of the negations: ~P(1) OR ~P(2) OR ~P(3), which is exactly EXISTS x, ~P(x).

The same story runs the other way. An existential statement EXISTS x, P(x) is a big "or," P(1) OR P(2) OR P(3), and negating a big "or" gives a big "and" of the negations, which is FORALL x, ~P(x). So the quantifier rules are the infinite-domain version of the two laws you already verified with a truth table. Seeing this connection means you have one idea to remember, not two.

Key idea: FORALL behaves like a big AND and EXISTS like a big OR, so De Morgan's laws produce the negation rules.

Let us make the mirror concrete with a tiny finite domain. Suppose the domain is just the three numbers 1, 2, and 3, and the predicate is "this number is even." The universal claim "all three are even" is plainly false, because 1 and 3 are odd. Its negation should be true, and the rule delivers "there exists one that is not even," which is satisfied by 1. So the negation came out true, matching the fact that the original was false. Working a rule on a small, checkable case like this is one of the best ways to trust it before using it on something abstract.

Negating nested quantifiers

When several quantifiers stack up, apply the rule repeatedly, moving the negation inward one quantifier at a time and flipping each as it passes. Every FORALL turns into EXISTS, every EXISTS turns into FORALL, and the innermost predicate gets negated last of all.

Worked example. Let us negate FORALL x, EXISTS y, (x + y = 0), one small move at a time.

1. Start by pushing the negation past the outer quantifier. The FORALL x flips to EXISTS x, and the "not" moves inside: we get EXISTS x, ~(EXISTS y, (x + y = 0)).
2. Now push the negation past the next quantifier. The EXISTS y flips to FORALL y, and the "not" moves further in: EXISTS x, FORALL y, ~(x + y = 0).
3. Finally negate the predicate itself. The opposite of x + y = 0 is x + y != 0, read "x plus y is not equal to 0."

The finished negation is EXISTS x, FORALL y, (x + y != 0), read "there exists an x such that for all y, x plus y is not 0." In words, some x can never be cancelled by any y. Over the integers the original statement was true, so its negation should be false, and indeed no such stubborn x exists. That truth-value check is a good habit: a correct negation always has the opposite truth value from the original.

Where people get stuck: the frequent slip is flipping only the first quantifier and leaving the rest alone, giving something like EXISTS x, EXISTS y, ~(...). Every quantifier the negation passes must flip. Move the "not" inward step by step, changing each quantifier as you go, and the errors disappear.

Negating a conditional inside a quantifier

Many theorems have the form FORALL x, (P(x) => Q(x)), so it pays to negate that shape fluently. Recall from Module 1 that a conditional is false only when its hypothesis holds and its conclusion fails, which we wrote as ~(P => Q) === P AND ~Q. Combining that with the quantifier rule gives a formula worth memorizing.

~(FORALL x, (P(x) => Q(x))) === EXISTS x, (P(x) AND ~Q(x))

Read the right side aloud: "there exists an x such that P of x holds and Q of x fails." That is precisely the description of a counterexample. To break "every x with property P also has property Q," you produce one x that has P but lacks Q.

Try it on a concrete claim: "every prime is odd." In symbols this is FORALL x, (prime(x) => odd(x)). Its negation is EXISTS x, (prime(x) AND ~odd(x)), that is, "there is a prime that is not odd." And there is one: x = 2 is prime and even. So the original claim is false, and 2 is the counterexample the negation told us to look for.

This exact pattern is doing double duty. It is how you disprove a false universal theorem, and it is how you write the opening line "suppose not" for a proof by contradiction. Getting the negation right is often half the battle in a proof, which is why we practiced it so carefully.

Where people get stuck: when negating P(x) => Q(x), many readers write another conditional, like P(x) => ~Q(x). That is not the negation. The negation of a conditional is an "and," P(x) AND ~Q(x): the hypothesis still holds, but now the conclusion fails. Keep the hypothesis true and negate only the conclusion, joined by "and."

When the inside is an "and" or an "or"

Sometimes the predicate inside a quantifier is itself a compound statement. Then you flip the quantifier as usual, and use plain De Morgan on the inside. For example, negating FORALL x, (P(x) AND Q(x)) gives EXISTS x, (~P(x) OR ~Q(x)): some x fails P or fails Q. Negating EXISTS x, (P(x) OR Q(x)) gives FORALL x, (~P(x) AND ~Q(x)): every x fails both. The two skills, flipping quantifiers and applying De Morgan to connectives, simply compose, one after the other. Work from the outside in, handling one layer at a time, and even a long statement negates without trouble.

Negation as the opening move of a proof

Let us see negation earn its keep at the start of a contradiction proof. Consider the claim "there is no largest integer." To prove it by contradiction, we assume the opposite and hunt for an absurdity, so the first job is to state that opposite precisely.

The claim "there is no largest integer" can be read as "it is not the case that some integer is larger than or equal to every integer." Negating it removes the outer "not," so the assumption we work from is "there exists an integer that is larger than or equal to every integer," in other words, a genuine largest integer, call it N. Notice how the negation handed us a concrete object, N, to grab onto.

From there the contradiction is quick: the integer N + 1 is larger than N, which contradicts N being the largest. So the assumption fails, and the original claim stands. We will study this technique in full in Module 4, but the point for now is where it began. The whole proof only got off the ground because we negated the statement correctly and turned a "there is no" into a workable "there is."

Where people get stuck: phrases like "there is no" and "none" already carry a hidden negation. When you negate them, two negatives can cancel. "There is no largest integer," once negated, becomes the positive "there is a largest integer." Watch for these buried "nots" so you do not accidentally negate twice or not at all.

Try it: write the negation

Negate the statement "for all real numbers x, if x > 0 then x^2 > 0."

Follow the shape. Flip the FORALL to EXISTS, keep the hypothesis, and negate the conclusion with an "and." The negation is "there exists a real number x such that x > 0 and x^2 <= 0." As a truth-value check, the original is true, so this negation should be false, and indeed no positive real has a nonpositive square. Nicely handled.

Recap

• To negate a quantified statement, flip the quantifier and negate the inside: ~(FORALL x, P(x)) === EXISTS x, ~P(x) and ~(EXISTS x, P(x)) === FORALL x, ~P(x).
• These rules are De Morgan's laws, since FORALL acts like a big AND and EXISTS like a big OR.
• For nested quantifiers, push the negation inward one step at a time, flipping every quantifier it passes.
• The negation of FORALL x, (P(x) => Q(x)) is EXISTS x, (P(x) AND ~Q(x)), which describes a counterexample.
• A correct negation always has the opposite truth value from the original, so checking it on a small example is a reliable way to catch mistakes before you rely on it.

Sources

1. Hammack, R. (2018). Section 2.10: Negating statements. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. OpenStax. (2023). 2.6 De Morgan's laws. In Contemporary mathematics. Rice University. openstax.org
3. Encyclopedia of Mathematics. (n.d.). Negation. European Mathematical Society. encyclopediaofmath.org
4. Encyclopedia of Mathematics. (n.d.). Quantifier. European Mathematical Society. encyclopediaofmath.org
5. Weisstein, E. W. (n.d.). de Morgan's laws. MathWorld: A Wolfram web resource. mathworld.wolfram.com
6. Levin, O. (n.d.). 3.1 Propositional logic. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
7. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof. LibreTexts. math.libretexts.org

From here on, almost everything in mathematics is phrased in the language of sets. Functions, relations, number systems, even proofs themselves are described with sets. The good news is that the core idea is something you have used since childhood, whenever you sorted things into groups. This lesson gives that everyday idea a precise vocabulary so we can prove things about it.

A set is an unordered collection of distinct objects, and those objects are called its elements or members. Picture a bag, or a club roster: what matters is who is in it, not the order you list them and not how many times you say a name. We write x IN A, read "x is an element of A" or "x is in A," to say x belongs to the set A, and x NOT IN A, read "x is not in A," when it does not.

Two features define a set, and both come straight from the bag picture. Order does not matter, and repetition does not count. So {1, 2, 3}, {3, 2, 1}, and {1, 1, 2, 3} are all the very same set. Listing an element twice adds nothing, and shuffling the order changes nothing. Read that once more, because it catches people off guard the first time.

Key idea: a set is a collection where order and repetition are ignored; only membership matters.

Two ways to describe a set

There are two standard ways to write down a set, and it is worth being comfortable with both.

• Roster notation simply lists the elements inside braces, as in A = {2, 4, 6, 8}. This is clear and direct when the set is small.
• Set-builder notation states a rule instead of a list, as in A = {x IN Z : x is even and 0 < x < 10}. Read this aloud as "the set of integers x such that x is even and x is between 0 and 10." The colon (some books use a vertical bar) is read "such that."

Both descriptions above name the exact same set, {2, 4, 6, 8}. Roster is handy when you can list everything; set-builder shines when the set is large or infinite, where listing is impossible. For instance, "all even integers" has no finite list, but the rule {x IN Z : x is even} pins it down perfectly.

A few sets appear so often that they get reserved names, and you will see them everywhere.

• N is the natural numbers, read "N," the counting numbers 1, 2, 3, and so on.
• Z is the integers, read "Z," which includes negatives, zero, and positives.
• Q is the rationals, read "Q," all fractions of integers.
• R is the real numbers, read "R," the full number line.

These four named sets nest neatly inside one another: every natural number is an integer, every integer is a rational (write n as n/1), and every rational is a real. In subset language that chain reads N SUBSET Z SUBSET Q SUBSET R. Picturing that nesting helps you keep the number systems straight, and it previews the surprising fact, coming in a later lesson, that R is somehow much larger than the others despite all of them being infinite.

Set-builder notation can also transform elements, not just filter them. For example, {2n : n IN N}, read "the set of 2n as n ranges over the naturals," is the set of positive even numbers, because it takes each natural number and doubles it. The part before the colon says how to build each element; the part after says where the input comes from. This build-and-filter flexibility is what makes set-builder notation so powerful for describing large sets.

Key idea: roster notation lists elements; set-builder notation gives a membership rule and reads "the set of x such that ...".

Subsets and equality

The most important relationship between two sets is the subset relationship. We say A is a subset of B, written A SUBSET B and read "A is a subset of B," when every element of A is also an element of B. In the language of last week's quantifiers, this is exactly

A SUBSET B means FORALL x, (x IN A => x IN B).

Read that as "for all x, if x is in A then x is in B." It is a beautiful link: the subset idea is just a universal conditional about membership. If, on top of that, B has at least one element that A lacks, we call A a proper subset of B. For example, {1, 2} is a proper subset of {1, 2, 3}, since 3 is in the second but not the first.

Now we reach the single most useful proof strategy of this whole module. Two sets are equal exactly when they contain the same elements, and that condition splits neatly into two subset checks.

A = B if and only if A SUBSET B and B SUBSET A.

To prove two sets are equal, then, you prove containment in both directions: first show every element of A lies in B, then show every element of B lies in A. This is called the double containment method, and it appears constantly, so it is worth naming and remembering now. We will use it heavily in the next lesson to prove set identities.

Key idea: A SUBSET B is a universal conditional about membership, and A = B means containment holds both ways.

A first tiny proof about subsets

Let us use the definition to prove one containment, so the abstract rule becomes a concrete habit. Let A be the set of multiples of 4 and B the set of even numbers. We will show A SUBSET B.

The definition tells us what to do: take an arbitrary element of A and show it must be in B. Here is the argument in small steps, each with its reason.

1. Let x be any element of A. (We start with an arbitrary member, because the definition is a "for all.")
2. Since x is a multiple of 4, we can write x = 4k for some integer k. (This is what "multiple of 4" means.)
3. Rewrite 4k as 2(2k). (Just factoring out a 2.)
4. Since 2k is an integer, x = 2(2k) has the form 2 times an integer, so x is even. (This is the definition of even.)
5. Therefore x IN B. Because x was arbitrary, every element of A lies in B, so A SUBSET B.

That is a complete little proof, and notice its shape: start with an arbitrary element, unpack a definition, do a small computation, and land in the target set. You just wrote the skeleton that every subset proof follows. Well done.

Where people get stuck

Two confusions trip up nearly everyone at the start, and naming them now prevents a lot of grief later.

First, do not mix up an element with a one-element set. The number 3 and the set {3} are different things: 3 is a number, while {3} is a box containing that number. So 3 IN {3} is true, but 3 = {3} is not. The box is not the same as what is inside it.

Second, do not confuse IN with SUBSET. Membership IN relates an element to a set, while SUBSET relates a set to a set. For the set A = {1, 2}, it is correct to write 1 IN A and also {1} SUBSET A, but writing 1 SUBSET A or {1} IN A is a category error. Ask yourself, "is the left side an element, or a whole set?" and pick the matching symbol.

The empty set and power sets

The empty set, written {} or with a special slashed-circle symbol, is the set with no elements at all. It sounds like a technicality, yet it plays a starring role. Here is a fact that surprises many readers: the empty set is a subset of every set.

Why is that true? Recall {} SUBSET B means FORALL x, (x IN {} => x IN B). But there is no x in the empty set to test, so the conditional is vacuously true for every x, exactly the vacuous-truth idea from Module 1. With no possible counterexample, the subset claim holds automatically. It is common to find this argument slippery the first time; the anchor is that a "for all" over an empty collection is always true, because nothing can violate it.

The power set of A, written P(A) and read "the power set of A," is the set of all subsets of A. It is a set whose elements are themselves sets. Let us build one concretely. If A = {1, 2}, then its subsets are the empty set, the two singletons, and A itself:

P(A) = { {}, {1}, {2}, {1, 2} }.

Count them: there are four. That is no accident. A finite set with n elements has exactly 2^n subsets, because building a subset means making an independent in-or-out choice for each of the n elements, and 2 choices repeated n times gives 2^n. So |P(A)| = 2^n, where the bars mean "the size of." For our two-element set, 2^2 = 4, matching the list.

This doubling returns when we count in Module 7, tying set theory directly to combinatorics. The same in-or-out reasoning that counts subsets will count many other things too.

Key idea: the empty set is a subset of every set (vacuously), and a set with n elements has 2^n subsets.

Try it: list the subsets

List all subsets of A = {a, b, c} and count them against the formula.

Go in order of size. The empty set: {}. The singletons: {a}, {b}, {c}. The pairs: {a, b}, {a, c}, {b, c}. The whole set: {a, b, c}. That is 8 subsets, and the formula predicts 2^3 = 8. They agree, so you know you did not miss any. Nicely organized.

Recap

• A set is an unordered collection of distinct elements; {1, 1, 2} and {2, 1} both mean {1, 2}.
• Describe sets by roster (a list) or set-builder (a rule, read "the set of x such that ...").
• A SUBSET B means FORALL x, (x IN A => x IN B), and A = B means each is a subset of the other (double containment).
• Keep IN (element to set) separate from SUBSET (set to set), and 3 separate from {3}.
• The empty set is a subset of every set, and the power set of an n-element set has 2^n members.

Sources

1. OpenStax. (2023). 1.1 Basic set concepts. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 1.2 Subsets. In Contemporary mathematics. Rice University. openstax.org
3. Hammack, R. (2018). Chapter 1: Sets. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
4. Levin, O. (n.d.). 0.3 Sets. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
5. Weisstein, E. W. (n.d.). Power set. MathWorld: A Wolfram web resource. mathworld.wolfram.com
6. Encyclopedia of Mathematics. (n.d.). Set theory. European Mathematical Society. encyclopediaofmath.org
7. Levin, O. (n.d.). 0.3: Sets. In Discrete mathematics. LibreTexts. math.libretexts.org

Now that we can describe sets, we can combine them, the way we combine numbers with plus and times. Sets have their own operations: union, intersection, difference, and complement. The lovely part is that each one is built from a logical connective you already know. Union rides on "or," intersection on "and," and complement on "not." So this lesson is really Module 1 wearing a set-theory costume.

Before the operations, we fix a universal set U, read "U," which contains everything currently under discussion. If we are talking about whole numbers, U might be all integers. Naming U matters most for the complement, as we will see, because "everything outside A" only makes sense once we agree on what "everything" is.

The core operations

Here are the four operations, each with its definition written in set-builder notation, so you can see the connective inside.

• Union A UNION B = {x : x IN A OR x IN B}, read "A union B," is everything in either set (or both).
• Intersection A INTERSECT B = {x : x IN A AND x IN B}, read "A intersect B," is everything in both sets at once.
• Difference A - B = {x : x IN A AND x NOT IN B}, read "A minus B," is everything in A that is not in B.
• Complement A^c = {x IN U : x NOT IN A}, read "A complement," is everything in the universe outside A.

Let us make these solid with numbers. Take A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Then A UNION B = {1, 2, 3, 4, 5, 6}, pooling both lists without repeats. The intersection A INTERSECT B = {3, 4}, the elements they share. The difference A - B = {1, 2}, the parts of A that B does not contain. Try covering the answers and recomputing one; matching the connective to the operation is the whole skill.

Notice how union rides on OR, intersection on AND, and complement on negation. This is exactly why the logic of Modules 1 and 2 transfers straight to sets. In particular, De Morgan's laws reappear here as set identities: (A UNION B)^c = A^c INTERSECT B^c and (A INTERSECT B)^c = A^c UNION B^c. The negation flips the connective, just as before, only now "not" is "complement," "and" is "intersect," and "or" is "union."

Reading a Venn diagram

The picture above is a Venn diagram, a simple map of how two sets sit inside the universe. The rectangle is the universe U. The left circle is A, the right circle is B, and the lens-shaped region where they overlap is the intersection A INTERSECT B. Everything inside either circle is the union. The part of A outside the overlap is A - B, and everything outside both circles, but still in the rectangle, is (A UNION B)^c.

Venn diagrams are more than decoration. When an identity looks doubtful, shading the regions on each side and comparing is a fast way to build confidence before you write a formal proof. The picture does not replace a proof, but it often shows you why the identity should be true, which makes the proof easier to find.

Here is how to use one in practice. To test (A UNION B)^c = A^c INTERSECT B^c, shade the left side by first shading the union of the two circles and then taking everything outside it. Now shade the right side by marking the outside of A and the outside of B and keeping only what both shadings share. You will find the same outer region highlighted both times. That visual match is a strong hint, and the formal element-chasing proof then confirms it beyond doubt.

Key idea: union is "or," intersection is "and," complement is "not," and a Venn diagram maps those regions.

Proving a set identity

A set identity is an equation between two set expressions that holds for all sets. We prove one with the double containment method from last lesson: show each side is a subset of the other, translating membership into logic at every step. Here is a complete proof of one distributive law, taken slowly.

Theorem. For all sets, A INTERSECT (B UNION C) = (A INTERSECT B) UNION (A INTERSECT C).

Proof. We chase an arbitrary element through the definitions. Each step is an "if and only if," which lets the same chain prove both containment directions at once.

1. Let x IN A INTERSECT (B UNION C). By the definition of intersection, this means x IN A and x IN B UNION C. (We just unpacked "intersect" into "and.")
2. By the definition of union, x IN B UNION C means x IN B or x IN C. So altogether we have x IN A and (x IN B or x IN C). (Unpacked "union" into "or.")
3. Now apply the distributive law of logic, the one about "and" over "or." The statement "A and (B or C)" is equivalent to "(A and B) or (A and C)." So our condition becomes (x IN A and x IN B) or (x IN A and x IN C). (This is the key logical move.)
4. Re-fold the definitions. The first group says x IN A INTERSECT B, the second says x IN A INTERSECT C, joined by "or," which means x IN (A INTERSECT B) UNION (A INTERSECT C). (We packed "and" back into "intersect" and "or" back into "union.")

Every step was reversible, an "if and only if," so the argument runs equally in both directions. That proves each side is a subset of the other, and therefore the two sets are equal. QED.

Read back over those four steps and notice the rhythm: unpack the set operations into logic, use a law of logic you already proved, then repack into set operations. That is the entire method. A set identity is really a logical equivalence about membership in disguise, so once you translate IN, UNION, and INTERSECT into OR and AND, the laws of logic finish the job for you. That is a genuinely powerful realization, and you just used it.

A second proof: De Morgan for sets

Let us prove one of the De Morgan identities the same way, so the pattern really sinks in. We will show that the complement of a union is the intersection of the complements.

Theorem. For all sets inside a universe U, (A UNION B)^c = A^c INTERSECT B^c.

Proof. We again chase an arbitrary element, and every line is an "if and only if."

1. Let x IN (A UNION B)^c. By the definition of complement, this means x is in U but x NOT IN A UNION B. (Unpacked "complement" into "not in.")
2. Saying x NOT IN A UNION B means it is not true that x IN A or x IN B. (Unpacked "union," keeping the outer "not.")
3. By De Morgan's law of logic, "not (in A or in B)" becomes "not in A and not in B." So x NOT IN A and x NOT IN B. (This is the key logical step, the plain De Morgan you verified with a truth table.)
4. Re-fold the definitions. "Not in A" means x IN A^c, and "not in B" means x IN B^c, joined by "and," which is x IN A^c INTERSECT B^c. (Packed "not in" back into complement, "and" back into intersect.)

Since every step reverses, both containments hold, and the two sets are equal. QED. Notice it was the identical rhythm as before, only the logic law in the middle changed from the distributive law to De Morgan. Once you own the rhythm, a whole family of set identities falls to the same three moves.

How the operations relate in size

A few containment facts hold no matter which sets you pick, and they are worth carrying around as intuition. The intersection is the small, cautious set: A INTERSECT B sits inside both A and B, because an element of the intersection must belong to each. The union is the big, generous set: both A and B sit inside A UNION B, because anything in either set is in the union.

Put together, these give the chain A INTERSECT B SUBSET A SUBSET A UNION B, and the same with B in the middle. Whenever an answer you compute seems to violate one of these, that is a signal to recheck, since the intersection can never be bigger than either set and the union can never be smaller. Simple sanity checks like this catch a surprising number of slips.

Where people get stuck

Three small errors are worth guarding against. First, set difference is not symmetric: A - B and B - A are usually different. With our example sets, A - B = {1, 2} but B - A = {5, 6}. Order matters for the minus sign.

Second, the complement depends on the universe. The complement of the even numbers is "all odd numbers" only if the universe is the integers; inside a different universe you get a different complement. Always know what U is before you take a complement.

Third, when proving an identity, do not stop after one direction unless every step was reversible. If your steps are one-way implications rather than "if and only if," you must argue both containments separately, once for SUBSET each way.

Try it: compute the three operations

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6} again. Find A UNION B, A INTERSECT B, and A - B.

The union pools everything: {1, 2, 3, 4, 5, 6}. The intersection keeps the shared elements: {3, 4}. The difference keeps A's elements that are missing from B: {1, 2}. If those three matched what you wrote, you have the operations down cold. Nice work.

Recap

• The four operations are union (or), intersection (and), difference (in A but not B), and complement (outside A, within U).
• A Venn diagram maps these as regions of two circles inside the universe rectangle.
• De Morgan's laws hold for sets: (A UNION B)^c = A^c INTERSECT B^c and (A INTERSECT B)^c = A^c UNION B^c.
• Prove a set identity by chasing an element through the definitions, using logic laws, and repacking; reversible steps prove both containments at once.
• Watch out: difference is not symmetric, and complement depends on the chosen universe U.

Sources

1. OpenStax. (2023). 1.3 Understanding Venn diagrams. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 1.4 Set operations with two sets. In Contemporary mathematics. Rice University. openstax.org
3. OpenStax. (2023). 1.5 Set operations with three sets. In Contemporary mathematics. Rice University. openstax.org
4. Hammack, R. (2018). Chapter 8: Proofs involving sets. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
5. Weisstein, E. W. (n.d.). Union. MathWorld: A Wolfram web resource. mathworld.wolfram.com
6. Encyclopedia of Mathematics. (n.d.). De Morgan laws. European Mathematical Society. encyclopediaofmath.org
7. MacTutor History of Mathematics Archive. (n.d.). The beginnings of set theory. University of St Andrews. mathshistory.st-andrews.ac.uk

This is the lesson the whole course has been pointing toward. We are going to write real proofs. A proof is a complete, convincing chain of reasoning that establishes a statement beyond any doubt, with every step justified. It is different from computing an answer, and it is normal for that difference to feel unfamiliar at first. We will build the skill one small move at a time, and the earlier lessons on logic, quantifiers, and definitions are exactly the toolkit we now put to work.

Most theorems are conditionals wrapped in a "for all," like FORALL x, (P(x) => Q(x)). A direct proof takes the most straightforward route through such a statement: assume the hypothesis P(x) for an arbitrary x, then use definitions, algebra, and facts you already know to deduce the conclusion Q(x).

What a direct proof is

Let us name the plan clearly, because having a plan removes most of the mystery.

1. Take an arbitrary x from the domain. "Arbitrary" means you assume nothing special about it, so whatever you prove will hold for every x at once.
2. Assume the hypothesis P(x) is true. This is allowed, because a conditional only makes a claim when the hypothesis holds.
3. Reason step by step until you reach the conclusion Q(x).

Why does proving it for one arbitrary x prove it for all of them? Because you never used any special feature of x, so the identical argument would work for any other value. That is the quiet power of the word "arbitrary." And if P(x) happens to be false for some x, the conditional is vacuously true there, so we never need to handle that case; assuming P covers everything that matters.

An analogy helps. Suppose you want to show that every card in a sealed deck is blue, but you may only pick one card, chosen with your eyes closed. If your argument for that one blindly chosen card never relies on which card it happens to be, then the same argument would have worked for any card, so all of them must be blue. Mathematical "arbitrary" is that blindfolded choice: you reason about one element while using nothing special about it, and the conclusion then covers the entire domain.

Key idea: a direct proof assumes the hypothesis for an arbitrary element and deduces the conclusion, which settles all cases at once.

The definitions we will use

Proofs live or die on precise definitions, so commit these three to memory. Each says a number has a certain shape, guaranteed by a hidden witness.

• An integer n is even if n = 2k for some integer k.
• An integer n is odd if n = 2k + 1 for some integer k.
• An integer a divides b, written a | b and read "a divides b," if b = a*m for some integer m.

The phrase "for some integer k" is doing real work in each definition. It promises a specific integer exists, and it lets you name that integer and put it into an equation. That named integer is your witness, the concrete handle you manipulate through the proof.

Reading a definition as a tool

Every definition can be used in two directions, and knowing which direction you are in keeps a proof on track.

When a definition sits in your hypothesis, you unpack it. "Assume n is odd" becomes "so n = 2k + 1 for some integer k," giving you an equation to work with. When a definition is your goal, you aim to reach its shape. To prove "m is even," your target is to write m in the form 2 times (some integer). So the skill is: unpack the definition you are given, and steer toward the form of the definition you want. Keep those two roles straight and a proof almost writes itself.

Key idea: unpack a definition in the hypothesis into a named witness; reach the definition's form to prove the conclusion.

Worked example one

Theorem. For every integer n, if n is odd then n^2 is odd.

Proof. Let us go one tiny step at a time, with a reason for each.

1. Let n be an arbitrary integer, and assume n is odd. (Setup: arbitrary element, assume the hypothesis.)
2. By the definition of odd, n = 2k + 1 for some integer k. (Unpacked the hypothesis into a witness k.)
3. Square both sides: n^2 = (2k + 1)^2. (Just applying the same operation to each side.)
4. Expand the right side: (2k + 1)^2 = 4k^2 + 4k + 1. (Ordinary algebra.)
5. Group to expose a factor of 2: 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. (Factored 2 out of the first two terms.)
6. Let m = 2k^2 + 2k. This is an integer, because it is built from the integer k by multiplying and adding. (Naming a new witness.)
7. Then n^2 = 2m + 1, which is exactly the definition of an odd number. So n^2 is odd. (Reached the target form.)

QED. Read the proof back and notice we reached the form 2m + 1, the shape of "odd," using only the assumption and algebra. That is a complete, honest argument. You just read a real proof, start to finish.

Worked example two

Theorem. The sum of two even integers is even.

Proof. Again, small steps with reasons.

1. Let a and b be even integers. (Arbitrary elements, hypothesis assumed.)
2. By the definition of even, a = 2j for some integer j, and b = 2k for some integer k. (Unpacked each into its own witness. Using different letters here matters.)
3. Add them: a + b = 2j + 2k. (Substitution.)
4. Factor out the 2: 2j + 2k = 2(j + k). (Distributive law.)
5. Since j + k is an integer, a + b has the form 2 times (an integer), so a + b is even. (Reached the target form.)

QED. Two proofs, same rhythm. That repetition is the point, and it is what makes proof-writing learnable.

A third example: the product of two odd integers

Theorem. If a and b are odd integers, then their product a*b is odd.

Proof. We follow the same template once more, so it becomes second nature.

1. Assume a and b are odd. (Arbitrary elements, hypothesis assumed.)
2. By the definition of odd, a = 2j + 1 and b = 2k + 1 for some integers j and k. (Unpacked each into its own witness.)
3. Multiply: a*b = (2j + 1)(2k + 1). (Substitution.)
4. Expand the product: (2j + 1)(2k + 1) = 4jk + 2j + 2k + 1. (Ordinary algebra.)
5. Group to expose a factor of 2: 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1. (Factored 2 from the first three terms.)
6. Since 2jk + j + k is an integer, a*b has the form 2 times (an integer) plus 1, so a*b is odd. (Reached the target form.)

QED. Three proofs now, and every one walked the same path. That is genuinely encouraging, because it means the technique, not luck, is carrying you.

The shape every direct proof shares

Step back and look at the skeleton both proofs shared, because it is a template you can reuse forever: state the assumption for an arbitrary element, unpack each definition into an equation with a named witness, do the algebra to reach the target form, then cite the definition of the conclusion to finish. When you can drive straight from hypothesis to conclusion like this, a direct proof is always the first technique to try.

Where people get stuck

A few habits cause most early trouble. First, reusing the same letter for two different witnesses. In example two we wrote a = 2j and b = 2k, not a = 2k and b = 2k, because a and b need not share the same witness. Give each its own letter.

Second, accidentally assuming the conclusion. Your goal is to derive Q, not to start by supposing it. If you catch yourself writing the conclusion as an early line, back up.

Third, checking a few numbers and calling it a proof. Testing n = 3, 5, 7 is fine for building intuition, but a universal statement needs a general argument about an arbitrary n, exactly as we did.

Writing proofs a reader can follow

A proof is a piece of writing meant to convince a human reader, so how you word it counts almost as much as the logic. A few habits make your proofs clear and professional, and they are easy to adopt from the start.

Write in complete sentences, not a column of loose equations. Small connective words carry the logic and should be visible. Begin by introducing your objects with "Let," as in "Let n be an arbitrary integer." Signal each consequence with words like "Then," "So," or "It follows that." Mark the final step with "Therefore," and close with "QED" or a small box so the reader knows the argument is finished.

Say your assumptions out loud rather than leaving them implicit. If you are proving a conditional, the first sentence should name the hypothesis you are assuming. If you introduce a witness, announce it: "since n is even, there is an integer k with n = 2k." A reader should be able to follow your reasoning without guessing what you had in mind, and every claim should rest on a stated definition or an earlier line. Proofs written this way are not only correct, they are pleasant to read, and that clarity is a skill worth building deliberately.

Try it: prove a small claim

Prove that if n is even, then n^2 is even.

Follow the template. Assume n is even, so n = 2k for some integer k. Square it: n^2 = (2k)^2 = 4k^2. Factor out a 2: 4k^2 = 2(2k^2). Since 2k^2 is an integer, n^2 has the form 2 times an integer, so n^2 is even. That is a full proof, and you built it from the same four moves. Nicely done.

Recap

• A direct proof of P => Q assumes P for an arbitrary element and deduces Q.
• Know the definitions cold: even is 2k, odd is 2k + 1, and a | b means b = a*m for some integer.
• Unpack a hypothesis definition into a named witness; steer toward the target definition's form to finish.
• The template: assume, unpack with witnesses, do algebra to the target form, cite the definition of the conclusion.
• Give each witness its own letter, never assume the conclusion, and argue for an arbitrary element rather than a few examples.

Sources

1. Hammack, R. (2018). Chapter 4: Direct proof. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Levin, O. (n.d.). 3.2 Proofs. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
3. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu
4. Weber, K. (2001). Student difficulty in constructing proofs: The need for strategic knowledge. Educational Studies in Mathematics, 48(1), 101-119. doi.org/10.1023/A:1015535614355
5. Mason, J., & Pimm, D. (1984). Generic examples: Seeing the general in the particular. Educational Studies in Mathematics, 15(3), 277-289. doi.org/10.1007/BF00312078
6. Encyclopedia of Mathematics. (n.d.). Proof theory. European Mathematical Society. encyclopediaofmath.org
7. Levin, O. (n.d.). 3: Symbolic logic and proofs. In Discrete mathematics. LibreTexts. math.libretexts.org

Direct proof is your first tool, but sometimes the hypothesis you are handed is awkward to work with, while the negation of the conclusion is easy. In exactly those moments, there is a slicker route: prove the contrapositive. This lesson shows you what that means, why it is allowed, and how to spot the situations where it turns a hard proof into an easy one.

Recall a fact from Module 1, one we flagged as important: a conditional and its contrapositive are logically equivalent.

(P => Q) === (~Q => ~P)

Read the right side aloud: "if not Q, then not P." Because the two statements are true in exactly the same rows of a truth table, proving ~Q => ~P proves the original P => Q just as surely. A proof by contrapositive does this: it assumes ~Q, the conclusion is false, and derives ~P, the hypothesis is false, using an ordinary direct-proof structure on the flipped statement.

Why the contrapositive works

It is worth being sure about why this is legitimate, so you can use it with full confidence. Two logically equivalent statements have identical truth tables, meaning they agree in every possible case. If you establish that one of them is always true, you have automatically established the other, because there is no situation where they could differ.

The contrapositive is not a trick or an approximation. It is the very same claim, rephrased. Think of it like proving "all my houseplants are alive" by proving "anything dead in my home is not one of my houseplants." Same content, viewed from the other end. So when the flipped version is easier to argue, you lose nothing by switching to it.

Key idea: a conditional and its contrapositive have identical truth tables, so proving one proves the other.

Building the contrapositive of a statement

Before proving anything, you need to form the contrapositive correctly, so let us practice that move on plain-English sentences. The recipe is fixed: swap the hypothesis and conclusion, and negate both.

Take "if it is a weekday, then the library is open." The hypothesis is "it is a weekday" and the conclusion is "the library is open." Negate each to get "it is not a weekday" and "the library is not open," then swap them into the contrapositive: "if the library is not open, then it is not a weekday." Read the original and the contrapositive back to back; they make the same promise from opposite ends.

One more, closer to mathematics. Take "if a number is a multiple of 6, then it is even." The contrapositive negates and swaps to "if a number is not even, then it is not a multiple of 6." Both are true, which is no coincidence, since a statement and its contrapositive always share the same truth value. Getting comfortable forming the contrapositive on easy sentences pays off when the mathematical ones arrive, because the mechanical step is identical.

Where people get stuck: a common early error is to negate without swapping, which produces the inverse ~P => ~Q instead of the contrapositive. Both steps are required: negate both parts, and reverse their order.

When to reach for it

The contrapositive shines when the conclusion Q is a clean, positive statement that becomes concrete once you negate it. A classic signal is a conclusion like "n is even" or "n is odd." Negating such a conclusion hands you an equation to manipulate, like n = 2k or n = 2k + 1, which is exactly the kind of thing a direct proof loves.

Meanwhile, the original hypothesis in these problems is often something like "n^2 is even," which is harder to use directly because unpacking it forces you to reason about a square, and taking a square root can leave the integers. When the hypothesis is stubborn but the negated conclusion is friendly, the contrapositive is the tool to pick up.

The same signal appears with divisibility conclusions. If a theorem concludes "n is not divisible by 3," negating that gives the cleaner "n is divisible by 3," which unpacks to n = 3k and gives you an equation to compute with. As a rule of thumb, whenever the conclusion is a "not" statement or a hard-to-use property, negating it during a contrapositive proof often turns it into a concrete, workable equation. Learning to read that signal is half of choosing the right technique.

Worked example

Theorem. For every integer n, if n^2 is even then n is even.

Let us first see why a direct proof is awkward. A direct proof would start from "n^2 is even," giving n^2 = 2k, and then try to conclude something about n. But solving for n means taking a square root, which does not stay inside the integers cleanly, so the argument stalls. This is our signal to flip to the contrapositive.

Contrapositive. If n is not even, that is, n is odd, then n^2 is not even, that is, n^2 is odd. We prove this instead, using a plain direct proof.

1. Assume n is odd. (This is ~Q, the negated conclusion, now our hypothesis.)
2. By the definition of odd, n = 2k + 1 for some integer k. (Unpacked into a witness.)
3. Square both sides: n^2 = (2k + 1)^2 = 4k^2 + 4k + 1. (Algebra.)
4. Group to expose a factor of 2: 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. (Factored out 2.)
5. Since 2k^2 + 2k is an integer, n^2 has the form 2m + 1, so n^2 is odd. (Reached the target form, which is ~P.)

We have shown that n odd forces n^2 odd, which is exactly the contrapositive of the theorem. Because a conditional is equivalent to its contrapositive, the original statement is proved: if n^2 is even then n is even. QED. Look at how smooth that was compared with the stalled direct attempt. That is the payoff of choosing the right technique.

A second worked example

Theorem. For every integer n, if 5n + 3 is even then n is odd.

The conclusion is "n is odd," a perfect candidate to negate, so we reach for the contrapositive again.

Contrapositive. If n is not odd, that is, n is even, then 5n + 3 is not even, that is, 5n + 3 is odd.

1. Assume n is even, so n = 2k for some integer k. (Unpacked the negated conclusion.)
2. Substitute: 5n + 3 = 5(2k) + 3 = 10k + 3. (Algebra.)
3. Rewrite to expose a factor of 2 plus 1: 10k + 3 = 2(5k + 1) + 1. (Since 3 is 2 plus 1.)
4. Since 5k + 1 is an integer, 5n + 3 has the form 2m + 1, so it is odd. (Reached ~P.)

That proves the contrapositive, and therefore the original. QED. Notice the identical shape: negate the conclusion, assume it, run a direct proof to the negated hypothesis.

Where people get stuck

The biggest hazard is confusing the contrapositive with the converse. The converse of P => Q is Q => P, which is a different, non-equivalent statement. The contrapositive is ~Q => ~P, which is equivalent. If you accidentally prove the converse, you have proved the wrong thing, so double check that you both swapped and negated.

A second slip is forgetting to negate carefully. The negation of "n is even" is "n is odd," and the negation of "n is odd" is "n is even." Write the negated conclusion and the negated hypothesis explicitly before you start, so you know your true starting point and true target.

Contrapositive is not contradiction

These two techniques are easy to blur together, because both begin by assuming something is false, so it helps to separate them now, before the next lesson. In a contrapositive proof, you assume only the negated conclusion, ~Q, and you aim for a specific target, the negated hypothesis ~P. Reaching that target completes the proof. Nothing is assumed about P at the start.

In a proof by contradiction, which we meet next, you assume the negation of the entire statement, and you have no fixed target. You simply reason until anything impossible appears, any clash of the form "R and not R." The contrapositive is more focused: it is really just a direct proof of a rephrased statement, with a clear destination. Keeping this distinction in mind will save confusion when both techniques are on the table.

A quick way to tell them apart: if you can name your goal in advance, you are doing a contrapositive proof. If you are hunting for any absurdity at all, you are doing a proof by contradiction. Both are valid, but they feel different once you have practiced each.

A note on honesty

When you write a proof by contrapositive, say so at the very top, with a line like "We prove the contrapositive." This tells your reader which statement you are actually establishing, so they are never confused about why you began by assuming the conclusion was false. The logic guarantees the two statements are interchangeable, but announcing the technique is a courtesy that makes your proof easy to follow.

This habit of signaling your method is part of writing clean proofs in general. A reader should always know what you are assuming, what you are aiming for, and by what strategy. Contrapositive is one of your sharpest tools, useful whenever a conclusion is easier to attack in negated form than the hypothesis is to use directly.

Try it: choose and prove

Decide whether a direct or contrapositive proof is easier for "if n^2 is odd then n is odd," then sketch it.

The hypothesis is about n^2, which is awkward, and the conclusion "n is odd" negates cleanly, so the contrapositive wins. Prove instead "if n is even then n^2 is even." Assume n = 2k, so n^2 = 4k^2 = 2(2k^2), which is even. That establishes the contrapositive, and therefore the original. Well chosen and well done.

Recap

• A proof by contrapositive proves P => Q by instead proving ~Q => ~P, using a direct proof on the flipped statement.
• It is valid because a conditional and its contrapositive have identical truth tables.
• Reach for it when the hypothesis is awkward, such as a fact about n^2, and the negated conclusion is a clean equation like n = 2k.
• Do not confuse the contrapositive ~Q => ~P with the converse Q => P; only the contrapositive is equivalent.
• Signal the method at the top with "We prove the contrapositive" so your reader always knows which statement you are establishing.

Sources

1. Hammack, R. (2018). Chapter 5: Contrapositive proof. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. OpenStax. (2023). 2.4 Truth tables for the conditional and biconditional. In Contemporary mathematics. Rice University. openstax.org
3. Levin, O. (n.d.). 3.2 Proofs. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
4. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof. LibreTexts. math.libretexts.org
5. Weber, K., & Alcock, L. (2004). Semantic and syntactic proof productions. Educational Studies in Mathematics, 56(2-3), 209-234. doi.org/10.1023/B:EDUC.0000040410.57253.a1
6. Selden, A., & Selden, J. (2003). Validations of proofs considered as texts: Can undergraduates tell whether an argument proves a theorem? Journal for Research in Mathematics Education, 34(1), 4. doi.org/10.2307/30034698
7. Encyclopedia of Mathematics. (n.d.). Propositional calculus. European Mathematical Society. encyclopediaofmath.org

Here is a technique with real power, especially for claims that say "such a thing cannot exist." A proof by contradiction, known by its Latin name reductio ad absurdum, proves a statement S by assuming its negation ~S and then showing that this assumption forces something impossible. Since a true assumption can never lead to a false result through valid steps, the assumption ~S must have been wrong, and so S is true.

You already reason this way in daily life. Suppose you assume your keys are in your bag, but searching every pocket turns up nothing. The assumption led to a conflict with the facts, so you conclude the keys are not in the bag after all. Mathematics uses the same move, only the "conflict with the facts" is a logical impossibility.

The idea in plain terms

Think of it as a detective's tactic. To show a suspect is innocent, you suppose they are guilty and follow that supposition to something that cannot be true, like the suspect being in two cities at once. The absurd consequence proves the supposition was false. In a proof, the impossibility usually takes the form R AND ~R, read "R and not R," a statement that is both true and false at once, which nothing can ever be.

What makes this valid is a fact about logic we established with truth tables: a correct chain of reasoning can never carry you from a true premise to a false conclusion. So if valid steps landed you at an impossibility, the one thing you merely supposed, ~S, has to be the source of the trouble.

Key idea: assume the opposite, reason validly to an impossibility, and conclude the original statement must be true.

The structure

Every proof by contradiction follows the same three-step frame.

1. Suppose, for contradiction, that ~S is true. (State the negation clearly. This is why we drilled negation in Module 2.)
2. Reason validly until you reach a statement that cannot hold, such as a number that is both even and odd, a set both empty and nonempty, or 0 = 1.
3. Conclude that ~S is impossible, hence S is true.

This method is especially powerful for statements of nonexistence, the "there is no such thing" claims, and for facts that resist a direct attack. The critical first move is to negate S correctly. A wrong negation dooms the proof from line one, no matter how clever the reasoning that follows, which is exactly why we spent a whole lesson on getting negations right.

Worked example: the square root of 2 is irrational

This is one of the most famous proofs in all of mathematics, and it is a proof by contradiction. Take it slowly and enjoy it.

Theorem. There is no rational number whose square is 2. Equivalently, the square root of 2 is irrational.

Proof. Suppose, for contradiction, that the square root of 2 is rational. Then it can be written as a fraction in lowest terms, meaning the numerator and denominator share no common factor.

sqrt(2) = a/b, where a and b are integers, b != 0, and a/b is fully reduced.

1. Square both sides: 2 = a^2 / b^2, which rearranges to a^2 = 2 b^2. (Basic algebra.)
2. The right side is 2 times an integer, so a^2 is even. (Definition of even.)
3. By a theorem from the contrapositive lesson, if a^2 is even then a is even. So a = 2c for some integer c. (Reusing an earlier result, and unpacking the definition.)
4. Substitute a = 2c into a^2 = 2 b^2: (2c)^2 = 2 b^2, that is 4c^2 = 2 b^2. (Substitution and algebra.)
5. Divide both sides by 2: b^2 = 2c^2. So b^2 is even, and by the same theorem b is even too. (Same reasoning applied to b.)
6. But now a and b are both even, so they share the common factor 2. (Combining steps 3 and 5.)

Step 6 is the collision. We assumed a/b was in lowest terms, with no common factor, yet we just showed 2 divides both. That is a contradiction, a statement of the form "the fraction is reduced and the fraction is not reduced." The assumption that the square root of 2 is rational led straight to an impossibility, so it must be false. Therefore the square root of 2 is irrational. QED. Sit with that for a moment: you just followed one of the great proofs in mathematics, line by line.

This result changed the course of mathematics. The ancient Pythagoreans believed every length could be written as a ratio of whole numbers, and the discovery that the diagonal of a unit square, which measures the square root of 2, could not, was genuinely shocking to them. The proof you just read is the reason we know it. It shows that the rational numbers, dense as they are, still leave gaps on the number line, gaps that the real numbers fill.

The engine behind the proof

It is worth naming what actually powered that argument, so you can reuse the idea. The whole proof turned on a fact about parity: if a square is even, its root must be even. We applied that fact twice, once to a and once to b, and each application squeezed out a factor of 2. Being forced to pull a factor of 2 from both the numerator and the denominator is what collided with "lowest terms."

This style of argument, where an assumption keeps forcing the same reduction until it cannot continue, appears throughout number theory. Recognizing the engine, rather than just memorizing the steps, is what lets you adapt the technique to a new problem, such as showing the square root of 3 is irrational by the same route.

A second example: no smallest positive real number

Theorem. There is no smallest positive real number.

Proof. This is a nonexistence claim, a perfect fit for contradiction.

1. Suppose, for contradiction, that there is a smallest positive real number; call it x. (Negation: assume the thing exists.)
2. Since x is positive, the number x/2 is also positive. (Half of a positive number is positive.)
3. Moreover x/2 < x, because halving a positive number makes it strictly smaller. (Basic inequality.)
4. So x/2 is a positive real number smaller than x. But x was supposed to be the smallest positive real. (Contradiction.)

The assumption produced a positive real smaller than the supposed smallest, which cannot be. Hence no smallest positive real number exists. QED. Notice how the negation handed us a concrete x to attack, and a single clever construction, x/2, broke it.

Where people get stuck

The first pitfall is negating the statement incorrectly at step one. If S is a "for all" statement, its negation is a "there exists," and vice versa, so review the quantifier rules before you write "suppose not." A sloppy negation means you are disproving the wrong thing.

The second pitfall is forgetting to actually use the assumption. In a contradiction proof, the assumed ~S should appear in your reasoning and be the thing that eventually clashes. If your argument never touches the assumption, you have probably wandered off into a direct proof by accident.

The third is expecting a particular contradiction. Any impossibility at all will do: 0 = 1, a number both even and odd, or a violated hypothesis like our reduced fraction. You are hunting for any clash, not a specific one.

A fourth, quieter pitfall is stopping too early. Once you reach the impossibility, you are not quite finished; you should write the concluding sentence that names the contradiction and states that the original claim therefore holds. Leaving that last line out makes a reader wonder whether you noticed the clash. A single clear sentence, such as "this contradicts our assumption, so the statement is true," closes the argument properly and shows you understood why the impossibility mattered.

When contradiction is the right choice

How do you know to reach for this technique rather than a direct proof? A few signals point the way. The clearest is a claim of nonexistence or impossibility: "there is no ...," "it is impossible to ...," or "no such number exists." Direct proofs are poor at these, because you cannot easily build an argument about a thing that is not there. Assuming it does exist, then breaking it, is far more natural.

Another signal is a uniqueness claim, such as "there is exactly one ..."; you assume two different such objects and derive that they must be equal, a contradiction with their being different. A third signal is any statement where the negation gives you a concrete object to grab, the way "assume a largest integer exists" handed us N to work with. Famous results across mathematics, including the proof that there are infinitely many prime numbers, rest on assuming the opposite and forcing an absurdity.

Key idea: choose contradiction for nonexistence, impossibility, and uniqueness claims, or when the negation hands you something concrete to break.

Why the contradiction settles it

Let us name precisely why this works, because it is a subtle and beautiful point. Every step from the assumption was a valid deduction, yet the destination was impossible. In logic, a valid argument can never carry you from a true premise to a false conclusion. So the only thing we merely supposed, the negation ~S, has to be the culprit, and its falsehood makes S true.

Notice too that the square-root proof reused the earlier contrapositive result as a stepping stone. Good proofs build on the theorems you have already established, so the more results you collect, the more tools you carry into the next problem. Reach for contradiction when a claim asserts that something cannot happen, or when assuming the opposite hands you a concrete object you can pick apart.

Try it: a quick contradiction

Prove by contradiction that there is no largest integer.

Suppose there is a largest integer, and call it N. Then N + 1 is also an integer, and it is larger than N. That contradicts N being the largest. So the assumption fails, and no largest integer exists. Short and clean, and you built it from the three-step frame. Well done.

Recap

• A proof by contradiction assumes the negation ~S and derives an impossibility, forcing S to be true.
• The frame is three steps: suppose not, reason to an impossibility, conclude the original.
• It shines for nonexistence claims and statements that resist a direct attack.
• The square root of 2 is irrational: assuming sqrt(2) = a/b in lowest terms forces both a and b even, contradicting "lowest terms."
• Negate carefully at step one, actually use the assumption, accept any impossibility as your contradiction, and close with a sentence naming the clash.

Sources

1. Hammack, R. (2018). Chapter 6: Proof by contradiction. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Weisstein, E. W. (n.d.). Proof by contradiction. MathWorld: A Wolfram web resource. mathworld.wolfram.com
3. Encyclopedia of Mathematics. (n.d.). Irrational number. European Mathematical Society. encyclopediaofmath.org
4. Levin, O. (n.d.). 3.2 Proofs. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
5. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu
6. OpenStax. (2023). 2.7 Logical arguments. In Contemporary mathematics. Rice University. openstax.org
7. Encyclopedia of Mathematics. (n.d.). Real number. European Mathematical Society. encyclopediaofmath.org

Mathematical induction is the technique for proving a statement P(n) holds for every natural number n, starting from some base value, often 0 or 1. At first it can seem like magic, proving infinitely many statements with a finite amount of writing. But there is a simple picture behind it that makes it feel inevitable, and once you have that picture, induction becomes one of your most reliable tools. It also has a big reputation for being confusing at first, so if it has not clicked before, this lesson is a fresh chance to build it from the ground up.

The domino picture

Imagine an endless line of dominoes, one for each natural number. You want to show that every single domino falls. Checking them one by one would take forever, so instead you check two things that together guarantee the whole line topples.

First, you make sure the first domino falls. Second, you make sure the dominoes are spaced so that whenever one falls, it knocks over the next. If both of those hold, then the first falls, which knocks the second, which knocks the third, and the wave continues forever. You never had to push each domino yourself; the setup does it for you. Induction is exactly this argument, with "domino number n falls" standing in for "the statement P(n) is true."

Key idea: if the first case holds, and each case forces the next, then every case holds.

The two things you must show

To prove FORALL n >= 1, P(n) by induction, you establish two parts.

1. Base case: prove P(1) directly. This is the first domino falling, and it is usually a quick check.
2. Inductive step: prove that FORALL k >= 1, (P(k) => P(k+1)). This is the spacing that lets each domino topple the next. Inside this step you assume P(k) is true, an assumption called the inductive hypothesis, and use it to derive P(k+1).

Once both parts are in place, the principle of induction guarantees P(n) for all n >= 1. Both parts genuinely matter. Without the base case the chain never starts, like dominoes perfectly spaced but never pushed. Without the inductive step the chain never continues, like a first domino that falls into empty space. You need both.

What kinds of statements is induction good for? A great many. It proves summation formulas, like the one we are about to see; divisibility claims, such as "3 divides n^3 - n"; inequalities that hold from some point on; and facts about recursively built objects, where each case is defined in terms of earlier ones. Whenever a claim is indexed by a whole number n and the n+1 version is naturally related to the n version, induction is a strong candidate. Keeping that pattern in mind helps you recognize when to reach for it.

The inductive step often feels strange the first time, because you are assuming P(k), which looks like assuming what you want to prove. It is not. You are only assuming the claim for one value k in order to establish the next value k+1. That is a conditional, "if this domino falls, the next one does," and proving a conditional is ordinary work.

Why induction is trustworthy

It is fair to ask why this two-part recipe really proves a statement about infinitely many numbers. The domino image gives the intuition, but there is solid ground underneath. Suppose you have proved the base case and the inductive step, yet the statement somehow failed for some numbers. Among all the numbers where it fails, there would be a smallest one; call it f. That smallest failing number cannot be the base value, because you proved the base case directly.

So f is larger than the base, which means f - 1 is a valid earlier case, and since f was the smallest failure, the statement holds at f - 1. But your inductive step says that whenever the statement holds at a number it holds at the next one, so it must hold at f too. That contradicts f being a failure. No smallest failure can exist, so there are no failures at all. This backing fact, that every nonempty collection of natural numbers has a least member, is called the well-ordering principle.

Finding the inductive step in practice

Students often stall not on the idea of induction but on the algebra of the step, so here is a dependable plan. Write down clearly what P(k) says and what P(k+1) says, side by side. Your job is to bridge from one to the other.

Look for how the k+1 case contains the k case: a sum up to k+1 is the sum up to k plus one more term, and an expression at k+1 can often be regrouped so the k expression appears. Once you have exposed the k case, substitute the inductive hypothesis, and finish with routine algebra. Almost every induction proof follows this same arc, so if you feel lost, return to this plan and work it one line at a time.

Worked example one: a summation formula

Theorem. For every natural number n >= 1, the sum 1 + 2 + 3 + ... + n = n(n+1)/2.

Proof by induction on n.

Base case (n = 1): the left side is just 1. The right side is 1(1+1)/2 = 1(2)/2 = 1. They agree, so P(1) holds. The first domino falls.

Inductive step: assume the formula holds for some k >= 1, that is, assume 1 + 2 + ... + k = k(k+1)/2. This is the inductive hypothesis. We must show the formula for k + 1, namely that 1 + 2 + ... + (k+1) = (k+1)(k+2)/2. Here are the steps.

1. Split off the last term: 1 + 2 + ... + k + (k+1) = [1 + 2 + ... + k] + (k+1). (Just grouping.)
2. Replace the bracket using the inductive hypothesis: = k(k+1)/2 + (k+1). (This is where the assumption earns its keep.)
3. Factor out the common (k+1): = (k+1)[k/2 + 1]. (Pulling out the shared factor.)
4. Combine the bracket over a common denominator: k/2 + 1 = (k+2)/2, so the expression is (k+1)(k+2)/2. (Ordinary algebra.)

The result (k+1)(k+2)/2 is exactly the formula with n = k+1. So P(k) implies P(k+1). With the base case and the inductive step both proved, induction gives the formula for all n >= 1. QED. Look back at step 2: the entire trick was turning the sum up to k+1 into the sum up to k plus one more term, so the inductive hypothesis could act.

Worked example two: a divisibility claim

Theorem. For every natural number n >= 1, the number 3 divides n^3 - n.

Proof.

Base case (n = 1): 1^3 - 1 = 0, and 3 divides 0, since 0 = 3 times 0. So the base case holds.

Inductive step: assume 3 divides k^3 - k, so we may write k^3 - k = 3m for some integer m (the inductive hypothesis). Consider the next case, (k+1)^3 - (k+1).

1. Expand (k+1)^3 = k^3 + 3k^2 + 3k + 1, so (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1. (Algebra.)
2. Regroup to reveal the previous case: = (k^3 - k) + 3k^2 + 3k. (Collecting the k^3 - k piece.)
3. Use the hypothesis k^3 - k = 3m: = 3m + 3k^2 + 3k = 3(m + k^2 + k). (Substitution and factoring out 3.)

The result is 3 times an integer, so 3 divides (k+1)^3 - (k+1). That completes the inductive step, and by induction the claim holds for all n >= 1. QED. Again the engine was the same: rewrite the k+1 case so the k case appears, then apply the hypothesis.

Where people get stuck

Three habits cause most induction trouble. First, skipping the base case. It feels minor, but without it the whole chain is unsupported, so always check P(1) explicitly, even when it is obvious.

Second, never actually using the inductive hypothesis. If your inductive step does not lean on the assumed P(k) at some point, you are probably not doing induction, and the argument likely has a gap. The hypothesis should appear as a substitution, as it did in both examples.

Third, treating the assumption that P(k) holds as circular reasoning. It is not, because you assume it only for a single k in order to reach k+1. You are proving a conditional, one link in the chain, not the whole theorem in a single line, and that is a perfectly valid thing to do.

Induction that starts somewhere other than 1

Nothing forces the base case to be n = 1. Some statements are only true from a certain point on, so you start the induction there. For instance, the inequality 2^n > n^2 is false at n = 2 and n = 3 and n = 4, but true from n = 5 onward. To prove it for all n >= 5, you would use n = 5 as the base case and then run the usual inductive step for k >= 5.

The domino picture still fits perfectly: you simply push the first domino further down the line and topple everything after it. Whenever a claim carries a phrase like "for all n >= 5," read that starting value as the base case and set up the induction from there. The method does not change, only the place where the chain begins.

Try it: check a base case

For the claim 1 + 3 + 5 + ... + (2n - 1) = n^2, verify the base case.

Set n = 1. The left side is the single term 2(1) - 1 = 1. The right side is 1^2 = 1. They match, so the base case holds, and the claim that the sum of the first n odd numbers equals n^2 is off to a correct start. Nicely checked.

Recap

• Induction proves P(n) for all n >= 1 using a base case and an inductive step, like toppling an endless line of dominoes.
• The base case proves P(1) directly; the inductive step proves P(k) => P(k+1).
• The inductive hypothesis is the assumed P(k), and it must be used somewhere in the step.
• The reliable move is to rewrite the k+1 case so the k case appears, then substitute the hypothesis.
• Always include the base case, actually use the hypothesis, and remember that assuming P(k) for one value is not circular.

Sources

1. Hammack, R. (2018). Chapter 10: Mathematical induction. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Levin, O. (n.d.). 2.5 Induction. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
3. Encyclopedia of Mathematics. (n.d.). Mathematical induction. European Mathematical Society. encyclopediaofmath.org
4. Weisstein, E. W. (n.d.). Principle of mathematical induction. MathWorld: A Wolfram web resource. mathworld.wolfram.com
5. Levin, O. (n.d.). 2: Sequences. In Discrete mathematics. LibreTexts. math.libretexts.org
6. MacTutor History of Mathematics Archive. (n.d.). Giuseppe Peano. University of St Andrews. mathshistory.st-andrews.ac.uk
7. Mason, J., & Pimm, D. (1984). Generic examples: Seeing the general in the particular. Educational Studies in Mathematics, 15(3), 277-289. doi.org/10.1007/BF00312078

Ordinary induction has one limitation. In the inductive step it lets you assume only the single previous case, P(k), to reach P(k+1). That is plenty for many problems, but some statements about k+1 depend on cases far earlier than k, and then one previous domino is not enough leverage. Strong induction fixes this by handing you a bigger assumption.

Why one previous case is sometimes not enough

Picture the dominoes again, but now some dominoes are heavy, and knocking one over requires the combined push of several earlier ones, not just the one immediately before. If your only guarantee is "each domino topples the very next," you cannot promise the heavy ones fall. You need a stronger guarantee: "if all the dominoes up to here have fallen, the next one falls too."

A concrete case is factoring a number. To understand k + 1 by breaking it into a product, you might get factors like 3 and 7, which are nowhere near k. Knowing only about P(k) tells you nothing about P(3) or P(7). To use those, you need to have assumed the statement for every earlier case, not just the last one.

Key idea: when the k+1 case depends on earlier cases you cannot predict, assume them all.

The structure

Strong induction, also called complete induction, keeps the same two-part shape but strengthens the hypothesis.

1. Base case(s): prove P for the smallest value or values. Some proofs need several base cases, not just one, to cover how far back the recursion reaches.
2. Inductive step: assume P(j) is true for every j from the base up to k, an assumption called the strong inductive hypothesis, and use any of those cases to prove P(k+1).

The difference from ordinary induction is exactly one thing: the size of the hypothesis. Ordinary induction assumes a single case, P(k). Strong induction assumes the whole run of cases, P(base) through P(k). Everything else, the base case and the goal of reaching P(k+1), is unchanged.

Ordinary and strong induction have equal power

It is natural to wonder whether strong induction can prove things ordinary induction cannot. It cannot; the two are logically equivalent in power, meaning any theorem provable by one is provable by the other. Strong induction is not a more powerful axiom, just a more convenient bookkeeping method. When a proof needs to reach back more than one step, strong induction saves you from awkward workarounds, so we use it for convenience, not necessity. Choose whichever makes a given proof cleaner.

There is a tidy way to see why they are equal in strength. Any strong-induction argument can be converted into an ordinary one by proving a slightly different statement, namely "the claim holds for every value from the base up to n." That combined statement only ever needs its own single previous case, so ordinary induction handles it, and it carries all the earlier cases along inside it. You do not need to perform this trick in practice; it just reassures you that reaching back to many earlier cases is fully legitimate, never a shortcut that proves too much.

A reliable template for strong-induction proofs

Having a fixed routine removes most of the guesswork, so here is a template you can follow every time. Begin by stating clearly that you are proving P(n) by strong induction. Prove the base case or cases directly, checking as many small values as your later reasoning will reach back to.

Then open the inductive step by writing out the strong hypothesis in full: "assume P(j) holds for all j with base value up to k." Now analyze k + 1. The usual move is to break it into smaller pieces, whether by factoring, by peeling off earlier terms, or by splitting into cases. Each smaller piece is an earlier case, so the strong hypothesis already covers it, and you assemble those pieces into the result for k + 1. Announcing the hypothesis in full at the start keeps you from forgetting that all earlier cases are fair game.

Worked example: every integer greater than 1 has a prime factor

Theorem. Every integer n >= 2 is divisible by at least one prime.

Proof by strong induction on n.

Base case (n = 2): the number 2 is prime, and it divides itself, so it has a prime factor. The base case holds.

Inductive step: let k >= 2, and assume the strong inductive hypothesis: every integer j with 2 <= j <= k has a prime factor. We prove the same for k + 1. There are exactly two cases.

1. Case 1: k + 1 is prime. Then k + 1 has itself as a prime factor, and we are done immediately. (A prime divides itself.)
2. Case 2: k + 1 is not prime. By the definition of a composite number, it factors as k + 1 = a * b where a and b are integers with 2 <= a <= k. (A nontrivial factor lies strictly between 1 and k + 1.)
3. Since 2 <= a <= k, the strong inductive hypothesis applies to a, so a has a prime factor p. (This is the step ordinary induction could not take.)
4. Because p divides a and a divides k + 1, it follows that p divides k + 1. (Divisibility passes through a chain.) So k + 1 has a prime factor.

In both cases k + 1 has a prime factor. By strong induction, every integer n >= 2 has a prime factor. QED. Notice the move in step 3: we applied the hypothesis to a, some number between 2 and k that we could not name in advance. That is precisely what the strong hypothesis makes possible.

Why ordinary induction would struggle here

Look closely at the factor a. It could be any value between 2 and k, depending on how k + 1 happens to factor, and it is usually not k itself. So knowing only P(k), the single previous case, would give us no information about P(a). Ordinary induction hands you exactly one earlier case, and it is the wrong one. Strong induction hands you all of them, so whatever a turns out to be, P(a) is already available.

This is the signature situation for strong induction: the recursive structure of a problem points back to some earlier but unpredictable case. Factoring does it, and so do many other constructions.

This little theorem is also the doorway to a much bigger one. Once you know every integer above 1 has a prime factor, you can repeat the idea: pull out a prime, factor what remains, pull out another prime, and continue. Because the leftover shrinks each time, the process must stop, and you are left with the number written as a product of primes.

That is the beginning of the fundamental theorem of arithmetic, which says every integer greater than 1 is a product of primes in essentially one way. Strong induction is the natural engine for proving results of this repeated-breakdown kind, which is why it appears so often in number theory. Keeping that picture in mind gives you a sense of when the technique will fit a new problem.

Another place it shines: recursive sequences

Sequences defined by looking back more than one step are the other classic home for strong induction. The Fibonacci numbers are the famous example: each term is the sum of the two before it, F(n) = F(n-1) + F(n-2). If you want to prove something about F(n), your argument will naturally need the statement for both n-1 and n-2, so you must have assumed both, which strong induction provides but ordinary induction does not.

Because such proofs reach back two steps, they typically require two base cases, one for each of the smallest values the recursion depends on. Whenever a definition or a problem references several earlier terms at once, expect to set up extra base cases and use the strong hypothesis.

To see the two base cases in action, imagine proving an inequality like F(n) <= 2^n for the Fibonacci numbers. In the inductive step you would write F(k+1) = F(k) + F(k-1), then replace F(k) and F(k-1) using the hypothesis for both of those earlier terms. Because the step leans on two predecessors, the chain needs two solid starting dominoes, so you check n = 1 and n = 2 as base cases before the step takes over. The shape of the recurrence tells you exactly how many base cases to prove.

Where people get stuck

The most common error is providing too few base cases. If your inductive step relies on cases two or three steps back, but you only proved a single base case, there is a gap near the start where the hypothesis does not yet cover what the step needs. Count how far back your step reaches, and supply that many base cases.

A second slip is forgetting that the strong hypothesis covers the entire range from the base up to k. You are entitled to use any of those earlier cases, not just k, so do not hesitate to apply the hypothesis to whatever earlier value your argument produces.

A third is defaulting to strong induction out of habit when ordinary induction would be cleaner. If your k+1 case connects only to the immediately preceding case, ordinary induction says exactly what you need with less machinery. Reach for the strong version when, and only when, your argument genuinely calls on cases further back. Matching the tool to the problem keeps proofs tidy and easy to read, which is worth caring about.

Try it: spot the key step

In the prime-factor proof, which single line would break if we had used ordinary induction instead of strong?

The line where we apply the hypothesis to the factor a, with 2 <= a <= k. Ordinary induction would only give us P(k), but a is generally not k, so we could not conclude that a has a prime factor. The strong hypothesis is what rescues that step. Good eye.

Recap

• Strong induction assumes P(j) for all j from the base up to k, rather than just P(k).
• Use it when the k+1 case depends on earlier cases you cannot predict, such as factors or recursive terms.
• It is logically equivalent in power to ordinary induction, just more convenient here.
• Every integer n >= 2 has a prime factor: if k+1 is prime it is done, otherwise a factor a in range carries a prime by the strong hypothesis.
• Supply enough base cases to cover how far back your inductive step reaches.

Sources

1. Hammack, R. (2018). Section 10.2: Proof by strong induction. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Levin, O. (n.d.). 2.5 Induction. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
3. Encyclopedia of Mathematics. (n.d.). Mathematical induction. European Mathematical Society. encyclopediaofmath.org
4. Weisstein, E. W. (n.d.). Principle of mathematical induction. MathWorld: A Wolfram web resource. mathworld.wolfram.com
5. LibreTexts Mathematics. (n.d.). A spiral workbook for discrete mathematics (Kwong). math.libretexts.org
6. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu
7. Levin, O. (n.d.). 2: Sequences. In Discrete mathematics. LibreTexts. math.libretexts.org

You have met functions before, but this lesson looks at them the way a proof-writer does, focusing on how a function pairs its inputs with its outputs. Three properties, with the names injective, surjective, and bijective, describe that pairing, and they run through the rest of higher mathematics. We will define each carefully, prove them in worked examples, and give you a plain picture for each. These ideas have a reputation for being slippery, mostly because the names sound technical, but the underlying pictures are simple, and building them slowly here will make the abstract definitions feel concrete.

A useful mental image is a vending machine. You press a button (an input), and the machine delivers exactly one item (an output). A function f: A -> B, read "f from A to B," assigns to each element of the domain A exactly one element of the codomain B. The "exactly one" is essential: a real machine never gives two different items for one button press.

The set of outputs actually produced, written {f(x) : x IN A}, is called the image or range. The image can be smaller than the whole codomain, because some items on the machine's menu might never actually come out. Keeping the codomain (the menu) separate from the image (what is really dispensed) will matter a lot in a moment.

Key idea: a function sends each domain element to exactly one codomain element; the image is the set of outputs actually hit.

Injective (one-to-one)

A function f is injective, also called one-to-one, if different inputs always give different outputs. Said the contrapositive way, which is how we usually prove it: if f(x1) = f(x2), then x1 = x2. No output is ever used by two different inputs.

The picture is a row of lockers where every person gets their own. If two people ever ended up assigned to the same locker, the assignment would not be one-to-one. To prove a function is injective, you assume f(x1) = f(x2) and work algebraically until you reach x1 = x2. That is the standard template, and we will use it below.

Surjective (onto)

A function f is surjective, also called onto, if every element of the codomain is actually hit by some input. In symbols, FORALL y IN B, EXISTS x IN A, f(x) = y, read "for all y in B, there exists an x in A with f of x equal to y." For a surjective function, the image fills the entire codomain, with nothing left out.

The picture here is a bank of mailboxes where every mailbox receives at least one letter. To prove a function is surjective, you take an arbitrary target y in the codomain and produce a specific input x in the domain with f(x) = y. Producing that x, often by solving the equation for it, is the whole job.

Bijective

A function f is bijective if it is both injective and surjective at once. A bijection pairs the elements of A and B perfectly: every input goes to a distinct output, and every output is used exactly once, with none left over on either side. It is a flawless matching between the two sets.

This perfect pairing is exactly the condition for a function to have an inverse, a function f^(-1): B -> A, read "f inverse from B to A," that undoes it, sending each output back to the unique input it came from. Injective guarantees "back to a single input," and surjective guarantees "every output has something to go back to," so together they make the inverse well defined.

Key idea: injective means no repeated outputs, surjective means no missed outputs, and bijective means both, which is exactly when an inverse exists.

Worked example

Claim. The function f: R -> R given by f(x) = 3x + 5 is a bijection.

Injective. We use the template: assume the outputs are equal and deduce the inputs are equal.

1. Suppose f(x1) = f(x2). Then 3x1 + 5 = 3x2 + 5. (Wrote out both sides.)
2. Subtract 5 from both sides: 3x1 = 3x2. (Same operation on each side.)
3. Divide both sides by 3: x1 = x2. (Same operation again.)

Since f(x1) = f(x2) forced x1 = x2, the function is injective.

Surjective. We take an arbitrary target and build an input that hits it.

1. Let y be an arbitrary real number. We want an x with 3x + 5 = y. (State the goal.)
2. Solve for x: subtract 5 to get 3x = y - 5, then divide by 3 to get x = (y - 5)/3. (Algebra.)
3. This x is a real number, so it lives in the domain, and checking, f((y-5)/3) = 3 * (y-5)/3 + 5 = (y - 5) + 5 = y. (Verified it hits y.)

Every real y is hit, so the function is surjective. Since it is both injective and surjective, it is a bijection, with inverse f^(-1)(y) = (y - 5)/3. QED. That inverse is exactly the input-building rule we found in the surjective part, which is no coincidence.

A second worked example

Claim. The function h: R -> R given by h(x) = x^3 is a bijection. Notice that cubing behaves very differently from squaring.

Injective. Suppose h(x1) = h(x2), so x1^3 = x2^3. Taking the real cube root of both sides is a valid, single-valued operation on the reals, and it gives x1 = x2. Unlike a square root, a real cube root does not introduce a second value, so the function is injective.

Surjective. Let y be an arbitrary real number. The real cube root of y, written as the value x with x^3 = y, exists for every real y, including negatives, since cubing a negative gives a negative. That x satisfies h(x) = y, so every target is hit and the function is surjective.

Both properties hold, so h is a bijection. Comparing it with x^2 shows how much the specific rule matters: cubing pairs the whole line perfectly, while squaring folds it in half.

What these properties say about set sizes

There is a deeper meaning hiding in these three words, and it will drive the cardinality lesson soon. An injective function from A to B tucks all of A inside B without collisions, which intuitively says A is no larger than B. A surjective function from A onto B manages to cover all of B, which says A is at least as large as B.

A bijection does both, so it says the two sets are the same size, a perfect one-to-one match with nothing left over. For finite sets this matches ordinary counting exactly. The surprise, coming later, is that this same idea lets us compare infinite sets, where it produces results that overturn everyday intuition. For now, hold onto the slogan: injective means "fits inside," surjective means "covers," and bijective means "same size."

A non-example, and why the sets matter

Contrast that with g: R -> R given by g(x) = x^2. This function is neither injective nor surjective. It fails injectivity because g(2) = 4 and g(-2) = 4, two different inputs sharing an output. It fails surjectivity onto R because no real number squares to a negative like -1, so those targets are never hit.

Here is the important twist: both failures can be repaired by changing the domain and codomain. If we restrict to g: [0, infinity) -> [0, infinity), allowing only nonnegative inputs and outputs, then squaring becomes a bijection. This is why stating the domain and codomain is part of defining a function at all, not an optional detail. The same rule can be a bijection or neither, depending on the sets you attach to it.

Undoing a function with its inverse

Let us look a little closer at why only bijections have inverses, since it ties the three properties together. An inverse f^(-1) is supposed to take any output back to the exact input that produced it. For that to be well defined, two things must be true, and they are precisely our two properties.

First, each output must come from only one input, otherwise the inverse would not know which input to return to. That is injectivity. Second, every element of the codomain must actually be an output, otherwise the inverse would have nothing to send some codomain elements back to. That is surjectivity. Remove either property and the inverse breaks. In our first example, f(x) = 3x + 5 had inverse f^(-1)(y) = (y - 5)/3, and you can check they undo each other: feeding an output back through the inverse returns the original input. That mutual undoing is the hallmark of a bijection and its inverse.

Where people get stuck

The most common confusion is mixing up the two proof templates. For injective, you start from f(x1) = f(x2) and aim for x1 = x2. For surjective, you start from an arbitrary y and aim to produce an x. They move in opposite directions, so name which one you are doing before you begin.

A second stumbling point is confusing the codomain with the image. Surjectivity is a claim about filling the whole codomain, so whether a function is surjective depends entirely on what codomain you declared. Change the codomain and you can change the answer, even though the rule stayed the same.

A third is stopping after checking only one property and declaring a function bijective. Bijective requires both injective and surjective, so you owe two separate arguments. Prove each one on its own, label them clearly, and only then conclude that the function is a bijection.

Try it: classify a function

Is f: Z -> Z given by f(n) = 2n injective? Is it surjective onto Z?

For injectivity, assume 2n1 = 2n2; dividing by 2 gives n1 = n2, so it is injective. For surjectivity, ask whether every integer is hit. The output 2n is always even, so an odd target like 3 is never produced, and the function is not surjective onto Z. So it is injective but not surjective. Nicely reasoned.

Recap

• A function f: A -> B sends each element of the domain to exactly one element of the codomain; the image is the set of outputs actually hit.
• Injective (one-to-one): f(x1) = f(x2) forces x1 = x2, so no output repeats.
• Surjective (onto): every codomain element is hit, so the image fills the codomain.
• Bijective: both at once, which is exactly when an inverse exists.
• Prove injective by assuming equal outputs and deducing equal inputs; prove surjective by building an input for an arbitrary target; the domain and codomain are part of the definition and can change the answer.

Sources

1. Hammack, R. (2018). Chapter 12: Functions. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Levin, O. (n.d.). 0.4 Functions. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
3. Encyclopedia of Mathematics. (n.d.). Injection. European Mathematical Society. encyclopediaofmath.org
4. Encyclopedia of Mathematics. (n.d.). Surjection. European Mathematical Society. encyclopediaofmath.org
5. Encyclopedia of Mathematics. (n.d.). Bijection. European Mathematical Society. encyclopediaofmath.org
6. Weisstein, E. W. (n.d.). Bijection. MathWorld: A Wolfram web resource. mathworld.wolfram.com
7. Levin, O. (n.d.). 0.4: Functions. In Discrete mathematics. LibreTexts. math.libretexts.org

We compare things constantly: this number is less than that one, this integer divides that one, these two people share a birthday. Mathematics captures all of these under one idea, the relation. This lesson makes the notion precise, then focuses on an especially important kind, the equivalence relation, which formalizes what it means for two things to be "the same in some respect." The payoff is large: once you see that "grouping things by a shared property" is a single mathematical idea, you gain a tool that reappears in arithmetic, geometry, and algebra alike.

Formally, a relation R on a set A is just a set of ordered pairs of elements from A. We write a R b, read "a is related to b," to mean the pair (a, b) belongs to the relation. That is all a relation is: a rule that, for any two elements, either holds or does not. "Less than," "divides," "is congruent to," and "has the same birthday as" are all relations under this definition.

Three key properties

Three properties of a relation come up again and again, so we name them and check each against a familiar example. Throughout, a, b, and c are elements of the set A.

• Reflexive: a R a holds for every a IN A. Every element relates to itself. Equality is reflexive, since every number equals itself.
• Symmetric: if a R b then b R a. The relation reads the same both directions. "Has the same birthday as" is symmetric.
• Transitive: if a R b and b R c, then a R c. Relations chain together. "Less than" is transitive, since a < b and b < c give a < c.

To test a relation for a property, you check the defining condition, and to show a property fails, you exhibit one counterexample, exactly the skill from the quantifier lessons. For instance, "less than" is not reflexive, because a < a is never true, and that single observation settles it.

Key idea: a relation is a set of pairs; reflexive, symmetric, and transitive describe how it behaves toward itself, in reverse, and in chains.

Equivalence relations are everywhere

Before the formal definition, it helps to see how common this idea is, because you already sort things this way without naming it. Grouping people by the month they were born is a relation, and it satisfies all three properties: everyone shares a birth month with themselves, sharing is mutual, and if two people share with a third, they share with each other.

In geometry, "is parallel to" groups lines by direction, and "is congruent to" groups triangles by shape and size. In arithmetic, "leaves the same remainder when divided by 5" groups the integers into five families. Each of these carves a set into natural clumps where the members are interchangeable for some purpose. That clumping is precisely what the three properties, working together, guarantee, which is why equivalence relations show up in nearly every branch of mathematics.

Equivalence relations

A relation that is reflexive, symmetric, and transitive all at once is called an equivalence relation. These three properties together capture the intuitive idea of "being the same in some respect": everything is the same as itself (reflexive), sameness does not care about order (symmetric), and things equal to the same thing are equal to each other (transitive).

The most important example in this course is congruence modulo n. Fix a positive integer n. We say a === b (mod n), read "a is congruent to b modulo n," when n divides the difference a - b. Informally, a and b leave the same remainder when divided by n. Let us prove this is genuinely an equivalence relation, checking all three properties in turn.

Claim. Congruence modulo n is an equivalence relation on the integers.

1. Reflexive: for any integer a, the difference a - a = 0, and n divides 0 since 0 = n times 0. So a === a. (Every element relates to itself.)
2. Symmetric: suppose a === b, so n divides a - b, meaning a - b = n*t for some integer t. Then b - a = n*(-t), and since -t is an integer, n divides b - a. So b === a. (The relation reverses.)
3. Transitive: suppose a === b and b === c. Then a - b = n*s and b - c = n*t for integers s and t. Adding these, a - c = n*(s + t), so n divides a - c and a === c. (The relation chains.)

All three properties hold, so congruence modulo n is an equivalence relation. QED. Read the three parts back and notice each was a short direct proof: unpack "divides" into an equation with a witness, do a little algebra, repack. The same proof skills from Module 4 are doing the work here, which is a nice sign that the techniques you built are paying off in a new setting. Each of the three sub-proofs stood on its own, and stringing them together established the whole claim.

Equivalence classes and partitions

Every equivalence relation quietly sorts its set into groups. The equivalence class of an element a, written [a] and read "the class of a," is the set of all elements related to a. Everything congruent to a lands in [a], and these classes turn out to fit together beautifully.

A fundamental theorem says the equivalence classes form a partition of the set: every element lies in exactly one class, and two different classes never overlap. In plain terms, the relation slices the set cleanly into non-overlapping groups that cover everything, with no element left out and none in two groups at once.

For congruence modulo 3, the integers split into exactly three classes, sorted by remainder.

• [0] = {..., -3, 0, 3, 6, ...}, the multiples of 3 (remainder 0),
• [1] = {..., -2, 1, 4, 7, ...}, the numbers one more than a multiple of 3 (remainder 1),
• [2] = {..., -1, 2, 5, 8, ...}, the numbers two more than a multiple of 3 (remainder 2).

These three classes are disjoint, no integer sits in two of them, and together they contain every integer, so they form a perfect partition. This link between equivalence relations and partitions is one of the most useful structural ideas in mathematics. It underlies modular arithmetic, the construction of the rational numbers as classes of fractions, and much more.

Key idea: an equivalence relation partitions its set into disjoint classes that together cover everything.

The correspondence runs both ways

We saw that an equivalence relation produces a partition. What makes this idea so powerful is that the reverse is also true. Start with any partition of a set, any way of slicing it into non-overlapping groups that cover everything, and define a relation by "a is related to b when they lie in the same group." That relation is automatically reflexive, symmetric, and transitive, so it is an equivalence relation.

In other words, equivalence relations and partitions are two descriptions of the exact same thing. To hand someone a way of grouping a set is to hand them an equivalence relation, and vice versa. This two-way correspondence is why the concept is so central: whenever you sort objects into categories, whether by remainder, by color, or by shape, you are secretly working with an equivalence relation, and all the structure of classes and partitions comes along for free.

Where people get stuck

The first pitfall is checking only one or two of the three properties and declaring a relation an equivalence relation. All three are required, so verify reflexive, symmetric, and transitive each in turn, and if any one fails, the relation is not an equivalence relation.

The second is assuming every natural-looking relation is symmetric. "Divides" is a good warning. On the positive integers, 2 divides 6, but 6 does not divide 2, so "divides" is not symmetric. It is reflexive and transitive, yet it fails symmetry, so it is not an equivalence relation. Always test symmetry rather than assume it.

The third is confusing an element with its class. The class [1] for congruence modulo 3 is an entire infinite set of integers, not the single number 1. Many different elements can name the same class; for example, [1] and [4] are the same class, because 1 and 4 are congruent modulo 3. Any member of a class can stand in as its label, and choosing a different member never changes the class itself. When you see [a], read it as "the whole family that a belongs to," and this confusion melts away.

Not every relation sorts into classes

Equivalence relations are about sameness, but relations can express other ideas too, and it is worth knowing that the three properties are not the only combination that matters. Consider "less than or equal to" on the integers. It is reflexive, since a <= a, and transitive, since a <= b and b <= c give a <= c. But it is not symmetric: 2 <= 5 does not give 5 <= 2.

Instead it has a different property, called antisymmetry: if a <= b and b <= a, then a = b. A relation that is reflexive, antisymmetric, and transitive is an order relation, and it captures ranking rather than sameness. You do not need the details now, but the contrast is useful: swapping one property, symmetry for antisymmetry, changes a "grouping" relation into a "ranking" relation. It is a good reminder to always check which properties a relation actually has rather than assuming it must be an equivalence relation.

Try it: is this relation an equivalence relation?

Consider the relation "a divides b" on the positive integers. Is it an equivalence relation?

Check the three properties. It is reflexive, since every number divides itself. It is transitive, since if a divides b and b divides c, then a divides c. But it is not symmetric: 2 divides 6 while 6 does not divide 2. Because symmetry fails, "divides" is not an equivalence relation. Good, you found the property that breaks.

Recap

• A relation on A is a set of ordered pairs; a R b means the pair is in the relation.
• Three key properties: reflexive (a R a), symmetric (a R b gives b R a), and transitive (chains combine).
• An equivalence relation has all three; congruence modulo n is the key example.
• An equivalence relation sorts its set into equivalence classes [a] that form a partition: disjoint and covering everything.
• Check all three properties before concluding, do not assume symmetry, and remember an equivalence class is a whole set of related elements, not a single element.

Sources

1. Hammack, R. (2018). Chapter 11: Relations. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Weisstein, E. W. (n.d.). Equivalence relation. MathWorld: A Wolfram web resource. mathworld.wolfram.com
3. Encyclopedia of Mathematics. (n.d.). Equivalence relation. European Mathematical Society. encyclopediaofmath.org
4. Encyclopedia of Mathematics. (n.d.). Relation. European Mathematical Society. encyclopediaofmath.org
5. Encyclopedia of Mathematics. (n.d.). Partition. European Mathematical Society. encyclopediaofmath.org
6. LibreTexts Mathematics. (n.d.). A spiral workbook for discrete mathematics (Kwong). math.libretexts.org
7. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu

How can we compare the sizes of two infinite sets? Counting the elements is hopeless, since both go on forever. The breakthrough, due to Georg Cantor in the nineteenth century, was to compare sizes by pairing instead of counting. This lesson follows that idea to a genuinely startling conclusion: some infinities are strictly bigger than others.

Same size means a perfect pairing

Here is the key move. Imagine matching socks without counting them: if you can pair every left sock with exactly one right sock and none is left over on either side, the two piles are the same size, even if you never learn the number. Cantor applied this to sets of any size.

Two sets have the same cardinality, written |A| = |B| and read "the size of A equals the size of B," when there is a bijection between them, a perfect pairing of their elements. From the last lesson on functions, a bijection is exactly a matching with no repeats and nothing missed. For finite sets this agrees with ordinary counting. Its power is that it keeps working for infinite sets, where counting cannot follow.

Key idea: two sets have the same size when a bijection pairs their elements perfectly, with none left over.

Notice what this definition frees us from. We never have to say how many elements a set has, only whether a matching exists. That is a lighter requirement, and it is exactly what makes infinite comparison possible. To show two infinite sets are the same size, you exhibit a bijection; to show one is no larger than another, you exhibit an injection into it. All the size questions in this lesson reduce to building the right function, which is a skill you already practiced in the previous lesson.

Countable sets

A set is countably infinite if it has the same cardinality as the natural numbers N = {1, 2, 3, ...}. Concretely, that means its elements can be arranged in a single list a1, a2, a3, ... that eventually reaches every element. A set is countable if it is finite or countably infinite. Surprisingly large sets turn out to be countable.

The integers are countable. At first this looks doubtful, since Z runs off to infinity in both directions, while N only goes one way. But we can list the integers by zig-zagging outward from zero: 0, 1, -1, 2, -2, 3, -3, .... Every integer appears exactly once somewhere in this list, and pairing each with its position gives a bijection with N. So Z is countable.

The rationals are countable. This is even more surprising, because the rationals are dense; between any two of them lies another. Yet they can still be listed. Arrange all fractions in an infinite grid, with numerators along one axis and denominators along the other, then sweep through the grid along diagonals, skipping any fraction already seen in a simpler form. This threads every rational number into one long list, so Q is countable too.

The lesson so far is that "listable" is a low bar to clear. Sets that look far bigger than the counting numbers, like all fractions, still line up into a single sequence.

It is worth picturing the rational sweep a bit more concretely, because the trick is charming. Put the fraction with numerator p and denominator q at grid position row p, column q. A single row or a single column is infinite, so you cannot list row by row, or you would never finish the first row.

Instead you travel along the short diagonals: first the fractions whose numerator and denominator sum to 2, then those summing to 3, then 4, and so on. Each diagonal is finite, so this march does reach every fraction eventually, and skipping repeats like 2/4 keeps each rational to a single appearance. That is the whole idea behind counting the rationals, and it is a good example of solving an "infinite in two directions" problem by re-slicing it into finite pieces.

A part can be as big as the whole

Infinite sizes behave in ways finite ones never do, and it is worth meeting one such surprise directly. Consider the perfect squares 1, 4, 9, 16, .... They seem far sparser than the natural numbers, thinning out as you go. Yet the pairing that sends each natural number n to n^2 is a bijection between all of N and the squares. Every natural number has exactly one square, and every square comes from exactly one natural number.

So the squares, a seemingly small slice of the naturals, have the very same cardinality as the whole set of naturals. With finite sets this is impossible; a proper part is always strictly smaller. With infinite sets it is routine. This is the heart of the famous "Hilbert's hotel" idea, where a full hotel with infinitely many rooms can still make space for more guests. Once pairing replaces counting, our finite intuitions have to be checked carefully.

The reals are uncountable

Everything above might suggest that all infinite sets are countable. They are not, and this is Cantor's most famous result. The real numbers cannot be listed, and the proof is a jewel called the diagonal argument. Here it is for the reals between 0 and 1.

Theorem. The set of real numbers in the interval from 0 to 1 is uncountable.

Proof (diagonal argument). Suppose, for contradiction, that we could list them all as decimals.

1. Write the supposed complete list as r1 = 0.d11 d12 d13 ..., then r2 = 0.d21 d22 d23 ..., then r3 = 0.d31 d32 d33 ..., and so on, where each dij is a decimal digit. (Assume the list captures every real in the interval.)
2. Now build a new number x = 0.b1 b2 b3 ... by walking down the diagonal. For each position k, look at the diagonal digit dkk, and choose bk to differ from it: say bk = 5 if dkk is not 5, and bk = 4 if dkk is 5. (This makes x disagree with row k in position k.)
3. By construction, x differs from r1 in the first digit, from r2 in the second digit, and in general from rk in the k-th digit. (So x is on no row of the list.)
4. But x is a real number between 0 and 1, so it should have been somewhere on the list. This contradicts the assumption that the list contained every such real. (The impossibility.)

The assumption that the reals in the interval could be listed leads to a contradiction, so no such list exists, and the reals in that interval are uncountable. QED. Sit with the cleverness of that construction: from any proposed list, the diagonal recipe manufactures a number the list forgot.

Why this matters: infinity has sizes

The consequence is profound. There are strictly more real numbers than natural numbers, so infinity is not a single thing but comes in different sizes. The countable infinity shared by N, Z, and Q is genuinely smaller than the uncountable infinity of R. Before Cantor, "infinite" sounded like one idea; after him, it became a landscape with levels. That reframing was among the most startling discoveries in the history of mathematics, and it grew directly from the humble idea of pairing.

An endless tower of infinities

Cantor did not stop at two sizes. The same diagonal idea, applied more generally, shows that the power set of any set is always strictly larger than the set itself. Since the power set is again a set, you can take its power set, and its power set, without end. That means there is no largest infinity; the sizes climb forever, level upon level.

You do not need the details of that generalization now, but the takeaway reshapes how "infinite" should feel. Instead of a single endpoint, infinity is an unbounded staircase of ever-larger sizes, with the countable infinity of N merely the first step. The reals sit above it, and above the reals sit larger sizes still. From one simple tool, comparing by pairing, an entire hierarchy opens up, and that is a fair candidate for the most beautiful chain of reasoning in the whole course.

Where people get stuck

The first hurdle is the instinct that all infinite sets must be the same size. The diagonal argument is the antidote: it proves, with full rigor, that no list can exhaust the reals, so their infinity strictly exceeds the countable one.

The second is doubting that the diagonal number really avoids every row. The point is precise: x was built to differ from row k in the k-th digit, for every k. Since two decimals that differ in some digit are different numbers, x cannot equal any row, so it is missing from the list.

Why countability is a useful label

Calling a set countable is more than a curiosity; it tells you the set can be processed one element at a time. If you can list a set as a1, a2, a3, ..., then you can reason about its elements in order, apply induction along the list, or run a procedure that visits each element in turn and is sure to reach any particular one. Uncountable sets do not offer this, which is one reason the countable-versus-uncountable line matters far beyond pure curiosity.

This is why the countability of the rationals is genuinely handy, not just surprising. It means every rational number can be reached by a systematic enumeration, so arguments that "go through all the rationals" are on solid ground. The uncountability of the reals, by contrast, warns you that no such enumeration of all real numbers can exist, so proofs about the reals must use other tools.

Try it: countable or not?

Is the set of even natural numbers countable? Give a reason.

Yes. The pairing that sends each natural number n to the even number 2n lists the evens as 2, 4, 6, 8, ..., reaching every even number exactly once. That is a bijection with N, so the even naturals are countably infinite. Nicely argued, and notice you just showed a proper subset of N has the same size as N.

Recap

• Cardinality is compared by bijections: |A| = |B| exactly when their elements pair up perfectly.
• A set is countable if finite or listable as a1, a2, a3, ...; the integers Z and rationals Q are both countable.
• Infinite sets can match proper parts of themselves, as N matches the perfect squares.
• The reals are uncountable, proved by Cantor's diagonal argument, which builds a real missing from any proposed list.
• Infinity comes in different sizes: countable N, Z, Q are strictly smaller than the uncountable R.

Sources

1. Hammack, R. (2018). Chapter 14: Cardinality of sets. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
2. Weisstein, E. W. (n.d.). Cantor diagonal method. MathWorld: A Wolfram web resource. mathworld.wolfram.com
3. Encyclopedia of Mathematics. (n.d.). Countable set. European Mathematical Society. encyclopediaofmath.org
4. Encyclopedia of Mathematics. (n.d.). Cardinal number. European Mathematical Society. encyclopediaofmath.org
5. Encyclopedia of Mathematics. (n.d.). Continuum hypothesis. European Mathematical Society. encyclopediaofmath.org
6. MacTutor History of Mathematics Archive. (n.d.). Georg Cantor. University of St Andrews. mathshistory.st-andrews.ac.uk
7. MacTutor History of Mathematics Archive. (n.d.). Infinity. University of St Andrews. mathshistory.st-andrews.ac.uk

Combinatorics is the art of counting without listing. When there are millions of possibilities, writing them all out is hopeless, so we need principles that count them for us. This lesson builds those principles from the ground up, then uses them to count arrangements and selections, two ideas that power everything from probability to computer science.

Two counting principles underlie almost everything, and both are simple once stated plainly.

• Multiplication principle: if a task is a sequence of independent choices, with m ways to make the first and n ways to make the second, then there are m * n ways in total. This extends to any number of stages.
• Addition principle: if a task can be done in one of several disjoint ways, with m options in the first category and n in the second and no overlap, then there are m + n ways in total.

Numbers make these concrete. Choosing an outfit from 3 shirts and 4 pants gives 3 * 4 = 12 outfits, because you pick a shirt and then pick pants, two stages, so you multiply. Choosing a single item that is either one of 3 shirts or one of 4 pants gives 3 + 4 = 7 options, because the categories do not overlap, so you add.

Multiply for "and", add for "or"

The quickest way to tell the principles apart is to listen for a hidden "and" or "or." When a task means doing one thing and then another, the choices stack in stages, and you multiply. When a task means picking from this group or that group, with no double counting, you add. Shirt and pants is an "and," so multiply. Shirt or pants, choose one item, is an "or," so add.

One caution keeps the addition principle honest: the categories must be disjoint, with nothing counted twice. If some item could belong to both groups, you would count it in each and overcount the total. When groups overlap, you subtract the shared part back out, an idea called inclusion-exclusion, but the clean addition principle applies only when the groups truly do not meet.

Key idea: multiply choices made in stages ("and"), add choices from disjoint categories ("or").

A multi-stage example

The multiplication principle scales to many stages, so let us count something bigger. Suppose a simple padlock code has 4 positions, and each position can be any digit from 0 to 9. How many codes are possible?

Each position is an independent stage with 10 choices, and there are 4 positions, so we multiply 10 by itself 4 times: 10 * 10 * 10 * 10 = 10000 codes. The reasoning is the same as the outfit example, just with more stages.

Now change the rules slightly: suppose no digit may repeat. Then the first position has 10 choices, the second has 9 left, the third has 8, and the fourth has 7, giving 10 * 9 * 8 * 7 = 5040. That second count is exactly the permutation P(10, 4), which shows how permutations are really the multiplication principle applied to an ordered, no-repeat selection.

A counting proof, start to finish

Real problems often need both principles inside one argument, so let us run a complete count slowly and give a reason at every step. Question: how many 3-digit numbers, from 100 to 999, have all three digits different?

1. Step 1: the hundreds digit. It can be 1 through 9 but not 0, or the number would only have two digits. That is 9 choices.
2. Step 2: the tens digit. Any of the ten digits works except the one already used. Reason: the no-repeat rule removes exactly one option, leaving 9 choices.
3. Step 3: the units digit. Two different digits are now taken, so 8 choices remain.
4. Step 4: combine. The stages happen one after another, an "and," so the multiplication principle applies: 9 * 9 * 8 = 648 numbers.

Pause on what made Step 4 legal. The count at each stage did not depend on which digits were chosen earlier, only on how many were used up. That is exactly the condition the multiplication principle needs. When a stage's count does change with earlier choices, you split the problem into cases, count each case separately, and add the disjoint cases with the addition principle. You just carried out a full counting argument, stage by stage, with every step justified. That is proof-writing applied to counting.

Factorials and permutations

The factorial of n, written n! and read "n factorial," is the product n * (n-1) * ... * 2 * 1, with the special convention that 0! = 1. So 4! = 4 * 3 * 2 * 1 = 24. Factorials count arrangements, as we are about to see.

A permutation is an ordered arrangement of objects. The number of ways to arrange n distinct objects in a row is n!, and the multiplication principle explains why: there are n choices for the first position, then n - 1 for the second, then n - 2 for the third, and so on down to 1. Multiplying those stage counts gives n!.

Often you arrange only some of the objects. The number of ways to place r of the n objects in order is

P(n, r) = n! / (n - r)!.

Worked example. How many ways can a president, vice president, and treasurer be chosen from a club of 10 people? The three roles are distinct, so order matters, and this is a permutation: P(10, 3) = 10! / 7! = 10 * 9 * 8 = 720. Reading it through the multiplication principle, there are 10 choices for president, then 9 for vice president, then 8 for treasurer.

Combinations

A combination is an unordered selection, that is, a subset where order does not matter. The number of ways to choose r objects from n without regard to order is the binomial coefficient

C(n, r) = n! / [r! (n - r)!], read "n choose r."

Where does the extra r! in the denominator come from? It divides out the orderings that a permutation counts separately. Each unordered group of r objects can be arranged in r! different orders, and a combination should count all of those as the same selection, so we divide the permutation count by r!.

Worked example. How many 3-person committees can be formed from 10 people? Now the members have no distinct roles, so order does not matter, and this is a combination: C(10, 3) = 10! / (3! * 7!) = (10 * 9 * 8)/(3 * 2 * 1) = 720/6 = 120. There are 120 committees, exactly one-sixth of the 720 role-assignments, because each committee could be arranged in 3! = 6 orders.

Permutation or combination?

The single question that settles which tool to use is: if I swap two of the chosen items, is it a different outcome? If yes, order matters and you want a permutation. If no, order is irrelevant and you want a combination. Roles like president and treasurer make swapping matter, so permutation. Seats on an unlabeled committee do not, so combination.

The relationship between them is worth remembering. Because each selection of r items can be ordered in r! ways, we always have P(n, r) = r! * C(n, r). In our examples, P(10, 3) = 720 is exactly 3! = 6 times C(10, 3) = 120. Permutations count ordered arrangements; combinations count unordered selections; the factor of r! bridges the two.

Key idea: use a permutation when order matters, a combination when it does not, and P(n, r) = r! * C(n, r) links them.

Combinations count subsets

There is a satisfying connection back to the set theory of Module 3. Choosing r objects from n, with order ignored, is precisely choosing a subset of size r from an n-element set. So C(n, r) counts the r-element subsets, and the binomial coefficient is really a subset counter in disguise.

This ties into a fact we met earlier: a set with n elements has 2^n subsets in total. If you instead count subsets by size, adding up the number of subsets of size 0, size 1, size 2, up to size n, you must get the same total. In symbols, the sum of C(n, 0) + C(n, 1) + ... + C(n, n) equals 2^n.

The two ways of counting all subsets, one by an in-or-out choice per element and one by grouping according to size, have to agree, and that agreement is a small proof in itself. Seeing counting and set theory reinforce each other like this is one of the quiet pleasures of the subject.

Two identities with counting proofs

Binomial coefficients obey two identities that save real work, and each can be proved by pure counting, with no factorial algebra at all. The first is the symmetry rule:

C(n, r) = C(n, n - r).

Why should choosing 7 people from 10 equal choosing 3 from 10? Because every choice of who is in is automatically a choice of who is out. Selecting the 7 committee members is the very same act as selecting the 3 people left off, so the two counts must agree: C(10, 7) = C(10, 3) = 120. In practice, when r is more than half of n, count the leftovers instead; it is the same answer with smaller numbers.

The second identity is Pascal's rule, and its proof is the addition principle doing exactly what it was built for:

C(n, r) = C(n - 1, r - 1) + C(n - 1, r).

1. Step 1: split into two disjoint cases. Fix one particular person in the group of n, say Ana. Every committee of r people either includes Ana or leaves her out, and never both, so these two categories are disjoint and cover every committee.
2. Step 2: count the committees that include Ana. Her seat is settled, so we choose the remaining r - 1 members from the other n - 1 people: C(n - 1, r - 1) ways.
3. Step 3: count the committees that leave Ana out. All r members now come from the other n - 1 people: C(n - 1, r) ways.
4. Step 4: add. Disjoint categories add, so the total is C(n - 1, r - 1) + C(n - 1, r), and it must equal C(n, r) because both sides count the same committees.

An argument like this is called a combinatorial proof: it shows two expressions are equal by showing that they count the same collection of objects in two different ways. It is a genuine proof technique, every bit as rigorous as the methods of Module 4, and it often explains an identity better than the algebra does. You have now proved a famous identity with nothing but a well-chosen case split.

Where people get stuck

The first and biggest error is choosing the wrong tool because you did not ask about order. Always run the swap test before computing. Mislabeling a problem is far more common than making an arithmetic slip.

The second is forgetting the disjointness condition when adding. If you add the sizes of two overlapping groups, you count the shared items twice. Check that your categories really do not meet before you reach for the addition principle.

The third is mixing up which count goes on top. In both P(n, r) and C(n, r), the n! is on top and the (n - r)! is on the bottom, with combinations carrying the extra r! below. Writing the formula out fully before plugging in numbers avoids this.

Try it: count the handshakes

At a party of 6 people, everyone shakes hands once with everyone else. How many handshakes occur?

A handshake is an unordered pair of people, since your shaking my hand is the same event as my shaking yours, so this is a combination: C(6, 2) = 6! / (2! * 4!) = (6 * 5)/(2 * 1) = 30/2 = 15. There are 15 handshakes. If you had treated it as ordered, you would have doubled it to 30, so the swap test really mattered. Nicely done.

Recap

• The multiplication principle multiplies choices made in stages ("and"); the addition principle adds choices from disjoint categories ("or").
• A factorial n! counts the arrangements of n objects, with 0! = 1.
• A permutation is an ordered arrangement: P(n, r) = n! / (n - r)!.
• A combination is an unordered selection: C(n, r) = n! / [r! (n - r)!], read "n choose r."
• Ask "does swapping change the outcome?" to choose the tool, and recall P(n, r) = r! * C(n, r).
• Counting arguments can prove identities: C(n, r) = C(n, n - r) because choosing who is in is choosing who is out, and Pascal's rule C(n, r) = C(n - 1, r - 1) + C(n - 1, r) follows by splitting on one fixed person. Such two-way counts are called combinatorial proofs.

Sources

1. OpenStax. (2023). 7.1 The multiplication rule for counting. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 7.2 Permutations. In Contemporary mathematics. Rice University. openstax.org
3. OpenStax. (2023). 7.3 Combinations. In Contemporary mathematics. Rice University. openstax.org
4. Hammack, R. (2018). Chapter 3: Counting. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
5. Levin, O. (n.d.). 1.1 Additive and multiplicative principles. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
6. Levin, O. (n.d.). 1.3 Combinations and permutations. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
7. Encyclopedia of Mathematics. (n.d.). Binomial coefficients. European Mathematical Society. encyclopediaofmath.org

The pigeonhole principle is a deceptively simple idea with surprising reach. In its basic form:

If n + 1 pigeons are placed into n holes, then some hole contains at least two pigeons.

The reasoning is immediate: if every hole held at most one pigeon, the holes could accommodate at most n pigeons, but we have n + 1. The power of the principle lies entirely in cleverly choosing what the "pigeons" and "holes" are.

Here is the everyday picture. A chest of drawers has 9 drawers, and you own 10 shirts. However you put the shirts away, some drawer ends up holding two. You have believed this your whole life without ever calling it mathematics. The pigeonhole principle simply gives that belief a name and a precise statement, and this lesson turns it into a genuine proof tool.

Two features make the principle special. First, it proves that something exists without ever finding it: it tells you two pigeons share a hole, but not which two pigeons and not which hole. Proofs like this are called nonconstructive, and writing your first one is a real milestone in a proof course. Second, the principle needs almost no computation. Most pigeonhole proofs are a few sentences long once the pigeons and holes are chosen well. All the real work, and all the cleverness, sits in that choice.

Simple applications

• Among any 13 people, at least two share a birth month, since there are only 12 months (holes) for 13 people (pigeons).
• In any group of 367 people, at least two share a birthday, because there are at most 366 possible dates.
• Pull 4 socks from a drawer that holds socks in 3 colors, and two of the socks you pulled must match, since 4 pigeons (your pulled socks) land in 3 holes (the colors).
• Two residents of any city of more than a million people have exactly the same number of hairs on their head, because a human head carries well under a million hairs. The residents are the pigeons, and the possible hair counts are the holes.

Read each example the same way: name the objects, name the categories, and check that the objects outnumber the categories. Nothing else is needed. Notice also what the conclusion does not say. It does not tell you which two people share a birth month, or which drawer got crowded. Existence is the entire claim, and for a surprising number of theorems, existence is all you need.

Why the principle is true: a two-line contradiction

The principle sounds obvious, and it is, but "obvious" is not a proof. Proving it takes two lines with the contradiction method from Module 4, and watching the proof go by is worth the minute it costs.

1. Step 1: suppose the conclusion fails. Assume every one of the n holes contains at most one pigeon. Reason: proof by contradiction starts by assuming the negation of what we want to show.
2. Step 2: count the pigeons. Adding over all the holes, the total number of pigeons is at most n * 1 = n. Reason: each of the n holes contributes at most one pigeon to the total.
3. Step 3: find the contradiction. We placed n + 1 pigeons, and n + 1 > n, so the total would be both at most n and more than n. That is impossible, so the assumption fails, and some hole holds at least two pigeons. QED.

That is the whole proof, and you have now proved the tool before using it, which is exactly the standard mathematics asks of you. There is also a useful contrapositive reading of the principle: if every hole holds at most one pigeon, then there are at most n pigeons in total. Same fact, arrow reversed, and sometimes that direction is the convenient one to quote.

The generalized pigeonhole principle

If N pigeons occupy k holes, then some hole contains at least ceil(N / k) pigeons, where ceil rounds up to the nearest integer. For instance, distributing 100 pigeons among 9 holes forces some hole to hold at least ceil(100/9) = ceil(11.1) = 12 pigeons. This refined version quantifies how crowded the busiest hole must be.

Read the notation aloud before leaning on it: ceil(x) is "the ceiling of x," the smallest integer that is greater than or equal to x. So ceil(11.1) = 12, and ceil(7) = 7, since a whole number is its own ceiling. The basic principle is the special case of N = n + 1 pigeons in k = n holes, because ceil((n + 1)/n) = 2.

The proof of the generalized form runs on the very same contradiction, with one extra observation about ceilings.

1. Step 1: suppose the conclusion fails. Assume every hole holds at most ceil(N / k) - 1 pigeons, one below the claimed crowding.
2. Step 2: bound the total. The total is then at most k * (ceil(N / k) - 1). Now the key fact: ceil(N / k) - 1 is strictly less than N / k, because the ceiling of a number sits less than 1 above it. Multiplying by k keeps the inequality, so the total is strictly less than N.
3. Step 3: contradiction. We placed exactly N pigeons, so the total cannot be less than N. The assumption fails, and some hole holds at least ceil(N / k) pigeons. QED.

A quick check with real numbers: in a class of 25 students, the 12 birth months are the holes, and ceil(25/12) = ceil(2.08) = 3, so at least three students share a birth month. The basic principle would only promise two. The generalized version sharpens the promise as the pigeons pile up.

How to choose the pigeons and the holes

Every pigeonhole proof stands or falls on one creative decision, so the decision deserves a checklist. Ask three questions, in order. First: what do I have many of? Those are the pigeons. Second: what finite set of labels can I attach, one label per object? Those are the holes. Third: do the objects strictly outnumber the labels? If yes, the principle hands you two objects wearing the same label, and the conclusion is usually one short sentence away.

There is also a signal worth memorizing. Conclusions shaped like "some two of them agree," with phrases such as "at least two share" or "there exist two with the same," rarely yield to direct computation, because you know nothing about the individual objects. Categories are the workaround: you do not need to know where any particular pigeon goes, only that there are too few holes for them all to sit alone.

Worked example: a proof by pigeonhole

Theorem. Among any 5 integers, some two have a difference divisible by 4.

Proof. When any integer is divided by 4, its remainder is one of exactly four values: 0, 1, 2, or 3. Make these four remainders the holes and the five integers the pigeons. Since 5 pigeons go into 4 holes, by the pigeonhole principle at least two of the integers, say a and b, land in the same hole, meaning they have the same remainder modulo 4. Then a and b are congruent modulo 4, so 4 divides a - b. Therefore some two of the five integers have a difference divisible by 4. QED.

Notice the pattern of every pigeonhole proof: identify a finite set of categories (the holes), argue that you have more objects than categories (the pigeons), and conclude that two objects must share a category. Choosing remainders as holes is an especially common and powerful trick, tying combinatorics back to the modular arithmetic of Module 6. Once you learn to spot the pigeons and the holes, existence claims that look impossible to prove directly become almost immediate.

A second worked proof: equal friend counts

The next theorem is a favorite because the obvious labeling almost works, and one small repair finishes the job. For this problem, say two people are friends only when each counts the other as a friend, so friendship goes both ways.

Theorem. In any group of n >= 2 people, some two people have the same number of friends within the group.

1. Step 1: label each person. Give each person the number of friends they have inside the group. Each label is one of the n values 0, 1, 2, and so on up to n - 1. Reason: you are not your own friend, so n - 1 is the largest count possible.
2. Step 2: shrink the holes. The labels 0 and n - 1 cannot both occur. If someone is friends with everyone else, their label is n - 1, and then no one can have label 0, since everyone has at least that one friend. If instead someone has label 0, no one can reach n - 1. Either way, at most n - 1 distinct labels actually appear.
3. Step 3: apply the principle. There are n people (pigeons) and at most n - 1 labels in use (holes), so two people carry the same label. That is exactly the claim. QED.

The move in Step 2 is the one to remember. A first count of the holes gave n, which matches the pigeons, and equal counts force nothing. Instead of stopping there, we looked closer and showed two of the holes exclude each other, which trimmed the count to n - 1. Shrinking the holes until the pigeons outnumber them is a standard repair. You will meet this exact theorem again in the next lesson, dressed in graph clothing: it says that two vertices of any graph share a degree.

A third worked proof: five points in a square

Pigeonholing works in geometry too, and there the holes are usually regions you invent. Here sqrt(2) is read "the square root of 2" and is about 1.41.

Theorem. Among any 5 points inside a square of side 2, some two points are at most sqrt(2) apart.

1. Step 1: build the holes. Cut the big square into four 1-by-1 squares, like a window with four panes. Reason: the problem hands us no categories, so we manufacture them, and four panes will be beaten by five points.
2. Step 2: place the pigeons. Each of the 5 points lies in one of the 4 panes. If a point sits exactly on a dividing line, assign it to either pane that touches it; every point still gets exactly one home. With 5 points in 4 panes, two points, say p and q, share a pane.
3. Step 3: measure. The farthest apart two points of a 1-by-1 square can be is its diagonal, which the Pythagorean theorem gives as sqrt(1^2 + 1^2) = sqrt(2). So p and q are at most sqrt(2) apart. QED.

All the creativity lived in Step 1. Nothing in the statement mentions panes; we invented four regions precisely so that five points would overload them. Choosing geometric holes, such as cells, strips, or arcs, is the standard way to pigeonhole in geometry, and the final step then leans on ordinary measuring tools.

Running the principle backwards: guarantees

So far we asked what a given pile of pigeons forces. Flip the question: how many pigeons must you gather to force a repeat? With k holes, the answer is k + 1, because k pigeons might spread out one per hole, and the next pigeon has nowhere new to go. Planning around the worst case, everything spread as thinly as possible, is the standard way to answer guarantee questions.

The generalized form flips the same way. To force some hole to hold t + 1 pigeons, you need k * t + 1 of them, since k * t pigeons could sit exactly t per hole. With socks in 4 colors, for example, 4 * 2 + 1 = 9 pulls guarantee three socks of one color, while 8 pulls might land exactly two of each.

Where people get stuck

The most frequent slip is concluding from equal numbers of pigeons and holes. Twelve people and twelve months force nothing, since everyone could claim a different month. The principle fires only when the pigeons strictly outnumber the holes, so check the inequality N > k before announcing a shared hole.

The second is expecting the principle to point at the pair. It proves that two objects agree, and it stops there: no procedure, no names. If a problem asks you to identify which two, pigeonholing alone will not do it. Existence is the entire product, which is exactly why the proofs can be so short.

The third is rounding down in the generalized form. The busiest hole holds at least the ceiling of N / k, not the floor. With 100 pigeons in 9 holes the guarantee is 12, not 11, because if every hole stopped at 11 the total would be at most 99. When the division comes out exact, ceiling and floor agree, and either reading is fine.

Try it: force a matching pair

A drawer holds loose socks in 4 colors. Pulling socks without looking, how many must you take to be certain of a matching pair?

Count the holes first: 4 colors. The worst case takes one sock of each color, 4 socks and no pair, and that is still legal. The 5th sock has no fifth color to hide in, so it must match one already drawn: 4 + 1 = 5 socks guarantee a pair. Nice work. You named the holes, played the worst case to its end, and let the principle close the argument, which is the shape of every guarantee proof.

Recap

• The pigeonhole principle: placing n + 1 pigeons in n holes forces some hole to hold at least two, proved in two lines by contradiction.
• The generalized form: N pigeons in k holes force some hole to hold at least ceil(N / k), read "the ceiling of N over k."
• Recipe: the pigeons are your objects, the holes are the labels you attach, and the pigeons must strictly outnumber the holes.
• The principle is nonconstructive: it proves two objects share a category without naming either one.
• Guarantee direction: k + 1 objects force a pair, and k * t + 1 objects force t + 1 alike.
• Standard hole choices include remainders modulo n, calendar categories, colors, friend counts, and invented geometric cells.

Sources

1. Weisstein, E. W. (n.d.). Pigeonhole principle. MathWorld: A Wolfram web resource. mathworld.wolfram.com
2. Hammack, R. (2018). Section 3.9: The division and pigeonhole principles. In Book of proof (3rd ed.). Virginia Commonwealth University. richardhammack.github.io
3. Levin, O. (n.d.). 1: Counting. In Discrete mathematics. LibreTexts. math.libretexts.org
4. LibreTexts Mathematics. (n.d.). Combinatorics (Morris). math.libretexts.org
5. LibreTexts Mathematics. (n.d.). A spiral workbook for discrete mathematics (Kwong). math.libretexts.org
6. Ramsey, F. P. (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1), 264-286. doi.org/10.1112/plms/s2-30.1.264
7. Sundstrom, T. (n.d.). Mathematical reasoning: Writing and proof, version 3. Grand Valley State University. scholarworks.gvsu.edu

A graph is a mathematical model of a network. It consists of a set of vertices (also called nodes) and a set of edges, each edge joining a pair of vertices. Graphs model roads between cities, friendships in a social network, links between web pages, and much more. We write G = (V, E) for the graph with vertex set V and edge set E.

This closing lesson gathers nearly everything you have built in the course, sets, relations, counting, induction, and pigeonholing, and points it all at one concrete kind of object: dots joined by lines. That really is the whole object. The dots are vertices, the lines are edges, and every definition below is a plain sentence about dots and lines made precise.

The subject has a famous birthplace. In 1736, the city of Königsberg had seven bridges linking two islands and two riverbanks, and residents wondered whether one walk could cross every bridge exactly once. Leonhard Euler settled the question by ignoring almost everything: the size of the islands, the lengths of the bridges, the bends of the river. He kept only the record of which land masses connect to which, four dots and seven lines, and proved the walk impossible. That act of stripping a problem down to dots and lines founded graph theory.

Read the picture the way you read notation. This graph has vertex set V = {A, B, C, D}, and its edge set E holds five edges: AB, AC, BD, CD, and the diagonal AD. Where a vertex sits on the page, and whether an edge is drawn long, short, straight, or curved, carries no meaning at all. Only the pattern of connections counts, so the same graph can be drawn in many different ways. That indifference to drawing is a strength: one theorem about the pattern covers subway maps, molecule diagrams, and server networks at once.

Degree and the handshaking lemma

The degree of a vertex is the number of edges meeting it. In the graph above, vertex A has degree 3 (edges to B, C, and D), while B, C, and D have degrees 2, 2, and 3. A cornerstone result connects degrees to edges.

Check those numbers yourself against the figure, one vertex at a time. A meets B along the top, C down the left side, and D along the diagonal, so its degree is 3. B meets A and D, degree 2. C meets A and D, degree 2. D meets B, C, and A, degree 3. The degree sum is 3 + 2 + 2 + 3 = 10, and the graph has 5 edges, so the sum came out exactly twice the edge count. That is no accident, and the next result says so.

Handshaking lemma. In any graph, the sum of all vertex degrees equals twice the number of edges: sum of degrees = 2 |E|.

Read |E| aloud as "the size of E," the number of edges. The lemma's name comes from a party picture: if each person's degree is the number of hands they shook, the lemma says the personal counts add up to twice the number of handshakes, because every handshake supplies two hands.

Proof. Each edge has two endpoints, so it contributes exactly 1 to the degree of each of its two vertices, that is 2 in total to the degree sum. Adding over all edges, the total degree count is 2 |E|. QED. An immediate consequence is that the number of vertices with odd degree is always even, since the degrees must sum to an even number. This is why, at any party, the number of people who have shaken hands an odd number of times is even.

That consequence deserves a slower walk, because its style of argument, splitting a sum and reasoning about parity, appears all over mathematics.

1. Step 1: split the degree sum. Sort the vertices into two piles, those of even degree and those of odd degree. The degree sum is the even pile's total plus the odd pile's total. Reason: every vertex lands in exactly one pile.
2. Step 2: handle the even pile. A sum of even numbers is even, so the even pile contributes an even total.
3. Step 3: force the odd pile. The whole sum equals 2 |E|, which is even, so the odd pile's total must be even as well. But a sum of odd numbers is even exactly when there is an even number of them. So the count of odd-degree vertices is even. QED.

This little parity theorem already reaches the heart of Königsberg. A walk that crosses every bridge exactly once forces every land mass to have even degree, except possibly the two where the walk starts and ends. Königsberg's four land masses all had odd degree, too many odd vertices, so no such walk exists. You just resolved a genuine historical puzzle with a counting argument. Well reasoned.

One more payoff arrives free of charge. Last lesson you proved that in any group of people, two have the same number of friends. Translate the words: people become vertices, friendships become edges, and friend counts become degrees. The theorem now reads: in any graph with at least two vertices, some two vertices have the same degree. Same proof, new costume. When a theorem survives a change of costume this smoothly, it is a sign you proved something structural, not something about people.

Paths, cycles, and connectedness

• A path is a sequence of distinct vertices, each joined to the next by an edge, like A - B - D.
• A cycle is a path that returns to its start without repeating an edge, like A - B - D - A.
• A graph is connected if there is a path between every pair of vertices; otherwise it splits into separate pieces called components.

Practice reading these on the figure. Can you travel from C to B? Yes, in at least two ways: C - A - B and C - D - B, so C and B are linked. The route A - B - D - A leaves A, visits B and D, and returns home along the diagonal without reusing an edge, so it is a cycle. Since every pair of vertices in the figure can reach each other, this graph is connected.

For contrast, picture six vertices forming two separate triangles with no edge between the triangles. Each triangle is fine on its own, but no path crosses the gap, so the graph is not connected; it has two components. Here is a tidy connection to Module 6: the relation "there is a path from x to y" is reflexive, symmetric, and transitive, so it is an equivalence relation on the vertices, and its equivalence classes are exactly the components. A definition from relations quietly organizes every graph you will ever meet.

A few named graphs

• A complete graph K_n has an edge between every pair of its n vertices, giving C(n, 2) = n(n-1)/2 edges, a direct payoff of the counting from earlier in this module.
• A tree is a connected graph with no cycles; a tree on n vertices always has exactly n - 1 edges.
• A bipartite graph splits its vertices into two groups with edges only running between the groups, never within one, which models pairings like students to courses.

Counting the edges of K_n, two ways

The claim that K_n has n(n-1)/2 edges is worth proving twice, once with each hat from this module, because two independent arguments that agree confirm each other.

1. Proof 1: combinations. An edge of K_n is exactly an unordered pair of distinct vertices, and last lesson counted those: C(n, 2) = n(n-1)/2. Reason: "choose 2 from n, order irrelevant" is precisely what C(n, 2) counts. One line, done.
2. Proof 2: the handshaking lemma. In K_n every vertex joins the other n - 1 vertices, so every degree is n - 1, and the degree sum is n(n - 1). The lemma says this sum is twice the edge count, so |E| = n(n-1)/2. Reason: halving an exact double recovers the original.

Check it small. K_4 should have 4 * 3 / 2 = 6 edges, and our figure is one edge short of K_4: it has 5 edges and is missing only B - C. Everything agrees. Reaching the same number by two unrelated routes is one of the most satisfying experiences in mathematics, and it is also how mathematicians catch their own slips.

A proof to grow on: why trees have n - 1 edges

The tree fact in the list above is exactly the kind of statement Module 5 trained you for, and the proof is induction on the number of vertices. Two helper facts feed it. First, every tree with at least 2 vertices has a leaf, a vertex of degree 1. Why: take a longest possible path in the tree and look at its final vertex. Any further neighbor would either extend the path, impossible since the path was longest, or close a cycle with an earlier vertex, impossible in a tree. So the final vertex touches only one edge.

Second, deleting a leaf and its single edge leaves a smaller tree, still connected and still cycle-free. With those two facts in hand, the induction almost writes itself.

1. Base case. A tree with 1 vertex has 0 edges, and 1 - 1 = 0, so the formula holds at the start.
2. Inductive step. Assume every tree with k vertices has k - 1 edges. Take any tree with k + 1 vertices, pick a leaf, and remove it together with its one edge. What remains is a tree with k vertices, so by the hypothesis it has k - 1 edges. Restoring the removed leaf and edge gives (k - 1) + 1 = k edges, and k = (k + 1) - 1, exactly the formula for k + 1 vertices.
3. Conclusion. By the principle of mathematical induction, every tree on n vertices has exactly n - 1 edges. QED.

Watch how much of the course showed up in that one proof. Induction supplied the frame, a small direct argument found the leaf, and the definitions of connected and cycle-free did the quiet load-bearing. Trees repay the effort: they model file systems, family descent, decision procedures, and the cheapest networks that still reach everyone.

Where people get stuck

The most common early error is reading meaning into the drawing. A long curvy edge is the same as a short straight one, and a vertex drawn in a corner is no different from one in the center. Two diagrams that look nothing alike can be the same graph. When in doubt, write out the vertex set and the edge set and compare those, not the pictures.

The second is forgetting to divide by 2. The degree sum counts every edge twice, once from each end, so the number of edges is half the degree sum, never the sum itself. And if a proposed degree list adds up to an odd number, stop: the handshaking lemma says no graph can produce it.

The third is blurring path and cycle. A path visits distinct vertices and ends somewhere new; a cycle comes home. Also, not every graph is connected, so before speaking of "the" path between two vertices, check that any path exists at all.

Try it: read a network

A graph has 5 vertices with degrees 3, 3, 2, 1, and 1. How many edges does it have? And second: could any graph have exactly three vertices of odd degree?

For the first, the degree sum is 3 + 3 + 2 + 1 + 1 = 10, and the handshaking lemma makes the edge count half of that: 5 edges. For the second, three odd-degree vertices would make the count of odd-degree vertices odd, and we proved that count is always even, so no such graph exists. Nice work: you used the lemma forward to count edges and backward to rule a graph out, the two opening moves of almost every graph argument.

Recap

• A graph G = (V, E) is a set of vertices joined by edges; only the pattern of connections matters, never the drawing.
• The degree of a vertex counts the edges meeting it, and the handshaking lemma says the degree sum equals 2 |E|, so the number of odd-degree vertices is always even.
• Paths travel through distinct vertices, cycles return to their start, and a graph is connected when every pair of vertices is joined by some path; "reachable by a path" is an equivalence relation whose classes are the components.
• K_n has C(n, 2) = n(n-1)/2 edges, provable by combinations or by handshaking, and a tree on n vertices has n - 1 edges, provable by induction after removing a leaf.
• Bipartite graphs model pairings, and every proof method from the course, direct, contrapositive, contradiction, induction, counting, and pigeonhole, reappears as a working graph tool.

Graph theory turns questions about networks into precise mathematics, and the proof techniques you have practiced, direct argument, counting, and pigeonholing, are exactly the tools that graph theorists use. This introduction is the doorway to a rich subject that touches computer science, operations research, and the study of the internet itself. Congratulations on completing the course.

Sources

1. OpenStax. (2023). 12.1 Graph basics. In Contemporary mathematics. Rice University. openstax.org
2. OpenStax. (2023). 12.2 Graph structures. In Contemporary mathematics. Rice University. openstax.org
3. Levin, O. (n.d.). 4.1 Definitions. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
4. Levin, O. (n.d.). 4.2 Trees. In Discrete mathematics: An open introduction (3rd ed.). discrete.openmathbooks.org
5. Encyclopedia of Mathematics. (n.d.). Graph theory. European Mathematical Society. encyclopediaofmath.org
6. Alexanderson, G. L. (2006). About the cover: Euler and Königsberg's bridges: A historical view. Bulletin of the American Mathematical Society, 43(4), 567-573. doi.org/10.1090/S0273-0979-06-01130-X
7. Hopkins, B., & Wilson, R. J. (2004). The truth about Königsberg. The College Mathematics Journal, 35(3), 198-207. doi.org/10.1080/07468342.2004.11922073