3
$\begingroup$

This is a generalisation of an older question inspired by a football tournament (which does not have an answer yet).

Let $\frak P$ be a partition of $\omega$ into blocks, that is, pairwise disjoint sets, such that every block has at least $2$ elements. (Blocks may be infinite.) Assume that $\frak P$ consists of infinite many blocks.

Is there for every $n\in\mathbb{N}$ a bijection $\varphi_n:\omega\to\omega$, such that the following condition is met?

Whenever $a\neq b\in\omega$ there is a unique $n\in\mathbb{N}$ such that $\{\varphi_n(a), \varphi_n(b)\}\subseteq B$ for some $B\in{\frak P}$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What if there is just one big block? Perhaps you want to assume there are infinitely many blocks? $\endgroup$
    – Joel David Hamkins
    Commented Oct 27, 2022 at 19:11
  • 1
    $\begingroup$ What I mean to say is that if there is only one block, then one will fail the uniqueness claim on $n$ in the desired property, since every $\varphi_n$ will work in this case. $\endgroup$
    – Joel David Hamkins
    Commented Oct 27, 2022 at 19:18
  • 2
    $\begingroup$ If there exists a cofinite block there is no such sequence of bijections $\endgroup$
    – Holo
    Commented Oct 27, 2022 at 21:47
  • $\begingroup$ @Holo More generally, if such a sequence of bijections exists, the number of blocks must be infinite. This is because, for any given $k\in\omega$, for sufficiently large $n$ the numbers $\varphi_n(1),\varphi_n(2),\dots,\varphi_n(k)$ will all be in different blocks. $\endgroup$
    – bof
    Commented Oct 28, 2022 at 2:53
  • 2
    $\begingroup$ I think "infinitely many blocks" is a necessary and sufficient condition. For sufficiency, it looks offhand like the straightforward inductive construction works. $\endgroup$
    – bof
    Commented Oct 28, 2022 at 3:03

1 Answer 1

Reset to default
4
$\begingroup$

If there are infinitely many blocks, then indeed you can find the permuations $\pi_n$ as desired. Indeed, there are computable such $\pi_n$. Furthermore, you don't need that every block has size at least two, but rather only that there is at least one block of size at least two.

We build the sequence of permuations $\pi_n$ in stages, so that at each stage, only finitely much of finitely many permutations is specified. We want gradually to fulfill the following requirements:

  • for each $n$ and $k$, the value of $\pi_n(k)$ is specified
  • for each $n$ and $k'$, there is some $k$ such that $\pi_n(k)=k'$
  • for each pair $a\neq b$, there is a unique $n$ such that $\pi_n(a)$ and $\pi_n(b)$ appear in the same block.

Now, the point is that we can gradually fulfill these requirements in a computable process that specifies more and more of the system of permuations. We can always fulfill the first requirement, for example, without any tension with the other requirements by specifying $\pi_n(k)$ to have a value appearing in a totally new block not yet used. We can fulfill the second requirement by using a value $k$ not yet mentioned in the construction. Infinitely often, we can give attention to the third requirement by selecting for a given pair $a\neq b$ a totally new $n$ not yet considered at all and placing $\pi_n(a)$ and $\pi_n(b)$ to have values in the same block. At each later stage, we can preserve this uniqueness property for this pair.

In this way, the permutations are gradually defined, while fulfilling the properties, and so there are indeed such permuations.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .