Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

Isomorphism of marked relations as an equivalence

Lax604544.RelationIsomorphismSemantics · concepts/Lax604544/RelationIsomorphismSemantics.lean · lax-604544

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Lemma

    Two marked relations are isomorphic if and only if there is a bijection between the two marked sets, as types, carrying one relation to the other in both directions. This is the equivalence under which decision problems are required to be invariant, read on the two sides of one instance.

    Concept map
    28 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax904597.Problems
    2import Lax904597.Interpretations
    3import Lax904597.Relativized
    4import Lax904597.Classes
    5import Lax904597.Sat
    6import Lax799700.SubgraphIso
    7import Lax485149.Problems
    8import Lax485149.TwoSat
    9import Lax485149.ClassNL
    10import Lax535992.HornSat
    11import Lax535992.ClassPTIME
    12import Lax564036.Hierarchy
    13import Lax564036.Tautology
    14import Lax624099.ClassRE
    15import Lax624099.FiniteSatisfiability
    16import Lax604544.Degrees
    17import Lax604544.RelationIsomorphism
    18import Lax604544.GraphIsomorphism
    19import Lax604544.DagIsomorphism
    20
    21/-!
    22---
    23title: Isomorphism of marked relations as an equivalence
    24type: lemma
    25---
    26Two marked relations are isomorphic if and only if there is a bijection
    27between the two marked sets, as types, carrying one relation to the other
    28in both directions. This is the equivalence under which decision problems
    29are required to be invariant, read on the two sides of one instance.
    30-/
    31
    32namespace Lax604544.RelationIsomorphismSemantics
    33
    34open FirstOrder FirstOrder.Language
    35open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.Classes
    36open Lax904597.Sat Lax799700.SubgraphIso
    37open Lax485149.Problems Lax485149.TwoSat Lax485149.ClassNL Lax535992.HornSat Lax535992.ClassPTIME
    38open Lax564036.Hierarchy Lax564036.Tautology Lax624099.ClassRE Lax624099.FiniteSatisfiability
    39open Lax604544.Degrees Lax604544.RelationIsomorphism
    40open Lax604544.GraphIsomorphism Lax604544.DagIsomorphism
    41
    42/-- Isomorphism of marked relations is an equivalence of the marked sets. -/
    43axiom relIsoOn_iff_equiv : ∀ {A : Type} (PV HV : A → Prop) (PE HE : A → A → Prop),
    44 RelIsoOn PV HV PE HE ↔
    45 ∃ e : {x // PV x} ≃ {x // HV x}, ∀ (x y : {x // PV x}), PE ↑x ↑y ↔ HE ↑(e x) ↑(e y)
    46
    47end Lax604544.RelationIsomorphismSemantics
    48
    Show Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…