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.



Can this fixed point theorem generalize to infinite structures?
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.


