2
$\begingroup$

Conjecture Let $U$ be an (infinite) set. Let $f$ be an $N$-ary (where $N$ is an arbitrary index set) relation on $U$ (that is a set of functions $N \rightarrow U$).

Let $\mathcal{L}_0$, $\mathcal{L}_1$ be $N$-indexed families of filters (on $U$).

I denote $\operatorname{up} \mathcal{L} = \prod_{i \in N} \mathcal{L} (i)$.

Let $\forall X \in \operatorname{up} \mathcal{L}_0 \cap \operatorname{up} \mathcal{L}_1 : \left( \prod_{i \in N} X_i \right) \cap f \neq \emptyset$.

Prove (or disprove) that $$ \exists c \in \{ 0, 1 \}^N \, \forall Y\in \prod_{i\in N}\mathcal{L}_{c (i)} (i) : \left( \prod_{i \in N} Y_i \right) \cap f \neq \emptyset . $$

$\endgroup$

1 Answer 1

3
$\begingroup$

Something's wrong in the last formula of the question. The elements of $f$ are functions $N\to U$, but the elements of $\prod_{i\in N}(\mathcal L_{c(i)}(i))$ are functions on $N$ whose values are subsets of $U$, elements of the filters $\mathcal L_{c(i)}(i)$, not elements of $U$. I'm going to assume that you meant that for every choice of sets $Y_i\in\mathcal L_{c(i)}(i)$ (for all $i\in N$), $(\prod_{i\in N}Y_i)\cap f\neq\emptyset$.

If that's the intended question, then here's a counterexample. Let $U$ and $N$ both be the set of natural numbers. Let $\mathcal L_0(0)=\mathcal L_1(0)=$ the filter of cofinite subsets of $U$. For all $n>0$, let $\mathcal L_0(n)$ be the principal filter generated by $\{0\}$ and let $\mathcal L_1(n)$ be the principal filter generated by $\{1\}$. Let $f$ be the family of those functions $x:N\to U$ such that $x(n)=0$ whenever $1\leq n\leq x(0)$, and $x(n)=1$ whenever $n>x(0)$. (The only important thing here is that $x(0)$ determines the values of $x$ at all points other than 0 and those values are 0 or 1.)

If $X\in\text{up }\mathcal L_0\cap\text{up }\mathcal L_1$, then $X_0$ contains all but finitely many elements of $\mathbb N$ while $X_k$ for any $k>0$ contains both 0 and 1. It follows immediately that $\prod_{i\in N}X_i$ contains an element of $f$, in fact infinitely many elements of $f$.

Now consider any fixed $c\in\{0,1\}^n$, and notice that there is at most one $k\in N$ such that the sequence $x=(k,c(1),c(2),\dots)$ (i.e., $c$ with $c(0)$ replaced by $k$) is in $f$. Let $Q=U-\{k\}$ if there is such a $k$ and $Q=U$ otherwise. Then one possibility for the $Y_i$ in (my interpretation of) the question is $Y_0=Q$ and $Y_i=\{c(i)\}$ for all $i>0$. Then $\prod_{i\in N}Y_i$ does not contain any element of $f$.

$\endgroup$
4
  • $\begingroup$ OK, I've read your proof carefully. Dear Andreas, you are much better that me in finding counterexamples about filters. Why you can do it and I cannot? What is your secret? Maybe, it is an army knife of some common examples of filters, such as cofinite filters, principal filters generated by $\{0\}$ and $\{1\}$, etc. What is it? $\endgroup$
    – porton
    Dec 11, 2014 at 22:54
  • 2
    $\begingroup$ I suppose there are two tools that I use. One is that I've been thinking about filters since approximately 1968, so I've developed some intuition about what is or isn't likely to work. The other, which I used in this case, is to try to carefully prove your conjecture, and see where the proof runs into difficulty. That provided a hint of how to build a counterexample, taking advantage of the difficulty. $\endgroup$ Dec 11, 2014 at 22:58
  • $\begingroup$ See also portonmath.wordpress.com/2011/02/24/my-math-sickness (a possible reason why I am sometimes bad in finding counter-examples) $\endgroup$
    – porton
    Dec 12, 2014 at 0:26
  • $\begingroup$ Your counter-example was used by me as a counter-example to yet two other conjectures: mathoverflow.net/q/190601/4086 and mathoverflow.net/q/190585/4086 $\endgroup$
    – porton
    Dec 13, 2014 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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