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