Sets of equations

Question

Let $I,J,K$ be three non-void sets, and let $\gamma$:$I\times J\times K\rightarrow\mathbb{N}$. Is there some nonempty set $X$, together with some functions {$\{ f_{i}:X\rightarrow X;i\in I\} $}, some subsets {$\{ \Omega_{j}\subset X;j\in J\} $}, and some points {$\{p_{k}\in X;k\in K} $} s.t. $\mid f_{i}^{-1}\left(p_{k}\right)\cap\Omega_{j}\mid=\gamma\left(i,j,k\right)$ $\left(i\in I,j\in J,k\in K\right)$, and $\mid f_{i}^{-1}\left(p\right)\mid\leq\mid\mathbb{R\mid}$$\left(i\in I,p\in X\right)$ ? In other words, is $\gamma$ ''representable'' as the number of solutions of some ''reasonable'' equations? [An elementary problem, indeed.]

Answer 1

Here is a second attempt (see edit history for previous version).

For each $t\in\mathbb{N}$, let $$P_{i,j,k,t}=\{1_{i,j,k,t},\ldots,n_{i,j,k,t},\ldots,\gamma(i,j,k)_{i,j,k,t}\}$$ (so that for each choice of $i\in I$, $j\in J$, $k\in K$, and $t\in\mathbb{N}$, we have a disjoint set of size $\gamma(i,j,k)$).

For each $t\in\mathbb{N}$, let $$Q_t=\{a_{k,t}\mid k\in K\}$$ (so for each $t\in\mathbb{N}$, this is just a copy of $K$, up to relabeling).

Let $$X=\coprod_{t\in\mathbb{N}}\left(Q_t\coprod_{\substack{i\in I,j\in J\\\k\in K}}P_{i,j,k,t}\right).$$ Define $$\Omega_j=\coprod_{i\in I,k\in K}P_{i,j,k,1}\subset X,$$ and $f_i:X\rightarrow X$ by $$f_{i_0}(n_{i,j,k,t})=\begin{cases}a_{k,1}\text{ if }i=i_0,t=1\\\ n_{i,j,k,t+1}\text{ otherwise}\end{cases}$$ $$f_i(a_{k,t})=a_{k,t+1}$$

Thus $$f_{i}^{-1}(n_{i,j,k,t})=\begin{cases}\emptyset\text{ if }t=1,2\\\ \{n_{i,j,k,t-1}\}\text{ if }t>2\end{cases}$$ $$f_i^{-1}(a_{k,t})=\begin{cases}\coprod_{j\in J}P_{i,j,k,1}\text{ if }t=1\\\ \{a_{k,t-1}\}\text{ if }t>1\end{cases}$$ We choose $p_k=a_{k,1}$.

Thus $f_i^{-1}(p_k)\cap \Omega_j=P_{i,j,k,1}$, so $|f_i^{-1}(p_k)\cap\Omega_j|=\gamma(i,j,k)$.

Unfortunately this still doesn't address your size concerns, i.e. the preimage of any element of $X$ being countable, because if $J$ is uncountable then $f_i^{-1}(a_{k,1})$ is uncountable (I added the whole mess with the $t$'s to make the preimages of all the other elements countable). I'll leave this as a community wiki, and if anyone sees a way of fixing it they are welcome to edit this.

Answer 2

This is basically a detailed description of a solution, based on Gerhard's answer.

Let $X=\mathbb{N}_0 \times I_0 \times K $, where $\mathbb{N}_0$ includes $0$ and similarly $I_0=I\cup 0$ with $0\not \in I$.

Let $p_k =(0,0,k)$, and let $\displaystyle \Omega_j=\bigcup_i \bigcup_k \bigcup_{n=1}^{\gamma_{ijk}} (n,i,k)$.

Define $f_i(n,i,k)=(0,0,k)=p_k$ and $f_i(n,i',k)=(n+1,i',k)$ for $i'\neq i$. We add $1$ to $n$ so that $f_i(p_k)\neq p_k$.

Note that for $x\neq p_k$, $|f_i^{-1}(x)|\leq 1$. On the other hand, $f_i^{-1}(p_k)=\mathbb{N} \times \{i\}\times \{k\} $, and then $f_i^{-1}(p_k)\cap \Omega_j =\{(n,i,k)\mid 1\leq n\leq \gamma_{ijk} \}$, which has the desired cardinality $\gamma_{ijk} $.

Remark: In a comment to Gerhard's answer, Ady says "I think you're underestimating the size of J." The size of $J$ actually plays no role in this problem as stated, as the sets $\Omega_j$ may overlap (and will overlap a lot in my construction). If you want to require the $\Omega_j$ to be disjoint, note that the other conditions force $|J|\leq |\mathbb{R}|$, as $\left|\bigcup_j \left( f_i^{-1}(p_k)\cap \Omega_j \right)\right| \leq |f_i^{-1}(p_k)|\leq |\mathbb R|$. We can modify the construction above by replacing $\mathbb N$ with $\mathbb R$, and can assure that the $\Omega_j$ are disjoint if we are more careful in choosing which $\gamma_{ijk}$ elements of $\mathbb{R}\times\{i\}\times\{k\}$ to include in $\Omega_j$ (above I chose the points $(n,i,k)$ for $n$ from $1$ to $\gamma_{ijk}$).

Answer 3

Consider the following construction. Let $Y$ be a subset of $X$ such that $Y$ is (equipollent to) $I \times K \times \omega$. I think of it as $I$-many copies of an array with $K$-many rows and each row has countably many elements. The $k$th row in the $i$th array is the preimage of $p_k$ under $f_i$. (For $h$ not equal to $i$, let $f_i$ send the $k$th row in the $h$th array to, say, the first element in that row, or perhaps instead to some subset of elements in that row, under the condition that those images are disjoint from the set of $p_k$.) For the sets $\Omega_j$, pick precisely $\gamma(i,j,k)$ elements from the $k$th row in the $i$th array and put them into $\Omega_j$. So far, we have achieved that the preimage of every point in the range of $f_i$ is at most countably infinite, for every $i$. We also have the desired condition on the intersection of the preimage of $p_k$ under $f_i$ with the set $\Omega_j$.

Now everything is done except for deciding where to put the $p_k$. As long as you avoid sending $f_i(x)$ to a $p_k$ for $x$ outside the ith array, you can label some of the array elements with $p_k$; this should be doable because you have control of how $f_i$ acts outside the $i$th array.

Alternatively, let the $p_k$ be disjoint from $Y$ and the $\Omega_j$, and let $f_i$ send the $p_k$ to themselves, or to some other set disjoint from the $\Omega_j$.

Gerhard "Ask Me About System Design" Paseman, 2011.04.17