FOM: submission
Rod Downey
Rod.Downey at MCS.VUW.AC.NZ
Fri Jul 30 16:38:38 EDT 1999
I would be happy to continue this discussion over a beer,
but fail to see the point in getting involved in a long
discusson. Yes
I do think that there is not enough introspection in mathematics,
and do agree that there is some differences between philosophically
driven and structurally driven
investigations. The references to the combinatorial argument
are given in the paper definability, computability and algebraic structures,
available from my web site.
Khisamiev proved that if
$X$ is a ce presented torsion free group then
it is computably presented. It is interesting that
I spoke with Chuck miller about this proof, and
when I described it to him
he understood why they could
not find it, since they were looking for a computable isomorphism, whereas
the isomorphism is only delta 2)
It is the paper called Hierarchies of Torsion free abelian groups)
The Higman argument is
in the Higman-Scott monograph. Sorry I had thought that we were
talking
about computability in
mathematics, not priority, although many of the arguments mentioned
use priority.
This was my mistake.
BTW it might be pointed out that that the ideas of most areas are not
used in others. Computablity theory is remarkable in the
prevalence of its ideas in other areas. And to
me very interesting that while some areas only use
PM rarely (such as combinatorial group theory)
there are others where it is dense. One of the problems is that
people know little of techniques from other areas.
By the way, when a combinatorialist uses a backtracking argument
as in e.g. the methodology for matching in a bipartite graph,
or in some competitive online algorithm,
or a computer scientist uses e.g. methods like the decidability
of S2S which, after Gurevich-Harrington certainly resembles
an infinite injury argument, are there 'priority?'
I suspect not but the ideas are very similar, as one would expect.
I remember when I taucht CS students at cornell spector forcing,
they immediately said ''oh that's easy, its just the proof that
you cannot solve consensus in a distributed environment' after Fischer-Lynch
Patterson.
Rod
More information about the FOM
mailing list