//
Skip to main content
PRL Project

Constructive reading of classical logic
Table of Contents

Previous Page Next Page

Kleene 84: {∀x:T.{A x} ⇔ ~(∃x:T.~(A x))}

This proof is interesting because this is the first encountered of Kleene's theorems that is doubly squashed - there is an outer squashing and a squashing of the inner (A x) of the ∀x.T:(A x). While we've seen that the outer squashing on the classical direction of theorems can be discarded immediately, we'll see that the inner squashing can also easily be discarded. If we have False or a squashed goal, for which both carry no evidence, we can open squashed terms in our hypotheses. Kleene theorem 85 is similar to this one.

We can use the construction rule to get down to the goal False. We can then spread the 'for all' operator in our hypotheses to give us x : T and {A x}. Since we have False as our goal, which has no evidence term, we can open the squashed term {A x} in the hypotheses because it has similar evidence. The tactic for revealing squashed hypotheses is ExposeClassical. The rest of the proof can be solved constructively without problem.

The backwards direction't can't be proved constructively. We can take off the outer squashing immediately and get down to the goal {A x}. We need to do a classical contradiction on this term because we can then apply the function f, as defined below in the second table, and instantiate x. We then have the goal ¬(A x), which we have evidence for from the classical contradiction.

∀[T:Type]. ∀[A: T → ℙ]. {∀x:T.(A x) ⇔ ¬(∃x:T.¬(A x)}
{∀x:T.{A x} ⇒ ¬(∃x:T.¬(A x))} ⇒ Extract: λf.λg.spread(g; x,nax.ap(nax.ap(f.x)))
∀x:T.{A x} ⇒ ¬(∃x:T.¬(A x))by λ(f.___)
f : ∀x:T.{A x} ⊢ ¬(∃x:T.¬(A x))by λ(g.___)
f : ∀x:T.{A x}, g : ∃x:T.¬(A x) ⊢ Falseby spread(g; x,nax.___)
f : ∀x:T.{A x}, x : T, nax : ¬(A x) ⊢ Falseby apseq(f;x;ax.___)
ax : {A x}, x : T, nax : ¬(A x) ⊢ Falseby Open {A x} with False
ax : (A x), x : T, nax : ¬(A x) ⊢ Falseby ap(nax.___)
ax : (A x), x : T ⊢ (A x)by ax

{¬(∃x:T.¬(A x)) ⇒ ∀x:T.{A x}} ⇐ Extract: λf.λax.(CC;g.any(ap(f.<x;nax>)))
{¬(∃x:T.¬(A x)) ⇒ ∀x:T.{A x}}by λ(f.___) then unsquash goal
f : ¬(∃x:T.¬(A x)) ⊢ ∀x.T:{A x}by λ(x.___)
f : ¬(∃x:T.¬(A x)), x : T ⊢ {A x}by (CC{A x};nax.___) Classical contradiction
f : ¬(∃x:T.¬(A x)), x : T, nax : ¬(A x) ⊢ {A x}by apseq(f;___;False.any(..))
x : T, nax : ¬(A x) ⊢ ∃x:T.¬(A x)by pair(x;___)
x : T, nax : ¬(A x) ⊢ ¬(A x)by nax

Nuprl Proof

⊢ ∀[T:Type]. ∀[A:T → ℙ]. {∀x:T.{A x} ⇔ ¬(∃x:T.(¬(A x))} | BY Auto | 1. T: Type 2. A: T → P ⊢ {∀x:T. {A x} ⇔ ¬(∃x:T. (¬(A x)))} | BY RepeatFor 4 ((D 0 THENA Auto)) |\ | 3. ∀x:T. {A x} | ⊢ {¬(∃x:T. (¬(A x)))} | | 1 BY (ElimClassical THENA Auto) | | | ⊢ ¬(∃x:T. (¬(A x))) | | 1 BY (D 0 THENA Auto) | | | 4. ∃x:T. (¬(A x)) | ⊢ False | | 1 BY D 4 | | | 4. x: T | 5. ¬(A x) | ⊢ False | | 1 BY (InstHyp [⌈x⌉] 3· THENA Auto) | | | 6. {A x} | ⊢ False | | 1 BY D 6 | | | 6. x@0: Unit | 7. A x | ⊢ False | | 1 BY D 5 | | | 5. x@0: Unit | 6. A x | ⊢ A x | | 1 BY Hypothesis \ 3. ¬(∃x:T. (¬(A x))) ⊢ {∀x:T. {A x}} | BY (ElimClassical THENA Auto) | ⊢ ∀x:T. {A x} | BY (D 0 THENA Auto) | 1 4. x: T ⊢ {A x} | BY (ClassicalContradiction THENA Auto) | 5. ¬(A x) ⊢ {A x} | BY D 3 | 3. x: T 4. ¬(A x) ⊢ ∃x:T. (¬(A x)) | BY (InstConcl [⌈x⌉]· THENA Auto) | ⊢ ¬(A x) | BY Hypothesis Proof


Previous Page Next Page


Table of Contents