First-order definable bijections and the notion of cardinality

Miklós Ajtai

The set theoretical definition that two sets have the same cardinality involves the existence of a bijection between them. In a more algorithmic setting it is more natural if, in the definition of cardinality, we restrict our attention to bijections which are given in some constructive way. We investigate this question in the case when the sets are subsets of $\{ 0,1\}^{{n}}$ , for a natural number $n$ , which are the sets of zeros of a constant depth polynomial size unlimited fan-in boolean circuit ( $AC_{{0}}$ circuit), or equivalently subsets of the set $\{ 1,...,n\}$ which can be defined by a first-order formula on a suitable structure whose universe is $\{ 1,...,n\}$ . We restrict our attention to bijections computable in both direction by an $AC_{{0}}$ -circuit, or equivalently bijections where, in both directions, each bit of the image can be defined by a first-order formula on a suitable structure.

We show that the notion of cardinality in this constructive world is essentially different from the set theoretical one, namely there are sets with identical cardinalities in the set theoretical sense so that there is no $AC_{{0}}$ computable bijection between them in either directions. The talk will also include results about $AC_{{0}}$ -definability which are needed for the proof. IBM Almaden Research Center
650 Harry Road
San Jose, CA 95120
USA e-mail: ajtai@almaden.ibm.com

back