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
    Commented 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$ Commented 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
    Commented 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
    Commented Dec 13, 2014 at 19:54

You must log in to answer this question.

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