An almost uniform subset of the Cartesian square

Question

Let $A$ be any set and $S$ be a subset of $A^2$ such that sets $\{a\in A\mid (x,a)\in S\}\mathbin\triangle\{a\in A\mid (y,a)\in S\}$ and $\{a\in A\mid (a,x)\in S\}\mathbin\triangle\{a\in A\mid (a,y)\in S\}$ are finite for any $x,y\in A$. What can be the set $S$?

There are two simple examples of the set $S$, when sets $\{a\in A\mid (x,a)\in S\}$ and $\{a\in A\mid (a,y)\in S\}$ are finite (cofinite) for any $x,y\in A$. If $A=\mathbb{Z}$, then $S$ can be $\{(a,b)\in\mathbb{Z}^2\mid a < b\}$. Are there any other examples?

Answer 1

At first, let us introduce some relevant definitions.

Definition. A $S\subseteq X\times Y$ is called

$\bullet$ horizontally finite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\in S\}$ is finite;

$\bullet$ horizontally cofinite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\notin S\}$ is finite;

$\bullet$ vertically finite in $X\times Y$ if for every $x\in X$ the set $\{y\in Y:(x,y)\in S\}$ is finite;

$\bullet$ vertically cofinite in $X\times Y$ if for every $x\in X$ the set $\{y\in X:(x,y)\notin S\}$ is finite.

Proposition 1. Is a set $S\subseteq X\times Y$ is horizontally cofinite and vertically finite, then either $X$ is finite or $Y$ is finite or else $X$ and $Y$ are countable.

Proof. Assume that the sets $X$ and $Y$ are infinite. Choose any countably infinite set $C\subseteq Y$. Since $S$ is horizontally cofinite, for every $y\in C$ the set $S^{-1}(y)=\{x\in X:(x,y)\in S\}$ is cofinite in $X$. Assuming that $X$ is uncountable, we can find an element $x\in \bigcap_{y\in C}S^{-1}(y)$. For this element the set $S(x)=\{y\in Y:(x,y)\in S\}$ contains $C$ and hence is infinite, which contradicts the vertical finiteness of $S$. This contradiction shows that the set $X$ is countable. Then the set $\bigcup_{x\in X}S(x)$ is countable too. Assuming that $Y$ is uncountable, we can find a point $y\in Y\setminus\bigcup_{x\in X}S(x)$, for which the set $S^{-1}(y)=\emptyset$ is not cofinite in $X$. This contradiction shows that the set $Y$ is countable. $\square$

Now take any set $S\subseteq A\times A$ such that all horizontal sections of $S$ are almost equal and all vertical sections of $S$ are almost equal. The almost equality $X=^* Y$ of two sets $X,Y$ means that $X\Delta Y$ is finite. This implies that there exist some sets $X,Y\subseteq A$ such that $\{a\in A:(x,a)\in S\}=^*Y$ and $\{a\in A:(a,y)\in S\}=^*X$ for every $x,y\in A$. Moreover, we can assume that

$\bullet$ $X=\emptyset$ if $X$ is finite;

$\bullet$ $X=A$ if $X\setminus A$ is finite;

$\bullet$ $Y=\emptyset$ if $Y$ is finite;

$\bullet$ $Y=A$ if $X\setminus A$ is finite.

Now to understand a possible structure of $S$ we should analyze the structure of the intersections $S_{11}=S\cap (X\times Y)$, $S_{01}=S\cap ((A\setminus X)\times Y)$, $S_{10}=S\cap (X\times (A\setminus Y))$ and $S_{00}=S\cap ((A\setminus X)\times(A\setminus Y))$.

The set $S$ satisfies the condition from the problem if and only if it satisfies the following four conditions:

$00)$ The set $S_{00}$ is horizontally finite and vertically finite in $(A\setminus X)\times (A\setminus Y)$;

$01)$ The set $S_{01}$ is horizontally finite and vertically cofinite in $(A\setminus X)\times Y$;

$10)$ The set $S_{10}$ is horizontally cofinite and vertically finite in $X\times (A\setminus Y)$;

$11)$ The set $S_{11}$ is horizontally cofinite and vertically cofinite in $X\times Y$.

Proposition 2. If the set $A$ is uncountable, then $X=Y\in\{\emptyset,A\}$.

Proof. First we show that $X\in\{\emptyset,A\}$. Assuming that $X\notin\{\emptyset,A\}$, we conclude that the sets $X$ and $A\setminus X$ are infinite, by the choice of the set $X$. Since $A$ is uncountable, either $X$ or $A\setminus X$ is uncountable. If $X$ is uncountable, then the condition (10) and Proposition 1 ensure that the set $A\setminus Y$ is finite and hence $Y$ is uncountable. Applying Proposition 1 to the condition (01), we conclude that the set $A\setminus X$ is finite, which contradicts our assumption. If $A\setminus X$ is uncountable, then we can apply Proposition to the condition (01) and conclude that $Y$ is finite and hence $A\setminus Y$ is uncountable. In this case we can apply Proposition 1 to the condition (10) and conclude that the set $X$ is finite, which contradicts our assumption. This contradiction shows that $X\in\{\emptyset,A\}$.

By analogy we can show that $Y\in\{\emptyset,A\}$.

Assuming that $X\ne Y$, we conclude that either $X=\emptyset$ and $Y=A$ or else $X=A$ and $Y=\emptyset$.

First we consider case $X=A$ and $Y=\emptyset$. In this case the set $S$ is horizontally cofinite and vertically finite in $A\times A$. By Proposition 1, $A$ is finite or countable, which is not the case. By analogy we can derive a constradiction assuming that $X=\emptyset$ and $Y=A$. This contradiction shows that $X=Y\in\{\emptyset,A\}$ and completes the proof. $\square$

It remains to analyze the structure of the set $S$ in case of countably infinite set $A$, which can be identified with $\omega$.

First observe that every set $S\subseteq X\times Y$ can be thought as a multivalued function assigning to each $x\in X$ the set $S(x)=\{y\in Y:(x,y)\in S\}$.

Under such description, sets $S\subseteq X\times Y$ which are horizontally finite and vertically finite correspond to finite-valued functions $S:X\multimap Y$ whose inverse $S^{-1}:Y\multimap X$ are also finite-valued.

In particular, $S\subseteq\omega\times\omega$ is horizontally and vertically finite if and only if there exist two non-decreasing unbounded functions $f,F:\omega\to\omega$ such that $S(x)\subseteq[f(x),F(x)]$ for all $x\in\omega$.

On the other hand, a set $S\subseteq\omega\times\omega$ is vertically finite and horizontally cofinite if and only if there exists two nondecreasing unbounded functions $f,F:\omega\to\omega$ such that $\{y\in\omega:y<f(x)\}\subseteq S(x)\subseteq\{y\in\omega:y<F(x)\}$ for all $x\in\omega$.