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
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
infinite random graph
0 references
graph endomorphism
0 references
embedding
0 references