6
$\begingroup$

Is the following filter known in set theory, and does it have a name ? For $k=1$ it is the filter of cofinite subsets.

Fix a natural number $k$ and a linear order $I$. Define a filter on the set of strictly increasing k-tuples $I^{(k)}:=\{(i_1,...,i_k): i_1<...<i_k \}$ as follows:

A subset $U$ of the set of strictly increasing k-tuples is big iff $U$ contains a tuple of strictly increasing $k$ elements from every infinite subset of I. In notation, call $U\subset I^{(k)}$ big iff for each infinite subset $J\subset I$ there is a $k$-tuple $(j_1,...,j_k)\in U$, $j_1<...<j_k$, $j_1,...,j_k\in J$.

For $k=1$ it means that $U$ intersects each infinite subset, i.e. is cofinite. For $k>1$ the proof that it is a filter uses the Ramsey theorem. The notion is not quite trivial: for $k=2$ and $I=\Bbb Z$ the subset of pairs with even sum is big, even though the subset of pairs with odd sum is not (take $J$ to be the subset of even numbers).

Perhaps an equivalent description in terms of subsets is clearer. A subset $U$ of the set $P^k(I)$ of subsets of size $k$ is big iff each infinite subset has a subset of size $k$ in $U$, i.e. in notation, $P^k(J)\cap U \neq \emptyset$ for each infinite $J\subset U$.

The motivation for the question is that this filter is implicit in the definition of dividing in model theory: a formula $\phi(-,b)$ does not k-divide in a model $M$ iff the subset $\{(b_1,...,b_k)\in M^k: tp(b_i)=tp(b), M\models\exists x \wedge_i \phi(x,b_i)\}$ is big in $p(M)^k=\{(b_1,...,b_k)\in M^k: tp(b_i)=tp(b)\}$,
for any (eqv.,each) linear order on $p(M)$, where $p(M)$ denotes the set of realisations of $tp(b)$ in $M$. Indeed, if it is not big, by definition there is an infinite subset $(b_J)_J$ of realisations of $tp(b)$ such that each $k$-tuple in $\phi$-inconsistent, i.e. $\phi(-,b)$ $k$-divides.

$\endgroup$

1 Answer 1

3
$\begingroup$

Unfortunately I don't have a good answer to your question. In particular, I don't know a place where this filter is directly discussed or given a name. But I still think there are some interesting comments to make. Maybe they will be of use to you, or perhaps jog something in the knowledge of other people who read this answer.

For $k>1$ it seems natural to view this filter as consisting of $k$-uniform hypergraphs. Specifically, if $P^k(I)$ is the set of $k$-element subsets of $I$, then a subset $E\subseteq P^k(I)$ is a $k$-uniform hypergraph with vertex set $I$. Let $\mathcal{F}^k(I)$ be the filter defined in the original post: $E\in\mathcal{F}^k(I)$ if and only for any infinite $J\subseteq I$, $E$ contains a $k$-element subset of $J$. If we reword this under the hypergraph viewpoint, then we get alternate description of the filter, which I think is illuminating.

$\mathcal{F}^k(I)$ is the collection of $k$-uniform hypergraphs on the vertex set $I$ which contain no infinite independent sets.

It follows from Ramsey's Theorem that a $k$-uniform hypergraph $H=(I,E)$ is in $\mathcal{F}_k(I)$ if and only if every infinite induced subgraph of $H$ contains an infinite complete set. As noted by the OP, this provides an easy way to see that $\mathcal{F}^k(I)$ is actually a filter. Assuming $I$ is infinite, it is a proper filter.

A remark on the even sum example. As noted by the OP, $\mathcal{F}_2(\mathbb{Z})$ contains the graph on $\mathbb{Z}$ in which an edge is drawn between two integers whose sum is even. Indeed, this graph has no independent set of size $3$.

In light of the previous remark, I think one can't help but define $\mathcal{F}^k_n(I)$ to be the set of $k$-uniform hypergraphs on $I$ with no independent set of size $n$. So $\mathcal{F}^k_n(I)\subseteq \mathcal{F}^k(I)$. Let $\mathcal{F}^k_{\text{fin}}(I)=\bigcup_{n>0}\mathcal{F}^k_n(I)$ be the set of $k$-uniform hypergraphs with a uniform finite bound on the size of an independent set. This is also a filter, since if $E_1,E_2\in \mathcal{F}^k_n(I)$ then $E_1\cap E_2\in \mathcal{F}^k_{R(n,n;2,k)}(I)$ where $R(n,n;2,k)$ is the relevant hypergraph Ramsey number (as defined here). Of course $\mathcal{F}^k_{\text{fin}}(I)$ is properly contained in $\mathcal{F}^k(I)$.

A remark on cofinite filters. The cofinite filter $\mathcal{F}(P^k(I))$ of cofinite subsets of $P^k(I)$ corresponds to the $k$-uniform hypergraphs with cofinite edge set. This filter is contained in $\mathcal{F}_{\text{fin}}^k(I)$, but of course not equal to it (e.g., the even-sum graph on $\mathbb{Z}$ above does not have a cofinite edge set). In general, an ultrafilter on an infinite ground set is nonprincipal if and only if it contains the cofinite filter. Is there something interesting to be said about ultrafilters on $P^k(I)$ that contain $\mathcal{F}^k(I)$ (or $\mathcal{F}^k_{\text{fin}}(I)$)?


Remarks on Dividing

The underlying hypergraphs involved in this viewpoint of dividing appear in The Characteristic Sequence of a First-Order Formula by M. Malliaris. In this paper, Malliaris fixes a theory $T$ and a formula $\varphi(x,y)$ and, for each $k\geq 1$ defines the hypergraph $P_k(y_1,\ldots,y_k)$ given by $\exists x\bigwedge_{i=1}^k\varphi(x,y_i)$. So given some (saturated enough) model $M\models T$ and parameter $b\in M^y$, if $p=\text{tp}(b)$, then $\varphi(x,b)$ does not $k$-divide (over $\emptyset$) if and only if the hypergraph $(p(M),P_k)$ is in $\mathcal{F}^k(p(M))$. Something similar to this is stated in Observation 2.4(4) of Malliaris's paper. A theme of the paper is that many model-theoretic notions can be reformulated and studied by means of these hypergraphs.

$\endgroup$
1
  • $\begingroup$ thank you, it is very illuminating but indeed,does not say much about the filter ... A way to rephrase your definition is to say that $\mathcal F ^k(I)$ is is the collection of k-uniform hypergraphs on the vertex set I without infinite anticliques. (just a slight change of terminology) $\endgroup$
    – user254885
    Jun 23, 2021 at 14:06

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.