Direct Proofs in Combinatorics

The Anatomy of a Direct Proof

At its heart, a direct proof is the most straightforward way to establish the truth of a statement of the form "If P, then Q." The strategy is simple:

1. Assume the hypothesis, P, is true.
2. Use definitions, logical deductions, and previously established facts to build a chain of reasoning.
3. Show that this chain inevitably leads to the conclusion, Q.

Let's see how this works in practice, starting with the world of sets.

Direct Proofs in Set Theory

A common task in combinatorics is to prove that two sets are equal. The standard method for proving that set $A$ equals set $B$ is to show they are subsets of each other. This requires a two-part proof:

1. Prove that $A\subseteq B$. (Show that any element in $A$ must also be in $B$.)
2. Prove that $B\subseteq A$. (Show that any element in $B$ must also be in $A$.)

Each part is a mini-direct proof. To prove $A\subseteq B$, we assume we have an arbitrary element $x\in A$ and then use the definitions of the sets to show that $x$ must also be in $B$. This technique is often called the "element-chasing method."

Let's explore a detailed example of this method.

As you saw in the reading, the proof relies on translating the set notation into logical statements. Let's break down the logic for the first part of that proof:

Theorem: For any sets $A,B,C$, it holds that $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$.

Proof (Part 1: $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$):

1. Assume the hypothesis: Let $x$ be an arbitrary element such that $x\in A\cap (B\cup C)$.
2. Unpack definitions: By the definition of intersection ($\cap$), this means:
   $x\in A$ and $x\in (B\cup C)$.
3. Unpack further: By the definition of union ($\cup$), $x\in (B\cup C)$ means:
   $x\in B$ or $x\in C$.
4. Combine and reason: Substituting this back, we have:
   $x\in A$ and ($x\in B$ or $x\in C$).
   This is a statement in logic. The distributive law of logic states that "P and (Q or R)" is equivalent to "(P and Q) or (P and R)". Applying this, we get:
   ($x\in A$ and $x\in B$) or ($x\in A$ and $x\in C$).
5. Repack using definitions: Now, we translate back to set notation:
   • ($x\in A$ and $x\in B$) is equivalent to $x\in (A\cap B)$.
   • ($x\in A$ and $x\in C$) is equivalent to $x\in (A\cap C)$.
6. Final step: Our logical statement becomes:
   $x\in (A\cap B)$ or $x\in (A\cap C)$.
   By the definition of union, this is exactly the same as $x\in (A\cap B)\cup (A\cap C)$.
7. Conclusion: We started by assuming $x$ was in $A\cap (B\cup C)$ and have shown it must be in $(A\cap B)\cup (A\cap C)$. Therefore, we have proven that $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$.

The second part of the proof, showing $(A\cap B)\cup (A\cap C)\subseteq A\cap (B\cup C)$, follows the same logic in reverse. I encourage you to try writing it out yourself, using the "Why?" prompts in the reading as a guide, before moving on.

To see more examples and hear the logic explained, the following video is very helpful.

Direct Proofs Involving Divisibility

Now, let's apply the same direct proof strategy to a different domain: number theory, specifically properties of divisibility. The structure of the proof remains the same, but the definitions we use will change.

The statement "a divides b," written as $a|b$, means that $b$ is a multiple of $a$. While we can think of this as $\frac{b}{a}$ being an integer, for writing proofs, it's far more powerful to use an algebraic definition based on multiplication.

Let's formalize the proof for the transitive property of divisibility shown in the video.

Theorem: For any integers $a,b,c$, if $a|b$ and $b|c$, then $a|c$.

Proof:

1. Assume the hypothesis: Assume $a|b$ and $b|c$.
2. Unpack definitions:
   • By the definition of divisibility, $a|b$ means there exists an integer $k_1$ such that $b=k_{1}a$.
   • Similarly, $b|c$ means there exists an integer $k_2$ such that $c=k_{2}b$.
3. State the goal: We want to show that $a|c$. This means we need to find an integer $k_3$ such that $c=k_{3}a$.
4. Chain logical steps: We have an expression for $c$ in terms of $b$, and an expression for $b$ in terms of $a$. We can substitute the second into the first: $$c=k_{2}b=k_2(k_{1}a)$$ Using the associative property of multiplication, we can regroup this as: $$c=(k_2{k}_1)a$$
5. Conclusion: Let $k_3=k_2{k}_1$. Since $k_1$ and $k_2$ are integers, their product $k_3$ is also an integer. We have successfully shown that $c=k_{3}a$ for some integer $k_3$. Therefore, by the definition of divisibility, $a|c$.

This proof perfectly illustrates the direct method: we assumed the "if" part and, by using definitions and simple algebra, we arrived at the "then" part. I recommend watching the other examples in the video to see this pattern repeated in slightly different contexts.

Your Turn: Practice Problems

Now it's time to try constructing a couple of direct proofs yourself. Use the structure we've discussed: state your assumptions, unpack definitions, manipulate the expressions, and form your conclusion.

Problem 1 (Sets): Prove that for any sets A and B, $A\subseteq A\cup B$.

Hint: Start by assuming $x\in A$. What does the definition of union tell you?

Problem 2 (Divisibility): Prove that for all integers $a$ and $b$, if $a|b$, then $a^2|b^2$. This problem and its solution are also available in the following resource.

Key Takeaways

In this lesson, we introduced the direct proof, the most fundamental proof technique in mathematics. The core strategy is always the same:

• Assume the hypothesis (the "if" part).
• Use definitions to translate high-level concepts (like set inclusion or divisibility) into concrete logical and algebraic statements.
• Build a bridge of logical deductions to arrive at the conclusion (the "then" part).
• Conclude by showing you have successfully derived the conclusion from the hypothesis.

You've now seen this method applied to both set theory and number theory, which are foundational areas for combinatorics.

Looking Ahead

While direct proofs are powerful, they are not always the easiest or even a possible way to prove a statement. What happens when assuming P doesn't seem to lead anywhere? In our next lesson, we will explore a powerful alternative: proof by contradiction. This technique allows us to prove a statement is true by showing that assuming it to be false leads to an impossible outcome.