A computational perspective on set theory

http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/

by jlhamilton • 16 years ago

37 10 16 years ago

terrytao.wordpress.com

ihodes3• 16 years ago

What a fascinating article - rarely do you run across such well written math material! I've got to disagree on the intuitiveness of Cantor's diagonal theory, though; that was one of the most beautiful and intuitive proofs in set theory for me: make a list (denumerable) of decimally expanded reals; change the digit on the diagonal of each; you've now created a number not on the list: QED. Bam.

ihodes3• 16 years ago

Really curious about the downvote—did I do something gouche?

nsrivast• 16 years ago

Is there a way to view vote history, or are people actually watching the number of votes their comments get?

Confusion• 16 years ago

Any random nitwit could have downvoted you; I don't think you should comment on that, unless you get multiple downvotes over at least 5 hours of time.

bitdiddle• 16 years ago

I think it's gauche? I upvoted you though for trying to use a nice french word :)

eds• 16 years ago

Agreed about the diagonalization method, but that's not what he said was unintuitive. He said the statement was unintuitive.

cousin_it• 16 years ago

Too bad the article didn't go all the way into computation-land, so I can't readily believe the "finitariness" of the insights contained there. For example, is the function E() actually implementable in Haskell? If it isn't, the whole premise kind of collapses... One way to make sense of this question would be to skip the red herring of constructibility and define reals as lazy streams of bits, then try to write actual code and stuff. (But how in the flying hell do you implement a rationality predicate on reals-as-streams?) There are probably other, non-equivalent ways. This stuff isn't trivial at all.

For a more enlightening perspective on such topics, see the blog "Mathematics and Computation", especially those articles:

http://math.andrej.com/2007/09/28/seemingly-impossible-funct...

http://math.andrej.com/2008/02/06/representations-of-uncompu...

A computational perspective on set theory

Related Stories