Claude Tardif - Constraint satisfaction problems, compactness and non-measurable sets

lmcs:16378 - Logical Methods in Computer Science, July 14, 2026, Volume 22, Issue 3 - https://doi.org/10.46298/lmcs-22(3:1)2026
Constraint satisfaction problems, compactness and non-measurable setsArticle

Authors: Claude Tardif

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.


Volume: Volume 22, Issue 3
Published on: July 14, 2026
Accepted on: June 11, 2026
Submitted on: August 21, 2025
Keywords: Logic, Logic in Computer Science

Consultation statistics

This page has been seen 413 times.
This article's PDF has been downloaded 143 times.