Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Rado (1949), the unnumbered observation at the start of printed p. 340 (canonical PDF).

Statement. The selection assertion becomes false if both its choice sets and its finite test and extension sets are instead allowed to be at most countable. This is a simultaneous relaxation of the hypotheses and change of the conclusion in Lemma 1.

Proof. Let II be an uncountable set and put Ai=N>0A_i=\mathbb N_{>0} for every i∈Ii\in I. For every at most countable N⊆IN\subseteq I, choose an injection xN:N⟶N>0x_N:N\longrightarrow\mathbb N_{>0}. Such an injection exists by countability; the simultaneous choices are made in the same choice setting as the paper. For the empty set use the empty function. Equivalently, enumerate each nonempty NN without repetitions and assign to an element its position in that enumeration. All the proposed countable-choice hypotheses hold.

If the modified conclusion held, there would be x∗:I→N>0x^*:I\to\mathbb N_{>0} such that for every at most countable F⊆IF\subseteq I some at most countable N⊇FN\supseteq F agreed with x∗x^* on FF. For two distinct i,j∈Ii,j\in I, take F={i,j}F=\{i,j\}. The corresponding xNx_N is injective, so x∗(i)≠x∗(j)x^*(i)\ne x^*(j). Thus x∗x^* would be an injection of an uncountable set into N>0\mathbb N_{>0}, a contradiction. □\square

The failure already appears on two-coordinate comparisons in the putative global conclusion. It does not contradict Lemma 1, whose sets AiA_i must be finite. This page proves the paper's displayed example; it is not a classification of all possible weaker compactness principles.