Ultraproduct of cycle graphs - why uncountably infinite and not connected?

Question

I'm learning about ultraproducts and have stumbled upon a typical example: show that the class of connected graphs isn't FO-axiomatizable. I understand what the construction of an ultraproduct looks like and how Łoś's theorem comes into play. So we take the ultraproduct of graphs consisting of single cycles (of growing lengths) and we can say the following about it:

• its every vertex has degree 2,
• it doesn't have cycles (as an FO-expressible property "there is no cycle of length k" holds for almost all graphs in the aforementioned family for all k).

So it's easy to see that the ultraproduct must consist of infinite single path or paths. But how can we show that it indeed is "paths", not "path"? So my questions are:

• how can we show that the number of vertices in the ultraproduct is uncountably infinite?
• how can we show that the ultraproduct isn't a single infinite path, but more of them?

Sidenote: I'm asking about uncountable infinity because I know for a fact that it's the case and my feeble attempt to prove what I want is as follows: a path may only consist of countably many vertices, so if we have uncountably many vertices, we must have more than one path (in fact uncountably many). But am I right? The longer I think about it, the less convinced I am.

Thanks in advance!

Answer 1

You can complete your argument by referring to Shelah's result in

On the Cardinality of Ultraproduct of Finite Sets, Journal of Symbolic Logic, Volume 35, Number 1, March 1970, DOI: 10.2307/2271159

He proves that if an ultraproduct of finite sets has cardinality $\lambda$, and $\lambda$ is infinite, then $\lambda^{\aleph_0}=\lambda$. In particular, $\lambda$ cannot be $\aleph_0$.

However, for your purposes, it is enough to know that some ultraproduct of finite sets is uncountable. For this there is an easier argument.

Let $\{0,1\}^n$ be the finite set of all strings of length $n$ of $0$'s and $1$'s for $n$ a positive integer. Let $\mathcal U$ be a nonprincipal ultrafilter on the set of positive integers. I claim that the ultraproduct $(\prod_{n > 0} \{0,1\}^n)/{\mathcal U}$ of these finite sets contains continuumly many distinct elements. To see this, choose any infinite $0,1$-sequence, say $\sigma=00101\cdots$, and consider the sequence of initial segments modulo $\mathcal U$: $$\text{InitSeg}(\sigma)/{\mathcal U}=(0,00,001,0010,00101,\ldots)/{\mathcal U}.$$ Different $\sigma$'s yield different elements of the ultraproduct, and there are $2^{\omega}$-many $\sigma$'s, so $|(\prod_{n>0} \{0,1\}^n)/{\mathcal U}|\geq 2^{\omega}$. (Easy to see that equality holds.)

Answer 2

For the uncountable cardinality, you can check the following answer of a question about cardinalities of ultraproducts.

Cardinality of ultraproduct

To check out connectedness, we can consider the ultraproducts of the cycles with vertices $H_n=\{1,\ldots\,2n\}$ (with $2n$ adjacent to $1$) with respect to a non-principal ultrafilter $\mathcal{U}$. Let us call such ultraproduct $H$. Then, we can consider the elements $\alpha=[(1,1,\ldots)]_\mathcal{U}$ and $\beta=[(1,2,3,\ldots,n,\ldots)]_\mathcal{U}$. Note that there is a formula $\varphi_k(x,y)$ stating that "the distance between $x$ and $y$ is at greater than $k$", namely,

$$\varphi_k(x,y):=\bigwedge_{r=0}^k\neg \exists x_1,\ldots,x_r\left(xRx_1\wedge yRx_r\bigwedge_{i=1}^{r-1}x_iRx_{i+1}\right).$$

Notice that, by Los' theorem, for every $k\in\mathbb{N}$ we have $H\models \varphi_k(\alpha,\beta)$. In other words, there is no finite path between $\alpha,\beta$, so $H$ is not connected.