Logic

Section A.2 Logic

Remark A.2.1.

Our study of linear algebra will cover two broad topic: computation and theory. To study the theory of matrices we will need to understand and make logical arguments. In this section we review all the necessary logical tools. This material will play a fair-sized role role in Chapter 4 and an even bigger role in Chapter 5

Definition A.2.2.

(Proposition) A proposition \(P\) is an unambiguous declarative statement that is either true or false.

Definition A.2.3.

(Theorem) A theorem is true proposition.

Definition A.2.4.

(Implication) An implication (or a conditional proposition or just a conditional) is a proposition of the form “If \(P\text{,}\) then \(Q\)” where \(P\) and \(Q\) are component propositions called the hypothesis or antecedent and conclusion or consequent, respectively. We write \(P\ra Q\text{.}\) Equivalent to “If \(P\text{,}\) then \(Q\)” are “\(Q\) only if \(P\)” and “If \(\neg Q\) then \(\neg P\text{,}\)” among others. The truth table for the implication is: \(\begin{array}{c|c|c} P\amp Q\amp P\ra Q\\ \hline \text{T} \amp \text{T} \amp \text{T} \\ \text{T} \amp \text{F} \amp \text{F} \\ \text{F} \amp \text{T} \amp \text{T} \\ \text{F} \amp \text{F} \amp \text{T} \end{array}\)

Definition A.2.5.

(Logical implication) Let \(P,Q\) be propositions. We write \(P\Ra Q\) and say “\(P\) logically implies \(Q\)” if for all possible combinations of truth values for \(P\) and \(Q\text{,}\) \(P\ra Q\) is true.

Theorem A.2.6.

(Proof by Contradiction) Let \(P\) be a proposition. If \(P\) implies any false statement, \(P\) itself is false.

Suppose \(P\) implies a false statement \(Q\text{.}\) Then \(P\rightarrow Q\) is true, and \(Q\) is false. By the truth table in Definition A.2.4, this is true only if \(P\) is false.

Definition A.2.7.

(The Biconditional) Let \(P,Q\) be propositions. We define the biconditional \(P\leftrightarrow Q\) by \(P\leftrightarrow Q\,:=\,[(P\rightarrow Q)\wedge(Q\rightarrow P)]\text{.}\)

Definition A.2.8.

(Logical equivalence) Let \(P,Q\) be propositions. We write \(P\equiv Q\) or \(P\Leftrightarrow Q\) and say “\(P\) is logically equivalent to \(Q\)” if for all possible combinations of truth values for \(P\) and \(Q\text{,}\) \(P\leftrightarrow Q\) is true.

Definition A.2.9.

(Propositional Function) A propositional function \(\P\) on \(U\) is a set \(\{x,\P(x)\}_{x\in U}\text{.}\) The range of \(\P\) is a nonempty subset of \(\{T,F\}\text{.}\)

Remark A.2.10.

Since a propositional function \(\P\) is in fact a set of propositions, one for each \(x\in U\text{,}\) we note that

\begin{equation*} \left(\fa x\in U,\,\P(x)\,\right)\equiv\left(\bigwedge_{x\in U}\P(x)\,\right) \end{equation*}

and so (as long as \(U\ne\emptyset\)) \(\fa x\in U,\,\P(x)\) is true, and only true, when ran\((\P)=\{T\}\text{.}\)

Remark A.2.11.

If a propositional function \(\P\) is proven true on some subset \(S\) of \(U\) then we may say that “For all \(x\in S,\,\P(x)\)” or equivalently “If \(x\in S\text{,}\) then \(\P(x)\text{.}\)” In the case that \(S\) is a proper subset of \(U\text{,}\) we may choose to regard \(S\) as a new universal set.

Remark A.2.12.

Let \(\P\) be a propositional function on \(U\text{.}\) If \(T\in\) ran \((\P)\) (which we may verify by exhibiting an \(x\in U\) for which \(\P(x)=T\)) then we may say that “There exists \(x\in U\) such that \(\P(x)\text{.}\)”

Definition A.2.13.

(Counterexample) Let \(\P\) be a propositional function on \(U\text{.}\) If there exists an object \(y\in U\) for which \(\P(y)\) is false, then \(y\) is called a counterexample to “\(\fa x\in U,\,\P(x)\)” (equivalently to “If \(x\in U\) then \(\P(x)\)” ) and we conclude that the proposition \(\fa x\in U,\,\P(x)\) is false.

Definition A.2.14.

(Converse) Let \(P\ra Q\) be an implication. The implication \(Q\ra P\) is called the converse of \(P\ra Q\text{.}\)

Remark A.2.15.

Recall that a proposition and its converse may have different truth values; for example it is the case that if \(x^2\lt 4\) then \(x\lt 2\) but it is not the case that if \(x\lt 2\text{,}\) then \(x^2\lt 4\) since we can find a counterexample to the latter, for example \(x=-3\text{.}\)

Definition A.2.16.

(Contrapositive) Let \(P\ra Q\) be an implication. The contrapositive form, or simply the contrapositive, of \(P\ra Q\) is the implication “If not \(Q\) then not \(P\text{,}\)” denoted \(\neg Q\ra\neg P\text{.}\)

Remark A.2.17.

(Equivalence of a proposition with its contrapositive) Let \(P,Q\) be propositions. Then \((P\ra Q)\equiv(\neg\,Q\ra\neg\,P)\text{.}\)

Theorem A.2.18.

(Modus Ponens) Let \(P,Q\) be propositions. Then \(P\wedge(P\ra Q)\Rightarrow Q\text{.}\) In particular, if \(P\) (data) is true, and one has the theorem \(P\Ra Q\text{,}\) then \(Q\) is true.

Remark A.2.19.

Modus ponens is the way one argues by the use of theorems as follows. If one cites a theorem of the form “If \(\P(x)\) then \(\Qp(x)\text{,}\)” and one considers some object \(x\in U\) for which \(\P(x)\) is true, then one may conclude that \(\Qp(x)\) is true.

Theorem A.2.20.

(Hypothetical Syllogism) Let \(P,Q,R\) be propositions. Then

\begin{equation*} (P\ra Q)\wedge(Q\ra R)\Rightarrow (P\ra R)\text{.} \end{equation*}

In particular, if \(P\Ra Q\) and \(Q\Ra R\) then \(P\Ra R\text{.}\)

Remark A.2.21.

Hypothetical syllogism permits us to chain implications together.

Definition A.2.22.

(Proof by Induction) We may prove various propositions on \(\N\) or on infinite subsets of \(\N\text{,}\) using the Principle of Mathematical Induction, as follows:

Propositional Function (PF): We express \(\P(n)=\) “(some proposition whose truth value may appear to depend on \(n\) but will in fact be shown to be \(T\) independent of \(n\)).”
Base Case (BC): We prove \(\P(1)\) true.
Induction Hypothesis (IH): Assume \(\ex n\in\N\) for which \(\P(n)\) is true, and fix such an \(n\text{.}\) Note that we are assuming the truth of, and invoking (by fixing such an \(n\)) the existentially quantified statement that \(\ex n\in\N\st\P(n)=T\text{,}\) and not assuming the truth of the universally quantified statement \(\fa n\in\N,\P(n)=T\text{,}\) the proof of which is our ultimate goal.
Induction Step (IS): In which we use the assumed truth of \(\P(n)\) to prove that \(\P(n+1)\) is true.
Conclusion (C): We conclude by MI that \(\P(n)\) holds for all \(n\in\N\text{.}\)

The style of your individual application of MI may vary; you may choose to write it in paragraph form or to enumerate the steps explicitly by number or acronym. In this text I will stick exclusively to the latter.

Example A.2.23.

As an example of these two ways we use to describe sets, consider

\begin{align*} \{x\in\R\,|\,\cos x=0\}\amp =\left\{\left.\frac{(2n+1)\pi}{2}\,\right|\,n\in\Z\right\}\\ \amp =\left\{x\in\R\,\left|\,\ex n\in\Z\text{ such that } x=\frac{(2n+1)\pi}{2}\right.\right\} \end{align*}

Definition A.2.24.

Let \(A,B\) be sets and let \(f:A\rightarrow B\text{.}\) We say \(f\) is

injective if \(\fa b\in \text{ ran } f,\ex!\,a\in A\st(a,b)\in f\text{,}\)
surjective if \(\fa b\in B,\,b\in\text{ ran } f\text{,}\)
bijective if \(f\) is both injective and surjective.

Prev Top Next