非空强不可比无互补族:当某一元素为单族私有时的界 $2^{n-1}-1$
low tier2026-11-13OP-1370本文含 4 个研究级成果审阅: Claude CodeEnglish
摘要
对于整数 $n \ge 3$ 和 $3 \le t \le n$,arXiv:2611.12199 的猜想 4.3 断言,$n$ 元集子集的 $t$ 个非空、两两强不可比且无互补族的总基数最大值 $M(n,t)$ 恰好为 $2^{n-1} - 1$。尽管先前的结果已确立 $2^{n-1} - 1 \le M(n,t) \le 2^{n-1}$,但上界仍留下一的差距。我们证明,只要基础集中至少有一个元素至多出现在某一个族 $\mathcal{A}_i$ 的集合中,猜想的上界 $\sum_{j} |\mathcal{A}_j| \le 2^{n-1} - 1$ 便成立,且仅要求 $\mathcal{A}_i$ 本身是无互补的。该论文自身的极值构造就具有这样的元素,因此这种形式的构型都无法达到 $2^{n-1}$。该证明表明,其余各族的并集打散的集合严格多于其包含的集合,并将指定的族连同这些被打散的集合限制在其余 $n-1$ 个元素的子集之中。我们还在三族情形下确立了猜想的界:当其中两族为单元素集时,当除一个无互补族之外的两族总基数严格小于 $2^{\lceil n/2 \rceil}$ 时;以及对于任意 $t \ge 3$,当除一个无互补族之外的其余各族之并的 VC 维(VC-dimension)严格小于 $\lceil n/2 \rceil$ 时。所有的定义、引理和定理均已在 Lean 4 中形式化并得到验证。
1. 引言
设 $n$ 和 $t$ 为正整数。若 $n$ 元集 $[n]$ 的子集族 $\mathcal{F}$ 不包含互补对,即对于每个集合 $A \in \mathcal{F}$,其补集 $A^c = [n] \setminus A$ 均不属于 $\mathcal{F}$,则称 $\mathcal{F}$ 是无互补的。若集合族系统 $\mathcal{A}_1, \dots, \mathcal{A}_t \subseteq 2^{[n]}$ 满足任意族中的集合都不是另一族中某个集合的子集,即对于所有指标 $i \ne j$,若 $A \in \mathcal{A}_i$ 且 $B \in \mathcal{A}_j$,均有 $A \not\subseteq B$ 且 $B \not\subseteq A$,则称它们是两两强不可比的。
在 arXiv:2611.12199 中,作者探讨了此类族的极值性质,重点关注最大总大小 \[ M(n,t) = \max \sum_{i=1}^t |\mathcal{A}_i|, \] 其中最大值取遍 $[n]$ 上所有由 $t$ 个非空、无互补、两两强不可比的族构成的系统。arXiv:2611.12199 的定理 1.7(形式化为 op_1370_uncomplemented_strongly_incomparable_upper_bound)证明了:对于所有自然数 $n$ 和 $t$,任意由无互补、强不可比族构成的系统均满足 $\sum_{i=1}^t |\mathcal{A}_i| \le 2^{n-1}$。这一通用的界可以通过代数方法建立;事实上,hilton_strong_incomparability_matrix 表明,对于每个 $n$,在域 $K$ 上均存在矩阵 $L \in K^{2^n \times 2^{n-1}}$ 和 $R \in K^{2^{n-1} \times 2^n}$,其乘积在不可比对上为零,而每个无互补族都会导出一个非奇异的主子矩阵。
另一方面,arXiv:2611.12199 的命题 4.2(形式化为 op_1370_uncomplemented_strongly_incomparable_lower_bound)针对所有 $n \ge 3$ 和 $3 \le t \le n$,构造了达到总大小 $\sum_{i=1}^t |\mathcal{A}_i| = 2^{n-1} - 1$ 的非空无互补强不可比族。例如,当 $n = 3$ 且 $t = 3$ 时,op_1370_case_n3_t3 确认了最大总大小为 $2^{3-1} - 1 = 3$。基于这一构造,arXiv:2611.12199 的猜想 4.3 猜测,对于所有 $n \ge 3$ 和 $3 \le t \le n$, \[ M(n,t) = 2^{n-1} - 1. \] 因此,arXiv:2611.12199 中的现有界留下了一个恰好为一的差距: \[ 2^{n-1} - 1 \le M(n,t) \le 2^{n-1}. \]
消除这一大小为一的差距的核心困难在于,线性代数界 $2^{n-1}$ 在 $t = 1$ 和 $t = 2$ 时是紧的,此时单个无互补族的大小即可达到 $2^{n-1}$。要求 $t \ge 3$ 且每个族非空,迫使不同族之间产生结构性相互作用和交叉不可比性,但仅从线性代数中导出所需要的减少量 1 是极具挑战的。
我们在若干结构条件下证明了猜想 4.3 的界;一般情形的猜想仍然悬而未决。我们的主要结果 op_1370_private_element_bound 证明了:对于任意 $t \ge 3$ 和任意 $n$,若存在一个元素 $x \in [n]$ 仅出现在至多一个族 $\mathcal{A}_i$ 的集合中,且 $\mathcal{A}_i$ 是无互补的,则 $\sum_{j=1}^t |\mathcal{A}_j| \le 2^{n-1} - 1$。在此条件下,其余 $t-1$ 个族均不要求是无互补的。命题 4.2 的构造恰好具有这种形式:元素 $1$ 仅出现在 $\mathcal{A}_1$ 的集合中。因此该定理表明,按照该论文的极值示例构建的构型都无法达到 $2^{n-1}$。我们还在其他几种情形下证明了猜想的界:当 $t = 3$ 且其中两族为单元素集(op_1370_three_two_singletons)时;当 $t = 3$ 且两族之并的大小严格小于 $2^{\lceil n/2 \rceil}$(op_1370_small_pair_bound)时;以及对于任意 $t \ge 3$,当所有其他族之并的 VC 维严格小于 $\lceil n/2 \rceil$(op_1370_low_vcdim_others_bound)时。所有证明均已在 Lean 4 中得到验证。
2. 预备知识
我们在 $n$ 元类型的子集构成的有限全集中展开讨论,这在 Lean 4 中建模为 Finset (Fin n)。此类子集的集合则是 Finset (Finset (Fin n)) 的元素。
我们首先回顾贯穿全文的形式化定义。
定义 1(is_uncomplemented)。设 $\alpha$ 为具有可判定相等性的有限类型。若集合族 $\mathcal{A} \in \operatorname{Finset}(\operatorname{Finset} \alpha)$ 中不存在某个集合与其补集同时属于 $\mathcal{A}$,则称其是无互补的: \[ \operatorname{is\_uncomplemented}(\mathcal{A}) \iff \forall A \in \mathcal{A},\, A^c \notin \mathcal{A}. \] 在 Lean 中,这被定义为: ``lean def is_uncomplemented {α : Type*} [Fintype α] [DecidableEq α] (𝒜 : Finset (Finset α)) : Prop := ∀ A ∈ 𝒜, Aᶜ ∉ 𝒜 `` 注:补集 $A^c$ 是相对于全集 $\alpha$ 而言的。$n$ 元集上的无互补族至多能包含 $2^{n-1}$ 个集合,因为对于每个互补对 $\{A, A^c\}$,它至多能包含其中的一个集合。
定义 2(strongly_incomparable)。设 $\iota$ 和 $\alpha$ 为类型。若带指标的族系统 $\mathcal{A} : \iota \to \operatorname{Finset}(\operatorname{Finset} \alpha)$ 满足一个族中的任意集合都不是另一个族中某个集合的子集,则称其是强不可比的: \[ \operatorname{strongly\_incomparable}(\mathcal{A}) \iff \forall i, j \in \iota,\, i \ne j \implies \forall A \in \mathcal{A}(i),\, \forall B \in \mathcal{A}(j),\, A \not\subseteq B. \] 在 Lean 中,这被定义为: ``lean def strongly_incomparable {ι α : Type*} (𝒜 : ι → Finset (Finset α)) : Prop := ∀ i j, i ≠ j → ∀ A ∈ 𝒜 i, ∀ B ∈ 𝒜 j, ¬(A ⊆ B) `` 注:该条件严格强于要求不同族中的集合互不相同。若 $A \in \mathcal{A}(i)$ 且 $B \in \mathcal{A}(j)$(其中 $i \ne j$),则 $A \subseteq B$ 与 $B \subseteq A$ 均不可能成立;特别地,只要 $i \ne j$,就有 $\mathcal{A}(i) \cap \mathcal{A}(j) = \emptyset$。
定义 3(打散与打散集(Shatterer))。对于集合族 $\mathcal{F} \subseteq 2^\alpha$,若对于每个子集 $S' \subseteq S$,均存在 $T \in \mathcal{F}$ 使得 $T \cap S = S'$,则称集合 $S \subseteq \alpha$ 被 $\mathcal{F}$ 所打散。由所有被 $\mathcal{F}$ 打散的集合构成的族记为 $\mathcal{F}.\operatorname{shatterer}$ 或 $\operatorname{shatterer}(\mathcal{F})$。 注:根据打散定理,每个有限族均满足 $|\mathcal{F}| \le |\operatorname{shatterer}(\mathcal{F})|$。
定义 4(VC 维(VC-dimension))。集合族 $\mathcal{F} \subseteq 2^\alpha$ 的 VC 维记作 $\operatorname{vcDim}(\mathcal{F})$,定义为被 $\mathcal{F}$ 打散的集合的最大基数: \[ \operatorname{vcDim}(\mathcal{F}) = \max \{ |S| : S \in \operatorname{shatterer}(\mathcal{F}) \}. \]
定义 5(私有元素条件)。设 $\mathcal{A} : \operatorname{Fin} t \to \operatorname{Finset}(\operatorname{Finset}(\operatorname{Fin} n))$ 为带指标的族系统。若没有任何其他族中的集合包含元素 $x \in \operatorname{Fin} n$,即: \[ \forall j \in \operatorname{Fin} t,\, j \ne i \implies \forall S \in \mathcal{A}(j),\, x \notin S, \] 则称元素 $x$ 对族 $i \in \operatorname{Fin} t$ 是私有的。在此条件下,属于 $\bigcup_{j \ne i} \mathcal{A}(j)$ 的所有集合均是去心基础集 $V = \{x\}^c$ 的子集。
3. 主要结果
主要结果在至少有一个基础集元素被隔离在至多一个族中的假设下,形式化解决了相关猜想(arXiv:2611.12199 的猜想 4.3)。
定理 1(op_1370_private_element_bound)。设 $n, t$ 为自然数,且 $t \ge 3$。设 $\mathcal{A}_0, \dots, \mathcal{A}_{t-1}$ 为 $n$ 元集子集的非空族,且两两强不可比。假设存在指标 $i \in \operatorname{Fin} t$ 和元素 $x \in \operatorname{Fin} n$ 满足: 1. $\mathcal{A}_i$ 是无互补的,且 2. 对于所有 $j \ne i$ 及每个 $S \in \mathcal{A}_j$,均有 $x \notin S$。 则所有 $t$ 个族的总集合数满足: \[ \sum_{j=0}^{t-1} |\mathcal{A}_j| \le 2^{n-1} - 1. \] 在 Lean 中,该定理陈述为: ``lean theorem op_1370_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 ` Lean 陈述与数学陈述直接对应:全集为 Fin n,族系统由满足 $3 \le t$ 的 Fin t 索引,各族被假设为 Nonempty 和 strongly_incomparable,指标 $i$ 的族是无互补的,元素 $x$ 不在任何其他族中出现,且在 Fin t 上的 Finset.card` 之和至多为 $2^{n-1} - 1$。
除定理 1 之外,另外三个定理在不同的结构假设下确立了猜想的上界 $2^{n-1} - 1$:
定理 2(op_1370_three_two_singletons)。对于 $n \ge 3$,若 $[n]$ 的子集的三个两两强不可比族 $\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2$ 满足 $\mathcal{A}_0 = \{A\}$ 与 $\mathcal{A}_1 = \{B\}$ 为单元素集,且 $\mathcal{A}_2$ 是无互补的,则: \[ |\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1. \]
定理 3(op_1370_small_pair_bound)。对于 $n \ge 3$,设 $\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2$ 为 $[n]$ 的子集的三个非空两两强不可比族。若 $\mathcal{A}_2$ 是无互补的,且前两族的总大小满足 $|\mathcal{A}_0| + |\mathcal{A}_1| < 2^{\lceil n/2 \rceil}$,则: \[ |\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1. \] 这里并不假设 $\mathcal{A}_0$ 或 $\mathcal{A}_1$ 是无互补的。
定理 4(op_1370_low_vcdim_others_bound)。对于 $n \ge 3$ 和 $t \ge 3$,设 $\mathcal{A}_0, \dots, \mathcal{A}_{t-1}$ 为 $[n]$ 的子集的非空两两强不可比族。若某一族 $\mathcal{A}_i$ 是无互补的,且并集 $\bigcup_{j \ne i} \mathcal{A}_j$ 的 VC 维严格小于 $\lceil n/2 \rceil$,则: \[ \sum_{j=0}^{t-1} |\mathcal{A}_j| \le 2^{n-1} - 1. \] 对任何 $j \ne i$ 的 $\mathcal{A}_j$ 均不需要无互补性假设。
theorem op_1370_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 14. 证明
主定理 op_1370_private_element_bound 的证明依赖于强不可比性、集合投影和打散容量之间的相互作用。
其基本策略如下。我们隔离出私有元素 $x \in \operatorname{Fin} n$,该元素至多属于一个族 $\mathcal{A}_i$ 的集合。令 $V = \{x\}^c$ 为基数为 $n-1$ 的去心全集。所有其他族 $\mathcal{A}_j$($j \ne i$)的并集 $B$ 完全由 $V$ 的子集组成。我们将指定的族 $\mathcal{A}_i$ 划分为两个集合系统:不包含 $x$ 的集合构成的 $C$,以及包含 $x$ 并去除 $x$ 后的集合构成的 $D$。$C$ 和 $D$ 都是 $V$ 的子集族。$\mathcal{A}_i$ 与其他族之间的强不可比性确保了 $C$ 中的每个集合都与 $B$ 中的每个集合不可比,且 $D$ 中没有任何集合能够包含 $B$ 的某个集合。此外,$\mathcal{A}_i$ 的无互补性确保了 $C$ 和 $D$ 在 $V$ 中是反互补的:对于任意 $c \in C$,其相对补集 $V \setminus c$ 不可能属于 $D$。在这些结构条件下,容量引理(op_1370_shattered_capacity)保证了 $|C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|} = 2^{n-1}$。最后,因为 $t \ge 3$,指标集 $I = (\operatorname{Fin} t) \setminus \{i\}$ 的大小至少为 2,所以 $B$ 至少是两个非空强不可比族的并集。严格打散引理(op_1370_incomparable_strict_shattering)证明了 $|B| < |\operatorname{shatterer}(B)|$。将这些界相加即可得到严格不等式 $\sum_j |\mathcal{A}_j| < 2^{n-1}$,从而证明了该定理。
我们现在陈述库中建立的辅助引理并详细说明它们的作用。
引理 1(op_1370_incomparable_strict_shattering)。设 $F$ 和 $G$ 为非空有限集合族,使得 $F$ 的每个成员均与 $G$ 的每个成员不可比: \[ \forall A \in F,\, \forall B \in G,\, A \not\subseteq B \text{ and } B \not\subseteq A. \] 则它们的并集打散的集合严格多于其基数: \[ |F \cup G| < |\operatorname{shatterer}(F \cup G)|. \] 证明:Lean 证明遵循对打散不等式 $|H| \le |\operatorname{shatterer}(H)|$ 的标准归纳证明,一次在单个基础元素 $a$ 上进行划分。将 $H$ 中不含 $a$ 的成员记为 $H_0$,含 $a$ 并去除 $a$ 的成员记为 $H_1$。则 $|\operatorname{shatterer}(H_0 \cup H_1)| + |\operatorname{shatterer}(H_0) \cap \operatorname{shatterer}(H_1)| \le |\operatorname{shatterer}(H)|$,其中第二项对集合 $S \cup \{a\}$ 进行计数。两个截面均继承了来自 $F$ 和 $G$ 的交叉不可比性。若在一个截面中来自 $F$ 和来自 $G$ 的部分均非空,则归纳假设给出该截面的严格不等式,而对另一截面使用打散不等式即可完成证明。否则,所有的 $F$ 均落在 $a$ 的一侧,所有的 $G$ 均落在另一侧,不妨设 $F \subseteq H_0$ 且 $G$ 给出 $H_1$。交叉不可比性使得 $H_0$ 与 $H_1$ 不相交(若集合 $A$ 同时属于两者,则会在两族之间产生 $A \subseteq A \cup \{a\}$),因此 $|H| = |H_0 \cup H_1| \le |\operatorname{shatterer}(H_0 \cup H_1)|$,而空集属于 $\operatorname{shatterer}(H_0) \cap \operatorname{shatterer}(H_1)$;所列不等式随即给出 $|H| < |\operatorname{shatterer}(H)|$。
引理 2(op_1370_shattered_capacity)。设 $V$ 为有限集。设 $B, C, D \subseteq 2^V$ 为 $V$ 的子集族,满足: 1. $C$ 的每个成员均与 $B$ 的每个成员不可比:$\forall c \in C,\, \forall b \in B,\, c \not\subseteq b \text{ and } b \not\subseteq c$。 2. $D$ 中没有成员包含 $B$ 的成员:$\forall d \in D,\, \forall b \in B,\, b \not\subseteq d$。 3. 对于每个 $c \in C$,相对补集 $V \setminus c$ 不在 $D$ 中:$\forall c \in C,\, V \setminus c \notin D$。 则: \[ |C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|}. \] 证明:在 $V$ 的幂集内部,令 $H$ 为包含 $B$ 的某个成员的集合构成的族,$Q$ 为与 $B$ 的每个成员均不可比的集合构成的族;记 $\bar X = \{V \setminus S : S \in X\}$。则 $C \subseteq Q$,从而 $\bar C \subseteq \bar Q$。由条件 2 可知 $D$ 与 $H$ 不相交,由条件 3 可知 $D$ 与 $\bar C$ 不相交,因此 $|D| + |H \cup \bar C| \le 2^{|V|}$。对于 $B$ 的打散集 $T$,某个 $b_0 \in B$ 与 $T$ 的交集为空集,因此 $V \setminus T \supseteq b_0$ 属于 $H$;且 $T$ 包含在某个 $b_1 \in B$ 内部,因此 $T \notin Q$ 且 $V \setminus T \notin \bar Q$。因此求补映射将 $\operatorname{shatterer}(B)$ 单射映射到 $H \setminus \bar Q \subseteq H \setminus \bar C$ 中,且 $|C| + |\operatorname{shatterer}(B)| \le |\bar C| + |H \setminus \bar C| = |H \cup \bar C|$,由此得出该界。
我们现在组合出 op_1370_private_element_bound 的证明。 令 $V = \{x\}^c \subseteq \operatorname{Fin} n$,故 $|V| = n - 1$。令 $I = (\operatorname{Finset.univ}) \setminus \{i\}$。定义: - $B = \bigcup_{j \in I} \mathcal{A}_j$, - $C = \{ S \in \mathcal{A}_i \mid x \notin S \}$, - $D = \{ S \setminus \{x\} \mid S \in \mathcal{A}_i,\, x \in S \}$。
我们验证引理 2 的假设:
- 基础集包含关系:根据假设 $hx$,对于所有 $j \ne i$ 和 $S \in \mathcal{A}_j$,均有 $x \notin S$,因此 $S \subseteq V$;从而每个 $S \in B$ 均满足 $S \subseteq V$。根据 $C$ 的定义,$x \notin S$,因此 $S \subseteq V$。对于任意 $d \in D$,$d = S \setminus \{x\}$,故 $x \notin d$ 且 $d \subseteq V$。
- $C$ 与 $B$ 的不可比性:设 $c \in C$ 且 $b \in B$。则 $c \in \mathcal{A}_i$,且对于某个 $j \in I$(故 $j \ne i$)有 $b \in \mathcal{A}_j$。由强不可比性
hinc,可得 $c \not\subseteq b$ 且 $b \not\subseteq c$。 - $B$ 与 $D$ 之间的包含条件:反设对某个 $b \in B$ 和 $d \in D$ 有 $b \subseteq d$。则对某个 $j \ne i$ 有 $b \in \mathcal{A}_j$,且对某个满足 $x \in s$ 的 $s \in \mathcal{A}_i$ 有 $d = s \setminus \{x\}$。因为 $s \setminus \{x\} \subseteq s$,所以有 $b \subseteq s$,这与 $\mathcal{A}_j$ 和 $\mathcal{A}_i$ 之间的强不可比性矛盾。因此 $D$ 中没有成员包含 $B$ 的成员。
- $C$ 与 $D$ 的反互补性:假设对某个 $c \in C$ 有 $V \setminus c \in D$。则存在满足 $x \in s$ 的 $s \in \mathcal{A}_i$ 使得 $V \setminus c = s \setminus \{x\}$。由于 $x \notin c$ 且 $x \in s$,两边与 $\{x\}$ 求并即得在 $\operatorname{Fin} n$ 中有 $s = c^c$。但这样一来 $c \in \mathcal{A}_i$ 且 $c^c \in \mathcal{A}_i$,与假设
is_uncomplemented (𝒜 i)矛盾。因此 $V \setminus c \notin D$。
现在我们计算基数。映射 $s \mapsto s \setminus \{x\}$ 在 $\{ s \in \mathcal{A}_i \mid x \in s \}$ 上是单射,因为 $s = (s \setminus \{x\}) \cup \{x\}$。因此 $|D| = |\{ s \in \mathcal{A}_i \mid x \in s \}|$。由于 $C = \{ s \in \mathcal{A}_i \mid x \notin s \}$,我们有: \[ |C| + |D| = |\mathcal{A}_i|. \] 此外,由于 $\mathcal{A}$ 是强不可比的,对于任意满足 $j, k \in I$ 的 $j \ne k$,族 $\mathcal{A}_j$ 与 $\mathcal{A}_k$ 均不相交(若 $A \in \mathcal{A}_j \cap \mathcal{A}_k$,则 $A \subseteq A$,与强不可比性矛盾)。因此: \[ |B| = \sum_{j \in I} |\mathcal{A}_j|, \] 从而 $\sum_{j \in \operatorname{Fin} t} |\mathcal{A}_j| = |\mathcal{A}_i| + |B| = |C| + |D| + |B|$。
接下来,因为 $t \ge 3$,$I$ 的基数为 $t - 1 \ge 2$。因此我们可以选取元素 $j \in I$ 并设 $J = I \setminus \{j\} \ne \emptyset$。对 $B$ 进行分解,我们写作 $B = \mathcal{A}_j \cup B'$,其中 $B' = \bigcup_{k \in J} \mathcal{A}_k$。由于每个 $\mathcal{A}_k$ 均非空,故 $\mathcal{A}_j$ 和 $B'$ 均非空。对于任意 $A \in \mathcal{A}_j$ 和 $T \in B'$,对某个 $k \ne j$ 有 $T \in \mathcal{A}_k$,因此由强不可比性可知 $A \not\subseteq T$ 且 $T \not\subseteq A$。将引理 1(op_1370_incomparable_strict_shattering)应用于 $\mathcal{A}_j$ 和 $B'$ 可得: \[ |B| < |\operatorname{shatterer}(B)|. \] 最后,应用引理 2(op_1370_shattered_capacity),我们得到: \[ |C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|} = 2^{n-1}. \] 将此式与 $|B| \le |\operatorname{shatterer}(B)| - 1$ 结合: \[ \sum_{j \in \operatorname{Fin} t} |\mathcal{A}_j| = |C| + |D| + |B| \le |C| + |D| + |\operatorname{shatterer}(B)| - 1 \le 2^{n-1} - 1. \] 这就完成了 op_1370_private_element_bound 的证明。
我们现在概述其余结果的证明:
op_1370_three_two_singletons 的证明: 此处 $t = 3$,$n \ge 3$,$\mathcal{A}_0 = \{A\}$,$\mathcal{A}_1 = \{B\}$,且 $\mathcal{A}_2$ 是无互补的。强不可比性蕴含 $A \not\subseteq B$、$B \not\subseteq A$,且每个 $S \in \mathcal{A}_2$ 均与 $A$ 和 $B$ 不可比。引理 op_1370_incomparable_two_sets_card_bound 指出,若 $A$ 与 $B$ 不可比,且无互补族 $F$ 的所有元素均与 $A$ 和 $B$ 不可比,则 $2|F| + 6 \le 2^n = 2 \cdot 2^{n-1}$。重写该不等式给出 $|F| \le 2^{n-1} - 3$。大小之和为 $|\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| = 1 + 1 + |\mathcal{A}_2| \le 2 + (2^{n-1} - 3) = 2^{n-1} - 1$。
op_1370_small_pair_bound 的证明: 令 $H = \mathcal{A}_0 \cup \mathcal{A}_1$。由于 $\mathcal{A}_0$ 与 $\mathcal{A}_1$ 不相交,因此 $|H| = |\mathcal{A}_0| + |\mathcal{A}_1| < 2^{\lceil n/2 \rceil}$。根据引理 op_1370_small_family_shatterer_uncomplemented,任意集合数少于 $2^{\lceil n/2 \rceil}$ 的族都具有无互补的打散集,因此 $\operatorname{shatterer}(H)$ 是无互补的。由引理 1 可知 $|H| < |\operatorname{shatterer}(H)|$。此外,$\operatorname{shatterer}(H)$ 中的集合及其补集均不可能属于 $\mathcal{A}_2$,因为任何被打散的集合都在 $H$ 中拥有一个超集和一个子集,这会破坏与 $\mathcal{A}_2$ 的不可比性。因此,$\operatorname{shatterer}(H)$ 与 $\mathcal{A}_2$ 不相交,且它们的并集 $\operatorname{shatterer}(H) \cup \mathcal{A}_2$ 是无互补的。因为 $n$ 个元素上的任意无互补族的大小至多为 $2^{n-1}$,所以我们得到: \[ |\operatorname{shatterer}(H)| + |\mathcal{A}_2| \le 2^{n-1}. \] 由于 $|H| < |\operatorname{shatterer}(H)|$,我们得出结论 $|\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1$。
op_1370_low_vcdim_others_bound 的证明: 令 $B = \bigcup_{j \ne i} \mathcal{A}_j$。若集合 $S$ 及其补集均被 $B$ 打散,则它们之中必有一个至少具有 $\lceil n/2 \rceil$ 个元素,这超过了 $B$ 的 VC 维。因此 $\operatorname{shatterer}(B)$ 是无互补的。引理 op_1370_uncomplemented_shatterer_others_bound 指出,只要指定的族和其余各族之并的打散集均是无互补的,界 $2^{n-1}-1$ 便成立;其证明就是上文给出的针对 op_1370_small_pair_bound 的论证,只需将 $H$ 替换为 $B$。该引理可直接应用。
5. 讨论
此处展示的结果在结构性假设下闭合了 arXiv:2611.12199 的命题 4.2 中的下界 $2^{n-1} - 1$ 与上界 $2^{n-1}$ 之间为一的差距;猜想 4.3 本身仍未解决。
具体而言,op_1370_private_element_bound 表明,只要某个元素 $x$ 仅出现在单个无互补族 $\mathcal{A}_i$ 的集合中,猜想的界 $\sum_{j} |\mathcal{A}_j| \le 2^{n-1} - 1$ 便成立。在此条件下,除 $\mathcal{A}_i$ 之外的族均不需要是无互补的;仅凭强不可比性就足以迫使其余各族的并在打散下严格扩张,从而限制了它们的总体容量。类似地,op_1370_small_pair_bound 和 op_1370_low_vcdim_others_bound 确认了只要其余各族在大小或 VC 维上是稀疏的,猜想便成立,同样不需要指定族之外具有无互补性。
然而,对于完全一般的构型,这些结果并未彻底解决猜想 4.3。特别是,它们对如下构型仍然悬而未决:每个基础元素都出现在至少两个族中,每个族的基数至少为 $2^{\lceil n/2 \rceil}$,且其余各族的 VC 维至少为 $\lceil n/2 \rceil$。op_1370_pair_shatter_surplus_counterexample 凸显了此类构型可以是非平凡的:它给出了 $n = 6$ 上三个基数均为 9 的无互补两两强不可比族,使得每个元素都出现在至少两个族中,且不在至少两个族中出现。因此,私有元素假设可能对所有族同时失效,且所有族都很大。在该示例中,对于这三个族中的任意一对,它们之并的打散集连同其补集的数量为 38。
由 arXiv:2611.12199 引申出的后续问题包括:
- 在没有私有元素的情况下,对 $\bigcup_{j \ne i} \mathcal{A}_j$ 的打散集相对于 $\mathcal{A}_i$ 的某种其他计数是否仍能给出界 $2^{n-1}-1$?
- 能否将
hilton_strong_incomparability_matrix背后的代数多项式方法与组合打散不等式相结合,从而在无元素隔离的一般情况下弥合这一大小为一的差距?
为什么是研究级成果
- Proves the conjectured upper bound for every n ≥ 3 in the three-family case when two families each consist of one set; the related paper leaves the bound open in this range
- Proves the conjectured bound for any number of families whenever one ground-set element occurs in at most one family, without requiring uncomplementedness of the others
- Proves the conjectured strict bound for all n when the first two of three families together have fewer than 2^ceil(n/2) sets, without requiring either of those two families to be uncomplemented
- Proves the strict bound for any number of nonempty incomparable families when all but one have union VC dimension below ceil(n/2), without requiring uncomplementedness of those other families
Lean 声明
- op_1370_private_element_boundLet at least three nonempty set families on an n-element ground set be mutually strongly incomparable. Suppose some element occurs in sets…
- op_1370_three_two_singletonsFor n at least three, if three mutually strongly incomparable families of subsets of an n-element set have their first two families…
- op_1370_small_pair_boundFor three nonempty strongly incomparable families on Fin n with n at least three, if the last family is uncomplemented and the first two…
- op_1370_low_vcdim_others_boundFor at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated…
- op_1370_uncomplemented_strongly_incomparable_upper_boundTheorem 1.7 of arXiv:2611.12199: for all natural numbers
nandt, if𝒜 : Fin t → Finset (Finset (Fin n))is a family such that each… - hilton_strong_incomparability_matrixFor every natural number n there are a field K, a matrix L over K with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a…
- op_1370_uncomplemented_strongly_incomparable_lower_boundLower bound in Proposition 4.2 of arXiv:2611.12199: for all integers
n ≥ 3and3 ≤ t ≤ n, there exists… - op_1370_case_n3_t3Base case
n = 3, t = 3of Conjecture 4.3 of arXiv:2611.12199 (OP-1370): if𝒜 : Fin 3 → Finset (Finset (Fin 3))is a family such that… - is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- strongly_incomparableAn indexed family of finset families
𝒜 : ι → Finset (Finset α)is strongly incomparable if for alli j : ιwithi ≠ j, for all… - op_1370_shattered_capacityFor set families B, C and D on a finite ground set V, assume each member of C is incomparable with every member of B, no member of D…
- op_1370_incomparable_strict_shatteringThe union of two nonempty mutually strongly incomparable finite set families shatters strictly more sets than it contains.
- op_1370_incomparable_two_sets_card_boundOn an n-element ground set with n at least three, let A and B be incomparable subsets, and let F be an uncomplemented family every member…
- op_1370_small_family_shatterer_uncomplementedIf a family of subsets of Fin n has fewer than 2^ceil(n/2) members, then its family of shattered sets contains no complementary pair.
- op_1370_uncomplemented_shatterer_others_boundFor at least three nonempty mutually strongly incomparable families on Fin n, with n at least three, suppose a designated family is…
- op_1370_pair_shatter_surplus_counterexampleThere are three families indexed by Fin 3 of subsets of Fin 6, each with nine sets, which are nonempty, uncomplemented, and mutually…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2611.12199 — Hilton's Conjecture on Uncomplemented Incomparable Families
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。