[<< wikibooks] Linear Algebra/Propositions
The point at issue in an argument is the
proposition.
Mathematicians usually write the point in full before the proof
and label it either Theorem for major points, Corollary
for points that follow immediately from a prior one, or Lemma
for results chiefly used to prove other results. 
The statements expressing propositions can be complex, with many subparts.
The truth or falsity of the entire proposition depends both on the
truth value of the parts, and on the words used to
assemble the statement from its parts.


=== Not ===
For example, where 
  
    
      
        P
      
    
    {\displaystyle P}
   is a proposition,
"it is not the case that 
  
    
      
        P
      
    
    {\displaystyle P}
  " is true provided that 
  
    
      
        P
      
    
    {\displaystyle P}
   is
false.
Thus, "
  
    
      
        n
      
    
    {\displaystyle n}
   is not prime" is true only when 
  
    
      
        n
      
    
    {\displaystyle n}
   is the
product of smaller integers.
We can picture the "not" operation with a
Venn diagram.

Where the box encloses all natural numbers, and inside the circle are
the primes, the shaded area holds numbers satisfying "not 
  
    
      
        P
      
    
    {\displaystyle P}
  ".
To prove that a "not 
  
    
      
        P
      
    
    {\displaystyle P}
  " statement holds, show that 
  
    
      
        P
      
    
    {\displaystyle P}
   is false.


=== And ===
Consider the statement form "
  
    
      
        P
      
    
    {\displaystyle P}
   and 
  
    
      
        Q
      
    
    {\displaystyle Q}
  ".
For the statement to be true both halves must hold:
"
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime and so is 
  
    
      
        3
      
    
    {\displaystyle 3}
  " is true, while
"
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime and 
  
    
      
        3
      
    
    {\displaystyle 3}
   is not" is false.
Here is the Venn diagram for "
  
    
      
        P
      
    
    {\displaystyle P}
   and 
  
    
      
        Q
      
    
    {\displaystyle Q}
  ".

To prove "
  
    
      
        P
      
    
    {\displaystyle P}
   and 
  
    
      
        Q
      
    
    {\displaystyle Q}
  ", prove that each half holds.


=== Or ===
A "
  
    
      
        P
      
    
    {\displaystyle P}
   or 
  
    
      
        Q
      
    
    {\displaystyle Q}
  " is true when either half holds:
"
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime or 
  
    
      
        4
      
    
    {\displaystyle 4}
   is prime" is true, while "
  
    
      
        7
      
    
    {\displaystyle 7}
   is not prime
or 
  
    
      
        4
      
    
    {\displaystyle 4}
   is prime" is false.
We take "or" inclusively so that if both halves are true
"
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime or 
  
    
      
        4
      
    
    {\displaystyle 4}
   is not" then the statement as a whole is true.
(In everyday speech, sometimes "or" is meant in an exclusive way— "Eat
your vegetables or no dessert" does not intend both halves to hold— but
we will not use "or" in that way.)
The Venn diagram for "or" includes all of both circles.

To prove "
  
    
      
        P
      
    
    {\displaystyle P}
   or 
  
    
      
        Q
      
    
    {\displaystyle Q}
  ", show that in all cases at least one
half holds (perhaps sometimes one half and sometimes the other,
but always at least one).


=== If-then ===
An "if 
  
    
      
        P
      
    
    {\displaystyle P}
   then 
  
    
      
        Q
      
    
    {\displaystyle Q}
  " statement (sometimes written
"
  
    
      
        P
      
    
    {\displaystyle P}
   materially implies 
  
    
      
        Q
      
    
    {\displaystyle Q}
  " or just
"
  
    
      
        P
      
    
    {\displaystyle P}
   implies 
  
    
      
        Q
      
    
    {\displaystyle Q}
  " or "
  
    
      
        P
        
        ⟹
        
        Q
      
    
    {\displaystyle P\implies Q}
  ") is true unless 
  
    
      
        P
      
    
    {\displaystyle P}
  
is true while 
  
    
      
        Q
      
    
    {\displaystyle Q}
   is false.
Thus "if 
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime then 
  
    
      
        4
      
    
    {\displaystyle 4}
   is not" is true
while "if 
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime then 
  
    
      
        4
      
    
    {\displaystyle 4}
   is also prime" is false.
(Contrary to its
use in casual speech, in mathematics "if 
  
    
      
        P
      
    
    {\displaystyle P}
   then 
  
    
      
        Q
      
    
    {\displaystyle Q}
  "
does not connote that

  
    
      
        P
      
    
    {\displaystyle P}
   precedes 
  
    
      
        Q
      
    
    {\displaystyle Q}
   or causes 
  
    
      
        Q
      
    
    {\displaystyle Q}
  .)
More subtly, in mathematics "if 
  
    
      
        P
      
    
    {\displaystyle P}
   then 
  
    
      
        Q
      
    
    {\displaystyle Q}
  " is
true when 
  
    
      
        P
      
    
    {\displaystyle P}
   is false:
"if 
  
    
      
        4
      
    
    {\displaystyle 4}
   is prime then 
  
    
      
        7
      
    
    {\displaystyle 7}
   is prime" and
"if 
  
    
      
        4
      
    
    {\displaystyle 4}
   is prime then 
  
    
      
        7
      
    
    {\displaystyle 7}
   is not" are both true statements,
sometimes said to be vacuously true.
We adopt this convention because we want statements like "if
a number is a perfect square then it is not prime" to be true, for
instance when the number is 
  
    
      
        5
      
    
    {\displaystyle 5}
   or when the number is 
  
    
      
        6
      
    
    {\displaystyle 6}
  .
The diagram

shows that 
  
    
      
        Q
      
    
    {\displaystyle Q}
   holds whenever 
  
    
      
        P
      
    
    {\displaystyle P}
   does (another phrasing is
"
  
    
      
        P
      
    
    {\displaystyle P}
   is sufficient to give 
  
    
      
        Q
      
    
    {\displaystyle Q}
  ").
Notice again that if 
  
    
      
        P
      
    
    {\displaystyle P}
   does not hold, 
  
    
      
        Q
      
    
    {\displaystyle Q}
   may or may not
be in force.
There are two main ways to establish an implication.
The first way is direct: assume that 
  
    
      
        P
      
    
    {\displaystyle P}
   is true and, using that
assumption, prove 
  
    
      
        Q
      
    
    {\displaystyle Q}
  .
For instance,
to show "if a number is divisible by 5 then twice that
number is divisible by 10", assume that the number is 
  
    
      
        5
        n
      
    
    {\displaystyle 5n}
   and
deduce that 
  
    
      
        2
        (
        5
        n
        )
        =
        10
        n
      
    
    {\displaystyle 2(5n)=10n}
  .
The second way is indirect: prove the
contrapositive
statement: "if 
  
    
      
        Q
      
    
    {\displaystyle Q}
   is false then 
  
    
      
        P
      
    
    {\displaystyle P}
   is false"
(rephrased, "
  
    
      
        Q
      
    
    {\displaystyle Q}
   can only be false when 
  
    
      
        P
      
    
    {\displaystyle P}
   is also false").
As an example, to show "if a number is prime then it
is not a perfect
square", argue that if it were a square 
  
    
      
        p
        =
        
          n
          
            2
          
        
      
    
    {\displaystyle p=n^{2}}
   then it could be
factored 
  
    
      
        p
        =
        n
        ⋅
        n
      
    
    {\displaystyle p=n\cdot n}
   where 
  
    
      
        n
        <
        p
      
    
    {\displaystyle n