AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap

defimported Lean

Given maps $f_X : X' \to X$ and $f_Y : Y' \to Y$, the pullback $p.\mathrm{comap}\,f_X\,f_Y$ is the finite-message protocol over $X'$, $Y'$ obtained by precomposing every message function with $f_X$ or $f_Y$ respectively, leaving the protocol tree structure unchanged.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) :
    Protocol X' Y' α
Defined in
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Built on 1
Used by 8

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- Pull back a finite-message protocol along functions `fX : X' → X` and `fY : Y' → Y`, composing each message function with the maps. -/
def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) :
    Protocol X' Y' α :=
  match p with
  | .output a => .output a
  | Protocol.alice f P =>
      Protocol.alice (f ∘ fX) (fun b => (P b).comap fX fY)
  | Protocol.bob f P =>
      Protocol.bob (f ∘ fY) (fun b => (P b).comap fX fY)
See it in the graphDiscuss this resultChallenge it