2014/09/18 by de la Vega, Ramiro
#03E50 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1409.5312
A structure A=(A;Ei)i∈ n where each Ei is an equivalence relation on A is called an n-grid if any two equivalence classes coming from distinct Ei's intersect in a finite set. A function χ: A → n is an acceptable coloring if for all i ∈ n, the set χ-1(i) intersects each Ei-equivalence class in a finite set. If B is a set, then the n-cube Bn may be seen as an n-grid, where the equivalence classes of Ei are the lines parallel to the i-th coordinate axis. We use elementary submodels of the universe to characterize those n-grids which admit an acceptable coloring. As an application we show that if an n-grid A does not admit an acceptable coloring, then every finite n-cube is embeddable in A.