Constraint satisfaction problems, compactness and non-measurable sets
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915838332764160 |
|---|---|
| author | Tardif, Claude |
| author_facet | Tardif, Claude |
| contents | A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness of A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A implies the existence of non-measurable sets in 3-space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14838 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constraint satisfaction problems, compactness and non-measurable sets Tardif, Claude Logic Logic in Computer Science 03E65, 68Q19 G.0 A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness of A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A implies the existence of non-measurable sets in 3-space. |
| title | Constraint satisfaction problems, compactness and non-measurable sets |
| topic | Logic Logic in Computer Science 03E65, 68Q19 G.0 |
| url | https://arxiv.org/abs/2508.14838 |