AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.comap

defimported Lean

Given functions $f_X : X' \to X$ and $f_Y : Y' \to Y$, comap pulls back a protocol $p$ over $X \times Y$ to a protocol over $X' \times Y'$ by pre-composing every message function with $f_X$ or $f_Y$ as appropriate, leaving output nodes unchanged.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Deterministic.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) : Protocol X' Y' α
Defined in
TCSlib, `CommunicationComplexity.Deterministic.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 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- Pull back a protocol along functions `fX : X' → X` and `fY : Y' → Y`. The resulting protocol over `X' × Y'` simulates the original by applying `fX` and `fY` to the inputs before each message function. -/
def CommunicationComplexity.Deterministic.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) : Protocol X' Y' α :=
  match p with
  | .output val => .output val
  | .alice f P => .alice (f ∘ fX) (fun b => (P b).comap fX fY)
  | .bob f P => .bob (f ∘ fY) (fun b => (P b).comap fX fY)
See it in the graphDiscuss this resultChallenge it