1
$\begingroup$

Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.

If $A,B$ are any sets, let $A \,\triangle \, B = (A\setminus B)\cup(B\setminus A)$.

Is there a bijection $\varphi:\o\to\oo$ such that for all $k\in \o$ we have $\big|\varphi(k)\,\triangle\,\varphi(k+1)\big| = 1$?

$\endgroup$
1
  • 4
    $\begingroup$ Well, isn't Gray code doing that? $\endgroup$ Commented Nov 10 at 23:33

1 Answer 1

3
$\begingroup$

I'll work with countably infinite binary strings $\alpha_i$ with finitely many $1$'s instead of sets.

Initialize $\alpha_1=(0,0,0,\ldots)$.

For each $i=1,2,\ldots$, let $\alpha_{2^{i-1}+1},\alpha_{2^{i-1}+2},\ldots,\alpha_{2^{i}}$ be the result of reversing the sequence of strings $\alpha_{1},\alpha_{2},\ldots,\alpha_{2^{i-1}}$ and then flipping the $i$th bit in each string to $1$.

Then $\alpha_1,\alpha_2,\ldots$ should be your infinite Gray code. It's just the extension of the standard Gray code to infinite length strings (see e.g. the example at https://en.wikipedia.org/wiki/Gray_code).

$\endgroup$

You must log in to answer this question.

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