定義 次の命題を従属選択公理(axiom of dependent choice)という．

非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとき，Xのある点列 { x_n }_n∈ωが存在して任意の n に対して x_nRx_n+1 となる．

命題1 選択公理 ⇒ 従属選択公理

証明 X≠ ∅ とし，二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする．A_x := { y∈X | xRy } と置く．A_x≠ ∅ だから { A_x }_x∈X に選択公理を適用して選択関数 f: X→∪_x∈X A_x⊂X を得る．あとは x₀∈X を一つ取り x_n+1 := f(x_n) と定めればよい．

命題2 従属選択公理 ⇒ 可算選択公理

証明 { X_i }_i∈ω を互いに素な非空集合の族とする．X := ∪_i∈ω X_i として二項関係R := ∪_i∈ω (X_i×X_i+1)⊂X×X を考える．このRは明らかに従属選択公理の仮定を満たす．よってある { x_n }_i∈ω が存在して任意の n に対して x_nRx_n+1 が成り立つ． x₀∈X_m となる m を取ると明らかに x_n∈X_m+n である． 故にΠ_i=m^∞X_i≠∅となる． 従ってΠ_i=0^∞X_i = Π_i=0^m-1X_i×Π_{i = m}^∞X_i≠ ∅ が分かる．

これにより，可算選択公理がZFで証明できないことを認めれば，従属選択公理がZFで証明できないことが分かる．

命題3 従属選択公理
⇒ 従属選択公理と同じ仮定の下で，任意の x₀∈X に対してある点列 { x_n }_n∈ω が存在して，任意の非負整数 n に対して x_nRx_n+1 となる．

証明 ← は明らかなので ⇒ を示す．

非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとし，x₀∈X を任意の元とする． A := { <x₁, …, x_m> | m≧1, x₀Rx₁, …, x_m-1Rx_m } と置く．二項関係 S⊂A×A を

<x₁, …, x_s>S< y₁, …, y_t> ⇔ s<tかつx₁=y₁, …, x_s=y_s

で定義する．この S は従属選択公理の仮定を満たす．よってある { a_n }_n∈ω が存在して 任意の n に対して a_nSa_n+1 が成り立つ． a_n∈A だから a_n = < a_n,1, …, a_n,sn> と書ける． S の定義より 0<s₀<s₁<… だから n+1≦s_n である．よって x_n+1 := a_{n, n+1} と定義できて，このとき任意の n に対して x_nRx_n+1 である．

定義 順序数αに対して，次の命題をDC(α)で表す．

関係 R⊂P(X)×X が「|Y| < |α| となる任意の部分集合 Y⊂X に対してある x∈X が存在して R(Y, x)」を満たすとき，ある f: α→X が存在して任意のβ<αに対して R(f"β, f(β)) となる．

f"β := { f(γ) | γ<β } である．

命題4 従属選択公理 ⇔ DC(ω)

証明 (⇒)関係 R⊂P(X)×X が「|Y| < |ω| となる任意の部分集合 Y⊂X に対してある x∈X が存在して R(Y, x)」を満たすとする．P_fin(X) := { Y⊂X | |Y|<|ω| }, A := P_fin(X)×X と置く．二項関係 S⊂A×A を

<Y, y>S<Z, z> ⇔ Y∪{z}=Z かつ R(Y, z)

で定める．このSは従属選択公理の仮定を満たす．よってAの点列 { < Y_n, y_n> }_n∈ω で任意の n に対して <Y_n, y_n>S<Y_n+1, y_n+1> を満たすものが存在する．命題3により Y₀ = ∅ とできる． このとき f: ω→X を f(n) := y_n+1 で定める．Y_n = f"n である．

R(Y_n, y_n+1) だったから R(f"n, f(n)) となる．

(←) 非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする．A := X×ωと置く．関係 S⊂P(A)×A を B∈P(A), <x, n>∈A に対して次のように定める．

(i) B=∅のとき．

S(∅, <x, n>) ⇔ n=0.

(ii) B≠∅が有限集合で，ある<y, m>∈B に対してm=|B| となるとき．

S(B, <x, n>) ⇔ n=|B|+1 かつある <y, |B|>∈B が存在して yRx.

(iii) それ以外のとき．常に S(B, < x, n>)．

この S はDC(ω)の仮定を満たす．よってある写像 f: ω→A が存在して任意の n<ω に対して S(f"n, f(n)) である．Sの定義から f(n) = <x_n, |f"n|+1> と書ける．|f"n| = n である．

故に f"(n+1) = {f(0), …, f(n)} = {<x₀, 0>, …, <x_n, n>} である．従って S の定義から x_nRx_n+1 である．よって { x_n }_n∈ωを取ればよい．

この命題により，DC(α)は従属選択公理の一般化と考えることができる．

定理 選択公理 ⇔ 任意の順序数αに対してDC(α)が成り立つ．

証明 (⇒)明らか．

(←)整列可能定理を示す．X を任意の集合とする．X に含まれない元∞を一つ取り Z := X∪{∞} と置く． 関係 R⊂P(Z)×Z を

R(Y, x) ⇔ x ∉ Y かつ Y⊂X　(x∈Xのとき)
R(Y, ∞) ⇔ Y=Z または Y=X

で定義する．この R は「任意の部分集合 Y⊂Z に対してある x∈Z が存在して R(Y, x)」を満たす． αを ￢|α|≦|Z| なる順序数とする．(このような順序数は選択公理を使わずに取れる．) R にDC(α)を適用して写像 f: α→Z を得る．β, γ<αについて，f(β)=f(γ)≠∞ならばβ=γである．

β≠γと仮定する．β<γとしてよい．f の取り方から R(f"γ, f(γ)) である．f(γ)≠∞だから R の定義により f(γ) ∉ f"γ となる．f(β)∈f"γ だから f(β)≠f(γ) となり矛盾する．

￢|α|≦|Z| だったから，f は単射ではない．故に f(β)=∞ となるβ<αが存在する．そこでγ := min{ β<α | f(β)=∞ } と置く．このとき R(f"γ, ∞) だからf"γ=X または f"γ=Z となるが，γの最小性から f"γ=X が分かる．故に f_γ: γ→X が全単射になる．

選択公理に対してAMCがあるように，従属選択公理に対してDMCがある．

定義 次の命題をDMC(Axiom of Dependent Multiple Choice)という．

非空集合 X 上の二項関係 R⊂X×X が「任意のx∈Xに対してあるy∈Xが存在してxRy」を満たすとき， X のある有限部分集合列 { F_n }_n=0^∞ が存在して，任意の n∈N と x∈F_n に対してある y∈F_n+1 が存在して xRy となる．

定理 従属選択公理 ⇒ DMC

定理 次の命題は( ZF 上)同値．

1. DMC
2. { X_n }_n=0^∞ を互いに素な非空集合の族で， |X₀|=1 とする． X := ∪_n=0^∞X_n として，全射 f: X→X は「x∈X_n+1 に対して f(x)∈X_n」を満たすとする．このときある { F_n }_n=0^∞ が存在して F_n⊂X_n, 0 < |F_n| < ∞, f(F_n+1)=F_n となる．
3. y∈X とするとき，DMCにおいて F₀={ y } とできる．即ち非空集合 X 上の二項関係 R⊂X×X が「任意のx∈Xに対してあるy∈Xが存在してxRy」を満たすとき，任意の y∈X に対して X のある有限部分集合列 { F_n }_n=0^∞ が存在して， F₀={ y } かつ任意の n∈N と x∈F_n に対してある y∈F_n+1 が存在して xRy となる．

証明 (1 ⇒ 2)2の条件を満たす { X_n }_n=0^∞ と f を取る． X := ∪_n=0^∞X_n 上の二項関係 R を

xRy ⇔ x=f(y)

で定めるとこれは「任意の x∈X に対してある y∈X が存在して xRy」を満たす．故にある { G_n }_n=0^∞ が存在して G_n⊂X, 0 < |G_n| < ∞ かつ「任意の n∈N と x∈G_n に対してある y∈G_n+1 が存在して xRy 」となる． a∈G₀ を一つ取り， a∈X_m となる番号 m を取る．このとき x_m := a, x_m-1 := f(x_m), …, x₀ := f(x₁) として

F_n := { x_n }　(0≦n≦mのとき)
F_n := G_n-m∩X_n　(n > mのとき).

と定める．このとき F_n⊂X_n, 0 < |F_n| < ∞, f(F_n+1)=F_n である．

(2 ⇒ 3)非空集合 X 上の二項関係 R⊂X×X が「任意の x∈X に対してある y∈X が存在して xRy」を満たすとする． y∈X をとる． n≧0 に対して X_n := { <y, x₁, …, x_n> | yRx₁, …, x_n-1Rx_n } と置く． X := ∪_n=0^∞X_n として， f: X→X を

f(x) := y　(x=y のとき)
f(x) := <y, x₁, …, x_n>　(x=<y, x₁, …, x_n, x_n+1>∈X_n+1のとき).

で定義する．この f は仮定2の条件を満たす．よってある { G_n }_n=0^∞ が存在して G_n⊂X_n, 0 < |G_n| < ∞, f(G_n+1)=G_n となる． π_n: X_n→X を第 n+1 成分への射影として F_n := π_n(X_n) とすれば F₀={ y } で { F_n }_n=0^∞ はDMCの条件を満たす．

(3 ⇒ 1)明らか．