Introduction to Proofs

Introduction to proofs in Propositional logic

◼
  • A proof or demonstration is a logical reasoning in which we show that a certain statement is true.
    • ◼
  • A theorem is a true statement that has a proof.
    • ◼
  • One of the fundamental objectives of this class is that the we learn to prove statements. That is, that we are able to construct proofs for true statements.
    • ◼
  • This section provides general guidelines on what procedures to take in order to prove propositions according to its logical propositional form that is, whether it is a negation, a disjunction, a conjunction, an implication, or an equivalence.
    • ◼
  • To prove ¬p we can assume p and arrive at a contradiction. That is, a proposition of a form p∨¬p.
    • ◼
  • Note that this also helps us prove p by assuming that ¬p is true and arriving at a contradiction.
    • ◼
  • To prove p∨q we can use any of the following methods:
    • ◼
  • Suppose ¬p and conclude q.
    • ◼
  • Suppose ¬q and conclude p.
    • ◼
  • Suppose ¬p and ¬q and get a contradiction.
    • ◼
  • Conclude p to then conclude p∨q.
    • ◼
  • Conclude q to then conclude p∨q.
    • ◼
  • To prove p∧q you can show p and q separately.
    • ◼
  • To prove pq you can use one of the following.
    • ◼
  • Suppose p is true and reason that q must be true. In this case we call p the hypothesis, and q the conclusion. This is called a direct proof.
    • ◼
  • Suppose that ¬q is true and then reason that ¬p must be true. This is called the contrapositive method.
    • ◼
  • Suppose that p is true, and that ¬q is true and arrive at a contradiction. This is called proof by contradiction. Note that sometimes we can will arrive to the contradiction being p∧¬p, in which case it is possible that the proof can be reconstructed to a proof by contrapositive.
    • When is pq false? A: When p is true and q is false. This is equivalent to saying when p is true and ¬q is true.
    ◼
  • There are though a few cases in which a proof by contradiction cannot be translated to a proof by contrapositive.
    • ◼
  • To prove p⧦q we can use any of the following methods:
    • ◼
  • Prove separately that pq and that qp. This method is known as the double implication method.
    • ◼
  • Find a statement r such that p and r are equivalent and q and r are equivalent.
    • ◼
  • In the case of propositional logic we will only have one inference rule.
    • ◼
  • From p and p→q we can infer q.
    • ◼
  • This inference rule is known as Modus Ponens
    • ◼
  • This is probably the most useful and simple tool used in deduction.
    • ◼
  • If we want to prove a statement of the form (p∨q)r we can prove both pr and qr.

    • Propositional Axioms

    ◼
  • Starting from the basics of propositional logic, together with an inference rule we can build formal proofs to statements.
    • ◼
  • Let us consider first the so called propositional axioms for some choice of propositions p,q,r:
    • 1
    .
    True
    2
    .
    p→(p∨q); p→(q∨p)
    3
    .
    ¬p→(¬q→¬(p∨q) )
    4
    .
    (p∧q)→p; (p∧q)→q
    5
    .
    p→(q→(p∧q))
    6
    .
    (p→(q→r))→((p→q)→(p→r))
    7
    .
    p→(¬p→False)
    8
    .
    (¬p→False)→p
    ◼
  • We will add extra ones for this class that just show the nature of equivalence as an abbreviation of a double implication:
    • 9
    .
    (p↔q) (pq); (p↔q) (qp)
    10
    .
    ((pq)∧(qp))(p↔q)
    ◼
  • Notice that each of these are meant to stand for any propositions p,q,r, not just in the case where they are atomic. As such we refer to these are axioms schemes rather than axioms them selves
    • ◼
  • That is, for example p→(p∨q) and p→(p∨(r∧s)) are both instances of axiom scheme 2. above.
    • ◼
  • When substituting atomic propositions for p,q, and r above notice that we get tautologies.

    • Formal Proofs

    ◼
  • In this section we will consider a set A of atomic propositions.
    • ◼
  • We let Prop(A) be the set of propositions built with atoms on A. Note that this set is built recursively by applying connectors to the elements of A, and the propositions built from it.
    • ◼
  • We will let Σ be a subset of Prop(A)
    • ◼
  • Let p∈Prop(A). A formal proof of p from Σ is a sequence
    p
    1
    ,
    p
    2
    ,...,
    p
    n
    with n≥1, and
    p
    n
    =p
    such that for k=1,...,n:
    • ◼
  • Either
    p
    k
    ∈Σ
    ,
    • ◼
  • or
    p
    k
    is a propositional axiom,
    • ◼
  • or there are
    i,j∈{1,...,k-1}
    such that pk can be inferred from
    p
    i
    and
    p
    j
    by Modus Ponens

    • Examples:

    ◼
  • Prove that from ((P∧Q)⟺R),(P⟺S),(S∧Q) we can conclude R.
    • ◼
  • We start with the premises and a few of our Axioms. We denote the use of the propositional axioms using bold notation.
    • 1
    .
    (P∧Q)⟺R (premise)
    2
    .
    (P⟺S) (Premise)
    3
    .
    (S∧Q) (Premise)
    4
    .
    (S∧Q)→S; (S∧Q)→Q (propositional axiom)
    5
    .
    S (Modus ponens 3 and 4)
    6
    .
    Q (Modus ponens 3 and 4)
    7
    .
    (P⟺S)(SP)(propositional axiom)
    8
    .
    SP (Modus ponens 2 and 7)
    9
    .
    P (Modus ponens 5 and 8)
    10
    .
    P(Q(P∧Q))(propositional axiom)
    11
    .
    Q(P∧Q) (Modus ponens 9 and 10)
    12
    .
    P∧Q (Modus ponens 6 and 11)
    13
    .
    ((P∧Q)⟺R)((P∧Q)R)(propositional axiom)(a↔b) (ab) a = (P∧Q) then ((P∧Q)↔b) ((P∧Q)b) b = R then ((P∧Q)↔R) ((P∧Q)R)
    14
    .
    (P∧Q)R (Modus ponens 1 and 13)
    15
    .
    R (Modus ponens 12 and 14)

    Extra note

    ◼
  • As we can see, the process is very cut and dry. One can actually take a few shortcuts and present the same proof in a more readable and concise way as follows:
    • 1
    .
    (P∧Q)⟺R (premise)
    2
    .
    (P⟺S) (Premise)
    3
    .
    (S∧Q) (Premise)
    4
    .
    S (from 3)
    5
    .
    Q (from 3)
    6
    .
    P (from 4 and 2)
    7
    .
    P∧Q (from 5 and 6)
    8
    .
    R from (1 and 7)
    ◼
  • This should be enough in terms of proving to a person but the reader should be mindful that the formal proof includes all 15 steps.

    • First Order Logic.

    Relations

    ◼
  • Let n∈. Let A be a set. By an n-ary relation on A we mean a set
    R⊆
    n
    A
    .
    • ◼
  • Examples:
    • ◼
  • {(n,m)∈
    2
    
    :nislessthanm}
    is a 2-ary (also called binary) relation on .
    • ◼
  • {n∈: n ∈} is a 1-ary (also called unary) relation on .
    • ◼
  • {n∈: n is prime} is a unary relation on .
    • ◼
  • {(p,q,r,s)∈
    4
    (
    2
    
    )
    :p,q,r,sarethecornersof
    a
    squareontheplane}
    is a 4-ary relation on
    2
    
    .
    • ◼
  • {(p,q,r)∈
    3
    
    :pq=r}
    is a 3-ary (also called ternary) relation on .
    • ◼
  • We will delve deeper into the properties of Relations in a future lesson, but it is important to get familiar with their definition now.
    • ◼
  • If a tuple of elements
    (
    a
    1
    ,...,
    a
    n
    )
    is in a relation
    R
    we usually write
    R(
    a
    1
    ,...,
    a
    n
    )
    . And say that
    (
    a
    1
    ,...,
    a
    n
    )
    satisfies R.
    • ◼
  • Sometimes if R is binary, and a tuple
    (a,b)
    belongs to R we write
    aRb
    • ◼
  • Examples
    • ◼
  • ⊆
    • ◼
  • <
    • ◼
  • ≤
    • ◼
  • =

    • Functions

    ◼
  • Let n∈. Let A be a set. By an n-ary function on A we mean a set
    F⊆
    n+1
    A
    such that for every
    (
    a
    1
    ,...,
    a
    n
    )∈
    n
    A
    there is a unique
    a
    n+1
    ∈A
    such that
    (
    a
    1
    ,...,
    a
    n
    ,
    a
    n+1
    )∈F
    . In this cases we usually write
    F(
    a
    1
    ,...,
    a
    n
    )=
    a
    n-1
    • ◼
  • We will see a more general and abstract definition of functions in the future but for First Order Logic we require a restricted definition as the one above.
    • ◼
  • Examples:
    • ◼
  • {(p,q,r)∈
    3
    
    :pq=r}
    is a binary function on .
    • ◼
  • {(n,k)∈
    2
    
    :
    2
    n
    =k
    } is a unary function on .

    • Predicates

    ◼
  • A predicate is a symbol that is used to represent a relation.It can thus be thought of as a symbol that represents a property (namely, the property that the elements of the relation satisfy, not unlike the properties in set builder notation).
    • ◼
  • We introduce the use of variables and constant symbols to apply predicates. Variables are going to be symbols that can represent an arbitrary object in our universe , while constant symbols, are going to be used to represent specific objects.
    • ◼
  • Consider the statement “John is a student and Mary is not”.
    • ◼
  • We can simply say that the statement above is a predicate and symbolize it by the letter p.
    • ◼
  • That does not give us as much information as if we used two symbols q and r to represent “John is a student” and “Mary is a student”. In this case we could symbolize the statement as q∧¬r. This gives us some extra information, in particular that we are talking about a disjunction and that if this statement was true, then r can not be true.
    • ◼
  • We can still add more information by symbolizing the property “is a student” by the symbol S and assign constant symbols such as j to John, and m to Mary. We can then symbolize the statement as S(j)∧¬S(m). This gives us the extra information that there is an element that satisfies S, and also one that does not. Further more we can also conclude that the objects that j and m are respectively representing are different.
    • ◼
  • In the case of a variable x the symbols S(x) would represent the variable statement “x is a student” whose truth value cannot be assigned a priori as different values of x would yield different truth values.
    • ◼
  • In a similar way in which we did the introduction of Predicates with one possible entry, we can also generalize and consider predicates with several entries.
    • ◼
  • Consider for example the statement "John and Mary are siblings".We can translate this to the property S(x,y) = “x and y are siblings” and we can use similar analysis to determine when substituting for x and y yields a true statement or a false one.
    • ◼
  • We can consider several other examples
    • ◼
  • “x is less than y”
    • ◼
  • “x is between y and z”
    • ◼
  • “x and y multiply out to z”

    • Quantifiers

    ◼
  • We will now introduce the notion of “quantification” into our symbolic system.
    • ◼
  • There are cases in which we would like to express that there is an element of a set that satisfies a specific property.
    • ◼
  • For example let j:="John", a:="Ana", and b:="Bob" represent the three roommates of a house. We might be interested in representing the statement p=“Someone (in the house) left the door unlocked”. If we use D(x) as “x left the door unlocked” we would be tempted to represent the statement as D(j)∨D(a)∨D(b).
    • ◼
  • We have ways of expressing the statement using propositional logic in the case that the set of possible witnesses for the property is finite.
    • ◼
  • This might get cumbersome if our list of possible witnesses is big. But, perhaps more importantly, this might be impossible if our list of possible witnesses is infinite.
    • ◼
  • Thus we introduce a new symbol to express this existence, namely ∃.
    • ◼
  • Thus we could symbolize p as ∃xD(x). Read as “There is x such that D(x)”.
    • ◼
  • We similarly introduce the symbol ∀. Where a statement of the form ∀xD(x) would be read as “for all x D(x)”. As opposed to possibly using a possibly very long conjunction.
    • ◼
  • We can then assign a truth value to statements involving quantifiers.
    • ◼
  • We can consider a generalized DeMorgan Principle. Namely, that for a predicate P(x)
    • ◼
  • ¬∀x P(x) is equivalent to ¬∃x ¬P(x)
    • ◼
  • ¬∃x P(x) is equivalent no ∀x ¬P(x)
    • ◼
  • IMPORTANT: We have to note that when we quantify we are actually quantifying over a particular set. And our universe may then determines whether the same statement can be true or false.
    • ◼
  • For example, in the universe of Natural numbers the statement: “¬∃x x<0” is true but in the universe of Integers this same statement will be false.
    • ◼
  • On the other hand there are statements whose truth value is independent on the Universe in which we quantify, for example ∀x x=x, or ∃x x≠x.

    • Other Proof Techniques

    ◼
  • There are several different ways of going about proving statements in first order logic. There are formal syntactic ways by following rules similar to those that we described above for propositional logic. Of course being more specific than propositional logic, all the methods above work, nevertheless, more specific techniques in syntactic proofs for first order logic are outside the scope of this class.
    • ◼
  • That being said there are a few common ways of tackling proofs and that is what we cover in this section.

    • Proving Existential Statements

    ◼
  • An existential statement is a statement of the form “There is ... such that...” in symbols we would usually write ∃xP(x).
    • ◼
  • For example: We can check the statement “There is a natural number less than 100 that is spelled in alphabetical order in English” is true by just showing that the statement holds for the number 40.
    • ◼
  • It can happen that there is more than one witness, for example consider the statement “There is an even whole number less than 9” we can choose any of the numbers 0,2,4,6,8 to show that the statement is correct and, logically speaking, the proof will yield the same result regardless of which witness we use.

    • Proving universal statements

    ◼
  • A universal statement is a statement of the form “For all ... we have ...”. In symbols we usually write ∀xP(x).
    • ◼
  • Proving a statement of the form ∀xP(x) is a bit more cumbersome than with existential ones. If we are dealing with a finite universe this can boil down to individually checking property P for all elements in our universe.
    • ◼
  • For example: If we are considering only single digit decimal numbers we can prove that “For all single digit numbers we have that the spelling of the number in English is not in alphabetical order”, by checking the spelling of each.one
    • ◼
  • For “zero” z comes after e, so 0 is not spelled in alphabetical order.
    • ◼
  • For “one” o comes after n, so 1 is not spelled in alphabetical order.
    • ◼
  • For “two” t comes after o, so 2 is not spelled in alphabetical order.
    • ◼
  • For “three” t comes after e, so 3 is not spelled in alphabetical order.
    • ◼
  • For “four” u comes after r, so 4 is not spelled in alphabetical order.
    • ◼
  • For “five” f comes after e, so 5 is not spelled in alphabetical order.
    • ◼
  • For “six” s comes after i, so 6 is not spelled in alphabetical order.
    • ◼
  • For “seven” s comes after e, so 7 is not spelled in alphabetical order.
    • ◼
  • For “eight” i comes after g, so 8 is not spelled in alphabetical order.
    • ◼
  • For “nine” n comes after i, so 9 is not spelled in alphabetical order.
    • ◼
  • Of course the process can be cumbersome depending on the size of the set and is impossible in the case of infinite sets.
    • ◼
  • That being said there is a general way of proving universal statements which includes introducing a variable to represent any arbitrary element in our set. As long as we don’t introduce any general assumptions on our arbitrary element, if we can conclude that the property holds for the element then we can conclude that it holds for all.
    • ◼
  • For example to prove that “For all natural numbers we have another natural number that is greater than it” (This statement can be symbolized as ∀xP(x) where P(x) can be of the form ∃y x<y) we can start by saying: Let n be a natural number. We then want to eventually get to prove P(n), namely that there is y such that n<y. We then use the technique above for proving existential which is getting a specific element (in terms of n). Namely we can use n+1. A clean proof would look as follows:
    • ◼
  • Let n∈
    • ◼
  • We want to show ∃y: n<y
    • ◼
  • Consider y =n+1.
    • ◼
  • note that n+1 ∈ and n<n+1.
    • ◼
  • Thus ∃y: n<y.
    • ◼
  • Since no further assumptions were made on n aside from membership in  we have
    • ◼
  • ∀x∃y x<y.

    • Induction

    ◼
  • When we are dealing with natural numbers (and in general any set of objects constructed recursively) there is a very powerful way of proving that they all satisfy a certain property. This is called the induction principle.
    • ◼
  • The induction principle states that if 0 satisfies a certain property, and we can show that if the property is satisfied by a number, then said property is satisfied by the next number, then we can conclude that the property holds for all natural numbers.
    • ◼
  • In symbols: Let P be a property. Show P(0), and show that P(k)P(k+1). then ∀n P(n), as long as we are quantifying over the natural numbers.
    • ◼
  • When we proceed this way we call P(k) our induction hypothesis.

    • A Few Examples

    1
    .
    Let us show that (¬b∧(¬ab))a.
    1
    .
    1
    .
    We suppose that ¬b∧(¬ab).
    1
    .
    2
    .
    The above indicates that we have both ¬b and ¬ab.
    1
    .
    3
    .
    Let us assume, for the purpose of contradiction, that a is false, thus ¬a is true.
    1
    .
    4
    .
    By modus Ponens we then get b (using ¬ab).
    1
    .
    5
    .
    But then we get a contradiction with b and ¬b.
    1
    .
    6
    .
    As we have arrived to a contradiction, we conclude that a is true.
    2
    .
    1
    .
    The statement “x is a real number distinct from 0” is equivalent to x>0∨x<0.
    2
    .
    2
    .
    We first assume that x>0.
    2
    .
    2
    .
    1
    .
    We multiply on both sides of the inequality x > x 0
    2
    .
    3
    .
    We now assume that x<0
    2
    .
    3
    .
    1
    .
    We multiply both side of the inequality by x, noting that we are multiplying by a negative. x x> 0
    2
    .
    4
    .
    Since we proved it for both cases, then we conclude.
    3
    .
    Show that if a number is a multiple of 6, then it is a multiple of 2.
    3
    .
    1
    .
    Let n be a multiple of 6. That means that there is k∈ such that n = 6k.
    3
    .
    2
    .
    We can factor 6, so n = 2(3k).
    3
    .
    3
    .
    Thus there is a number 3k∈ such that n = 2 (3k). Thus n is a multiple of 2
    4
    .
    1
    .
    We proceed by induction on n.
    4
    .
    1
    .
    5
    .
    Thus by the principle of induction we can conclude that for all n∈ we have 0+1+...+n = n(n+1)/2
    5
    .
    2
    .
    THis means that n is odd.
    5
    .
    3
    .
    THis means that n = 2k+1 for k∈

    Extra Notes (For the avid reader, aka optional)

    ◼
  • We note that the treatment of the topic of First order Logic was given informally. There is a formal, yet much more intricate, way of giving the definitions above that lies outside of the scope of this class. Nevertheless for the avid reader we include some of the basics of that formalization.

    • Languages

    ◼
  • A first order language is comprised of the following symbols:
    • 1
    .
    Logical connectives: ∧, ∨, ,⧦, ¬
    3
    .
    Equality: =
    4
    .
    Quantifiers: ∀ (read as “for all” or “for every”) ∃ (read as “exists” or sometimes “there is”).
    5
    .
    Constant Symbols: Usually denoted by letters disjoint from those used in the variables.
    6
    .
    Relation symbols: Where an arity is associated with each relation symbol. Usually denoted by capital letters.
    7
    .
    Function symbols: Where an arity is associated with each function symbol. Usually denoted by capital letters disjoint from the relation symbols.
    ◼
  • We may only consider languages in the future where we consider only the logical symbols ∧, and ¬ and ∀ as the only quantifier.
    • ◼
  • Since the first elements are contained in every language, we just abbreviate languages by writing their constant, relation and function symbols.
    • ◼
  • Examples:
    • ◼
  • Where ∈ is a binary relation symbol.
    • ◼
  • Where < is a binary relation symbol.
    • ◼
  • Where E is a binary relation symbol.
    • ◼
  • Where e is a constant symbol,
    • ◼
  • and × is a binary function symbol,
    • ◼
  • Where we have a function symbol for each real number.
    • ◼
  • Where 0 is a constant symbol,
    • ◼
  • and 1 is a constant symbol,
    • ◼
  • and + is a binary function symbol,
    • ◼
  • and × is a unary function symbol.

    • Terms

    ◼
  • Given a Language ℒ we build its terms recursively as follows:
    • ◼
  • τ is a term if it is a variable
    • ◼
  • τ is a term if it is a constant symbol

    • Formulas

    ◼
  • Given a language ℒ we build its formulas recursively as follows:
    • ◼
  • ϕ is a formula if there is a formula ψ and ϕ is of the form ¬ψ, ∀xψ, or ∃xψ

    • ℒ-Structures

    ◼
  • Up to this point everything has been completely syntactical. That is, everything has been purely symbolical, and we have not given an interpretation to any of the symbols that we have. In order to move on with the next step we will introduce the notion of ℒ-structures.
    • ◼
  • We can then extend the notion of interpretations to terms, and then we can speak on when certain formulas can be seen as propositions, or predicates. Those interested in such an approach to First Order Logic should consider taking a Logic course in the future.