MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.]

share|cite|improve this question
Try first for I of size 1. Put the (generally countable) preimage of p_k as a row, so you have a Kx\omega array. Now pick \gamma(j,k) elements from the kth row and put them in \Omega_j. This gets you f_1 as defined on the first array. For larger I and the ith f, use a disjoint by K x \omega array and repeat. Define f_h(x) for x in the ith array (for h not equal i) to be the 1st element that is not any p_k and is in the same row as x. All preimages are countable, although K and \Omega_j may not be. Gerhard "Ask Me About System Design" Paseman, 2011.04.17 – Gerhard Paseman Apr 17 '11 at 8:16

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.

share|cite|improve this answer
@Zev Thank you. This is interesting, yet what about the second condition? I mean [as you've already remarked], you are not controlling the size of the preimages [not necessarily countable!]. – Ady Apr 17 '11 at 7:45
@Ady - Yes, my first attempt was just to write down what seemed to be the most natural sets and functions, without controlling the sizes. I've changed things a bit to reduce the problem somewhat, but it is still there. Perhaps we need to mod out by an appropriate equivalence relation to force things to get smaller? – Zev Chonoles Apr 17 '11 at 7:58
He is asking for each preimage under f_i to be countable, right? Or is he asking for the union (over I) of the preimages of each p to be countable? Gerhard "Ask Me About System Design" Paseman, 2011.04.17 – Gerhard Paseman Apr 17 '11 at 8:19
No. He is asking for each preimage under f_i to be not larger [in size] than the power of the continuum. – Ady Apr 17 '11 at 8:45
Good. I hope he (or perhaps other than he, forgive my presumption) likes the ideas in the comment I made to the question. I think that keeps the preimage size down. Gerhard "Ask Me About System Design" Paseman, 2011.04.17 – Gerhard Paseman Apr 17 '11 at 16:42

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}$).

share|cite|improve this answer
Thanks for the clarification. Not only does adding 1 to n keep f_i(p_k) from being p_k, it keeps it from being p_l for any l in K. I hope this clears things up for Ady. Gerhard "Ask Me About System Design" Paseman, 2011.04.18 – Gerhard Paseman Apr 18 '11 at 9:01
+1 I hereby give you my second upvote. (I would give you+ 7, but then others might think me strange in a bad, unfriendly way.) Gerhard "Ask Me About System Design" Paseman, 2011.04.19 – Gerhard Paseman Apr 20 '11 at 6:20

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

share|cite|improve this answer
@Gerhard Sounds promising, yet too vague. E.g., may I ask who is X? Thx anyway. P.S. I think you're underestimating the size of J. – Ady Apr 18 '11 at 5:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.