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), Lemma 2, statement on printed p. 340, proof on pp. 340–341 (canonical PDF).

Statement. Let rr be a finite-rank function on MM satisfying (R1)–(R3), let II be an arbitrary set, and let Ai⊆MA_i\subseteq M be finite for every i∈Ii\in I. There are pairwise distinct representatives ai∈Aia_i\in A_i whose whole image is independent if and only if

r(⋃i∈FAi)≥∣F∣for every finite F⊆I.(1)r\left(\bigcup_{i\in F}A_i\right)\ge |F| \quad\text{for every finite }F\subseteq I. \tag{1}

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 AiA_i is inherited from the source's notation and is essential. Condition (1) applied to a singleton also ensures that AiA_i 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 FF, the independent set of distinct representatives {ai:i∈F}\{a_i:i\in F\} has rank ∣F∣|F| and is contained in ⋃i∈FAi\bigcup_{i\in F}A_i. Monotonicity of finite rank gives (1).

Conversely, assume (1). For each finite N⊆IN\subseteq I, the family (Ai)i∈N(A_i)_{i\in N} satisfies the finite theorem's hypothesis for every subfamily. That external theorem supplies an injective selection xN:N→Mx_N:N\to M with xN(i)∈Aix_N(i)\in A_i and independent image. Choose one such xNx_N for every finite NN; for N=∅N=\varnothing use the empty map.

Apply Lemma 1 to these local choices. It gives ai∈Aia_i\in A_i such that, for every finite F⊆IF\subseteq I, there is finite N⊇FN\supseteq F with ai=xN(i)a_i=x_N(i) for all i∈Fi\in F.

Since xNx_N is injective, its restriction to FF is injective. Since its image is independent, the image of that restriction is independent by heredity. Thus

r({ai:i∈F})=∣{ai:i∈F}∣=∣F∣.(2)r(\{a_i:i\in F\})=|\{a_i:i\in F\}|=|F|. \tag{2}

Taking FF to be any two distinct indices proves global injectivity. If TT is a finite subset of the global image, its preimage under the injective selection is a finite set FF, and (2) gives r(T)=∣T∣r(T)=|T|. This is precisely independence of the whole image. □\square

Source comparison. The source proves (2) by the equivalent rank sandwich on the two parts of xN(N)x_N(N). 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.