//

## Kleene 61: {(A ∨ B) ⇔ (~A ⇒ B)}

∀[A,B: ℙ]. {(A ∨ B) ⇔ (¬A ⇒ B)}
{(A ∨ B) ⇒ (¬A ⇒ B)} ⇒ Extract: λf.λna.decide(f; a.any(na(a)); b.b)
 A ∨ B ⇒ (¬A ⇒ B) by λ(f.___) aob : A ∨ B ⊢ ¬A ⇒ B by λ(na.___) aob : A ∨ B, na : ¬A ⊢ B by decide(f; a. slot1 ; b. slot2 ) a : A, na : ¬A ⊢ B by apseq(na.__;False.any(..)) for slot1 a : A ⊢ A by a b : B, na : ¬A ⊢ B by b for slot2
{(¬A ⇒ B) ⇒ (A ∨ B)} ⇐ Extract: λf.(CC;g.inr(ap(f.λa.ap(f.λa.ap(g.inl(a))))))
 (¬A ⇒ B) ⇒ A ∨ B by λ(f.___) f : ¬A ⇒ B ⊢ A ∨ B by (CC{A ∨ B};g.___) Classical contradiction f : ¬A ⇒ B, g : ¬(A ∨ B) ⊢ A ∨ B by inr(___) f : ¬A ⇒ B, g : ¬(A ∨ B) ⊢ B by apseq(f;___;b.b) g : ¬(A ∨ B) ⊢ ¬A by λ(a.___) g : ¬(A ∨ B), a : A ⊢ False by ap(g.___) a : A ⊢ A ∨ B by inl(a)

### Nuprl Proof

⊢ ∀[A,B:ℙ]. {(A ∨ B) ⇔ (¬A ⇒ B)} | BY (D 0 THENA Auto) |\ | 1. A: ℙ | ⊢ ∀[B:ℙ]. {(A ∨ B) ⇔ (¬A ⇒ B)} | | 1 BY (D 0 THENA Auto) | |\ | | 2. B: ℙ | | ⊢ {A ∨ B ⇔ (¬A) ⇒ B} | | | 1 2 BY RepeatFor 4 ((D 0 THENA Auto)) | | |\ | | | 3. A ∨ B | | | ⊢ {(¬A) ⇒ B} | | | | 1 2 3 BY RepeatFor 2 ((D 0 THENA Auto)) | | | | | | | 4. ¬A | | | ⊢ {B} | | | | 1 2 3 BY D 3 | | | |\ | | | | 3. A | | | | ⊢ {B} | | | | | 1 2 3 4 BY D 4 | | | | | | | | | ⊢ A | | | | | 1 2 3 4 BY Hypothesis | | | \ | | | 3. B | | | ⊢ {B} | | | | 1 2 3 BY ElimClassical Unsquash goal | | | | | | | ⊢ B | | | | 1 2 3 BY Hypothesis | | \ | | 3. (¬A) ⇒ B | | ⊢ {A ∨ B} | | | 1 2 BY (ClassicalContradiction THENA Auto) Add contradiction of goal to hypotheses | | | | | 4. ¬(A ∨ B) | | ⊢ {A ∨ B} | | | 1 2 BY (ElimClassical THENA Auto) Unsquash goal | | | | | ⊢ A ∨ B | | | 1 2 BY D 3 | | |\ | | | 3. ¬(A ∨ B) | | | ⊢ ¬A | | | | 1 2 3 BY (D 0 THENA Auto) | | | | | | | 4. A | | | ⊢ False | | | | 1 2 3 BY D 3 | | | | | | | 3. A | | | ⊢ A ∨ B | | | | 1 2 3 BY (OrLeft THENA Auto) | | | | | | | ⊢ A | | | | 1 2 3 BY Hypothesis | | \ | | 3. ¬(A ∨ B) | | 4. B | | ⊢ A ∨ B | | | 1 2 BY (OrRight THENA Auto) | | | | | ⊢ B | | | 1 2 BY Hypothesis | \ | 2. B: ℙ | 3. {x:Unit| A ∨ B ⇔ (¬A) ⇒ B} | ⊢ Ax ∈ {x:Unit| A ∨ B ⇔ (¬A) ⇒ B} | | 1 BY Auto \ 1. A: ℙ 2. B: ℙ 3. {x:Unit| A ∨ B ⇔ (¬A) ⇒ B} ⊢ Ax ∈ {x:Unit| A ∨ B ⇔ (¬A) ⇒ B} | BY Auto PDF version of proof