Induction Proofs: Generalized Rules of De Morgan and Distribution
SUMMARY
This class addresses the topic of induction proofs in mathematics and propositional logic. The two types of existing proofs are explained: internal or deductive proofs, which are based on the rules of logic, and external or metamathematical proofs, which are necessary to prove statements that refer to logic itself. Mathematical Induction is introduced as a demonstration method that allows proving that certain statements hold for all natural numbers. An example is presented with the corresponding proof, and the generalized forms of De Morgan’s laws and the distributive laws in propositional logic are explained, along with their respective induction proofs. This class is of great importance for understanding the fundamentals of mathematics and logic and for applying them in different areas of knowledge.
LEARNING OBJECTIVES:
By the end of this class, the student will be able to:
- Recognize the two types of proofs to be distinguished: internal or deductive proofs and external or metamathematical proofs.
- Apply mathematical induction to perform proofs involving natural numbers and propositional logic.
- Use conjunction and disjunction notations to write expressions in propositional logic.
- Understand the generalized form of De Morgan’s laws and the Distributive Laws in Propositional Logic.
- Understand the concept of the induction hypothesis and its role in the induction proof.
INDEX
INTERNAL AND EXTERNAL PROOFS
MATHEMATICAL INDUCTION PROOFS
INDUCTION PROOFS IN PROPOSITIONAL LOGIC
GENERALIZED FORM OF DE MORGAN’S LAWS
GENERALIZED FORM OF THE DISTRIBUTIVE LAWS
Internal and External Proofs
There are two types of proofs that must be distinguished. So far, we have seen many examples of formal proofs. These types of proofs emerge from the rules of logic. Such proofs are said to take place “within logic,” and therefore they are also referred to as “internal” or deductive proofs. These formal proofs have a limited scope because they only serve to prove statements that can be written in the language of logic. However, we might want to prove some things about logic itself. We might want to prove that all statements of propositional logic satisfy a certain property. Such statements, which refer to logic itself, cannot be established or proved within logic. To prove such statements, we use an external proof. External proofs are sometimes called “metamathematical,” and we have already encountered such things, like when we saw the (meta)deduction theorem. It is here that we contextualize inductive proofs.
Mathematical Induction Proofs
Mathematical Induction is a method of proof that allows us to prove that some things hold for all natural numbers.
EXAMPLE: It is possible to prove that any number of the form 11^n - 4^n, where n is any natural number, is always divisible by 7.
PROOF: If we observe what happens with n=1, we will see that:
11^1 - 4^1 = 7
which is obviously divisible by 7.
Now suppose that 11^n - 4^n is divisible for a n=k. From this, we will prove that this expression will also hold for n=k+1. We can do this as follows:
Therefore, if 11^k - 4^k is divisible by 7, then 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k} will also be divisible by 7, which is the same as saying that 11^{k+1} - 4^{k+1} is divisible by 7. From here, we have that if 11^k - 4^k is divisible for k=1, then it will be for k=2, k=3, k=4,\cdots and so on, and therefore divisible for any n\in\mathbb{N}. When this occurs, we say that the induction is complete. ■
Induction Proofs in Propositional Logic
For the induction proofs that we will perform next, it will first be necessary to introduce the following notation convention
NOTATION: Let F_1,\cdots, F_n be any finite set of expressions in propositional logic. The conjunctions and disjunctions of these expressions are introduced as follows:
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
With this, we can now deal with the following two generalized forms.
Generalized Form of De Morgan’s Laws
Given a finite set of expressions in propositional logic F_1,\cdots, F_n, the following two properties will always hold:
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
PROOF: First, we will prove by induction on n that \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
First, we must check what happens with the initial case n=1. In this case, it is clear that \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Now suppose the property works for some n=k; that is, given a finite collection of expressions F_1, F_2, \cdots, F_k, it holds that:
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Then we will prove that it consequently holds
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
Using the definition of conjunction, we have that:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
On this expression, we can apply De Morgan’s laws (the usual one on two terms) to obtain:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Now, if we apply the induction hypothesis, we obtain:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
And for this reason, the induction is complete, and the property holds for any n in general. The second relation can be obtained in a completely analogous way, so I’ll leave it as an exercise for the reader, mwahaha!
Generalized Form of the Distributive Laws
Similar to De Morgan’s laws, the distributive laws can be generalized as follows. Let \{F_1, \cdots, F_n\} and \{G_1,\cdots, G_m\} be two finite sets of any expressions, then the following equivalences hold:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
PROOF: To build this proof, we must perform a double induction on n and m. Next, I will do the induction first on n and then on m for the expression \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
If we take m=1, then this expression is written as
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
Which is the same as saying:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Now we will prove this expression by induction on n.
If we take n=1, then the expression reduces to
F_1 \vee G_1 \equiv F_1 \vee G_1.
Which we already know is true. Now suppose it holds for some n=k; that is, the induction hypothesis will be:
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Then, from this, we will show that consequently, it holds for n=k+1.
By the definition of conjunction, we have that:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
Now, using the \vee-distribution, we have:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
And right at this point, we can use the induction hypothesis to obtain:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
Therefore, we have proved by induction that for all n\in\mathbb{N}, it holds that
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
Completing the induction on n, we have verified that the initial case for m=1, works. Now we just need to complete the induction on m. To do the latter, we establish the induction hypothesis for a m=l, that is, it works:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
and from this, we will prove that it also works for m=l+1.
Starting, as always, from the definition of conjunction, we have that
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
Now, using the \vee-distribution, we have
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Consequently, using the induction hypothesis, you can write
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
And if we now take the result of the induction on n
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
Which, finally, by the definition of conjunction, we have
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
And therefore, the induction on m is complete, and the expression
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
is valid for all n,m\in\mathbb{N}.
This exploration of induction proofs has demonstrated how rigorous mathematical demonstration techniques can be applied not only in the realm of natural numbers but also in propositional logic. Through induction, we have established the validity of the generalized forms of De Morgan’s laws and the distributive laws, thereby reinforcing the understanding of the logical foundations underlying various areas of mathematical knowledge. This approach is not only essential for the development of abstract reasoning skills but also serves as a powerful tool for tackling complex problems in mathematics and beyond.