Skip to main content
deleted 315 characters in body
Source Link
Gabe Conant
  • 3.3k
  • 3
  • 23
  • 34

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 fact that $\mathcal{F}^k(I)$ is a filter isn't an essential part of the definition of $k$-dividing. However, it does correspond to the fact that the collection of $k$-nondividing formulas forms a filter, which is sometimes useful, especially when analyzing dividing in theories with quantifier elimination.

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.

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 fact that $\mathcal{F}^k(I)$ is a filter isn't an essential part of the definition of $k$-dividing. However, it does correspond to the fact that the collection of $k$-nondividing formulas forms a filter, which is sometimes useful, especially when analyzing dividing in theories with quantifier elimination.

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.

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.

Source Link
Gabe Conant
  • 3.3k
  • 3
  • 23
  • 34

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 fact that $\mathcal{F}^k(I)$ is a filter isn't an essential part of the definition of $k$-dividing. However, it does correspond to the fact that the collection of $k$-nondividing formulas forms a filter, which is sometimes useful, especially when analyzing dividing in theories with quantifier elimination.

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.