Classical reasoning support

noncomputable def Classical.indefiniteDescription {α : Sort u} (p : α → Prop) (h : ∃ (x : α), p x) : { x : α // p x }

Equations

• Classical.indefiniteDescription p h = Classical.choice ⋯

noncomputable def Classical.choose {α : Sort u} {p : α → Prop} (h : ∃ (x : α), p x) : α

Equations

• Classical.choose h = (Classical.indefiniteDescription p h).val

theorem Classical.choose_spec {α : Sort u} {p : α → Prop} (h : ∃ (x : α), p x) : p (Classical.choose h)

theorem Classical.em (p : Prop) : p ∨ ¬p

Diaconescu's theorem: excluded middle from choice, Function extensionality and propositional extensionality.

theorem Classical.exists_true_of_nonempty {α : Sort u} : Nonempty α → ∃ (x : α), True

noncomputable def Classical.inhabited_of_nonempty {α : Sort u} (h : Nonempty α) : Inhabited α

Equations

• Classical.inhabited_of_nonempty h = { default := Classical.choice h }

noncomputable def Classical.inhabited_of_exists {α : Sort u} {p : α → Prop} (h : ∃ (x : α), p x) : Inhabited α

Equations

• Classical.inhabited_of_exists h = Classical.inhabited_of_nonempty ⋯

noncomputable def Classical.propDecidable (a : Prop) : Decidable a

All propositions are Decidable.

Equations

• Classical.propDecidable a = Classical.choice ⋯

noncomputable def Classical.decidableInhabited (a : Prop) : Inhabited (Decidable a)

Equations

• Classical.decidableInhabited a = { default := inferInstance }

noncomputable def Classical.typeDecidableEq (α : Sort u) : DecidableEq α

Equations

• Classical.typeDecidableEq α x✝ x = inferInstance

noncomputable def Classical.typeDecidable (α : Sort u) : α ⊕' (α → False)

Equations

• Classical.typeDecidable α = match Classical.propDecidable (Nonempty α) with | isTrue hp => PSum.inl default | isFalse hn => PSum.inr ⋯

noncomputable def Classical.strongIndefiniteDescription {α : Sort u} (p : α → Prop) (h : Nonempty α) : { x : α // (∃ (y : α), p y) → p x }

Equations

• One or more equations did not get rendered due to their size.

noncomputable def Classical.epsilon {α : Sort u} [h : Nonempty α] (p : α → Prop) : α

the Hilbert epsilon Function

Equations

• Classical.epsilon p = (Classical.strongIndefiniteDescription p h).val

theorem Classical.epsilon_spec_aux {α : Sort u} (h : Nonempty α) (p : α → Prop) : (∃ (y : α), p y) → p (Classical.epsilon p)

theorem Classical.epsilon_spec {α : Sort u} {p : α → Prop} (hex : ∃ (y : α), p y) : p (Classical.epsilon p)

theorem Classical.epsilon_singleton {α : Sort u} (x : α) : (Classical.epsilon fun (y : α) => y = x) = x

theorem Classical.axiomOfChoice {α : Sort u} {β : α → Sort v} {r : (x : α) → β x → Prop} (h : ∀ (x : α), ∃ (y : β x), r x y) : ∃ (f : (x : α) → β x), ∀ (x : α), r x (f x)

the axiom of choice

theorem Classical.skolem {α : Sort u} {b : α → Sort v} {p : (x : α) → b x → Prop} : (∀ (x : α), ∃ (y : b x), p x y) ↔ ∃ (f : (x : α) → b x), ∀ (x : α), p x (f x)

theorem Classical.propComplete (a : Prop) : a = True ∨ a = False

theorem Classical.byCases {p : Prop} {q : Prop} (hpq : p → q) (hnpq : ¬p → q) : q

theorem Classical.byContradiction {p : Prop} (h : ¬p → False) : p

theorem Classical.not_not {a : Prop} : ¬¬a ↔ a

The Double Negation Theorem: ¬¬P is equivalent to P. The left-to-right direction, double negation elimination (DNE), is classically true but not constructively.

@[simp]

theorem Classical.not_forall {α : Sort u_1} {p : α → Prop} : (¬∀ (x : α), p x) ↔ ∃ (x : α), ¬p x

theorem Classical.not_forall_not {α : Sort u_1} {p : α → Prop} : (¬∀ (x : α), ¬p x) ↔ ∃ (x : α), p x

theorem Classical.not_exists_not {α : Sort u_1} {p : α → Prop} : (¬∃ (x : α), ¬p x) ↔ ∀ (x : α), p x

theorem Classical.forall_or_exists_not {α : Sort u_1} (P : α → Prop) : (∀ (a : α), P a) ∨ ∃ (a : α), ¬P a

theorem Classical.exists_or_forall_not {α : Sort u_1} (P : α → Prop) : (∃ (a : α), P a) ∨ ∀ (a : α), ¬P a

theorem Classical.or_iff_not_imp_left {a : Prop} {b : Prop} : a ∨ b ↔ ¬a → b

theorem Classical.or_iff_not_imp_right {a : Prop} {b : Prop} : a ∨ b ↔ ¬b → a

theorem Classical.not_imp_iff_and_not {a : Prop} {b : Prop} : ¬(a → b) ↔ a ∧ ¬b

theorem Classical.not_and_iff_or_not_not {a : Prop} {b : Prop} : ¬(a ∧ b) ↔ ¬a ∨ ¬b

theorem Classical.not_iff {a : Prop} {b : Prop} : ¬(a ↔ b) ↔ (¬a ↔ b)

@[reducible]

noncomputable def Exists.choose {α : Sort u_1} {p : α → Prop} (P : ∃ (a : α), p a) : α

Extract an element from a existential statement, using Classical.choose.

Equations

• Exists.choose P = Classical.choose P

theorem Exists.choose_spec {α : Sort u_1} {p : α → Prop} (P : ∃ (a : α), p a) : p (Exists.choose P)

Show that an element extracted from P : ∃ a, p a using P.choose satisfies p.