On 23 Jun., 14:57, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote: > Tim Little <t...@little-possums.net> writes: > > In fact it would be a lot easier if instead of reals, we talked about > > sets of natural numbers, and instead of computable reals, we talked > > about recursively enumerable sets of natural numbers. > > It would be even more easy if instead of the uncountability of the reals > we talked about the standard proof of Cantor's theorem: > > Let f be a function taking elements of a set A to subsets of A. There > is then a subset of A not in the range of f. For consider the set > > D = {x in A | x not in f(x)}. > > There is no a in A such that f(a) = D: if there were, we'd have a in > f(a) iff a not in f(a), a contradiction.
That could be a good proof, if we knew that all subsets of an infinite set A would exist. But already Fraenkel wrote in the third edition of his famous book (1928, p. 279f) with respect to the axiom of power set, that: der Begriff "Teilmenge? eine andere, wesentlich engere Bedeutung hat als in der CANTORschen Mengenlehre. In dieser konnten wir bei der Bildung der Potenzmenge Um eine beliebige Gesamtheit von Elementen aus m zu einer Teilmenge von m zusammenfassen und waren dann sicher, daß diese sich unter den Elementen von Um findet. Jetzt ist uns eine derartige, weitgehende Freiheit gewährende "Bildung? einer Teilmenge von m nicht gestattet, also auch ihr Auftreten unter den Elementen von Um keineswegs gesichert. (Contrary to the second edition of 1923, Fraenkel now knew Skolem's proof of the same year and had to explain how it could be circumvented.)
Therefore, there is not every subset of an infinite set. Why then should exist the subset of A that contains its pre-image if it does not contain it, and does not contain ist, if it contains it?
With no doubt this is a curious result of logic, but it has not the least to do with cardinalities of sets.
