Lax Lean Archive

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

Invariance and characterization of the isomorphism problems

Lax604544.IsomorphismInvariance · concepts/Lax604544/IsomorphismInvariance.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

    Having isomorphic marked graphs, having isomorphic simple marked graphs and having isomorphic acyclic marked graphs with valid witnesses are invariant under isomorphism of instances, and an instance is a yes-instance of Digraph Isomorphism, Graph Isomorphism or DAG Isomorphism exactly when it has the corresponding property.

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

    This concept declares 6 statements. Each proof establishes one of them relative to its assumptions.

    1 dagIso_iff proven

    2 digraphIso_iff proven

    3 graphIso_iff proven

    4 hasDagIso_iso proven

    5 hasDigraphIso_iso proven

    6 hasGraphIso_iso proven

    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: Invariance and characterization of the isomorphism problems
    24type: lemma
    25---
    26Having isomorphic marked graphs, having isomorphic simple marked graphs and
    27having isomorphic acyclic marked graphs with valid witnesses are invariant
    28under isomorphism of instances, and an instance is a yes-instance of
    29Digraph Isomorphism, Graph Isomorphism or DAG Isomorphism exactly when it
    30has the corresponding property.
    31-/
    32
    33namespace Lax604544.IsomorphismInvariance
    34
    35open FirstOrder FirstOrder.Language
    36open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.Classes
    37open Lax904597.Sat Lax799700.SubgraphIso
    38open Lax485149.Problems Lax485149.TwoSat Lax485149.ClassNL Lax535992.HornSat Lax535992.ClassPTIME
    39open Lax564036.Hierarchy Lax564036.Tautology Lax624099.ClassRE Lax624099.FiniteSatisfiability
    40open Lax604544.Degrees Lax604544.RelationIsomorphism
    41open Lax604544.GraphIsomorphism Lax604544.DagIsomorphism
    42
    43/-- Having isomorphic marked graphs is isomorphism-invariant. -/
    44axiom hasDigraphIso_iso : ∀ {A B : Type} [twoGraphs.Structure A] [twoGraphs.Structure B],
    45 (A ≃[twoGraphs] B) → (HasDigraphIso A ↔ HasDigraphIso B)
    46
    47/-- The yes-instances are exactly the instances with the defining property. -/
    48axiom digraphIso_iff : ∀ (A : Type) [twoGraphs.Structure A], DigraphIso A ↔ HasDigraphIso A
    49
    50/-- Having isomorphic simple marked graphs is isomorphism-invariant. -/
    51axiom hasGraphIso_iso : ∀ {A B : Type} [twoGraphs.Structure A] [twoGraphs.Structure B],
    52 (A ≃[twoGraphs] B) → (HasGraphIso A ↔ HasGraphIso B)
    53
    54/-- The yes-instances are exactly the instances with the defining property. -/
    55axiom graphIso_iff : ∀ (A : Type) [twoGraphs.Structure A], GraphIso A ↔ HasGraphIso A
    56
    57/-- Having isomorphic marked acyclic graphs is isomorphism-invariant. -/
    58axiom hasDagIso_iso : ∀ {A B : Type} [twoDags.Structure A] [twoDags.Structure B],
    59 (A ≃[twoDags] B) → (HasDagIso A ↔ HasDagIso B)
    60
    61/-- The yes-instances are exactly the instances with the defining property. -/
    62axiom dagIso_iff : ∀ (A : Type) [twoDags.Structure A], DagIso A ↔ HasDagIso A
    63
    64end Lax604544.IsomorphismInvariance
    65
    Show ProofShow ProofShow ProofShow ProofShow ProofShow 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…