Natural Deduction and Proof-Theoretic Notions

Core Concepts

Single turnstile (⊢): Represents provability
- Shows something can be proven using natural deduction
- Based on syntactic manipulation
- Cannot talk about truth or falsity directly
- Deals with what can be proven within the system
Double turnstile (⊨): Represents tautological entailment
- Deals with truth values and valuations
- Used with truth tables
- Concerns semantic meaning
Important Note: While these are fundamentally different concepts, they are "extensionally equivalent" - they end up proving the same things, just through different methods

Definition: A sentence is a theorem if it can be proven starting from no assumptions
Parallels the concept of a tautology from truth tables
How to prove a theorem:
- Draw an assumption line with nothing above it
- First numbered sentence must be below the assumption line
- Must derive the sentence without using any assumptions
- Usually requires starting with a subproof
- Cannot prove something is NOT a theorem within the system
Example given in lecture:
- Proving N ∨ ¬N is a theorem
- Can be done through TND (tertium non datur) or indirect proof
- Shows that either a sentence or its negation must be true

Definition: Two sentences are provably equivalent if each can be proved from the other
Requirements:
- Need two separate complete proofs
- First proof: Start with sentence A, end with sentence B
- Second proof: Start with sentence B, end with sentence A
Example from lecture:
- Proving equivalence between U → I and ¬(U ∧ ¬I)
- Requires careful use of subproofs and negation rules
- Shows how to handle complex logical structures