The lines of the Lean statement that state the theorem, then the definitions in the file that it uses.
Local definitions the statement names, followed through the definitions they name in turn. The match is by name in the source text, so a name reached only through notation can be missed; the full file is below.
structure OAI.StrongThinTree.MultiGraph line 9
structure MultiGraph (n m : ℕ) where left : Fin m → Fin n right : Fin m → Fin n loopless : ∀ e, left e ≠ right e
definition OAI.StrongThinTree.MultiGraph.cut line 16
def cut {n m : ℕ} (G : MultiGraph n m) (T : Finset (Fin m)) (S : Finset (Fin n)) : Finset (Fin m) := T.filter fun e => (G.left e ∈ S ∧ G.right e ∉ S) ∨ (G.right e ∈ S ∧ G.left e ∉ S)
definition OAI.StrongThinTree.MultiGraph.Connected line 21
def Connected {n m : ℕ} (G : MultiGraph n m) (T : Finset (Fin m)) : Prop := ∀ S : Finset (Fin n), S.Nonempty → S ≠ Finset.univ → (G.cut T S).Nonempty
definition OAI.StrongThinTree.MultiGraph.SpanningTree line 24
def SpanningTree {n m : ℕ} (G : MultiGraph n m) (T : Finset (Fin m)) : Prop := G.Connected T ∧ ∀ e ∈ T, ¬ G.Connected (T.erase e)
definition OAI.StrongThinTree.MultiGraph.EdgeConnected line 27
def EdgeConnected {n m : ℕ} (G : MultiGraph n m) (k : ℕ) : Prop := ∀ S : Finset (Fin n), S.Nonempty → S ≠ Finset.univ → k ≤ (G.cut Finset.univ S).card
definition OAI.CurrentKS.frame line 36
def frame : List Bool → List Bool | [] => [true] | b :: bs => false :: b :: frame bs
definition OAI.CurrentKS.encodeNat line 40
def encodeNat (n : ℕ) : List Bool := frame (Computability.encodeNat n)
inductive type OAI.CurrentKS.StackAction line 42
inductive StackAction where | stay | pop | push (bit : Bool) deriving DecidableEq
definition OAI.CurrentKS.StackAction.apply line 48
def StackAction.apply : StackAction → List Bool → List Bool | .stay, xs => xs | .pop, xs => xs.tail | .push b, xs => b :: xs
structure OAI.CurrentKS.Instruction line 53
structure Instruction (k q : ℕ) where next : Option (Fin q) actions : Fin k → StackAction
definition OAI.CurrentKS.Instruction.halt line 57
def Instruction.halt (k q : ℕ) : Instruction k q := ⟨none, fun _ => .stay⟩
structure OAI.CurrentKS.Machine line 59
structure Machine where stackCount : ℕ states : ℕ initial : Fin states inputStack : Fin stackCount outputStack : Fin stackCount table : List (Instruction stackCount states)
structure OAI.CurrentKS.Config line 67
structure Config (k q : ℕ) where state : Option (Fin q) «stacks» : Fin k → List Bool
definition OAI.CurrentKS.topCode line 71
def topCode : List Bool → ℕ | [] => 0 | false :: _ => 1 | true :: _ => 2
definition OAI.CurrentKS.headsCode line 76
def headsCode : (k : ℕ) → (Fin k → List Bool) → ℕ | 0, _ => 0 | k + 1, s => topCode (s 0) + 3 * headsCode k (fun j => s j.succ)
definition OAI.CurrentKS.Machine.step line 80
def Machine.step (M : Machine) (c : Config M.stackCount M.states) : Config M.stackCount M.states := match c.state with | none => c | some q => let instruction := M.table.getD (3 ^ M.stackCount * q.val + headsCode M.stackCount c.stacks) (Instruction.halt M.stackCount M.states) ⟨instruction.next, fun j => (instruction.actions j).apply (c.stacks j)⟩
definition OAI.CurrentKS.Machine.init line 90
def Machine.init (M : Machine) (input : List Bool) : Config M.stackCount M.states := ⟨some M.initial, fun j => if j = M.inputStack then input else []⟩
definition OAI.CurrentKS.Machine.run line 93
def Machine.run (M : Machine) (input : List Bool) (fuel : ℕ) : Config M.stackCount M.states := (M.step^[fuel]) (M.init input)
structure OAI.AlgorithmicThinTrees.ExplicitInput line 101
structure ExplicitInput where n : ℕ m : ℕ k : ℕ graph : MultiGraph n m
structure OAI.AlgorithmicThinTrees.BinaryInput line 107
structure BinaryInput where n : ℕ p : ℕ k : ℕ left : Fin p → Fin n right : Fin p → Fin n ordered : ∀ i, left i < right i distinct : Function.Injective (fun i => (left i, right i)) multiplicity : Fin p → ℕ
abbreviation OAI.AlgorithmicThinTrees.BinaryInput.Edge line 117
abbrev BinaryInput.Edge (x : BinaryInput) := Σ i : Fin x.p, Fin (x.multiplicity i)
definition OAI.AlgorithmicThinTrees.BinaryInput.edgeEquiv line 119
noncomputable def BinaryInput.edgeEquiv (x : BinaryInput) : x.Edge ≃ Fin (Fintype.card x.Edge) := Fintype.equivFin x.Edge
definition OAI.AlgorithmicThinTrees.BinaryInput.graph line 122
noncomputable def BinaryInput.graph (x : BinaryInput) : MultiGraph x.n (Fintype.card x.Edge) where left e := x.left (x.edgeEquiv.symm e).1 right e := x.right (x.edgeEquiv.symm e).1 loopless e := ne_of_lt (x.ordered (x.edgeEquiv.symm e).1)
inductive type OAI.AlgorithmicThinTrees.Input line 128
inductive Input where | explicit (x : ExplicitInput) | binary (x : BinaryInput)
9 more definitions are reached the same way; the full file lists them.