A topological example from Church's undecidability paper

178 Views Asked by At

A. Church, in his classical paper An unsolvable problem in elementary number theory in American Journal of Mathematics Vol. 58 No. 2. (1936), pp. 345-363, (available here), wrote:

There is a class of problems of elementary number theory which can be stated in the form that it is required to find an effectively calculable function $f$ of $n$ positive integers, such that $f(x_1,x_2,\dots,x_n)=2$ is a necessary and sufficient condition for the truth of a certain proposition of elementary number theory involving $x_1,x_2,\dots,x_n$ as free variables.

As an example he gave:

[...] [A] problem of this class is, for instance, the problem of topology, to find a complete set of effectively calculable invariants of closed three-dimensional simplicial manifolds under homeomorphisms. This problem can be interpreted as a problem of elementary number theory in view of the fact that topological complexes are representable by matrices of incidence. In fact, as is well known, the property of a set of incidence matrices that it represent a closed three-dimensional manifold, and the property of two sets of incidence matrices that they represent homeomorphic complexes, can both be described in purely number-theoretic terms.

I'd like to understand the gist of this example, although it's not needed in the rest of the paper. What's a "topological complex"? Is that a simplicial complex? In which sense can it be represented as incidence matrices, assuming it's the same concept from graph theory?