My first attempt was completely incorrect. Here is an outline of the proof, missing all of the details, and changing some notations.
Demonstrate, given any scattered set $C$, how to effectively pick an element $\varphi (C) \in C$.
Start with a scattered set $C$.
Letting $p_0 = \varphi ( C )$, ...
Thank you! I have one question regarding "Since C consists of isolated points": the set $\{ 1/n \mid n \in \mathbb N_{>0}\} \cup \{0\}$ does not contain any dense-in-itself subsets but $0$ is not an isolated point. That's what I thought. But what am I missing?
My French is "terrible" as well but I will read the rest of the paper and definitely get back to you here with a comment about whether it is actually what he did.
No hurry, I have to be afk for some hours. I am looking forward to reading your edit later. And thanks a lot for your help, as always. I like your answers.
@Matt: Thank-you very much for pointing out a grave error in my thinking. The proof is a little dense, but I think the above gives an outline of the major points.
@DaveL.Renfro: Thank-you for your comments (a correction has already been made above). It almost seems as though these topologists/set-theorists anticipated our modern notion of effectiveness, though perhaps lacked the necessary machinery to make their notion precise. The starting point Sierpiński gives (with an "effective" enumeration of the rational open balls) is so close to how effective descriptive set theory begins that one begins to wonder.
@DaveL.Renfro (your penultimate comment): In this case the answer to my question is: yes, it can be done without transfinite induction but the purpose of the paper is to show it without. Which leaves me with a new question: why did they want to make proofs without transfinite induction at the time? It seems to me that it adds nothing in this case. Once one picks one particular enumeration of the rational balls then the enumeration of any scattered set resulting from transfinite induction is uniquely determined.
@ArthurFischer I still don't know the answer to my question: does the effective enumeration not immediately follow from transfinite induction and the enumeration of the rational balls? Or in other words: is the lengthy proof in this paper needed or can one short cut using transfinite induction?
@Matt: While all countable ordinals are countable (duh) there is no reason to expect that they are all effectively enumerable. (To make an analogy with more modern notions, the countable ordinals above $\omega_1^{\text{CK}}$ (the Church-Kleene ordinal) have no recursive representation as a well-ordering on $\omega$, and so is you want to show that there is a recursive enumeration of a set, you cannot go beyond this point.) [cont...]
[...inued] Unless you could somehow guarantee that a transfinite inductive proof would end at an ordinal that was effectively enumerable, such a proof would not establish an effective enumeration of the set in question. The inductive method I original envisioned would be very close to the Cantor-Bendixson derivative, but you can construct subsets of $\mathbb{R}^n$ with arbitrarily large (but always countable) Cantor-Bendixson rank.
@MattN. Too early. I'm going to delete that worthless comment. Need coffeeee!
@DaveL.Renfro (your penultimate comment): In this case the answer to my question would be: yes, it can be proved using transfinite induction but the purpose of the paper is to show it without. Which leaves me with a new question: Why did they want to make proofs without transfinite induction at the time? It seems to me that once one picks one particular enumeration of the rational balls then the enumeration of any scattered set resulting from transfinite induction is uniquely determined and hence effective.
@ArthurFischer I think your two last comments provide an answer to the OP. I need to think about it some more to properly understand them.
The longer I think about it the less it makes sense: If $C$ is a subset of $\mathbb R$ of cardinality $> \aleph_0$ how could one possibly enumerate it? If an enumeration is an injective map into $\mathbb N$ then $|\mathbb N| = \aleph_0 < |C|$. And certainly in this paper we enumerate using $\mathbb N$ not the ordinals since $\varphi$ is defined using rational base elements.
@Matt: Again, this proof is not just to show that the set is countable (this had previously been shown using transfinite numbers). The proof is meant to in addition construct a bijection between the natural numbers and the set. This could additionally be seen in the light of the various philosophical stances of the time, where constructivists held that to show that an object exists was to actually construct the object in question, and not just show that non-existence would lead to a contradiction.
Hi. (This is really my first time using chat here, so it'll be a learning process for me.)
Now, I think that we are just missing each other. I am trying to figure out where this uncountable set $C$ is coming from, or what importance you are giving it.
Yes, but in a previous paper Sierpinski showed (via transfinite induction) that such a $C$ must be countable. (This is referred to on the first page of the paper.)
1) We can give an effective enumeration of the rational basic balls. Let's call it $f$. In the paper he uses $f$ to construct $\varphi$ -- an effective choice function on a scattered set $C$. But $\varphi$ is even more than just a choice function: it seems to yield an (effective) enumeration of $C$: it assigns to every point of $C$ exactly one natural number.
(by transfinite induction)
Hence my question: he gives a proof without transfinite induction. Why is this desirable?
1) Yes, $\varphi$ is essentially a choice function for the subsets of $C$.
But as your $\{ 1/n : n \in \omega \} \cup \{ 0 \}$ example shows, the naive use of this would not yield an injection into $\omega$. (Where would $0$ go? It has to be handled at the very end.)
I think one of my last comments in the question page yields some hints as to why they were doing this.
Some mathematicians felt that existence proofs should actually construct the objects in question. If this became a dominant philosophy, then transfinite induction would not prove countability.
To stave of this possibility, they were interested in additionally showing which theorems would hold under different philosophies of mathematics.
I'm confused about $\{ 1/n : n \in \omega \} \cup \{ 0 \}$: The $\varphi$ he gives in the paper doesn't seem to be a choice function since there is no ball only containing zero.
But $\{ 1/n : n \in \omega \} \cup \{ 0 \}$ is scattered.
Recall that $\varphi (C)$ would be the unique element of $S_n \cap C$ where $S_n$ is the first sphere/ball containing only one point of $C$.
So $\varphi (C') = 0$ would imply that $C' \subseteq C$ only contains finitely many $1/n$.
This is essentially what I meant by "the naive use" would not work: we have to go through all the $1/n$ before enumerating $0$.
Moreover, we can construct complicated scattered sets which would require the naive inductive use of $\varphi$ to go beyond $\omega^\omega$ and $\omega^{\omega^\omega}$, etc.
They were related: I'm now starting to understand why transfinite induction is bad. Not fully yet, though.
But yes, I think I'm satisfied for now.
Thank you!
I will have to think about the $\{ 1/n : n \in \omega \} \cup \{ 0 \}$ example some more. I think it's the key to why transfinite induction does not yield and effective enumeration.
But we know how to enumerate it. It just requires a simple fix. The problem is that this is the simplest bad set, and really bad scattered sets won't lend themselves to simple fixes.
Discussion between Arthur Fischer and…
Discussion between Arthur Fischer and…