Exercice 6, § 4

a) Soient A un ensemble, (X_i)_{1 ≤ i ≤ m}, (Y_j)_{m+1 ≤ j ≤ m+n} deux familles finies de parties de A. Soit h le plus petit entier tel que pour tout entier r ≤ m − h, et toute partie {i_1, . . . , i_{r+h}} de r + h éléments de {1, m}, il existe une partie {j_1, . . . , j_r} de r éléments de :m + 1, m + n: telle que la réunion des X_{i_α} (1 ≤ α ≤ r + h) rencontre chacun des Y_{j_β} (1 ≤ β ≤ r) (ce qui entraîne m ≤ n + h). Montrer qu’il existe une partie finie B de A ayant au plus n + h éléments, telle que tout X_i (1 ≤ i ≤ m) et tout Y_j (m + 1 ≤ j ≤ m + n) rencontre B. (Considérer sur l’intervalle {1, m + n} la relation d’ordre dont le graphe est la réunion de la diagonale et des couples (i, j) tels que 1 ≤ i ≤ m, m + 1 ≤ j ≤ m + n et X_i ∩ Y_j ≠ ∅, et appliquer à cet ensemble ordonné l’exerc. 5.) b) Soient E et F deux ensembles finis, x ↦ A(x) une application de E dans $\mathfrak{P}(F)$. Pour qu’il existe une injection f de E dans F telle que, pour tout x ∈ E, on ait f(x) ∈ A(x), il faut et il suffit que pour toute partie H de E, on ait Card( $\bigcup_{x \in H} A(x)$ ) ≥ Card(H) (méthode analogue à celle de a), avec h = 0). c) Les hypothèses étant celles de b), soit G une partie de F; pour qu’il y ait une injection f de E dans F telle que pour tout x ∈ E, on ait f(x) ∈ A(x) et en outre telle que f(E) ⊃ G, il faut et il suffit que la condition de b) soit vérifiée, et en outre que pour toute partie L de G, le cardinal de l’ensemble des x ∈ E tels que A(x) ∩ L ≠ ∅ soit ≥ Card(L). (Soit (a_i)_{1 ≤ i ≤ p} la suite des éléments distincts de G rangés dans un certain ordre, (b_j)_{p+1 ≤ j ≤ p+m} la suite des éléments distincts de F rangés dans un certain ordre, (c_k)_{p+m+1 ≤ k ≤ p+m+n} la suite des éléments distincts de E rangés dans un certain ordre. Considérer sur l’ensemble {1, p + m + n} la relation d’ordre dont le graphe est formé de la diagonale et des couples (i, j) tels que: ou bien 1 ≤ i ≤ p, p + 1 ≤ j ≤ p + m et a_i = b_j, ou bien 1 ≤ i ≤ p, p + m + 1 ≤ j ≤ p + m + n et a_i ∈ A(c_j), ou bien p + 1 ≤ i ≤ p + m, p + m + 1 ≤ j ≤ p + m + n et b_i ∈ A(c_j); appliquer ensuite l’exerc. 5.)