Can this fixed point theorem generalize to infinite structures?

Question

Suppose that $n$ is a natural number, $X$ is a set, and $S\subseteq X^{2}$ is a subset such that if $x,y\in X$, then there is a unique tuple $(x_{0},\dots,x_{n})$ where $x_{0}=x,x_{n}=y$ and $(x_{i},x_{i+1})\in S$ for $0\leq i<n$ (this condition is equivalent to saying that if $\chi_{S}$ is the characteristic function of $S$, then each entry in the matrix $\chi_{S}^{n}$ is $1$). Then does there necessarily exist some $x\in X$ where $(x,x)\in S$? Is $|\{x\in X\mid(x,x)\in S\}|^{n}=|X|$?

We observe that by the Lowenheim-Skolem theorem, if there is an infinite set $S\subseteq X^{2}$ where every entry in $\chi_{S}^{n}$ is $1$ but where there is no $x\in X$ with $(x,x)\in X$, then there is an example of every infinite cardinality.

Proposition: If $X$ is finite, then $|\{x\in X\mid(x,x)\in S\}|^{n}=|X|$.

Proof: Suppose that $X=\{1,\dots,r\}$. Suppose that the matrix $\chi_{S}$ has characteristic polynomial $(x-\lambda_{1})\dots(x-\lambda_{r})$. Then each entry in $\chi_{S}^{n}$ is $1$, so $\chi_{S}^{n}$ has characteristic polynomial $$(x-\lambda_{1}^{n})\dots(x-\lambda_{r}^{n})=x^{n-1}(x-r).$$ Therefore, we conclude that there is some $i$ such that $|\lambda_{i}|=\sqrt[n]{r}$ but where $\lambda_{j}=0$ whenever $j\neq i$. However, $$\{x\in X\mid(x,x)\in S\}=\text{Tr}(\chi_{A})=\lambda_{1}+\dots+\lambda_{r}=\lambda_{i},$$ so $$\{x\in X\mid(x,x)\in S\}=\sqrt[n]{r}.$$

Example: Suppose that $X=K^{n}$. Let $S$ be the collection of all pairs $$((x_{1},\dots,x_{n}),(a,g_{x_{2},\dots,x_{n-1}}(x_{1}),\dots,g_{x_{n-1}}(x_{n-2}),g(x_{n-1})))$$. Then every entry in the (possibly infinite) matrix $\chi_{S}^{n}$ is $1$. However, I claim that $\{x\in X\mid(x,x)\in S\}=|K|$. More specifically, I claim that the mapping $L:\{x\in X\mid(x,x)\in S\}\rightarrow K$ defined by $L(x_{1},\dots,x_{n})=x_{n}$ is a bijection by constructing its inverse $M$. If $x\in X$, then we define a sequence $M(x)=(x_{1},\dots,x_{n})$ by reverse recursion; we set $x_{n}=x$ and ​$x_{i}=g_{x_{i+1},\dots,x_{n-1}}^{-1}(x_{i+1})$ for $i\in\{1,\dots,n-1\}$. It is not too hard to see that $M:K\rightarrow\{x\in X\mid(x,x)\in S\}$ and that $L$ and $M$ are inverses of each other. Therefore $|\{x\in X\mid(x,x)\in S\}|=|K|$ in this case.

Answer 1

Here's one way to build an infinite counterexample with $n=2$ for simplicity:

We start with (say) $X_0=\{0\}, S_0=\emptyset$. Having defined $X_m, S_m$, we define $X_{m+1}, S_{m+1}$ as follows:

• To get $X_{m+1}$, we add to $X_m$ a fresh element $c_{(x,y)}$ for each pair $(x,y)\in X_m^2$ such that there is no $z\in X_m$ with $(x,z),(z,y)\in S_m$.

• To get $S_{m+1}$, we add to $S_m$ all pairs of the form $(x,c_{(x,y)})$ and $(c_{(x,y)},y)$ for $(x,y)\in X_m^2$ such that no $z\in X_m$ has $(x,z),(z,y)\in S_m$.

Now let $X=\bigcup_{m\in\mathbb{N}}X_m$, $S=\bigcup_{m\in\mathbb{N}}S_m$.

This same idea works for any $n\ge 2$ and for any (infinite) cardinality.