A question about a proof in one of Sierpiński's papers

Question

The following is a question about Sierpiński's paper "Une démonstration du théorème sur la structure des ensembles de points", (link):

We call a set dense-in-itself if it does not contain any isolated points. An isolated point $x$ is a point for which a neighbourhood exists that does not contain points of the set other than $x$.

Let $C$ be a subset of $\mathbb R$ such that it does not contain any dense-in-itself subsets. Using an enumeration of the countable basis consisting of the balls $B(q,\frac{1}{n})$ we can show (without using the axiom of choice) that there exists a function $\varphi$ that picks a point $p$ in $C$. We can define $\varphi$ by observing that there is at least one ball that only contains one point of $C$. Define $\varphi$ to return the first point in the enumeration of the basic calls such that the ball contains no other points of $C$.

$\varphi$ is a well-defined function on all subsets of $C$.

It seems to me that $\varphi$ therefore is a choice function for $C$ and furthermore that it yields a enumeration of $C$.

In the paper he sets $p_0 = \varphi (C)$ and then goes on to define families $\mathcal K$ of subsets of $C$ with the properties

(i) $\{p_0\} \in \mathcal K$

(ii) if $A_i$ in $\mathcal K$ then $\bigcup_i A_i \in \mathcal K$

(iii) if $E \subsetneq C$ is in $\mathcal K$ then $E \cup \varphi (C \setminus E)$ is also in $\mathcal K$.

He uses $\mathcal K$ to give a proof that $C$ with the above property is enumerable without using the axiom of choice and without using transfinite induction.

My question is: Does effective enumerability of $C$ not immediately follow from the fact that $\varphi$ is a choice function for $C$ (via transfinite induction)?

I suspect I might be using some form of choice in my thoughts without being aware of it. Thanks for your help.

Answer 1

My first attempt was completely incorrect. Here is an outline of the proof, missing all of the details, and changing some notations.

1. Demonstrate, given any scattered set $C$, how to effectively pick an element $\varphi (C) \in C$.
2. Start with a scattered set $C$.

3. Letting $p_0 = \varphi ( C )$, consider the smallest family $\mathcal{K}_0$ of subsets of $C$ satisfying the following:

   1. $p_0 \in E$ for all $E \in \mathcal{K}_0$;
   2. $\mathcal{K}_0$ is closed under arbitrary unions;
   3. Given any proper subset $E$ of $C$ in $\mathcal{K}_0$ the set $E \cup \{ \varphi ( C \setminus E ) \}$ belongs to $\mathcal{K}_0$.

4. Show that $\mathcal{K}_0$ has the additional property that for any $E , G \in \mathcal{K}_0$ either $E \subseteq G$ or $G \subseteq E$ holds.

5. Picking $p \neq p_0 \in C$ consider $E_p = \bigcup \{ E \in \mathcal{K}_0 : p \notin E \}$; note that $E_p \neq \emptyset$ and $E_p \in \mathcal{K}_0$.

6. Note that $\varphi ( C \setminus E_p ) = p$ for all $p \neq p_0$ in $C$.

7. Given distinct $p , p^{\prime} \in C \setminus \{ p_0 \}$ note that either $E_{p} \subseteq E_{p^{\prime}}$ or the reverse inclusion holds. It then follows that either $p^{\prime} \in C \setminus E_{p}$ or $p \in C \setminus E_{p^{\prime}}$ (but not both).
8. For each $p \in C \setminus \{ p_0 \}$ denote by $n ( p )$ the index of the first sphere $S_n$ for which $S_n \cap C \setminus E_p = \{ p \}$.
9. Show that for distinct $p , p^\prime \in C \setminus \{ p_0 \}$ we have $n(p) \neq n(p^\prime)$.
10. Enumerate $C \setminus \{ p_0 \}$ according to the values of $n(p)$. (Add $p_0$ as a first element.)

---

Addendum: The following would not have been possible without the comments made by Dave L. Renfro, below. (Of course, any errors or mis-statements contained below are solely my fault.)

In his Cardinal and Ordinal Numbers, Sierpiński says the following:

If we can establish a 1-1 correspondence (at least one) between the elements of two given sets $A$ and $B$, then we say that the sets are effectively equivalent, and write $A \mathrel{\text{ef}\mathord{\sim}} B$.

What is meant here is that effective equivalence is a stronger notion than equivalence, where one must only demonstrate that two sets are in 1-1 correspondence without exhibiting any particular correspondence. (I guess this can be read somewhat intuitionistically, but also seems to parallel modern notions.)

More contemporaneous with the paper in question, in Les exemples effectifs et l'axiome du choix [Fund.Math., Tom.2 (1921), 112-118, link] Sierpiński gives the following definition.

Lorsque nous avons défini un objet particular $p$ jouissant de propriétés donnés $P$, nous disons que nous avons un exemple effectif d'un objet jouissant de propriétés $P$.

[Google-Translate-aided translation: When we have defined a particular object $p$ enjoying the properties $P$, we say that we have an effective example of an object enjoying the properties $P$.]

So the effectiveness in the paper linked in the OP is only about exhibiting a particular 1-1 correspondence with the natural numbers.

Answer 2

I don't have access to Zermelo's paper at the moment, nor the ability to read French, but the argument you give here seems awfully similar to the one in Zermelo's 1908 paper in which he reproves the well-ordering theorem using $\Theta$-chains.

Despite by best effort I could not find when and where it was proved that $A$ can be well-ordered if and only if $\mathcal P(A)\setminus\{\varnothing\}$ has a choice function. I wouldn't be surprised if that was noted after Sierpinski wrote his paper, but I wouldn't be surprised if that was known before.

In either case, it is possible that Sierpinski is trying to show that $C$ is countable which is more than to say that it is well-orderable.

Answer 3

This is intended to supplement the answers already given by expanding on the comments I made yesterday.

Regarding my comment that results were often first proved using transfinite induction, see my 25 November 2005 sci.math post in the thread titled "Transfinite exhaustion" and my 1 September 2006 sci.math post in the thread titled "No irrationals".

Also, you may want to search my posts in sci.math that mention Sierpinski (some, but not all, of these posts can be found using this Google archive search and this Math Forum archive search). For example, in this 3 January 2005 sci.math post in the thread titled "outer measure of the Vitali non-measurable set", I mentioned the following:

An interestingly pathological related result that doesn't seem to be very well known, possibly because the paper in question doesn't appear in the three volume collection of Sierpinski's papers ("Oeuvres Choisies", 1974-1976), is proved in [1]. Sierpinski proves that there exists a pairwise disjoint collection of perfect sets in [0,1] x [0,1] such that if we choose a point from each set in this collection, then we will always wind up with a nonmeasurable set that has outer Lebesgue (planar) measure 1.

[1] Waclaw Sierpinski, "Sur un problème concernant les familles d'ensembles parfaits", Fundamenta Mathematicae 31 (1938), 1-3.

I'll now give some comments about Sierpinski's notion of effectiveness.

Sierpinski used the term effective in a way that is different from the way it is used today or from the way it was used by Borel. Today, the term effective is typically used to imply some form of recursive or computable construction – effective descriptive set theory, effective analog, effective method, effective theory, etc. Borel used the term effective in a somewhat similar way, although Borel's usage was for a less precise constructive metamathematical notion than its usage today.

There does not seem to be much in the literature about Sierpinski's usage of effective, aside from Sierpinski's own words. Moreover, I suspect Sierpinski's explanations have been rendered slightly less precise in the few English translations of his works. I must confess that I do not have a very clear idea of what Sierpinski meant by effective.

From afar, Sierpinski's meaning seems clear. An effective example is one that we can point to (or indicate) or one that we can construct, although not necessarily in a recursive way. However, difficulties seem to arise on closer inspection. Suppose I am able to prove the existence of an object by a method that (always) leads to a fixed outcome, without regard as to whether this was by non-constructive means, by non-recursive means, or by a use of the Axiom of Choice. Have I given an effective example in the sense of Sierpinski? (I think the answer is NO, but I am not really sure.) On the other hand, suppose I give a construction (whatever that means) of an object, but the proof I give that the construction leads to a unique object is itself non-constructive, such as would be the case if the proof of uniqueness was by obtaining a contradiction from the assumption of non-uniqueness. (I think the answer is YES, but I am not really sure.) Finally, suppose I want to prove that a set with property $P$ exists and I do this by proving (1) and (2) (that follow) about the collection $\mathcal C$ of sets that have property $P$: (1) I obtain a contradiction (by possibly non-constructive means) from the assertion that the collection $\mathcal C$ is empty. (2) I obtain a contradiction (by possibly non-constructive means) that the collection $\mathcal C$ contains more than one set. Have I given, in the sense of Sierpinski, an effective example of a set with property $P?$ I think the answer is NO. However, the following comments from p. 57 of Fraenkel/Bar-Hillel's 1958 book (also on p. 68 of the 1973 edition) suggest that the answer may be YES:

Not always need the example be given in a constructive way; its formulation may make use of a non-predicative procedure (pp. 174ff) or be based upon joining an existential proof which shows that there are objects satisfying the definition, to a demonstration that no more than one such object can exist. One might maintain that also in this way an effective example was given.

Note: The discussions about Sierpinski's and Luzin's notions of effectiveness (pp. 54-59) in the 1958 edition are written from a more classical point of view, a view that I believe better captures the spirit of the era in which Luzin and Sierpinski worked, than the corresponding discussion in the 1973 edition (pp. 67-73).

At this point, let's look at what is said in the 1965 English edition of Sierpinski's book Cardinal and Ordinal Numbers.

Chapter II.4: Effectively equivalent sets (pp. 29-30) This discusses what it means for two sets, which have the same cardinality, to be effectively equivalent (i.e. there exists an effective bijection between the sets). To me the discussion does not seem to answer the questions I raised above.

In the remaining two sections of Chapter II Sierpinski proves several theorems, and states several other theorems whose proofs are similar to those he does prove, that involve the behavior of cardinal equivalence and effective cardinal equivalence with unions, Cartesian products, exponentiations of sets, and the Cantor-Bendixson theorem. In all the cases that Sierpinski discusses, the standard proofs of these results are sufficiently "effective" that we can use the same proofs to prove the effective versions. As an example, I will prove the following result: $(A_1$ is effectively equivalent to $A_2)$ and $(B_1$ is effectively equivalent to $B_2)$ implies $({A_1}^{B_1}$ is effectively equivalent to ${A_2}^{B_2}).$ We begin by letting $f_{A}:{A_1} \rightarrow {A_2}$ and $f_{B}:{B_1} \rightarrow {B_2}$ be two effectively defined bijective functions, functions whose existence we are permitted to assume. Given $f \in {A_1}^{B_1},$ we define ${\Phi}(f) \in {A_2}^{B_2}$ by ${\Phi}(f) = {f_A} \circ f \circ {f_{B}}^{-1}.$ This defines a specific function ${\Phi}: {A_1}^{B_1} \rightarrow {A_2}^{B_2},$ a function that we can verify is a bijection, and hence we have shown that ${A_1}^{B_1}$ is effectively equivalent to ${A_2}^{B_2}.$ Note that the usual proof we used (how $\Phi$ is defined) is effective in the sense that any non-effectiveness that could arise in the definition of $\Phi$ can only arise from a non-effectiveness in obtaining the functions $f_A$ and $f_B.$

Chapter III.1: Denumerable and effectively denumerable sets (pp. 38-40) This is also worth looking at. Incidentally, there seems to be a typo in the sequence at the top of p. 39. I believe the sequence should begin as $a_2,$ $a_1,$ $a_4,$ $a_3,$ $a_6,$ $a_5,$ $\ldots$ . There is some discussion of how Borel's notion of effectively denumerable differs from Sierpinski's notion of effectively denumerable on pp. 39-40.

Chapter III.2 – III.5 (pp. 40-47) In these sections Sierpinski establishes the effective denumerability of several naturally occurring sets: the rational numbers (p. 40); any infinite set of non-overlapping (non-degenerate) intervals (pp. 41-42); the set of points of left [or of right; or of unilateral] discontinuity of a strictly increasing real-valued function (p. 43); the set of all finite sequences of rational numbers and the sets ${\mathbb Q}^2,$ ${\mathbb Q}^3,$ $\dots$ and the set of circles with rational radii and centers in ${\mathbb Q}^2$ (pp. 43-44); the set of all finite subsets of an effectively denumerable set (p. 45); the set of algebraic numbers (pp. 46-47).

Chapter III.6 (pp. 48) Here Sierpinski defines the notion effectively non-denumerable as:

$\dots$ we are able to relate to every infinite sequence of the elements of that set an element of the set different from any of the elements of the sequence in question.

Regarding the above definition, Sierpinski cites the following paper:

Petr Sergeevich Novikov, On effectively nondenumerable sets (Russian), Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 1939, 35-40. Zbl 24.30103; JFM 65.1169.04 [There is a French summary of Novikov's paper.]

In the paragraphs leading up to the definition of effectively nondenumerable, Sierpinski showed that the set of all infinite sequences of natural numbers has the property stated in the definition.

Chapter IV This deals with sets that have cardinality of the set of real numbers. Unlike the countable version on pp. 30-37 (described above), in this chapter the proofs of some of the theorems involving effectiveness require slightly more care than their non-effective versions.

Chapter VI (pp. 95-96 & 99) This gives some discussion of the Axiom of Choice (AC) and Sierpinski's notion of effectiveness. Incidentally, I think the topmost paragraph on p. 96 is roughly saying that we don't need AC to show $(\forall$ sets in the collection$)(\exists$ choice of an element in the set), but we do need (in general) AC to show $(\exists$ choice of an element in the set$)(\forall$ sets in the collection). That is, assuming AC vs. not assuming AC can be roughly understood as a quantifer reversal in the same way as with assuming uniform continuity vs. assuming continuity.

Sierpinski's 1965 book Cardinal and Ordinal Numbers also discusses various implications that hold between the statements $AC(*,n),$ where $n$ is a positive integer and $AC(*,n)$ (my notion) is the statement that the Axiom of Choice holds for an arbitrary collection of sets each having cardinality $n.$ See my 30 April 2007 sci.math post in the thread titled "I don't like the Axiom of Choice". Incidentally, the following comment (written by me), which appears at the beginning of that post, was about Gregory H. Moore's book Zermelo's Axiom of Choice: Its Origins, Development, and Influence, and thus I was happy to learn from this 1 March 2013 Math Stackexchange post that Moore's book is being reprinted by Dover. In my case, back in Fall 2008 I managed to obtain for about $100 (after an online search) a very good copy of the original 1982 hardcover edition of Moore's book.

Yes, that's the book. I'm shocked that a book like this, with such obvious wide-spread appeal throughout mathematics & logic & philosophy, has gone out of print, and even more surprised that it hasn't been picked up by Chelsea or Dover. There must be some reason those two publishers can't reprint it, because this book is a virtual slam-dunk compared to much of what they reprint.

Whyburn's review of a 1930 book by Sierpinski, a book that was a precursor to Sierpinski's Cardinal and Ordinal Numbers, is also worth reading:

Whyburn, Review of Sierpinski's Lecons sur la Nombres Transfinis, Bulletin of the American Mathematical Society 36 #3 (March 1930), 175-176.

In particular, Whyburn criticizes Sierpinski's views that can also be found on p. 53 (footnote 2) of Sierpinski's 1965 Cardinal and Ordinal Numbers, where Sierpinski says:

The truth of the proposition stating that we are able to indicate an element of the set $A$ depends on the time and on the person who makes it. Logic knows various propositions of this kind, e.g. the propositions: "I am 75 years old", "I am in Paris", "It is Friday to-day".

Incidentally, Sierpinski turned 75 on 14 March 1957 and the Foreword to the earliest edition of the book in which this remark appears is dated November 1957.

See also Zyoiti Suetuna's reviews of two papers by Motokiti Kondo in Journal of Symbolic Logic 17 (1952), pp. 63-64.

Also, the following paper may be of interest. I have a LaTeX file of a carefully prepared English translation of this paper (made with the assistance of someone who has experience with translations), but unfortunately I don't presently have the means to share it with anyone. [The situation described in the last paragraph of this post still holds, but I expect it to change for the better soon.]

Sierpinski, Un exemple effectif d'un ensemble dénombrable de nombres réels qui n'est pas effectivement énumérable [An effective example of a denumerable set of real numbers that is not effectively denumerable], Fundamenta Mathematica 21 (1934), 46-47.

Finally, Volume 1 of the 1966 English edition of Kuratowski's Topology includes a brief discussion of Sierpinski's notion of effectiveness, especially with regard to separable metric spaces and the Cantor-Bendixson theorem. See Section 23.VIII: The concept of effectiveness (p. 254).

Regarding what Kuratowski says, I think his notion of a well defined base of a topology means that we are permitted to assume, in determining whether a proof is effective, that a fixed base has been provided to us in advance. However, we do not assume any of the present-day notions of recursive presentation of the base, such as one finds in Moschovakis' 1980 book Descriptive Set Theory (Chapter 3B:Recursive presentations, pp. 128-135; also on pp. 96-101 of the 2009 2nd edition).