De Bruijn-Erdős via compactness, does it break for uncountable graphs?
​
Proving: if every finite subgraph of G is k-colorable, then G is k-colorable.
For each vertex v, variables Pv,1,...,Pv,k ("v gets color i"). Axioms in Σ:
- Pv,1 ∨ ... ∨ Pv,k for each v
- ¬(Pv,i ∧ Pv,j) for i≠j
- ¬(Pu,i ∧ Pv,i) for each edge (u,v), each i
Σ satisfiable iff G is k-colorable. Every finite subset of Σ only mentions finitely many vertices/edges, and that induced finite subgraph is k-colorable by hypothesis, so every finite subset is satisfiable. By compactness, Σ is satisfiable, so G is k-colorable.
But isnt ropositional compactness is usually stated for countable languages? G could have uncountably many vertices, so Σ has uncountably many variables. Does compactness still hold as-is, or do I need the general version (via Zorn/ultrafilters) for uncountable Σ? If it still works, what's the justification? Thank you!