# Self-similarity in ultrafilters over N

First, some notation:

• Set variables, $X, Y$, range over sets of natural numbers, $\mathbb{N}={1,2,3,..}$.

• Square brackets represent sets of natural numbers based on a formula. $$[φ(\mathbf{n})]=\{φ(n)|n∈N\}$$ So, $[2n]=\{2,4,6…\}$ and $[\mathbf{n}^2] = {1, 4, 9, ..}$

• $X_Y$ = the selection of $X$ based on $Y$: $$X_Y = \{X_k|k\in Y\}$$ where $X_k$ is the $k$-th member of $X$ (in numeric order).

So, $X_{[2n]}$ consists of every second element of X and $X_{[n^2]} = \{X_1, X_4, X_9,…\}$

Now, the question: Is there a non-principal ultrafilter, $F$, over $\mathbb{N}$ such that:

1. For each $k \in \mathbb{N}$, $[k\mathbf{n}]\in F$.
2. If $X \in F$, then, for every $k$, $[k\mathbf{n}]_X \in F$.
-
How did you come up with the question? – tomasz Nov 3 '12 at 18:15
I am trying to prove the existence of sizings of sets of natural numbers which have satisfy some similarity conditions - for example - that $$\sigma(X) = \sigma(Y) \iff \sigma([kn]_X) =\sigma([kn]_Y)$$. By sizings, I mean the kinds of orderings developed in the citations on my answer to math.stackexchange.com/questions/1393/…. – fmkatz Nov 3 '12 at 20:25
@fmkatz, the answer also depends on the set axiom system: according to Herrlich's Axiom of Choice, in ZF+AD there are no non-principal (he calls them "free") ultrafilters on $\mathbb N$ – alancalvitti Jan 14 '13 at 19:41

If I correctly understand your notation, the set $[kn]_X$ in requirement 2 is just $\{kx:x\in X\}$, so you are asking for the ultrafilter $F$ to be invariant under the operation $\mathbb N\to\mathbb N$ of multiplication by $k$ (for all $k$). There is no ultrafilter that accomplishes this, even for a single $k>1$. The reason is the theorem that, if an ultrafilter is mapped to itself by an operation $f$ on its underlying set, then the ultrafilter must contain the set of fixed-points of $f$.
For the particular operation you asked about, the (proof of) the general theorem can be specialized to the following. Partition $\mathbb N$ into the set $X$ of those numbers whose binary expansion ends with an even number of 0's (i.e., odd numbers, numbers congruent to 4 mod 8, etc.) and the set $Y$ of numbers whose binary expansion end with an odd number of 0's (congruent to 2 mod 4, or to 8 mod 16, etc.) An ultrafilter $F$ must contain exactly one of these two sets. But $[2n]_X=Y$ and $[2n]_Y=X$, so $F$ cannot satisfy your requirement 2.
By the way, rather than $[2n]_Y=X$, it should say $[2n]_Y\subseteq X$. But this is all we need. – Andrés Caicedo Nov 14 '12 at 0:13