Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source. Rado (1949), Lemma 2, statement on printed p. 340, proof on pp. 340–341 (canonical PDF).
Statement. Let be a finite-rank function on satisfying (R1)–(R3), let be an arbitrary set, and let be finite for every . There are pairwise distinct representatives whose whole image is independent if and only if
Lemma 2 itself asserts the sufficiency of (1); the necessity is the remark printed directly after it ("Clearly, (7) is necessary", p. 340), where (7) is the paper's label for (1). Finiteness of is inherited from the source's notation and is essential. Condition (1) applied to a singleton also ensures that is nonempty. No rank evaluation on an infinite union is assumed.
External input. The exact finite independent-representative theorem is Rado (1942), Theorem 3, as invoked by the 1949 source.
Proof. Necessity follows because, for finite , the independent set of distinct representatives has rank and is contained in . Monotonicity of finite rank gives (1).
Conversely, assume (1). For each finite , the family satisfies the finite theorem's hypothesis for every subfamily. That external theorem supplies an injective selection with and independent image. Choose one such for every finite ; for use the empty map.
Apply Lemma 1 to these local choices. It gives such that, for every finite , there is finite with for all .
Since is injective, its restriction to is injective. Since its image is independent, the image of that restriction is independent by heredity. Thus
Taking to be any two distinct indices proves global injectivity. If is a finite subset of the global image, its preimage under the injective selection is a finite set , and (2) gives . This is precisely independence of the whole image.
Source comparison. The source proves (2) by the equivalent rank sandwich on the two parts of . Both subadditivity and hereditary independence are expanded in the linked finite-rank page. The local-to-global step, the distinctness requirement, and the finite-support definition of independence are all retained. This is a complete relative proof; the finite theorem from the separate 1942 paper remains external.