Can you prove equivalence without being able to calculate it?

Question

In mathematics we often seek to classify objects up to an equivalence relation, where two objects A and B are said to be equivalent if there exists a map $f:A\rightarrow B$ satisfying certain properties. Examples include trying to classify (some class of) n-manifolds up to homeomorphism, or finite groups up to isomorphism, or (some class of) varieties modulo birational equivalence.

What examples can you give where you can prove equivalence abstractly, but there is no known algorithm to find the map which induces the equivalence?

For example, could you give examples of manifolds you could prove to be homeomorphic (or homotopic, or simple homotopic, or whatever), but where you had no algorithmic way of finding the homeomorphism between them explicitly? I think such examples are philosophically interesting, because they highlight how much stronger weaker "proving something" might be than "calculating something", with each answer providing an example.
Inspired by this question.

Answer 1

If you assume the axiom of choice, then every vector space has a basis, all bases of a given vector space have the same cardinality, and two vector spaces are isomorphic iff they have bases of the same cardinality. Now if the cardinality of the ground field is infinite, but smaller than the cardinality of the basis, then the cardinality of the basis is the same as the cardinality of the vector space! Pithily, we've shown here that "two vector spaces of huge cardinality are isomorphic iff they have the same size".

So now we can just think of a vector space over $\mathbf{Q}$ of cardinality that of the reals, for which we know a basis, for example the vector space of formal finite sums sum_i q_i.[r_i], where r_i is real, [r_i] is a symbol, q_i is a rational (i.e. the formal vector space with basis the real numbers), and we can just think of a vector space over Q of cardinality that of the reals for which we can't find a basis without invoking the axiom of choice, for example the real numbers themselves (one needs AC to find a basis because if we have a basis we can construct a non-measurable set, and yet there are models of ZF where every subset of R is measurable). These two vector spaces are provably isomorphic in ZFC but you'll never "write down an isomorphism" because for any reasonable definition of "write down" this would turn into a proof that they were isomorphic in ZF, and such a proof can't exist.

Answer 2

The subject of computable model theory gives real substance to the phenomenon you describe, and in the context of countable structures at least, takes it to the next level. The question shouldn't be merely that two objects are isomorphic (or equivalent), but "there is no known" computable isomorphism, but rather: you should want there provably to be no computable isomorphism. This is precisely the topic of much of computable model theory. In computable model theory, one undertakes to do model theory, but with a view to the computability of the structures and theories that arise. In particular, in computable model theory one pays very much attention to the question of whether isomorphisms might be computable.

It turns out that there is a twisted knot of variations on the concept of isomorphism and categoricity when computability enters the picture. For example, we know what it means to say that two countable structures A and B are isomorphic. But what should it mean to say that they are computably isomorphic? Let us suppose that A and B have underlying set ω. Do you mean that there is a computable bijection of ω that is an isomorphism of A with B? What if A and B have computable presentations, and all of them happen to be isomorphic? Do you insist that the witnessing isomorphisms be computable? What if they have computable presentations, which are all isomorphic, but not all of those isomorphisms are computable? What if the isomorphism class of the computable presentations of A splits into subclasses determined by whether there is a computable isomorphism or not? A similar picture arises with categoricity. Classicially, a theory is countably categorical if all its countable models are isomorphic. In computable model theory, what should we mean by computable cateogoricity? Do we mean only that all computable models of the theory are isomorphic? Do you insist that all computable models of the theory be isomorphic by computable isomorphsism? etc. etc. etc.

The jumble is by now, of course, sorted out by the practitioners, and there is an established terminology to cover these diverse situations. For example, here you find that two computable structures A and B are of the same computable isomorphism type if there is computable isomorphism taking A to B. The dimension of a structure A is the number of computable isomorphism types of computable structures (classically) isomorphic to A. A computable structure A is computably categorical if every computable structure isomorphic to A is computably isomorphic to A, or equivalently, if the dimension of A is 1.

Some good examples:

• Dense linear orders. Any two computable endless dense linear orders (such as the rationals) are isomorphic by a computable isomorphism. Thus, the rational order is computably categorical.

• Atomless Boolean algebras. Any two computable atmoless Boolean algebras are computably isomorphic.

• Algebraically closed fields. This is a decidable theory and therefore has computable models (in any given characteristic). Ershov proved that an ACF is computably categorical iff it has finite transcendence degree over its prime subfield. Thus, for example, any two computable presentations of the algebraic numbers are computably isomorphic.

Some bad examples:

• It gets as bad as you could possibly want. Goncharov proved that for each n<=ω, there is a computable structure with dimension n. This means that the computable presentations split into n nonempty classes of structures, such that all the structures are classically isomorphic, but computable isomorphisms exist only within the classes and never between the classes. (See S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.)

• Goncharov and others have used this method to produce examples of groups, partially orders sets, unary and other algebras of any computable dimension n. See this survey paper.

• The Natural numbers (N,<) have a computable presentation in which the successor function is not computable. See Shore's article.

• More generally, the spectrum of a model is the collection of Turing degrees of the presentations of that model. Knight proved that every non-trivial structure A has isomorphic copies of any higher Turing degree. See this presentation.

This last fact provides universal examples of your phenomenon, because it shows that any nontrivial structure (group, graph, partial order, etc.) will have isomorphic copies for which there is no computable isomorphism, even with oracles for one of the structures.

Thus, I take Knight's and Goncharov's theorems as a sweeping answer to your question, at least in the case of countable structures. And to summarize more generally, the fact that there are myriad provably distinct isomorphism notions in the context of computability, I believe, is one way of looking at what your question is really about.

Answer 3

The following proof that there exist irrational numbers $a$ and $b$ such that $a^b$ is rational is, I think, in the spirit of your questions...

Either $(\sqrt 2)^{\sqrt 2}$ is rational, giving an example, or it is not, and in that case $((\sqrt 2)^{\sqrt 2})^{\sqrt 2}$ is an example.

Answer 4

Computability Theory has many examples of this. For example, the halting set $K$ is order-isomorphic to $\mathbb{N}$, but there is no computable order-preserving bijection between them.

Answer 5

The first example that comes to my mind is that the Banach spaces $\ell_\infty$ and $L_\infty [0, 1]$ are isomorphic (that is, there exists a linear homeomorphism of one onto the other), and yet it seems that one can't just write down an operator that provides the linear homeomorphism. The existence of such an operator between the two above-mentioned spaces was first established by Pelczynski.

A similar example is that if $K$ is an uncountable compact metric space, then the Banach space $C(K)$ of continuous scalar-valued functions on $K$ (equipped with the supremum norm) is isomorphic to $C[0,1]$, the space of continuous scalar-valued function on the compact interval $[0, 1]\subseteq \mathbb{R}$. Thus, for example, if $\Delta$ denotes the Cantor set, then $C(\Delta)$ and $C[0,1]$ are isomorphic as Banach spaces. The proof of this relies on a result called Miljutin's Lemma, who proved the existence of the isomorphism. Anyway, I think that this also qualifies as an example.

Answer 6

I think, Milnor's exotic spheres are an example (see his 1956 article). He uses Morse theory to deduce the homeomorphism between the exotic spheres. But the gradient flow used in Morse theory is not really explicit, but only a solution of some differential equation.

Similar in spirit are many diffeomorphism/homeomorphism proofs in algebraic topology. A standard tool is the h-cobordism theorem (by Smale and Freedman) which tells you that if for two manifolds X and Y of dimension greater than 3, there is a cobordism W such that $X \to W$ and $Y\to W$ are homotopy equivalences and $X$, $Y$ are simply connected, then $X$ and $Y$ are homeomorphic. If the dimension is greater than 4, even diffeomorphic. This homeomorphism/diffeomorphism is not really explicit either.

Answer 7

Group cohomology has it's original $H^* K(G,1) = H^* BG$ definition, but there is also the purely algebraic definition via the "bar construction", group cocycles, etc. But by-and-large, group cohomology is uncomputable (for, say, finitely presented groups). Cameron Gordon has an old result that says that $H^2$ of a finitely-presented group is not computable, in general.

In a sense this isn't really answering your question. The maps in these cases are explicit, it's impossible to compute the objects themselves, not the maps.

ref: Gordon, C. Some embedding theorems and undecidability questions for groups. Combinatorial and geometric group theory (Edinburgh, 1993), 105--110, London Math. Soc. Lecture Note Ser., 204, Cambridge Univ. Press, Cambridge, 1995.

Answer 8

Isn't this done all the time in basic set theory with the Schroeder-Bernstein Theorem, where we deduce equivalence (in this context, the existence of a bijection) without presenting one?

Answer 9

ZFC implies that the reals have a well ordering, but this well ordering is, in some sense, provably uncomputable.

Given some facts about isomorphisms between well-orderings with base sets of the same cardinality, could one not prove that a well ordering of the reals is equivalent to something in an extremely non-constructive way?

And given that you tagged this question "math-philosophy" I feel I should point out that intuitionists like Brouwer would have answered the original question with a resounding NO!

Answer 10

I give you this example, from the upper edge of the propositional calculus hierarchy:

cardinal equivalence: For each boolean formula, |quantifications| = |assignments|.

Abstractly, the linear induction on n variables is provable using all the basics: True, Nil, union, intersection, +, =, zero, and +1, upon the number of variables. Set cardinality is the principle primitive operation, used in every part of the proof. The key final lines look roughly like: |Qa union Qb| + |Qa intersets Qb| = |Qa| + |Qb|. and so then, |Q| = |Qa| + |Qb| = |Pa| + |Pb| = |P|.

The base case on zero variables has two parts, the True case, and the Nil case. The induction proceeds by substituting (True, Nil) for the first variable, obtaining two smaller formulas, called Pa, and Pb. The hypothesis |Q| = |P| applies to the two smaller formulas.

Okay, so. The equivalence is clearly a fundamental identity. However.

However, one to one mapping between satisfying assignments and valid quantifications is generally out of the question, as far as I know (else PSpace = NP would nearly follow). quantifications refer to subsets, subsets of subsets, ..., with arbitrary alternations admitting deeply rich subset structures, of the original set of satisfying assignments. So, quantifications are "encodable" by something the same size as an assignment, but the one to one map you are asking for is Unknown, in general. I suppose thats different from saying "it does not exist".

And it does exist for the special case, for monotone boolean formulas. The map between assignments and valid quantifications is straightforward, and is the most obvious linear map any amateur could attempt to construct between valid quantifications and satisfying assignments. I suggest that the 2cnf to 2qbf p to Q solution map could be more studied, for details on how to construct such, or else why such would fail in general. I have not gotten around to that yet.

In general, counting assignments is in a class by itself, called #P. An amateur may presume a class called #Q, too; a professional would give details.

+++

By the way, I am still asking: is this identity known by any other name? I tried calling it #P=#Q, twelve years ago, few knew what #P was, and #Q was too deep to describe in emails, way back then.