# Special infinitary relations and ultrafilters

(This problem appeared in face of me trying to generalize my theory of (binary) funcoids to the theory of $n$-ary funcoids (I call them "multifuncoids") for arbitrary $n$.)

Let $I$ is some indexing set.

By filters I will mean (not necessarily proper) filters on some fixed set $U$.

I will call a multifuncoid a $I$-ary relation $f$ between subsets of $U$ such that

1. for every $k \in I$, subsets $A$ and $B$ of $U$, and family $L = L_{i \in I \setminus \{ k \}}$ of subsets of $U$ we have $$f ( L \cup \{ (k ; A \cup B) \} ) \Leftrightarrow f ( L \cup \{ (k ; A) \} ) \vee f ( L \cup \{ (k ; B) \} ) .$$

2. for every $k \in I$, and family $L = L_{i \in I}$ we have $L_k=\emptyset \Rightarrow \neg f (L)$.

Let $a = a_{i \in I}$ is some family of filters.

I will call funcoidal product $\prod a$ of a family $a = a_{i \in I}$ of filters an $I$-ary relation between subsets of $U$ such that for every family $R = R_{i \in I}$ of sets we have $$\left( \prod a \right) R \Leftrightarrow \forall i \in I \forall A \in a_i : A \cap R_i \neq \emptyset .$$ It simple to show that funcoidal product is a multifuncoid.

Conjecture For every non-empty multifuncoid $f$ there exist a family $a = a_{i \in I}$ of ultrafilters such that $f \supseteq \prod a$.

If this conjecture is false, under which additional conditions it will be true? (I know that it is true for finite set $I$, but am interested also in the infinite case.)

Addition: I think that the following condition may be necessary: $f(\{(i;A_i\cup B_i) | i\in I\}) \Leftrightarrow f(\{(i;A_i) | i\in I\}) \vee f(\{(i;B_i) | i\in I\})$ for each families $A=A_{i\in I}$ and $B=B_{i\in I}$ of subsets of $U$.
-
Is the additional condition formulated correctly? It seems to me that it fails even for the two-element index set $I=\{0,1\}$ when $a_0$ and $a_1$ are ultrafilters. Take $A_0=B_1=U$ and $A_1=B_0=\emptyset$. – Andreas Blass Apr 7 '11 at 14:31
I am in awe of the kindness of the mathematicians who responded. The question makes no attempt to define the totally unfamiliar terms, save for a link to porton's web page, where the reader has to pick a paper, take a deep breath, and wade into porton's stuff. I don't think the way the question is worded really deserves such kindness. – Todd Trimble Apr 7 '11 at 16:15
I found the question quite self-contained, I certainly didn’t read any porton’s paper. – Emil Jeřábek Apr 7 '11 at 16:37
@Daniel, @Emil: perhaps you are right and I was being unfair to porton. I had some difficulty understanding what a multifuncoid was supposed to be at first reading, which is when I clicked on the link. On another more careful reading, I think it is indeed decipherable -- my apologies. – Todd Trimble Apr 7 '11 at 16:52
But I still think Andreas and Emil are kind! :-) – Todd Trimble Apr 7 '11 at 16:53

For $a$ an $I$-indexed family of filters and $S$ an $I$-indexed family of subsets of $U$ such that $U\smallsetminus S_i\notin a_i$ for every $i\in I$, define the restricted product $\prod^Sa$ by $$\left(\prod\nolimits^Sa\right)R\Leftrightarrow\left(\prod a\right)R\land\{i\in I:R_i\ne S_i\}\text{ is finite.}$$ This is again a nonempty multifuncoid.

Then:

1. Every nonempty multifuncoid $f$ contains a restricted product of ultrafilters. Fix $S$ such that $f(S)$. For every $J\subseteq I$ finite, let $A_J$ be the set of sequences $a$ of ultrafilters such that $S_i\in a_i$ for every $i$, and $f(R)$ holds for every $R$ where $R_i\in a_i$ for $i\in J$, and $R_i=S_i$ for $i\notin J$. Then $A_J$ is closed in $(\beta U)^I$, $A_J\cap A_{J'}\supseteq A_{J\cup J'}$, and $A_J\ne\varnothing$ by the finite case, hence there exists $a\in\bigcap_JA_J$ by compactness of $(\beta U)^I$. Then $f\supseteq\prod^Sa$.

2. The restricted product of an infinite family of ultrafilters does not contain any product of a family of ultrafilters (assuming $U$ has more than one element), thus refuting the original wording of your conjecture. Indeed, if $f=\prod^Sa$ and $f(R)$, then $R_i=S_i$ for all but finitely many $i$, whereas if $g=\prod b$ is a product of a family of ultrafilters, we can for every $i\in I$ fix $R_i\in b_i$ such that $R_i\ne S_i$; then $g(R)$, but not $f(R)$, so $g\nsubseteq f$.

Point 1 says that the intuition behind the conjecture is basically sound, but the notion of the product has to be modified to make it really work to take into account that the axioms of multifuncoids only concern local behaviour when a single (or finitely many, by iteration) coordinate is changed, they do not imply anything about what happens when infinitely many coordinates change.

Since the proof above refers to the case of finitely many coordinates in a stronger form than what is claimed to hold in the question, I may as well give a self-contained proof of 1.

As before, fix $S$ such that $f(S)$. By definition, $S_i\ne\varnothing$ for every $i$. If $a$ is a family of filters such that $S_i\in a_i$ for all $i\in I$, consider a modified product \begin{align} \left(\prod\nolimits_ma\right)R&\Leftrightarrow(\forall i\in I)\,R_i\in a_i,\\ \left(\prod\nolimits_m^Sa\right)R&\Leftrightarrow\left(\prod\nolimits_ma\right)R\land\{i\in I:R_i\ne S_i\}\text{ is finite.} \end{align} Note that if all $a_i$ are ultrafilters, then $\prod_ma=\prod a$, and $\prod_m^Sa=\prod^Sa$. It thus suffices to find $a$ such that $\prod_m^Sa\subseteq f$, and all $a_i$ are ultrafilters.

Let $P$ be the set of all families $a$ of proper filters such that $S_i\in a_i$ for all $i$, and $\prod_m^Sa\subseteq f$. We define a partial order on $P$ by $a\le b$ iff $a_i\subseteq b_i$ for all $i\in I$. It is easy to see from the definition of a multifuncoid that:

(*) Whenever $f(R)$, $R_i\subseteq R'_i$ for every $i$, and $R_i=R'_i$ for all but finitely many $i$, then $f(R')$.

It follows that $P$ is nonempty, since $a\in P$, where $a_i$ is the filter generated by $S_i$. Since the pointwise union of any chain in $P$ is an element of $P$, Zorn’s lemma implies that there exists a maximal element $a\in P$.

I claim that every $a_j$ is an ultrafilter. Assume for contradiction that it is not, and let $X\subseteq U$ be such that $X,U\smallsetminus X\notin a_j$. Define $b$ by $b_i=a_i$ for $i\ne j$, and $b_j$ is the filter generated by $a_j\cup\{X\}$. Since $a< b$, we have $b\notin P$, thus there exists $R$ such that $\neg f(R)$, $R_i=S_i$ for all but finitely many $i$, $R_i\in a_i$ for all $i\ne j$, and $X\cap Y\subseteq R_j$ for some $Y\in a_j$. Symmetrically, there exists $R'$ and $Y'\in a_j$ such that $\neg f(R')$, $R'_i=S_i$ for all but finitely many $i$, $R'_i\in a_i$ for $i\ne j$, and $(U\smallsetminus X)\cap Y'\subseteq R'_j$. Using (*) and the closure of $a_i$ under intersections, we can replace $R_i$ with $R_i\cap R'_i$ for all $i\ne j$, and the same for $R'_i$. Thus, without loss of generality, $R_i=R'_i$ for all $i\ne j$. But then by the definition of a multifuncoid, $\neg f(R'')$, where $R''_i=R_i=R'_i$ for $i\ne j$, and $R''_j=R_j\cup R'_j$. However, $R''_j\supseteq Y\cap Y'\in a_j$, hence $R''\in\prod_m^Sa\subseteq f$, a contradiction.

$%%%%$

-
I see I do not fully understand your counter-example and also that your result contradicts with my intuition (thus my intuition being wrong). By these reason I will stop my writing (mathematics21.org/algebraic-general-topology.html) now and go to learn. I have purchased the book "The Theory Of Ultrafilters" by W. W. Comfort, S. Negrepontis but have not yet fully learned it. Now it's the time. – porton Apr 7 '11 at 17:13
@porton: Your conjecture seems to be a moving target. It couldn't hurt to work on it for yourself for a bit. – Daniel Litt Apr 7 '11 at 17:30
Some attempts on further clarification. In case it’s not obvious, I’m implicitly using the following observation: if $a_i$ is an ultrafilter, then the condition “$\forall A\in a_i\,A\cap R_i\ne\varnothing$” from the definition of $\prod a$ simplifies to “$R_i\in a_i$”. The point of the counterexample is that any $R$ such that $(\prod^Sa)R$ agrees with $S$ on all but finitely many coordinates, whereas for a product $\prod b$ of ultrafilters you can find $R$ such that $R_i\in b_i$ is distinct from $S_i$ for every $i$, so that $(\prod b)R$ but not $(\prod^Sa)R$. – Emil Jeřábek Apr 7 '11 at 17:36
@Emil Jeřábek: Oh, sorry, it's my error, I was uncareful. I will delete my wrong comment where I blame you for an error. – porton Apr 7 '11 at 17:39
@Emil Jeřábek: I made a modified version of my conjecture: mathoverflow.net/questions/61118/… – porton Apr 9 '11 at 6:18

If I've correctly deciphered your definitions, then the following should be a counterexample to your conjecture (even with the condition that you added later). Take both $I$ and $U$ to be the set $N$ of natural numbers. Define $f$ to be true for an $N$-indexed sequence $(A_i)$ of subsets of $N$ if and only if there is no finite upper bound (independent of $i$) for the cardinalities of the sets $A_i\cap\{0,1,2,\dots,i\}$.

-
@Andreas Blass: The $f$ you defined is a multifuncoid. But it is not obvious for me why this is a counter-example for my conjecture that is why your $f$ is not above any product of ultrafilters. Could you explain? – porton Apr 7 '11 at 16:58
Consider a product of ultrafilters $a_i$. Define $A_i$ to be the unique singleton in $a_i$ if $a_i$ is principal and to be $N\setminus\{0,1,\dots,i\}$ if $a_i$ is non-principal. Then $A_i\in a_i$ for all $i$, but $f$ applied to the sequence $(A_i)$ is false because the cardinalities of the sets $A_i\cap\{0,1,\dots,i\}$` are bounded above by 1. – Andreas Blass Apr 8 '11 at 13:16
@Andreas Blass: I did a bad error, I forgot the second condition in the definition of multifuncoids (now added). This breaks your proof. I think we can fix it replacing "if there is no finite upper bound (independent of i) for the cardinalities of the sets $A_i\cap\{0,1,2,\dots,i\}$" with "if there is no finite upper bound (independent of i) for the cardinalities of the sets $A_i\cap\{0,1,2,\dots,i\}$ and every set $A_i$ is not empty", but I have not yet checked this. – porton Apr 8 '11 at 14:47
@Andreas Blass: In your comment you've proved only that the multifuncoid defined by you is not a superset of certain funcoidal product of filters. I however need to verify a different supposition, whether a funcoidal product of filters has other subsets except of the empty set. See also my previous comment about my error in the formulation of the question and a modified question: mathoverflow.net/questions/61118/… – porton Apr 15 '11 at 21:33