All countable monoids embed into the monoid of the infinite random graph (Q960939)

From MaRDI portal
scientific article
Language Label Description Also known as
English
All countable monoids embed into the monoid of the infinite random graph
scientific article

    Statements

    All countable monoids embed into the monoid of the infinite random graph (English)
    0 references
    0 references
    0 references
    0 references
    29 March 2010
    0 references
    From the authors summary: ``We prove that the full transformation monoid on a countably infinite set is isomorphic to a submonoid of \(\text{End}(R)\), the endomorphism monoid of the infinite random graph \(R\). Consequently, \(\text{End}(R)\) embeds each countable monoid, satisfies no nontrivial monoid identity, and has an undecidable universal theory.'' Note that the infinite random graph satisfies the existentially closed adjacency property, and it is a universal graph, i.e., each countable subgraph is isomorphic to an induced subgraph of \(R\).
    0 references
    0 references
    0 references
    infinite random graph
    0 references
    graph endomorphism
    0 references
    embedding
    0 references
    0 references