Mathematicians prove finite structure behind infinite logical systems
Researchers have solved a decades-old puzzle in mathematical logic, proving that complex infinite structures contain only finitely many distinct definitional layers. The discovery has implications for how computer scientists design databases and formal verification systems that must handle large-scale logical relationships efficiently.
Originaltitel: THE REDUCTS OF THE HOMOGENEOUS BINARY BRANCHING C-RELATION
<p>Let (L; C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of (L; C), i.e., the structures with domain L that are first-order definable in (L; C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of (L; C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.</p>