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 , for a natural number , which are the sets of zeros of a constant depth polynomial size unlimited fan-in boolean circuit ( circuit), or equivalently subsets of the set which can be defined by a first-order formula on a suitable structure whose universe is . We restrict our attention to bijections computable in both direction by an -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 computable bijection between them in either directions.
The talk will also include results about -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