论文标题
在某些$σ^{b} _ {0} $ - 公式概括计数原理上的$ v^{0} $
On some $Σ^{B}_{0}$-formulae generalizing counting principles over $V^{0}$
论文作者
论文摘要
我们对各种计数原则进行形式化，并比较$ v^{0} $的优势。 In particular, we conjecture the following mutual independence between: (1) a uniform version of modular counting principles and the pigeonhole principle for injections, (2) a version of the oddtown theorem and modular counting principles of modulus $p$, where $p$ is any natural number which is not a power of $2$, (3) and a version of Fisher's inequality and modular counting principles. 然后，我们提供足够的条件来证明它们。我们给出了$ php $ -tree和$ k $ - 评估的概念的变化，以表明注射命中原则的任何证据证明了统一的计数原则为Axiom计划，因此不能具有$ O（n）$ - 评估。至于其余两个，我们利用了$ p $ -tree和$ k $ - 评估的众所周知的概念，并减少了某些多项式家庭的存在，目睹了违反相应的组合原理的行为，而违反了对模块化计数原则的违反。
We formalize various counting principles and compare their strengths over $V^{0}$. In particular, we conjecture the following mutual independence between: (1) a uniform version of modular counting principles and the pigeonhole principle for injections, (2) a version of the oddtown theorem and modular counting principles of modulus $p$, where $p$ is any natural number which is not a power of $2$, (3) and a version of Fisher's inequality and modular counting principles. Then, we give sufficient conditions to prove them. We give a variation of the notion of $PHP$-tree and $k$-evaluation to show that any Frege proof of the pigeonhole principle for injections admitting the uniform counting principle as an axiom scheme cannot have $o(n)$-evaluations. As for the remaining two, we utilize well-known notions of $p$-tree and $k$-evaluation and reduce the problems to the existence of certain families of polynomials witnessing violations of the corresponding combinatorial principles with low-degree Nullstellensatz proofs from the violation of the modular counting principle in concern.
