6.2: Common mathematical statements

Last updated
Save as PDF

Page ID: 83427

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In mathematics, we often want to prove that some statement \(P\) logically implies some other statement \(Q\text{;}\) i.e. we want to prove that \(P \Rightarrow Q\) or \((\forall x)(P(x) \Rightarrow Q(x))\text{.}\) Note that the universal form covers the common statement “all \(A\) are \(B\)”, since this can be rephrased “for all \(x\text{,}\) if \(x\) is \(A\) then \(x\) is \(B\)”.

Below are some common methods for proving \(P \Rightarrow Q\text{.}\) In the universal case \((\forall x)(P(x) \Rightarrow Q(x))\text{,}\) the domain of \(x\) may be infinite, so we cannot prove \(P(x) \Rightarrow Q(x)\) for each specific \(x\text{,}\) one-by-one. Instead, we treat \(x\) as a fixed but arbitrary object in the domain, and try to construct an argument proving \(P(x) \Rightarrow Q(x)\) which does not depending on knowing the specific object \(x\text{.}\) So all of the methods below can also be used in the universal case.

Since a conditional \(P \rightarrow Q\) is true automatically when \(P\) is false, it will be a tautology as long as we cannot have the case of \(P\) true and \(Q\) false at the same time. (See Figure 1.3.1.) Therefore, we (almost always) begin a proof by assuming that \(P\) is true, and proceed to demonstrate that \(Q\) must then also be true, based on that assumption.