
```
 Cardinal Equivalence Theorem 

```

For each boolean formula, |quantifications| = |assignments|.


The set of valid quantifications has some cardinality, call that |Q(B)|.
The set of satisfying assignments has some cardinality, call that |P(B)|.
Those two numbers are equal, |Q(B)| = |P(B)|, range from 0 through 2^n.


Question one: 
Does anyone know the theorem by any other name? 


++ Variable order 


Changing the order of the variables of B changes the particulars 
of each set, but their cardinalities are still the same.  

If we knew more precisely what swapping two variables 
does to the previously valid set of quantifications, 
then perhaps some form of Zipper Theorem could Be.
However, my competency with quantifiers is less 
than necessary or sufficient to even compose 
any informally stated Zipper Theorem.


++ Question two: 


Linear Corollary: Monotone QBFs are linearly decidable. 


I only know this result as a followup to the Cardinal Equivalence.
Is there a well known name for the Linear Corollary as a theorem? 


thank you, daniel.  

pehoushek1 at gee mail dot com. 



 cardinal equivalence:  for each boolean formula, |quantifications| = |assignments|.
I think Daniel might be asking about the following proposition: 



> 
> Let $f:\{0,1\}^n\to\{0,1\}$ be any function (i. e., an "n-ary boolean function"). The number of true formulas $$ Q\\_1 x\\_1 \ldots Q\\_n x\\_n : f(x\\_1,\ldots,x\\_n) = 1,$$ where each $Q\\_i$ is a quantifier $\forall$ or $\exists$, is equal to the number of $(x\\_1,\ldots,x\\_n)$ for which $f(x\\_1,\ldots,x\\_n) = 1$. 
> 
> 
> 


The proof is very easy (by induction on $n$). It's an amusing proposition, no doubt, but I don't know of any applications. It might make an interesting advanced exercise in a discrete mathematics course, though. 


I've implicitly answered the question, but explicitly: 



> 
> Does anyone know the theorem by any other name? 
> 
> 
> 


I'm not aware of such. 



> 
> Have you or anyone you know ever heard of this equivalence? 
> 
> 
> 


I discovered it a few years ago, apparently about five years after you did. Nobody I tried to tell seemed interested by it, though. 



> 
> Do you prefer any other name, for casting into stone? (imo This theorem belongs in at least one major book...)
> 
> 
> 


I prefer no name, actually. I don't think it's important enough to have the status of "theorem" (which is why I've been calling it a "proposition"), but I'm willing to be convinced otherwise. 


