循环图的超积为何不可数无穷且不连通？

数据老陈

2026-5-19

Hey! Great question—this is one of my favorite ultraproduct examples for showing a natural property isn't first-order axiomatizable. Since you already grasp ultraproduct constructions and Łoś's theorem, let's jump right into the details:

Step 1: Pick Our Base Graphs

Let’s define a sequence of cycle graphs where each ( G_k ) is a single cycle of length ( k ) (so ( G_3 ) is a triangle, ( G_4 ) is a square, ( G_5 ) is a pentagon, etc.). Every ( G_k ) is obviously connected—it’s a single closed loop, so you can get from any vertex to any other via the cycle.

Step 2: Build the Ultraproduct

Let ( \mathcal{U} ) be a non-principal ultrafilter on the natural numbers (this is key—principal ultrafilters would just collapse the ultraproduct to one of the original ( G_k ), which won’t help us). We then construct the ultraproduct ( \mathbb{G} = \prod_{\mathcal{U}} G_k ).

Step 3: Use Łoś's Theorem to Analyze ( \mathbb{G} )

We can apply Łoś's theorem to prove two critical properties of ( \mathbb{G} ):

Every vertex in ( \mathbb{G} ) has degree 2: The statement "all vertices have degree exactly 2" is a first-order sentence (( \forall v , (\text{deg}(v) = 2) )). Since this holds for every ( G_k ), Łoś's theorem guarantees it holds for ( \mathbb{G} ).
( \mathbb{G} ) has no finite cycles: For any fixed positive integer ( m ), consider the first-order sentence ( \phi_m ): "There is no cycle of length ( m )". For every ( k > m ), ( G_k ) satisfies ( \phi_m )—a cycle of length ( k ) can’t contain a smaller cycle of length ( m ). A non-principal ultrafilter includes all co-finite subsets of ( \mathbb{N} ), so "almost all" ( G_k ) satisfy ( \phi_m ). By Łoś's theorem, ( \mathbb{G} ) satisfies ( \phi_m ) too. Since this is true for every ( m ), ( \mathbb{G} ) has no finite cycles whatsoever.

Step 4: The Contradiction That Proves Our Point

Here’s where we connect the dots to show connectedness isn’t first-order axiomatizable:

Suppose, for contradiction, that the class of connected graphs is first-order axiomatizable. That means there exists a set of first-order sentences ( T ) such that a graph is connected if and only if it models ( T ). Every ( G_k ) is connected, so every ( G_k \models T ). A core property of ultraproducts is that if all base models satisfy ( T ), the ultraproduct does too—so ( \mathbb{G} \models T ), which would mean ( \mathbb{G} ) is connected.
But what actually is ( \mathbb{G} )? It’s a graph where every vertex has degree 2 and no finite cycles. The only such graphs are disjoint unions of bidirectional infinite paths (infinitely long straight lines with no loops). A disjoint union of multiple infinite paths is not connected—there’s no finite path between a vertex in one path and a vertex in another.

This contradiction tells us our initial assumption was wrong: connectedness cannot be defined by any set of first-order sentences.

内容的提问来源于stack exchange，提问作者Mike