The Following Are Equivalent (TFAE)

This file provides the tactics tfae_have and tfae_finish for proving goals of the form TFAE [P₁, P₂, ...].

Parsing and syntax

We implement tfae_have in terms of a syntactic have. To support as much of the same syntax as possible, we recreate the parsers for have, except with the changes necessary for tfae_have.

The following parsers are similar to those for have in Lean.Parser.Term, but instead of optType, we use tfaeType := num >> impArrow >> num (as a tfae_have invocation must always include this specification). Also, we disallow including extra binders, as that makes no sense in this context; we also include " : " after the binder to avoid breaking tfae_have 1 → 2 syntax (which, unlike have, omits " : ").

def Mathlib.Tactic.TFAE.tfaeHave : Lean.ParserDescr

tfae_have introduces hypotheses for proving goals of the form TFAE [P₁, P₂, ...]. Specifically, tfae_have i <arrow> j := ... introduces a hypothesis of type Pᵢ <arrow> Pⱼ to the local context, where <arrow> can be →, ←, or ↔. Note that i and j are natural number indices (beginning at 1) used to specify the propositions P₁, P₂, ... that appear in the goal.

example (h : P → R) : TFAE [P, Q, R] := by
  tfae_have 1 → 3 := h
  ...

The resulting context now includes tfae_1_to_3 : P → R.

Once sufficient hypotheses have been introduced by tfae_have, tfae_finish can be used to close the goal. For example,

example : TFAE [P, Q, R] := by
  tfae_have 1 → 2 := sorry /- proof of P → Q -/
  tfae_have 2 → 1 := sorry /- proof of Q → P -/
  tfae_have 2 ↔ 3 := sorry /- proof of Q ↔ R -/
  tfae_finish

All relevant features of have are supported by tfae_have, including naming, destructuring, goal creation, and matching. These are demonstrated below.

example : TFAE [P, Q] := by
  -- `tfae_1_to_2 : P → Q`:
  tfae_have 1 → 2 := sorry
  -- `hpq : P → Q`:
  tfae_have hpq : 1 → 2 := sorry
  -- inaccessible `h✝ : P → Q`:
  tfae_have _ : 1 → 2 := sorry
  -- `tfae_1_to_2 : P → Q`, and `?a` is a new goal:
  tfae_have 1 → 2 := f ?a
  -- create a goal of type `P → Q`:
  tfae_have 1 → 2
  · exact (sorry : P → Q)
  -- match on `p : P` and prove `Q`:
  tfae_have 1 → 2
  | p => f p
  -- introduces `pq : P → Q`, `qp : Q → P`:
  tfae_have ⟨pq, qp⟩ : 1 ↔ 2 := sorry
  ...

Equations

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

def Mathlib.Tactic.TFAE.tfaeFinish : Lean.ParserDescr

tfae_finish is used to close goals of the form TFAE [P₁, P₂, ...] once a sufficient collection of hypotheses of the form Pᵢ → Pⱼ or Pᵢ ↔ Pⱼ have been introduced to the local context.

tfae_have can be used to conveniently introduce these hypotheses; see tfae_have.

Example:

example : TFAE [P, Q, R] := by
  tfae_have 1 → 2 := sorry /- proof of P → Q -/
  tfae_have 2 → 1 := sorry /- proof of Q → P -/
  tfae_have 2 ↔ 3 := sorry /- proof of Q ↔ R -/
  tfae_finish

Equations

• Mathlib.Tactic.TFAE.tfaeFinish = Lean.ParserDescr.node `Mathlib.Tactic.TFAE.tfaeFinish 1024 (Lean.ParserDescr.nonReservedSymbol "tfae_finish" false)

Setup

def Mathlib.Tactic.TFAE.getTFAEList (t : Lean.Expr) : Lean.MetaM (Q(List Prop) × List Q(Prop))

Extract a list of Prop expressions from an expression of the form TFAE [P₁, P₂, ...] as long as [P₁, P₂, ...] is an explicit list.

Equations

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

partial def Mathlib.Tactic.TFAE.getTFAEList.getExplicitList (l : Q(List Prop)) : Lean.MetaM (List Q(Prop))

Convert an expression representing an explicit list into a list of expressions.

Proof construction

partial def Mathlib.Tactic.TFAE.dfs (hyps : Array (ℕ × ℕ × Lean.Expr)) (atoms : Array Q(Prop)) (i : ℕ) (j : ℕ) (P : Q(Prop)) (P' : Q(Prop)) (hP : Q(«$P»)) : StateT (Std.HashSet ℕ) Lean.MetaM Q(«$P'»)

Uses depth-first search to find a path from P to P'.

def Mathlib.Tactic.TFAE.proveImpl (hyps : Array (ℕ × ℕ × Lean.Expr)) (atoms : Array Q(Prop)) (i : ℕ) (j : ℕ) (P : Q(Prop)) (P' : Q(Prop)) : Lean.MetaM Q(«$P» → «$P'»)

Prove an implication via depth-first traversal.

Equations

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

partial def Mathlib.Tactic.TFAE.proveChain (hyps : Array (ℕ × ℕ × Lean.Expr)) (atoms : Array Q(Prop)) (i : ℕ) (is : List ℕ) (P : Q(Prop)) (l : Q(List Prop)) : Lean.MetaM Q(List.Chain (fun (x1 x2 : Prop) => x1 → x2) «$P» «$l»)

Generate a proof of Chain (· → ·) P l. We assume P : Prop and l : List Prop, and that l is an explicit list.

partial def Mathlib.Tactic.TFAE.proveGetLastDImpl (hyps : Array (ℕ × ℕ × Lean.Expr)) (atoms : Array Q(Prop)) (i : ℕ) (i' : ℕ) (is : List ℕ) (P : Q(Prop)) (P' : Q(Prop)) (l : Q(List Prop)) : Lean.MetaM Q(«$l».getLastD «$P'» → «$P»)

Attempt to prove getLastD l P' → P given an explicit list l.

def Mathlib.Tactic.TFAE.proveTFAE (hyps : Array (ℕ × ℕ × Lean.Expr)) (atoms : Array Q(Prop)) (is : List ℕ) (l : Q(List Prop)) : Lean.MetaM Q(«$l».TFAE)

Attempt to prove a statement of the form TFAE [P₁, P₂, ...].

tfae_have components

def Mathlib.Tactic.TFAE.mkTFAEId : Lean.TSyntax ((((((`_private.Mathlib.Tactic.TFAE.num 0).str "Mathlib").str "Tactic").str "TFAE").str "Parser").str "tfaeType") → Lean.MacroM Lean.Name

Construct a name for a hypothesis introduced by tfae_have.

Equations

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

def Mathlib.Tactic.TFAE.elabIndex (i : Lean.TSyntax `num) (maxIndex : ℕ) : Lean.MetaM ℕ

Turn syntax for a given index into a natural number, as long as it lies between 1 and maxIndex.

Equations

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

Tactic implementation

def Mathlib.Tactic.TFAE.elabTFAEType (tfaeList : List Q(Prop)) : Lean.TSyntax ((((((`_private.Mathlib.Tactic.TFAE.num 0).str "Mathlib").str "Tactic").str "TFAE").str "Parser").str "tfaeType") → Lean.Elab.TermElabM Lean.Expr

Accesses the propositions at indices i and j of tfaeList, and constructs the expression Pi <arr> Pj, which will be the type of our tfae_have hypothesis

Equations

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

"Old-style" tfae_have

We preserve the "old-style" tfae_have (which behaves like Mathlib have) for compatibility purposes.

def Mathlib.Tactic.TFAE.tfaeHave' : Lean.ParserDescr

tfae_have introduces hypotheses for proving goals of the form TFAE [P₁, P₂, ...]. Specifically, tfae_have i <arrow> j := ... introduces a hypothesis of type Pᵢ <arrow> Pⱼ to the local context, where <arrow> can be →, ←, or ↔. Note that i and j are natural number indices (beginning at 1) used to specify the propositions P₁, P₂, ... that appear in the goal.

example (h : P → R) : TFAE [P, Q, R] := by
  tfae_have 1 → 3 := h
  ...

The resulting context now includes tfae_1_to_3 : P → R.

Once sufficient hypotheses have been introduced by tfae_have, tfae_finish can be used to close the goal. For example,

example : TFAE [P, Q, R] := by
  tfae_have 1 → 2 := sorry /- proof of P → Q -/
  tfae_have 2 → 1 := sorry /- proof of Q → P -/
  tfae_have 2 ↔ 3 := sorry /- proof of Q ↔ R -/
  tfae_finish

All relevant features of have are supported by tfae_have, including naming, destructuring, goal creation, and matching. These are demonstrated below.

example : TFAE [P, Q] := by
  -- `tfae_1_to_2 : P → Q`:
  tfae_have 1 → 2 := sorry
  -- `hpq : P → Q`:
  tfae_have hpq : 1 → 2 := sorry
  -- inaccessible `h✝ : P → Q`:
  tfae_have _ : 1 → 2 := sorry
  -- `tfae_1_to_2 : P → Q`, and `?a` is a new goal:
  tfae_have 1 → 2 := f ?a
  -- create a goal of type `P → Q`:
  tfae_have 1 → 2
  · exact (sorry : P → Q)
  -- match on `p : P` and prove `Q`:
  tfae_have 1 → 2
  | p => f p
  -- introduces `pq : P → Q`, `qp : Q → P`:
  tfae_have ⟨pq, qp⟩ : 1 ↔ 2 := sorry
  ...

Equations

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