Re: Cantor's diagonal and describable sets

On Sep 22, 8:53 am, mike123456...@xxxxxxxxx wrote:
Could someone help me understand the flaw in the following logic?

A) Suppose you construct a set of all describable sets over the
integers and these consist of sentences of some finite length in some
language and call them {E}. This collection is countable.




How are going to contruct {E}? We can construct all the
sentences of some finite length. The trouble is, how do you
weed this down to sentences which describe sets? One problem
occurs with sentences like

run <algorithm> till it stops, then use the final value
to contruct a set.

This is only a description if <alogrithm> stops. But there is
no way in general to tell if a given alorithms ever stops.

So yes, given a list of describable numbers we can contruct
a number which is not on the list. But it is not a contradiction
to say that this new number is not describable, because the list
itself is not describable.

- William Hughes


.

Quantcast