Mastering Real Analysis Tactics In Lean 4: A Practical Guide

Welcome, fellow mathematicians and Lean enthusiasts! Today, we're diving deep into the fascinating world of Real Analysis within the Lean 4 theorem prover. If you've been exploring Lean for formalizing mathematical proofs, you've likely encountered tactics that seem a bit… opaque. Many resources explain what a tactic does, but fail to provide concrete examples or clear type signatures, leaving you scratching your head. This is especially true for tactics that deal with foundational concepts like existence statements. One such area that can be tricky is understanding how to effectively use tactics like choose. This guide aims to demystify these powerful tools, providing clear explanations, practical examples, and the crucial type signatures you need to wield them with confidence. We'll break down the choose tactic and illustrate its usage in the context of real analysis proofs, making your formalization journey smoother and more productive.

Understanding the choose Tactic: Extracting Witnesses from Existence Statements

The choose tactic is a cornerstone for working with existential quantifiers (statements of the form ∃x, P(x)). In mathematics, when we prove an existence statement, we don't just assert that something exists; we often implicitly or explicitly provide a witness – a specific object that satisfies the property. The choose tactic in Lean 4 formalizes this process. Its primary purpose is to take an existing hypothesis that asserts the existence of some object with a certain property and extract that object as a new variable in your proof context. This new variable, often called a "witness," can then be used in subsequent steps of your proof. The fundamental idea behind choose is that if you have a proof that ∃x, P(x), then you know there is such an x, and you want to name it so you can reason about it. Without choose, you'd be stuck with a statement like ∃x, P(x) without being able to refer to the x that makes P(x) true.

Let's consider the core functionality of choose. When you apply choose to a hypothesis h : ∃x, P x, Lean will, by default, introduce a new variable (let's call it w) and a new hypothesis (let's call it hw) that essentially states hw : P w. The choose tactic is quite flexible. You can often specify the names for both the witness variable and the hypothesis that states the property holds for that witness. For instance, choose w hw using h would attempt to extract a witness w from the hypothesis h, asserting that P w holds, and naming this assertion hw. If you omit the names, Lean will generate them automatically, often using names like ᾰ, ᾰ_1, etc., which are functional but can make proofs harder to read. Therefore, it's highly recommended to provide meaningful names for your witnesses and their associated hypotheses. This clarity is paramount in complex formal proofs. Think of it like naming variables in a traditional programming language – descriptive names make the code (or in this case, the proof) much easier to understand and debug. The choose tactic is particularly powerful when combined with other tactics, allowing you to break down complex existential statements into manageable pieces. It's the bridge between asserting existence and constructively using that existence in your argument. It’s the tool that allows you to say, “Yes, I know something exists that satisfies this condition, and now I’m going to give it a name so I can work with it.” This is crucial in many areas of mathematics, including real analysis, where existence theorems are abundant.

choose Tactic: Syntax and Type Signatures

Understanding the syntax and type signatures of the choose tactic is crucial for effective use. The general form of the choose tactic looks something like this:

choose <witness_name> <hypothesis_name> using <hypothesis_with_exists>

Let's break this down:

• <witness_name>: This is the name you want to give to the existential witness. This will be a new variable introduced into your local context.
• <hypothesis_name>: This is the name you want to give to the new hypothesis that states the property holds for the <witness_name>. This hypothesis will essentially be P(<witness_name>).
• using <hypothesis_with_exists>: This specifies which hypothesis in your current context contains the existential statement ∃x, P(x) that you want to deconstruct.

If you omit <witness_name> and <hypothesis_name>, Lean will generate default names. However, as stressed before, explicit naming is highly beneficial for readability and maintainability of your proofs.

Now, let's consider the type signature. While tactics don't have type signatures in the same way that functions or definitions do in Lean, their behavior is dictated by the types of the hypotheses they operate on. When choose is applied to a hypothesis h of type ∃x, P x, where P is a predicate (a function returning a Prop), the tactic transforms this hypothesis into:

1. A new variable w of type X (where X is the type of x in the original ∃x, P x).
2. A new hypothesis hw of type P w.

So, effectively, the transformation is:

h : ∃x, P x choose> w : X and hw : P w

The type of P here is X → Prop. The choose tactic relies on the fact that if an existential statement is true, there must exist a specific element of type X that makes the predicate P true. The tactic provides you with direct access to this element (w) and asserts that the predicate holds for it (hw). This is a constructive aspect of Lean's logic. It's important to note that the choose tactic requires a proof of the existential statement. You can't just apply it to a statement that hasn't been proven yet. The hypothesis h must already be present in your context, meaning you've already established its truth through other means.

A Concrete Example: Proving Properties of Real Numbers

Let's illustrate the choose tactic with a practical example relevant to real analysis. Suppose we want to prove a simple statement: if for every positive real number y, there exists a real number x such that x^2 = y, then for any positive real number a, there exists a real number b such that b^2 = a.

This might seem trivial, but it demonstrates how choose helps us transfer universally quantified information to a specific instance. In Lean, this could look something like this:

import Mathlib.Tactic
import Mathlib.Data.Real.Basic

-- Assume the following lemma has been proven elsewhere:
lemma exists_sqrt_for_positive_real (y : ℝ) (hy : 0 < y) : ∃ x : ℝ, x^2 = y := by -- This is a placeholder, a real proof would be more involved
  sorry

-- Our goal: If for every positive y, there exists an x such that x^2 = y,
-- then for any positive a, there exists a b such that b^2 = a.
theorem transfer_exists_sqrt (a : ℝ) (ha : 0 < a) : ∃ b : ℝ, b^2 = a := by
  -- We are given that for every positive real number `y`, there exists `x` such that `x^2 = y`.
  -- Let's formalize this given premise. We can think of it as a general property.
  -- In a real proof, this would likely be a universally quantified statement like `∀ y, 0 < y → ∃ x, x^2 = y`.
  -- For this example, let's assume we have access to `exists_sqrt_for_positive_real`
  -- which is the `∃ x, x^2 = y` part for a given `y` and `0 < y`.

  -- Our goal is to show `∃ b : ℝ, b^2 = a`.
  -- We know `a` is positive (`ha : 0 < a`).
  -- We can use the `exists_sqrt_for_positive_real` lemma by substituting `a` for `y`.
  apply exists_sqrt_for_positive_real
  exact ha -- This provides the `hy : 0 < y` part for our specific `a`.

  -- Now, Lean has applied the lemma, and our goal is likely transformed. 
  -- However, the prompt implies a scenario where we might *already* have
  -- an existential hypothesis and need to extract from it.
  -- Let's adjust the scenario slightly to better showcase `choose`.

-- Let's refine the example to directly use `choose` on an existential hypothesis.

theorem choose_example (P : ℝ → Prop) (hP_exists : ∃ x : ℝ, P x) : P (Classical.choose hP_exists) := by
  -- We have a hypothesis `hP_exists` which states that there exists a real number `x` such that `P x` is true.
  -- We want to show that `P` holds for a specific witness.
  -- The `choose` tactic allows us to extract this witness.
  
  -- Let's use `choose` to name the witness `w` and the fact that `P w` is true as `hP_w`.
  choose w hP_w using hP_exists
  
  -- After `choose w hP_w using hP_exists`, our context now contains:
  -- w : ℝ
  -- hP_w : P w
  -- And the original hypothesis `hP_exists` is gone (or transformed).
  -- Our goal is to show `P w`.
  
  -- We can now directly use the hypothesis `hP_w` to prove our goal.
  exact hP_w

-- A slightly more complex example, showing how the extracted witness can be used.
theorem choose_example_2 (a : ℝ) (ha : 0 < a) : ∃ b : ℝ, b^2 = a := by
  -- Let's assume we have a lemma that states: for any positive real `y`, its square root exists.
  -- `lemma sqrt_exists (y : ℝ) (hy : 0 < y) : ∃ x : ℝ, x^2 = y := Real.sqrt_eq_iff_sq_eq.mpr (le_of_lt hy)` -- Using a mathlib lemma
  
  -- Apply the lemma. This adds an existential hypothesis to our context.
  -- The goal here is not to *prove* the existence, but to *use* it.
  -- Let's simulate having such a hypothesis already.
  
  have h_exists_b : ∃ b : ℝ, b^2 = a := by 
    apply Real.sqrt_eq_iff_sq_eq.mpr
    exact ha

  -- Now we have `h_exists_b : ∃ b : ℝ, b^2 = a` in our context.
  -- We want to show `∃ b : ℝ, b^2 = a`. The goal is already met if we can construct a witness.
  -- This is a bit meta. Let's rephrase: Suppose we have a function `f` and we want to show `∃ x, f x = 5`.
  -- If we prove `f(2) = 5`, we can use `exists.intro 2 (by apply f_eq_5)`.
  -- The `choose` tactic is for when you have `∃ x, P x` and you want to name `x` and `P x`.
  
  -- Let's focus on extracting information from an *existing* existential hypothesis.
  -- Suppose we have a proof that `∃ x, P x`.
  -- And we want to show `Q(x)` for that `x`.

  -- Example: If there exists a real number `x` such that `x > 5`, then `x > 0`.
  -- Let's formalize `∃ x : ℝ, x > 5` as a hypothesis.
  let P := fun x : ℝ => x > 5
  let h_exists_x : ∃ x : ℝ, P x := Exists.intro 6 (by -- 6 is a witness for x > 5
    norm_num -- Proof that 6 > 5
  )
  
  -- Now, let's use `choose` on `h_exists_x`.
  -- We want to show `P (Classical.choose h_exists_x)`, which is `(Classical.choose h_exists_x) > 5`.
  -- Or, more generally, we want to use the witness.

  -- Let's try proving: If there exists `x` s.t. `x^2 = 4`, then `x ≠ 0`.
  -- This requires us to extract `x`.
  
  have h_sq_4 : ∃ x : ℝ, x^2 = 4 := by 
    apply Exists.intro 2 -- Witness is 2
    norm_num -- Proof that 2^2 = 4

  -- Now, apply `choose` to `h_sq_4`.
  -- We want to extract `x` and prove `x ≠ 0`.
  choose x hx using h_sq_4
  -- Now `x : ℝ` and `hx : x^2 = 4` are in our context.
  -- Our goal is to show `x ≠ 0`.
  
  -- We can use `hx` (which is `x^2 = 4`) to prove `x ≠ 0`.
  -- If `x = 0`, then `x^2 = 0`, which contradicts `x^2 = 4`.
  
  by_contradiction -- Assume `x = 0`
  intro h_x_eq_0
  rw [h_x_eq_0] at hx -- Substitute `x = 0` into `hx`
  simp at hx -- `simp` can simplify `0^2 = 4` to `0 = 4`
  -- Now `hx` is `0 = 4`, which is false.
  -- `simp` will recognize this contradiction, or we can use `exact False.elim` if needed.
  -- The contradiction is implicitly handled by `simp` or the theorem prover.
  -- Let's make it explicit for clarity:
  cases hx -- `hx` is `0 = 4`, which is `False`

In the choose_example above, we show that if we have any hypothesis hP_exists : ∃ x : ℝ, P x, we can extract a witness w and a proof hP_w : P w using choose w hP_w using hP_exists. We then simply use hP_w to satisfy the goal P w. The choose_example_2 is a bit more illustrative, showing how you might have an existential statement (here, ∃ x : ℝ, x^2 = 4) and then use choose to name the x and its property (x^2 = 4), and then use that property to prove something else about x (namely, x ≠ 0). This demonstrates the constructive power of choose: it doesn't just assert existence; it gives you the object to work with.

Why choose is Important in Formalizing Real Analysis

Real Analysis is replete with theorems that assert the existence of objects. Consider the Intermediate Value Theorem, which guarantees the existence of a root within an interval. Or theorems about the existence of suprema and infima for bounded sets. Formalizing these theorems in Lean requires rigorously managing these existential claims. The choose tactic is indispensable here. When a theorem proves ∃ x, P x, formalizing the proof often involves extracting that x using choose so that you can then analyze its properties, show it satisfies further conditions, or use it to construct another object.

For example, proving that a continuous function on a closed interval attains its maximum value. The proof often relies on the existence of a supremum for the set of function values. Once the existence of the supremum (let's call it s) is established, you'd use choose to get a handle on s and potentially construct a sequence that converges to s, or show that s itself is attained by the function. Without choose, you'd be left with the abstract statement "the supremum exists" without a way to refer to it directly in your proof steps. This is why understanding choose and its associated syntax (like Classical.choose which is the underlying function choose uses, though choose as a tactic is more user-friendly) is so vital. It transforms an abstract existence claim into a concrete object within your formal proof, enabling you to proceed constructively. The formalization of mathematics is not just about verifying statements; it's about building proofs constructively, and choose is a key tool in this endeavor, allowing us to give names to the mathematical objects whose existence we have proven. This direct manipulation of proven-into-existence objects is what makes formal systems like Lean so powerful for exploring the foundations of mathematics.

Conclusion

Navigating the intricacies of theorem provers like Lean 4 can be challenging, especially when tactics lack explicit examples. The choose tactic, fundamental for handling existential statements, is one such area where clarity is essential. By understanding its syntax, its role in deconstructing ∃ statements, and its practical application through examples, you can significantly enhance your ability to formalize complex mathematical arguments in real analysis and beyond. Remember, the goal of formalization is not just to verify, but to build robust, constructive proofs. Tactics like choose are your allies in this quest, bridging the gap between abstract existence and tangible mathematical reasoning.

For further exploration into Lean 4 and its vast mathematical library, I highly recommend visiting the ** Mathlib Documentation**. It's an invaluable resource for understanding tactics, definitions, and theorems in Lean.