I am currently reading the book "Set theory on the real line" by Bartoszynski and Judah and I do have problems to proof the following statement: Suppose $\mathcal{F}$ is a filter on $\omega$ including the Fréchet-Filter $\mathcal{G}$ ($\mathcal{G}\subset\mathcal{F}$). Then the following is equivalent:

(i) For every partition of $\omega$ into finite sets $\{I_n:n\in\omega\}$, there exists $X\in\mathcal{F}$ such that $X\cap I_n=\emptyset$ for infinitely many $n\in\omega$.

(ii)For every function $f\in\omega^\omega$ which is finite to one, $f(\mathcal{F})=\{X\subset\omega:f^{-1}(X)\in\mathcal{F}\}$ is not the Fréchet-Filter.

[A function is finite to one if each point in its range space is the image of only finitely many points in the domain]

The book says, $(i)\Leftrightarrow (ii)$ is obvious. But I can't proof it.


I employ the set-theorists' notation: $\{f(a):a\in A\}=f''A$ (read $f$-double-tick-$A$) when $A\subset$ dom $f$. Also $f^{-1}B=\{x: f(x)\in B\}.$

For $(i)\implies (ii)$:

First, if $\omega$ \ $f''\omega$ is infinite, then $f^{-1}f''\omega=\omega\in \mathbb F$ but $f''\omega$ is not in the Frechet filter.

Second, if $\omega$ \ $f''\omega$ is finite, let $\quad J=\{f^{-1}\{n\}:n\in \omega\}$ \ $\{\phi\}.$ $$\text {Let } Y\in \mathbb F \text { such that } K=\{j\in J:Y\cap j=\phi\} \text {is infinite.}$$ $$\text {Let } Z= \cup \{j\in J: Y\cap j\ne \phi\}=\cup (J \backslash K).$$ Then $Z\supset Y\in \mathbb F$ so $Z\in \mathbb F.$ Let $X=f''Z.$ Then $f^{-1}X=Z\in \mathbb F,$ but $\omega$ \ $X$ is infinite (and hence $X$ is not in the Frechet filter): Because $L=\omega$ \ $Z=\cup K$ is infinite, so $\omega$ \ $X=f''L$ is infinite .

For $(ii)\implies (i)$:

Let $\{I_n\}$ be a partition of $\omega$ into (non-empty) finite sets . Let $f''I_n=\{n\}$ for each $n\in \omega.$ Let $X\subset \omega$ such that $\omega$ \ $X$ is infinite and such that $Y=f^{-1}X\in \mathbb F.$ $$\text {Then }\quad \{n\in \omega: \phi =Y\cap I_n\}=\omega \backslash X \quad \text {which is infinite.}$$ Remark: The notation $f''A$ is not merely convenient, but avoids the ambiguity of $f(A) $ when $A$ is both a member and a subset of dom$(f)$.

  • $\begingroup$ I never heard of "double-tick", only "double-prime" or "double-hook" (depends if it's $f''$ or $f``$ (equiv. $f"$)), or "the direct image of $A$". $\endgroup$ – Asaf Karagila May 15 '16 at 15:33
  • $\begingroup$ @Asaf Karagila. I have heard the set theorists at U. of Toronto and at York U. (Toronto) always saying "double-tick." $\endgroup$ – DanielWainfleet May 15 '16 at 15:37
  • $\begingroup$ I'm no stranger to the American sitcom trope that Canadians are weird, but this is the first time I actually see real life evidence for that! ;-) $\endgroup$ – Asaf Karagila May 15 '16 at 15:40
  • $\begingroup$ @AsafKaragila. Among the double-tickers were Franklin Tall, originally from USA & Stavo Todorcevic,originally from another planet, and Andrew ( last name I forget), originally Polish. $\endgroup$ – DanielWainfleet May 15 '16 at 21:08
  • $\begingroup$ We always used $f[A]$ for the set $\{f(a) : a \in A \}$. So there is a difference between $f[a]$ and $f(a)$. It's harder to pronounce though. $\endgroup$ – Henno Brandsma May 16 '16 at 4:29

A finite-to-one function $f : A \to B$ partitions $A$ into finite sets, namely $f^{-1}(\{b\})$ for each $b \in B$.

In the other direction, given a partition $I_n$ of $A$, you may define $f : A \to \omega$ as follows: each $a \in A$ is in exactly one $I_n$ (since this is what it means to be a partition), so you can unambiguously define $f(a) = n$. Then the preimage of each $n$ is $I_n$, so if the $I_n$ are finite, then $f$ is finite-to-one.

This correspondence is the key to the question: prove that an $I_n$ and $X$ satisfying the properties of (i) correspond to an $f$ satisfying the properties of (ii) (recall that $f(\mathcal F)$ is not the Fréchet filter precisely if it has an element with infinite complement, so you just need to find such an element) and likewise if (ii) holds there is an element of $f(\mathcal F)$ with infinite complement, so you need to demonstrate that it satisfies the conclusions of (i).

  • $\begingroup$ Thanks, i found a proof for $(ii)\rightarrow (i)$, which i hope is correct. I still have problems with the other direction: So let $f\in\omega^\omega$ be a finite-to-one function. Then $M:=\{f^{-1}(n):n\in\omega\}$ is a partition of $\omega$ into finite sets. Thus, one can find $X\in\mathcal{F}$ s.t. $X\cap I_n=\emptyset$ for infinitely many $n\in\omega$. But f does not have to be surjective, so i cannot conclude that $\omega-X$ is infinite. $\endgroup$ – peer May 15 '16 at 16:34
  • $\begingroup$ I haven't thought about this in too much detail, but -- though you are correct $f$ need not be surjective, it does at least have to have infinite image. Is that enough? $\endgroup$ – Ben Millwood May 16 '16 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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