The Lattice of Congruences of a Finite Line Frame
| Autor: | Daniel Penazzi, Pedro Sánchez Terraf, Miguel Campercholi, Carlos Areces |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Logic Matemáticas Mathematics::Number Theory 0102 computer and information sciences 01 natural sciences Upper and lower bounds Theoretical Computer Science MODAL ALGEBRA Matemática Pura purl.org/becyt/ford/1 [https] Combinatorics Arts and Humanities (miscellaneous) Lattice (order) FOS: Mathematics Equivalence relation BISIMULATION EQUIVALENCE LATTICE OF SUBALGEBRAS 0101 mathematics Bisimulation Physics ALGEBRAIC FUNCTION 010102 general mathematics purl.org/becyt/ford/1.1 [https] Mathematics - Logic purl.org/becyt/ford/1.2 [https] Congruence relation F.4.1 F.1.2 Ciencias de la Computación Logic in Computer Science (cs.LO) Join and meet Kripke frame 010201 computation theory & mathematics Hardware and Architecture PERMUTING RELATIONS Ciencias de la Computación e Información 03B45 (Primary) 06B10 06E25 03B70 (Secondary) Logic (math.LO) Software CIENCIAS NATURALES Y EXACTAS |
| Zdroj: | CONICET Digital (CONICET) Consejo Nacional de Investigaciones Científicas y Técnicas instacron:CONICET |
| DOI: | 10.48550/arxiv.1504.01789 |
| Popis: | Let $\mathbf{F}=\left\langle F,R\right\rangle $ be a finite Kripke frame. A congruence of $\mathbf{F}$ is a bisimulation of $\mathbf{F}$ that is also an equivalence relation on F. The set of all congruences of $\mathbf{F}$ is a lattice under the inclusion ordering. In this article we investigate this lattice in the case that $\mathbf{F}$ is a finite line frame. We give concrete descriptions of the join and meet of two congruences with a nontrivial upper bound. Through these descriptions we show that for every nontrivial congruence $\rho$, the interval $[\mathrm{Id_{F},\rho]}$ embeds into the lattice of divisors of a suitable positive integer. We also prove that any two congruences with a nontrivial upper bound permute. Comment: 31 pages, 11 figures. Expanded intro, conclusions rewritten. New, less geometrical, proofs of Lemma 19 and (former) Lemma 34 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|