Introduction to Proof & Discrete Math

Every proof is a chain of statements, so we begin with the atom of logic: the proposition. A proposition is a declarative sentence that is either true or false, but not both. "7 is a prime number" is a proposition (true). "The integer 12 is odd" is a proposition (false). By contrast, "What time is it?" and "Solve this equation" are not propositions because they make no claim, and "x + 1 = 5" is not a proposition on its own because its truth depends on the value of x. We usually name propositions with letters like P, Q, and R.

The five connectives

We build larger statements from smaller ones using logical connectives. Each has a symbol and a fixed meaning:

• Negation ~P ("not P"): true exactly when P is false.
• Conjunction P AND Q: true only when both parts are true.
• Disjunction P OR Q: true when at least one part is true. This is the inclusive "or" - it also allows both.
• Conditional P => Q ("if P then Q"): false only when P is true and Q is false.
• Biconditional P <=> Q ("P if and only if Q"): true when both parts have the same truth value.

Understanding the conditional

The conditional P => Q trips up most beginners. Here P is the hypothesis and Q is the conclusion. The statement claims a promise: whenever P holds, Q must follow. The only way to break that promise is for P to be true while Q is false. In every other case the promise is kept, so the conditional is true. In particular, when P is false the conditional is vacuously true, because no promise was ever triggered. For example "if 3 is even, then the moon is made of cheese" is a true statement, simply because the hypothesis is false.

Related conditionals

From P => Q we form three relatives that you must keep straight:

• The converse: Q => P (the parts swapped).
• The inverse: ~P => ~Q (both parts negated).
• The contrapositive: ~Q => ~P (swapped and negated).

A conditional and its contrapositive are always equivalent, they mean the same thing, but a conditional and its converse are not equivalent. "If it is raining, then the ground is wet" does not tell you the ground being wet means it is raining, since a sprinkler could be the cause. Confusing a statement with its converse is one of the most common logical errors, and recognizing the difference will protect your proofs throughout this course.

A truth table lists every possible combination of truth values for the component propositions and computes the resulting value of the whole statement. With n distinct propositions there are 2^n rows, since each proposition can independently be true (T) or false (F). Truth tables let us settle questions of logic mechanically, with no guesswork.

The basic tables

Here are the tables for the conditional and biconditional, the two worth memorizing:

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

Tautologies and contradictions

A tautology is a statement that is true in every row, no matter the inputs, such as P OR ~P (the law of the excluded middle). A contradiction is false in every row, such as P AND ~P. A statement that is sometimes true and sometimes false is called a contingency. Tautologies are the backbone of valid reasoning: a correct argument form is one whose conclusion follows in every case.

Logical equivalence

Two statements are logically equivalent, written with the symbol ===, when they have identical truth tables, the same value in every row. Equivalent statements are interchangeable in any argument. Two equivalences are used constantly in proofs.

Conditional as disjunction. The conditional can be rewritten without an arrow: P => Q === ~P OR Q. You can confirm this by checking that both are false only in the single row where P is true and Q is false.

De Morgan's laws. These describe how negation distributes over AND and OR:

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

In words, the negation of "both" is "at least one fails," and the negation of "at least one" is "both fail." Let us verify the first law with a full truth table:

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

The last two columns match in all four rows, so the equivalence holds. De Morgan's laws are exactly what you use when you negate a complicated statement to set up a proof by contradiction, so they will return again and again.

Propositional logic cannot express "every integer has a successor," because the sentence talks about all integers at once. For that we need predicate logic. A predicate is a statement whose truth depends on one or more variables, such as P(x): "x > 0". On its own P(x) is neither true nor false, but P(3) is true and P(-1) is false. Every predicate comes with a domain (also called the universe of discourse), the set of values the variable may take. Choosing the domain is part of stating the claim.

The two quantifiers

Quantifiers turn a predicate into a genuine proposition by specifying how many elements of the domain satisfy it.

• The universal quantifier FORALL x, P(x) asserts that P(x) is true for every x in the domain. To prove it, you must handle all cases; to disprove it, a single counterexample suffices.
• The existential quantifier EXISTS x, P(x) asserts that P(x) is true for at least one x. To prove it, exhibiting one example (a witness) is enough; to disprove it, you must rule out every element.

For example, over the domain of integers, FORALL x, x^2 >= 0 is true, while EXISTS x, x^2 = 2 is false because no integer squares to 2. Notice how the domain matters: over the real numbers, EXISTS x, x^2 = 2 becomes true, witnessed by the square root of 2.

Nested quantifiers

Statements often stack quantifiers, and order matters. Compare these two claims over the integers:

• FORALL x, EXISTS y, (x + y = 0): for every integer x there is an integer y making the sum zero. True: given x, choose y = -x. Here y is allowed to depend on x.
• EXISTS y, FORALL x, (x + y = 0): there is one fixed integer y that works for every x. False: no single y can cancel every x at once.

The lesson is that reading left to right, an inner quantifier lives "inside" the outer one, so a FORALL x, EXISTS y statement lets the witness y be chosen after x is known, while EXISTS y, FORALL x demands a single witness that works uniformly. Swapping the two quantifiers can change a true statement into a false one, so always read carefully and preserve the order.

Before you can disprove a claim or set up a proof by contradiction, you must know its exact negation. For quantified statements there is a clean rule, sometimes called the quantifier version of De Morgan's laws.

The negation rules

To negate a quantified statement, flip each quantifier and negate the predicate inside:

• ~(FORALL x, P(x)) === EXISTS x, ~P(x). "Not everything satisfies P" means "something fails P."
• ~(EXISTS x, P(x)) === FORALL x, ~P(x). "Nothing satisfies P" means "everything fails P."

This makes intuitive sense. The claim "all swans are white" is false precisely when there exists a swan that is not white. The claim "some student failed" is false precisely when every student did not fail, that is, all passed.

Negating nested quantifiers

For several quantifiers, apply the rule repeatedly, moving the negation inward one quantifier at a time and flipping each as you pass it. Every FORALL becomes EXISTS, every EXISTS becomes FORALL, and the innermost predicate gets negated last.

Worked example. Negate the statement FORALL x, EXISTS y, (x + y = 0).

1. Flip the outer quantifier: ~(FORALL x, ...) becomes EXISTS x, ~(EXISTS y, (x + y = 0)).
2. Flip the next quantifier: ~(EXISTS y, ...) becomes FORALL y, ~(x + y = 0).
3. Negate the predicate: ~(x + y = 0) is x + y != 0.

The finished negation is EXISTS x, FORALL y, (x + y != 0): there is some x such that no y makes the sum zero. Over the integers the original is true, so this negation is correctly false.

Negating a conditional inside a quantifier

Many theorems have the form FORALL x, (P(x) => Q(x)). Recall that a conditional is false only when its hypothesis holds but its conclusion fails, so ~(P => Q) === P AND ~Q. Therefore:

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

For instance, the negation of "every prime is odd" is "there exists a prime that is not odd," and indeed x = 2 is such a prime. This exact pattern is how you find a counterexample to a false theorem, and how you state the assumption "suppose not" at the start of a proof by contradiction. Getting the negation right is often half the battle in a proof.

A set is an unordered collection of distinct objects, called its elements or members. We write x IN A to say x is an element of A, and x NOT IN A otherwise. Two features define a set: order does not matter and repetition does not count, so {1, 2, 3}, {3, 2, 1}, and {1, 1, 2, 3} are all the same set.

Two ways to describe a set

• Roster notation lists the elements: A = {2, 4, 6, 8}.
• Set-builder notation states a rule: A = {x IN Z : x is even and 0 < x < 10}, read "the set of integers x such that x is even and between 0 and 10." The colon (or a vertical bar) means "such that."

Some sets are so common they have names: N the natural numbers, Z the integers, Q the rationals, and R the reals.

Subsets and equality

A is a subset of B, written A SUBSET B, when every element of A is also an element of B. Formally, A SUBSET B means FORALL x, (x IN A => x IN B). If additionally B has an element not in A, we call A a proper subset. Two sets are equal exactly when they contain the same elements, which gives the single most useful proof strategy of this module:

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

To prove two sets equal, you prove containment in both directions. This "double containment" method appears constantly.

The empty set and power sets

The empty set {} (also written with the symbol for nothing) has no elements. It is a subset of every set, because the statement FORALL x, (x IN {} => x IN B) is vacuously true, there is no x in the empty set to check. The power set P(A) is the set of all subsets of A. For example, if A = {1, 2}, then

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

A finite set with n elements has exactly 2^n subsets, because each element is independently either in or out of a given subset. So |P(A)| = 2^n. This doubling will reappear when we count in Module 6, tying set theory directly to combinatorics.

Sets combine through a handful of operations, each defined by a logical connective on the membership condition. Fix a universal set U that contains everything under discussion.

The core operations

• Union A UNION B = {x : x IN A OR x IN B}, everything in either set.
• Intersection A INTERSECT B = {x : x IN A AND x IN B}, everything in both.
• Difference A - B = {x : x IN A AND x NOT IN B}, in A but not B.
• Complement A^c = {x IN U : x NOT IN A}, everything in the universe outside A.

Notice how union rides on OR, intersection on AND, and complement on negation. This is why the logic of Modules 1 and 2 transfers directly to sets. For example, De Morgan's laws reappear as set identities: (A UNION B)^c = A^c INTERSECT B^c and (A INTERSECT B)^c = A^c UNION B^c.

Proving a set identity

Set identities are proved by the double containment method: show each side is a subset of the other, translating membership into logic. Here is a complete proof of one distributive law.

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

Proof. We show the two sets contain exactly the same elements by chasing an arbitrary element through the definitions.

1. Let x IN A INTERSECT (B UNION C). By definition of intersection, x IN A AND x IN B UNION C. By definition of union, the second part means x IN B OR x IN C.
2. So we have x IN A AND (x IN B OR x IN C). By the distributive law of logic, this is equivalent to (x IN A AND x IN B) OR (x IN A AND x IN C).
3. That is exactly x IN (A INTERSECT B) OR x IN (A INTERSECT C), which means x IN (A INTERSECT B) UNION (A INTERSECT C).
4. Every step is an "if and only if," so the argument runs in both directions, proving each set is a subset of the other. Therefore the two sets are equal. QED.

The pattern is worth absorbing: a set identity is really a logical equivalence about membership in disguise. Once you translate IN, UNION, and INTERSECT into OR and AND, the laws of logic finish the job.

Most theorems are conditionals: FORALL x, (P(x) => Q(x)). A direct proof takes the most straightforward route: assume the hypothesis P(x) is true for an arbitrary x, then use definitions, algebra, and known facts to deduce the conclusion Q(x). Because x is arbitrary, proving it for a general x proves it for all of them at once. If P is false the conditional is vacuously true, so we only ever need to handle the case where P holds.

The definitions we will use

Proofs live or die on precise definitions. Commit these to memory:

• 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, if b = a*m for some integer m.

The phrase "for some integer k" is doing real work: it introduces a witness you can name and manipulate.

Worked example one

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

Proof. Let n be an arbitrary integer, and assume n is odd. By definition there is an integer k with n = 2k + 1. Then

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.

Let m = 2k^2 + 2k, which is an integer because it is built from the integer k by multiplication and addition. Then n^2 = 2m + 1, which is exactly the definition of an odd number. Therefore n^2 is odd. QED.

Worked example two

Theorem. The sum of two even integers is even.

Proof. Let a and b be even integers. By definition, a = 2j and b = 2k for some integers j and k. Then

a + b = 2j + 2k = 2(j + k).

Since j + k is an integer, a + b has the form 2 * (integer), so a + b is even. QED.

Notice the shape shared by both proofs: state the assumption, 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. A good proof reads as complete sentences, justifies each step, and ends when the conclusion is reached. When you can drive straight from hypothesis to conclusion this way, a direct proof is always the first thing to try.

Sometimes the hypothesis of a conditional is hard to use directly, while the negation of the conclusion is easy to work with. In that situation we prove the contrapositive. Recall from Module 1 that

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

Because a statement and its contrapositive are logically equivalent, proving ~Q => ~P proves the original P => Q. A proof by contrapositive assumes ~Q (the conclusion is false) and derives ~P (the hypothesis is false), using an ordinary direct-proof structure on the flipped statement.

When to reach for it

The contrapositive shines when the conclusion Q is a "positive" statement that becomes concrete when negated. A classic signal is a conclusion like "n is even" or "n is odd," because its negation gives you an equation to manipulate, whereas the original hypothesis might only tell you something about n^2, which is harder to factor.

Worked example

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

A direct proof would start from "n^2 is even," giving n^2 = 2k, and then try to conclude something about n, but taking a square root does not stay inside the integers cleanly. The contrapositive is far easier.

Contrapositive. If n is not even (that is, n is odd), then n^2 is not even (that is, n^2 is odd).

Proof. Assume n is odd. Then n = 2k + 1 for some integer k, so

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,

which is odd, since 2k^2 + 2k is an integer. We have shown that n odd forces n^2 odd, which is 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.

A note on honesty

When you write a proof by contrapositive, say so at the top ("We prove the contrapositive") so your reader knows what statement you are actually establishing. The logic guarantees the two are interchangeable, but signaling the technique makes the proof easy to follow. This method is one of your sharpest tools whenever a conclusion is easier to attack in negated form than the hypothesis is to use directly.

A proof by contradiction (also called reductio ad absurdum) proves a statement S by assuming its negation ~S and showing that this assumption forces something impossible, a contradiction, usually a statement of the form R AND ~R. Since a true assumption can never lead to a false conclusion, the assumption ~S must have been wrong, so S is true.

The structure

1. Suppose, for contradiction, that ~S is true.
2. Reason validly until you reach a statement that cannot hold (a number both even and odd, a set both empty and nonempty, 0 = 1, and so on).
3. Conclude that ~S is impossible, hence S is true.

This method is especially powerful for statements of nonexistence ("there is no such thing") and for claims that resist direct attack. The critical first move is to negate S correctly, which is exactly why we practiced negation in Module 2.

Worked example: the square root of 2 is irrational

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 we can write it as a fraction in lowest terms:

sqrt(2) = a/b, where a and b are integers with no common factor and b != 0.

1. Square both sides: 2 = a^2 / b^2, so a^2 = 2 b^2.
2. Then a^2 is even. By the theorem from the previous lesson (n^2 even implies n even), a is even, so a = 2c for some integer c.
3. Substitute: (2c)^2 = 2 b^2, that is 4c^2 = 2 b^2, so b^2 = 2c^2.
4. Then b^2 is even, so by the same theorem b is even as well.
5. But now a and b are both even, so they share the common factor 2. This contradicts our assumption that a/b was in lowest terms.

The assumption that the square root of 2 is rational leads to a contradiction, so it must be false. Therefore the square root of 2 is irrational. QED.

Why the contradiction settles it

Every step from the assumption was a valid deduction, yet we arrived at an impossibility. In logic, a valid argument can never carry you from a true premise to a false conclusion, so the one thing we merely assumed, the rationality of the square root of 2, has to be the culprit. Notice how this proof reused the earlier contrapositive result as a stepping stone; good proofs build on the theorems you have already established. Reach for contradiction when a claim asserts that something cannot happen, or when assuming the opposite hands you a concrete object to break.

Mathematical induction proves a statement P(n) for every natural number n (starting from some base, often 0 or 1). The idea is the domino effect: if the first domino falls, and each fallen domino knocks over the next, then all the dominoes fall. Formally, to prove FORALL n >= 1, P(n), you establish two things:

1. Base case: prove P(1) directly (the first domino falls).
2. Inductive step: prove that FORALL k >= 1, (P(k) => P(k+1)) (each domino topples the next). Inside this step you assume P(k), called the inductive hypothesis, and use it to derive P(k+1).

Once both hold, the principle of induction guarantees P(n) for all n >= 1. The base case and the inductive step are equally essential: without the base case the chain never starts, and without the step the chain never continues.

Worked example one: a summation formula

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

Proof by induction on n.

Base case (n = 1): the left side is just 1, and the right side is 1(2)/2 = 1. They agree, so P(1) holds.

Inductive step: assume the formula holds for some k >= 1, that is 1 + 2 + ... + k = k(k+1)/2 (this is the inductive hypothesis). We must show it holds for k + 1. Starting from the left side for k + 1:

1. 1 + 2 + ... + k + (k+1) = [1 + 2 + ... + k] + (k+1).
2. Apply the inductive hypothesis to the bracket: = k(k+1)/2 + (k+1).
3. Factor out (k+1): = (k+1)[k/2 + 1] = (k+1)(k + 2)/2.

The result (k+1)(k+2)/2 is exactly the formula with n = k + 1. So P(k) => P(k+1). By induction, the formula holds for all n >= 1. QED.

Worked example two: a divisibility claim

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

Proof. Base case (n = 1): 1^3 - 1 = 0, and 3 divides 0. Good.

Inductive step: assume 3 | (k^3 - k), so k^3 - k = 3m for some integer m. Consider (k+1)^3 - (k+1):

(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k.

Using the hypothesis, this equals 3m + 3k^2 + 3k = 3(m + k^2 + k), which is 3 times an integer. So 3 divides (k+1)^3 - (k+1). By induction the claim holds for all n >= 1. QED.

The engine of every induction proof is the same: reduce the k+1 case to the k case so the inductive hypothesis can do the work. Isolating the previous case, as we did by peeling off (k+1) or by grouping k^3 - k, is the skill to practice.

Ordinary induction assumes only P(k) to prove P(k+1). But some statements about k+1 depend on cases well before k, so a single previous case is not enough. Strong induction (also called complete induction) strengthens the hypothesis: to prove P(n) for all n, you assume P(j) holds for every j from the base up to k, and use any of them to prove P(k+1).

The structure

1. Base case(s): prove P for the smallest value(s). Some proofs need several base cases.
2. Inductive step: assume P(j) is true for all j with base <= j <= k (the strong inductive hypothesis), and prove P(k+1).

Strong and ordinary induction are logically equivalent in power, but strong induction is far more convenient whenever the case you are building reaches back more than one step.

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): 2 is prime, and it divides itself, so it has a prime factor. Good.

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

1. If k + 1 is prime, then it has itself as a prime factor, and we are done.
2. If k + 1 is not prime, then by definition it factors as k + 1 = a * b where a and b are integers with 2 <= a <= k. By the strong inductive hypothesis, a has a prime factor p. Since p divides a and a divides k + 1, we get that p divides k + 1. 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.

Why ordinary induction would struggle here

The factor a could be any value between 2 and k, not necessarily k itself, so knowing only P(k) would not help. Strong induction lets us call on P(a) for whatever a the factorization produces. Whenever the recursive structure of a problem points back to some earlier but unpredictable case, as with factoring, recursively defined sequences, or well-founded games, strong induction is the right tool.

A function f: A -> B assigns to each element of the domain A exactly one element of the codomain B. The set of values actually hit, {f(x) : x IN A}, is the image (or range), which may be smaller than the whole codomain. Three properties classify how a function pairs its inputs and outputs.

Injective (one-to-one)

f is injective if different inputs always give different outputs: f(x1) = f(x2) forces x1 = x2. No output is used twice. To prove injectivity, assume f(x1) = f(x2) and deduce x1 = x2.

Surjective (onto)

f is surjective if every element of the codomain is hit: FORALL y IN B, EXISTS x IN A, f(x) = y. The image equals the whole codomain. To prove surjectivity, take an arbitrary y in B and produce an x in A with f(x) = y.

Bijective

f is bijective if it is both injective and surjective. A bijection pairs the elements of A and B perfectly, one to one with none left over, and is exactly the condition for f to have an inverse function f^(-1): B -> A.

Worked example

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

Injective. Suppose f(x1) = f(x2). Then 3x1 + 5 = 3x2 + 5. Subtract 5 from both sides: 3x1 = 3x2. Divide by 3: x1 = x2. So f is injective.

Surjective. Let y be an arbitrary real number. We need x with 3x + 5 = y. Solving, x = (y - 5)/3, which is a real number, and indeed f((y-5)/3) = 3 * (y-5)/3 + 5 = (y - 5) + 5 = y. So every y is hit, and f is surjective.

Since f is both injective and surjective, it is a bijection, with inverse f^(-1)(y) = (y - 5)/3. QED.

By contrast, g: R -> R with g(x) = x^2 is neither injective (since g(2) = g(-2) = 4) nor surjective onto R (since no real squares to -1). Restricting the domain and codomain, however, can repair both properties, which is why stating the domain and codomain is part of defining a function at all.

A relation R on a set A is any set of ordered pairs from A, and we write a R b to mean (a, b) is in the relation. Relations generalize the idea of comparison: "less than," "divides," "is congruent to," and "has the same birthday as" are all relations. Three properties are especially important.

• Reflexive: a R a for every a IN A. Every element relates to itself.
• Symmetric: if a R b then b R a. The relation reads the same both ways.
• Transitive: if a R b and b R c, then a R c. Relations chain together.

Equivalence relations

A relation that is reflexive, symmetric, and transitive all at once is an equivalence relation. Equivalence relations capture the idea of "being the same in some respect." The most important example in this course is congruence modulo n: for a fixed positive integer n, we say a === b (mod n) when n divides a - b.

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

1. Reflexive: a - a = 0, and n divides 0, so a === a.
2. Symmetric: if n divides a - b, then a - b = n*t for some integer t, so b - a = n*(-t), and n divides b - a. Thus a === b gives b === a.
3. Transitive: if n divides a - b and n divides b - c, write a - b = n*s and b - c = n*t. Adding, a - c = n*(s + t), so n divides a - c and a === c.

All three properties hold, so congruence modulo n is an equivalence relation. QED.

Equivalence classes and partitions

An equivalence relation sorts A into equivalence classes: the class of a, written [a], is the set of all elements related to a. A fundamental theorem says these classes form a partition of A: every element lies in exactly one class, and distinct classes do not overlap. For congruence modulo 3, the integers split into exactly three classes by remainder:

• [0] = {..., -3, 0, 3, 6, ...} (remainder 0),
• [1] = {..., -2, 1, 4, 7, ...} (remainder 1),
• [2] = {..., -1, 2, 5, 8, ...} (remainder 2).

These three classes are disjoint and together contain every integer, a perfect partition. This connection between equivalence relations and partitions is one of the most useful structural ideas in mathematics, underlying modular arithmetic, quotient constructions, and much more.

How can we compare the sizes of infinite sets? The key idea, due to Georg Cantor, is to use bijections. Two sets have the same cardinality, written |A| = |B|, when there is a bijection between them, a perfect pairing of their elements. This definition matches ordinary counting for finite sets and extends sensibly to infinite ones.

Countable sets

A set is countably infinite if it has the same cardinality as the natural numbers N = {1, 2, 3, ...}, meaning its elements can be listed in a sequence 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. Although Z extends in both directions, we can list it by zig-zagging: 0, 1, -1, 2, -2, 3, -3, .... Every integer appears exactly once, so this listing is a bijection with N.
• The rationals are countable. Arrange all fractions p/q in an infinite grid indexed by numerator and denominator, then sweep through it along diagonals, skipping any fraction already seen in lower terms. This threads every rational into a single list, so Q is countable too, even though the rationals are dense on the number line.

The reals are uncountable

Not every infinite set is countable. Cantor proved that the real numbers cannot be listed, using his celebrated diagonal argument. Here is the idea for the reals between 0 and 1.

Theorem. The set of real numbers in (0, 1) is uncountable.

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

1. r1 = 0.d11 d12 d13 ...
2. r2 = 0.d21 d22 d23 ...
3. r3 = 0.d31 d32 d33 ..., and so on, supposedly capturing every real in the interval.

Now build a new number x = 0.b1 b2 b3 ... by walking down the diagonal and changing each digit: let b_k be, say, 5 if the diagonal digit d_kk is not 5, and 4 if d_kk is 5. By construction x differs from r1 in the first digit, from r2 in the second digit, from r_k in the kth digit, and so on. So x is a real number in (0, 1) that is on no line of the list, contradicting the assumption that the list contained every real. Therefore no such list exists, and the reals in (0, 1) are uncountable. QED.

The consequence is profound: there are strictly more real numbers than natural numbers, so infinity comes in different sizes. The countable infinity of N, Z, and Q is genuinely smaller than the uncountable infinity of R. This was one of the most startling discoveries in the history of mathematics, and the diagonal argument that proves it is a masterpiece of the proof techniques you have been building.

Combinatorics is the art of counting without listing. Two principles underlie everything.

• Multiplication principle: if a task splits into a sequence of independent choices with m ways for the first and n ways for the second, there are m * n ways 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), there are m + n ways total.

For example, choosing an outfit from 3 shirts and 4 pants gives 3 * 4 = 12 combinations (multiplication, since the choices are made in stages). Choosing a single item that is either one of 3 shirts or one of 4 pants gives 3 + 4 = 7 options (addition, since the categories are disjoint).

Factorials and permutations

The factorial n! is the product n * (n-1) * ... * 2 * 1, with the convention 0! = 1. A permutation is an ordered arrangement of objects. The number of ways to arrange n distinct objects in a row is n!, because there are n choices for the first position, n - 1 for the second, and so on. To arrange only r of the n objects in order, the count 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? Order matters (the roles are distinct), so this is P(10, 3) = 10! / 7! = 10 * 9 * 8 = 720.

Combinations

A combination is an unordered selection, a subset. 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)!], also written as "n choose r."

The extra r! in the denominator divides out the orderings that a permutation would count separately. Worked example. How many 3-person committees can be formed from 10 people? Order does not matter, so

C(10, 3) = 10! / (3! * 7!) = (10 * 9 * 8)/(3 * 2 * 1) = 720/6 = 120.

The distinction is the whole story: permutation for ordered arrangements, combination for unordered selections. A helpful check is to ask, "if I swap two chosen items, is it a different outcome?" If yes, use permutations; if no, use combinations. Notice that P(10, 3) = 720 is exactly 3! = 6 times C(10, 3) = 120, since each committee can be ordered in 3! ways.

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.

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.

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.

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 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.

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.

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

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.

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.

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.

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.