Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 2 exercises

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 2

Exercise 2.1

A function of the form

    g : { A ∣ A is a structure } → { 0 , 1 }

is said to be finitary iff there exists a natural number n such that for all structures A and B, if A ( Pi ) = B ( Pi ) for every i < n, then g ( A ) = g ( B ).

Prove that for all finitary g, there is a sentence φ such that g is the truth table for φ.

Exercise 2.2

Prove that for every sentence φ, if φ is not logically equivalent to ⊥, then there exists a sentence logically equivalent to φ of the form

    ( Q0,0 ∧ Q0,1 ∧ ⋅ ⋅ ⋅ ∧ Q0,n ) ∨ ( Q1,0 ∧ Q1,1 ∧ ⋅ ⋅ ⋅ ∧ Q1,n ) ∨ ⋅ ⋅ ⋅ ∨ ( Qm,0 ∧ ⋅ ⋅ ⋅ ∧ Qm,n )

where each Qi,j is either Pj or ¬ Pj.

(This is called disjunctive normal form.)

As a hint, think about the truth table of φ.

Exercise 2.3

Prove that for every sentence φ, if φ is not logically equivalent to ⊤, then there exists a sentence logically equivalent to φ of the form

    ( Q0,0 ∨ Q0,1 ∨ ⋅ ⋅ ⋅ ∨ Q0,n ) ∧ ( Q1,0 ∨ Q1,1 ∨ ⋅ ⋅ ⋅ ∨ Q1,n ) ∧ ⋅ ⋅ ⋅ ∧ ( Qm,0 ∨ ⋅ ⋅ ⋅ ∨ Qm,n )

where each Qi,j is either Pj or ¬ Pj.

(This is called conjunctive normal form.)

Exercise 2.4

A set of symbols S is called complete iff for every sentence, there exists a logically equivalent sentence that is built up using only parameters and symbols in S.

The two previous exercises show that { ⊥ , ¬ , ∧ , ∨ } and { ⊤ , ¬ , ∧ , ∨ } are complete sets of symbols.

  1. Prove that the following are complete sets of symbols:

    1. { ¬ , ∧ }
    2. { ¬ , ∨ }
    3. { ¬ , → }
  2. Prove that the following are not complete sets of symbols:

    1. { ¬ }
    2. { ∧ , ∨ , → , ↔ }

      Hint: For 2.4.2.2, consider the structure A such that A ( Pn ) = 1 for every n.

Exercise 2.5

Define a binary operation NAND on the set of sentences by setting NAND ( φ , ψ ) equal to ¬ ( φ ∧ ψ ).

Let Σ be a theory such that

Prove that for every sentence, there is a logically equivalent sentence that belongs to Σ.

Exercise 2.6

  1. Prove that logical consequence ⊨ is a reflexive and transitive relation on the set of all sentences.

    (In other words, ⊨ is a partial ordering.)

  2. Prove that logical equivalence ╞╡ is a reflexive, symmetric and transitive relation on the set of all sentences.

    (In other words, ╞╡ is an equivalence relation.)

  3. Prove that ╞╡ has infinitely many equivalence classes and that each equivalence class is infinite.

Exercise 2.7

Let Σn be the set of sentences that involve only Pi for i < n.

Let ⊨n be the logical consequence relation ⊨ restricted to to Σn.

It follows easily from Exercise 2.6 that ⊨n is a partial ordering of Σn.

Let ╞╡n be the logical equivalence relation restricted to Σn.

It follows easily from Exercise 2.6 that ╞╡n is an equivalence relation on Σn.

  1. Prove that each ╞╡n equivalence class is infinite but there are only finitely many ╞╡n equivalence classes.
  2. Consider the following two diagrams.

    [⊤]
    |
    [⊥]
           
    [⊤]
    / \
    [P0] [¬ P0]
    \ /
    [⊥]

    The diagram on the left indicates that, considering Σ0 under ╞╡0, there are only two equivalence classes, those of ⊥ and ⊤.

    Also, moving up the left diagram corresponds to the relation ⊨0 between members of the equivalence classes.

    The diagram on the right indicates that, considering Σ1 under ╞╡1, there are only four equivalence classes, those of ⊥, P0, ¬ P0 and ⊤.

    Also, moving up the right diagram corresponds to the relation ⊨1 between members of the equivalence classes.

    Now choose a complete set of representatives for Σ2 under ╞╡2 and draw a corresponding diagram for the partial ordering ⊨2.

Exercise 2.8

Describe a computer algorithm for deciding whether an string of symbols is a sentence in Polish notation without parentheses or commas. Then, should it be a sentence, the algorithm continues by computing the truth table and deciding whether the sentence is valid or not.

Exercise 2.9

Complete the proof of Soundness Theorem 2.3.

Exercise 2.10

Complete the proof of Finiteness of Deductions Lemma 2.4.

Exercise 2.11

Let Σ be a theory.

Assume that for every natural number n, either Pn belongs to Σ or ¬ Pn belongs to Σ.

  1. Prove that Σ is complete.
  2. Prove that if Σ is consistent, then Σ has exactly one model.

Exercise 2.12

This exercise has been expanded into three, Exercises 2.22, 2.23 and 2.24, which have been added below.

Exercise 2.13

Complete the proof of Theorem 2.11.

In other words, address the ¬-in, R1, R2 and R3 rules in the right-to-left direction of the proof.

Exercise 2.14

Let Σ be a theory.

Describe a computer algorithm for listing all of the proofs from Σ.

Running the algorithm, the hypothetical computer would output p0 , then p1 , then p2 etc. so that

    { q ∣ q is a proof from Σ } = { pn ∣ n is a natural number }

Your algorithm will use Σ as an oracle, which means that in addition to the usual commands, it may query whether a given sentence belongs to Σ.

Exercise 2.15

What if your hypothetical computer were your actual computer but it could run forever without breaking down when left in isolation without any sort of interaction with other devices or beings. In particular, it has its own limitless power source.

You write a program based on your algorithm from Exercise 2.14 and run the program on your hypothetical computer. Will it perform as expected? Explain.

Exercise 2.16

Find a justification for the deduction

    { } ⊢ ( φ → ψ ) ↔ ( ( ¬ ψ ) → ( ¬ φ ) ).

The sentence ( ¬ ψ ) → ( ¬ φ ) is called the contrapositive of the sentence φ → ψ.

Exercise 2.17

Let φ and ψ be sentences such that φ ⊨ ψ but ψ ⊭ φ .

Prove that there is a sentence χ such that

    φ ⊨ χ but χ ⊭ φ

and

    χ ⊨ ψ but ψ ⊭ χ .

Suggestions:

1) Think about the special case in which φ is F and ψ is any satisfiable sentence.

2) Think about how this is related to Exercise 2.7.

Exercise 2.18

Let I and J be subsets of ω

Let φ be a sentence built up from Pn for n ∈ I.

Let ψ be a sentence built up from Pn for n ∈ J.

Assume φ ⊨ ψ.

Prove that there is a sentence χ that is built up from Pn for n ∈ I ∩ J such that φ ⊨ χ and χ ⊨ ψ .

Suggestion: First think about I = { 0 , 1 } and J = { 1 , 2 } .

Definitions and exercises 2.19 and 2.20 regarding graphs

The next two exercises apply propositional logic to the theory of graphs.

Define a graph to be a pair ( V , E ) where V is a set and E ⊆ V × V such that, for all x , y ∈ V,

The members of V are called vertices and the pairs in E are called edges.

Two vertices are said to be adjacent iff they form an edge.

A function c : V ↦ k is called a k-coloring iff c ( x ) ≠ c ( y ) for all ( x , y ) ∈ E.

In other words, a graph coloring assigns different colors to adjacent vertices.

Often, we consider a positive natural number k = { 0 , ... , k-1 } as the set of colors, in which case there are k many colors.

It is easy to see that for every subset W ⊆ V, if we put

    F = E ∩ ( W × W ),

then ( W , F ) is also a graph.

We refer to ( W , F ) as the subgraph of ( V , E ) that is induced by F in this situation.

Now we have the terminology needed for the following two exercises.

Exercise 2.19

Let ( V , E ) be a graph with V = ω.

Recall that ω = { 0 , 1 , 2 , 3 , etc } and 2 = { 0 , 1 }.

For m,n ∈ ω, let φm,n be the sentence

    ( ¬ Pm ∧ Pn ) ∨ ( Pm ∧ ¬ Pn )

Let Σ be the theory

    { φm,n | (m,n) ∈ E }.

Prove that the following three statements are equivalent:

  1. ( V , E ) has a 2-coloring.
  2. Σ is satisfiable.
  3. For every finite W ⊆ V, the subgraph of ( V , E ) induced by W has a 2-coloring.

Exercise 2.20

Let ( V , E ) be a graph with V = ω.

Recall that 3 = { 0 , 1 , 2 }.

Prove that the following two statements are equivalent:

  1. ( V , E ) has a 3-coloring.
  2. For every finite W ⊆ V, the subgraph of ( V , E ) induced by W has a 3-coloring.
Suggestion: For your solution, use the following notation. For all n ∈ ω and i ∈ 3, put

    Qn,i   equal to   P3n+i.

For yourself, perhaps, think of Qn,0 as a red light bulb, Qn,1 as a yellow light bulb, and Qn,2 as a green light bulb for each n ∈ ω.

Now seek inspiration from Exercise 2.19 but you will need to define and use a different theory.

Bonus exercise: A result of De Bruijn and Erdős says that, for every positive natural number k, Exercise 2.20 remains true if 3 is replaced by k. Generalize your solution to Exercise 2.20 to prove this.

Exercise 2.21

Consider the following justification.
  1. { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0 ∧ P1 by the ∧-out rule.
  2. { P0 ∧ P1 } ⊢ P0 by the ∧-out rule.
  3. { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0 by the rule R2 and lines 1 and 2.

Of course, this is not the only justifications of { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0.

Prove that every justification of { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0 uses rule R2 in its final line.

Hint: For each of the fourteen rules other than R2, explain why it cannot be used in the final line of a justification of { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0.

Exercise 2.22

Let S = { r | r is a function from n to 2 for some n ∈ ω }.

We will use the function restriction notation from Chapter 1.

In particular, if r ∈ S and m < n = dom ( r ), then r ↾ m = < r ( i ) | i < m > ∈ S.

We say that T is a binary tree iff T ⊆ S and, for every r : n → 2 and m < n, if r belongs to T, then r ↾ m belongs to T.

In particular, S is a binary tree.

An infinite branch through T is a function b : ω → 2 such that b ↾ n ∈ T for every n ∈ ω.

A famous result called Kőnig's Infinity Lemma says that if T is an infinite binary tree, then there is an infinite branch through T.

You may not use Kőnig's Infinity Lemma in this exercise because you are going to prove it.

  1. Briefly explain the following facts:

    1. S is countable.
    2. { b | b is an infinite branch through S } is uncountable.
    3. { T | T is a binary tree } is uncountable
    4. If T is an infinite binary tree, then there is a bijection from ω onto T.
  2. Let T be an infinite binary tree.

    Let f : ω → T be a bijection.

    Whenever n ∈ ω and dom ( f ( j ) ) = n, let δn,j be the conjunction of Pj and all those ¬ Pi with i ≠ j and dom ( f ( i ) ) = n.

    Written another way, δn,j is the sentence

        Pj ( ⋀ { ¬ Pi | dom ( f ( i ) ) = n and i ≠ j } ) .

    Let φn be the disjunction of all those δn,j with dom ( f ( j ) ) = n.

    Written another way, φn is the sentence

        { δn,j | dom ( f ( j ) ) = n } .

    Let ψn be the conjunction of all the sentences δn,j → δm,i with m ≤ n = dom ( f ( j ) ) and f ( i ) = f ( j ) ↾ m.

    Written another way, ψn is the sentence

        { δn,j → δm,i | m ≤ n = dom ( f ( j ) ) and f ( i ) = f ( j ) ↾ m } .

    Let Γn = { φn , ψn }.

    Let Σn = ⋃ { Γm | m ≤ n }.

    Let Σ = ⋃ { Σn | n ∈ ω }.

    1. Explain why each δn,j is a sentence. In other words, why is the conjunction in its definition finite?
    2. Explain why each φn is a sentence. In other words, why is the disjunction in its definition finite and nonempty?
    3. Explain why each ψn is a sentence. In other words, why is the conjunction in its definition finite and nonempty?
    4. Explain why Σ is an infinite theory.
    5. Prove that each Σn has a model.
    6. Prove that if A is a model of Σ and

          b = { f ( j ) | A ( Pj ) = 1 } ,

      then:

      1. b is a function,
      2. dom ( b ) = ω , and
      3. b is an infinite branch through T

    7. Use parts 5 and 6 and the Compactness Theorem 2.10 to prove Kőnig's Infinity Lemma.

    Exercise 2.23

    Let Σ be an infinite theory. Assume that every finite subtheory of Σ has a model.

    You may not use Compactness Theorem 2.10 in this exercise because you are going to learn a different proof of it.

    Let f : ω → Σ be a bijection.

    Let Σn = { f ( j ) | j < n and f ( j ) is built up from Pi for i < n }.

    Let S = { r | r is a function from n to 2 for some n ∈ ω }.

    Let T be the subset of S that consists of functions r : n → 2 such that, for every structure A, if A ( Pi ) = r ( i ) for all i < n, then A is a model of Σn.

    1. Explain why T is an infinite binary tree.
    2. By Kőnig's Infinity Lemma, T has an infinite branch.

      Let b : ω → 2 be an infinite branch through T.

      Define a structure A by setting A ( Pi ) = b ( i ) for all i ∈ ω.

      Prove that A is a model of Σ

    Exercise 2.24

    Let T be an infinite binary tree.

    You may not use Kőnig's Infinity Lemma in this exercise because you are going to learn its traditional proof.

    Notation:

    • For every r : m → 2, define Tr to be the set of s : n → 2 such that r = s ↾ m or s = r ↾ n.

      Each Tr is a subtree of T but it might not be infinite.

    • For all r : m → 2 and i ∈ 2, define r< i > to be the unique s : m + 1 → 2 such that s ↾ m = r and s ( m ) = i.

    Define a function b : ω → 2 by recursion by setting

        b ( n ) = 0 iff T( b ↾ n )< 0 > is infinite.

        b ( n ) = 1 iff T( b ↾ n )< 0 > is finite.

    1. Prove by induction on n ∈ ω that T b ↾ n is infinite.
    2. Prove that b : ω → 2 is an infinite branch through T.

    Link to an additional exercise with another application of the Compactness Theorem

        [PDF]