Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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$.
share|cite|improve this question
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…. – 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.

share|cite|improve this answer
I had a hunch that the Gravatar looks familiar! Welcome to math.SE!! – Asaf Karagila Nov 7 '12 at 13:41
Welcome, indeed. There is probably noone better suited to answer this question. But, perhaps I need to clarify the notation. – fmkatz Nov 7 '12 at 20:10
Sorry, I was going down the wrong path, there. Do you have a reference for the general theorem about fixed points? Thanks. – fmkatz Nov 7 '12 at 20:19
Nice to see you here! – Andrés Caicedo Nov 10 '12 at 16:46
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

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.