## Diagram: Formal Proof Structure for a Set Theory Theorem ### Overview The image is a diagram illustrating the step-by-step proof of a mathematical theorem using a formal proof assistant (likely Lean or a similar system). It visually breaks down the proof into its initial state, the tactics applied, the intermediate states, and the final conclusion. The diagram uses a flowchart style with text annotations and arrows to show the progression. ### Components/Axes The diagram is organized into three main vertical sections: 1. **Left Column (Tactics):** Lists the proof tactics used. 2. **Center Column (Proof Flow):** Shows the logical state of the proof before and after each tactic application, connected by downward-pointing block arrows. 3. **Right Column (Annotations):** Provides descriptive labels for the states. **Textual Elements & Spatial Grounding:** * **Top (Center):** The theorem statement. * **Left Side (Center-Left):** A curly brace labeled "Tactics" groups two lines of code. * **Right Side (Top-Right):** A curly brace labeled "Initial state" points to the first state block. * **Right Side (Center-Right):** A curly brace labeled "States" points to the second state block. * **Bottom (Center):** The text "Proof Finished". ### Detailed Analysis **1. Theorem Statement (Top Center):** ``` theorem my_subset_intsec_mono (h : s ⊆ t) : s ∩ u ⊆ t ∩ u := by ``` * **Language:** The text is in a formal proof language syntax. The primary language is English with embedded mathematical notation. * **Transcription:** The theorem is named `my_subset_intsec_mono`. It takes a hypothesis `h` which states that set `s` is a subset of set `t` (`s ⊆ t`). The goal to prove is that the intersection of `s` and `u` (`s ∩ u`) is a subset of the intersection of `t` and `u` (`t ∩ u`). The `:= by` indicates the start of the proof script. **2. Proof Flow & States (Center Column):** The proof progresses through two main states, separated by a downward arrow. * **Initial State (Top Block):** ``` h : s ⊆ t ⊢ s ∩ u ⊆ t ∩ u ``` * **Components:** This block lists the given hypothesis (`h`) and the goal to be proven (indicated by the turnstile symbol `⊢`). * **Annotation:** This block is labeled "Initial state" by the brace on the right. * **First Tactic Application (Arrow & Left Column):** A downward arrow points from the Initial State to the next state. To the left of this arrow is the first tactic: ``` intro x xsu ``` * **Tactic:** `intro` is used to introduce variables and hypotheses into the context. Here, it introduces a variable `x` and a hypothesis `xsu`. * **Intermediate State (Middle Block):** ``` h : s ⊆ t xsu : x ∈ s ∩ u ⊢ x ∈ t ∩ u ``` * **Components:** The context now includes the original hypothesis `h` and the new hypothesis `xsu`, which states that `x` is an element of `s ∩ u`. The goal has been transformed into proving that `x` is an element of `t ∩ u`. * **Annotation:** This block is labeled "States" by the brace on the right. * **Second Tactic Application (Arrow & Left Column):** A second downward arrow points from the Intermediate State to the final text. To the left of this arrow is the second tactic: ``` exact ⟨h xsu.1, xsu.2⟩ ``` * **Tactic:** `exact` is used to provide a precise term that proves the current goal. The term `⟨h xsu.1, xsu.2⟩` constructs a proof of the conjunction `x ∈ t ∩ u` by proving `x ∈ t` (using `h` on the first part of `xsu`) and `x ∈ u` (using the second part of `xsu`). * **Final State (Bottom Text):** ``` Proof Finished ``` * This text indicates the successful completion of the proof. ### Key Observations * **Proof Structure:** The diagram clearly shows a "proof by introduction and exact proof term" pattern, common in formal verification. * **State Transformation:** The core logical move is transforming a subset goal (`⊆`) into an element membership goal (`∈`) for an arbitrary element `x`, which is a standard technique. * **Notation:** The proof uses standard set theory notation (`⊆`, `∩`, `∈`) and logical notation (`⊢`). The pair notation `⟨...⟩` is used for constructing a proof of a conjunction (AND). * **Clarity:** The annotations ("Initial state", "Tactics", "States") effectively segment the diagram for educational purposes. ### Interpretation This diagram is an educational tool that deconstructs a concise formal proof into its logical steps. It demonstrates how high-level mathematical reasoning (proving a property about set intersections) is translated into a sequence of primitive, verifiable tactics in a proof assistant. * **What it demonstrates:** The proof shows that if `s` is contained in `t`, then anything common to `s` and another set `u` must also be common to `t` and `u`. The tactics reveal the underlying mechanism: take an arbitrary element from the left-hand intersection, use the subset hypothesis to show it's in `t`, and note it's already in `u` by definition. * **Relationship between elements:** The "Tactics" column contains the *instructions* or *actions*. The "States" column contains the *current knowledge* or *proof state*. The arrows show how each action transforms the state. The annotations provide a meta-commentary on the structure. * **Notable pattern:** The proof is minimal and efficient. It uses the `intro` tactic to set up the context perfectly for the `exact` tactic to finish in one step. There are no redundant steps or branching, indicating a straightforward, well-structured proof. The diagram itself is a clear example of how to visualize formal proof development for teaching or documentation.