Theorem ac6s 10392

Description: Equivalent of Axiom of Choice. Using the Boundedness Axiom bnd2 9803, we derive this strong version of ac6 10388 that doesn't require 𝐵 to be a set. (Contributed by NM, 4-Feb-2004.)

Hypotheses

Ref	Expression
ac6s.1	⊢ 𝐴 ∈ V
ac6s.2	⊢ (𝑦 = (𝑓‘𝑥) → (𝜑 ↔ 𝜓))

Assertion

Ref	Expression
ac6s	⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝜑 → ∃𝑓(𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓))

Distinct variable groups:   𝑥,𝑓,𝐴   𝑥,𝑦,𝐵,𝑓   𝜑,𝑓   𝜓,𝑦

Allowed substitution hints:   𝜑(𝑥,𝑦)   𝜓(𝑥,𝑓)   𝐴(𝑦)

Proof of Theorem ac6s

Dummy variable 𝑧 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		ac6s.1	. . 3 ⊢ 𝐴 ∈ V
2	1	bnd2 9803	. 2 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝜑 → ∃𝑧(𝑧 ⊆ 𝐵 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝑧 𝜑))
3		vex 3442	. . . . 5 ⊢ 𝑧 ∈ V
4		ac6s.2	. . . . 5 ⊢ (𝑦 = (𝑓‘𝑥) → (𝜑 ↔ 𝜓))
5	1, 3, 4	ac6 10388	. . . 4 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝑧 𝜑 → ∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓))
6	5	anim2i 617	. . 3 ⊢ ((𝑧 ⊆ 𝐵 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝑧 𝜑) → (𝑧 ⊆ 𝐵 ∧ ∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓)))
7	6	eximi 1836	. 2 ⊢ (∃𝑧(𝑧 ⊆ 𝐵 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝑧 𝜑) → ∃𝑧(𝑧 ⊆ 𝐵 ∧ ∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓)))
8		fss 6676	. . . . . . 7 ⊢ ((𝑓:𝐴⟶𝑧 ∧ 𝑧 ⊆ 𝐵) → 𝑓:𝐴⟶𝐵)
9	8	expcom 413	. . . . . 6 ⊢ (𝑧 ⊆ 𝐵 → (𝑓:𝐴⟶𝑧 → 𝑓:𝐴⟶𝐵))
10	9	anim1d 611	. . . . 5 ⊢ (𝑧 ⊆ 𝐵 → ((𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓) → (𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓)))
11	10	eximdv 1918	. . . 4 ⊢ (𝑧 ⊆ 𝐵 → (∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓) → ∃𝑓(𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓)))
12	11	imp 406	. . 3 ⊢ ((𝑧 ⊆ 𝐵 ∧ ∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓)) → ∃𝑓(𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓))
13	12	exlimiv 1931	. 2 ⊢ (∃𝑧(𝑧 ⊆ 𝐵 ∧ ∃𝑓(𝑓:𝐴⟶𝑧 ∧ ∀𝑥 ∈ 𝐴 𝜓)) → ∃𝑓(𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓))
14	2, 7, 13	3syl 18	1 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝜑 → ∃𝑓(𝑓:𝐴⟶𝐵 ∧ ∀𝑥 ∈ 𝐴 𝜓))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395   = wceq 1541  ∃wex 1780   ∈ wcel 2113  ∀wral 3049  ∃wrex 3058  Vcvv 3438   ⊆ wss 3899  ⟶wf 6486  ‘cfv 6490

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2115  ax-9 2123  ax-10 2146  ax-11 2162  ax-12 2182  ax-ext 2706  ax-rep 5222  ax-sep 5239  ax-nul 5249  ax-pow 5308  ax-pr 5375  ax-un 7678  ax-reg 9495  ax-inf2 9548  ax-ac2 10371

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2068  df-mo 2537  df-eu 2567  df-clab 2713  df-cleq 2726  df-clel 2809  df-nfc 2883  df-ne 2931  df-ral 3050  df-rex 3059  df-rmo 3348  df-reu 3349  df-rab 3398  df-v 3440  df-sbc 3739  df-csb 3848  df-dif 3902  df-un 3904  df-in 3906  df-ss 3916  df-pss 3919  df-nul 4284  df-if 4478  df-pw 4554  df-sn 4579  df-pr 4581  df-op 4585  df-uni 4862  df-int 4901  df-iun 4946  df-iin 4947  df-br 5097  df-opab 5159  df-mpt 5178  df-tr 5204  df-id 5517  df-eprel 5522  df-po 5530  df-so 5531  df-fr 5575  df-se 5576  df-we 5577  df-xp 5628  df-rel 5629  df-cnv 5630  df-co 5631  df-dm 5632  df-rn 5633  df-res 5634  df-ima 5635  df-pred 6257  df-ord 6318  df-on 6319  df-lim 6320  df-suc 6321  df-iota 6446  df-fun 6492  df-fn 6493  df-f 6494  df-f1 6495  df-fo 6496  df-f1o 6497  df-fv 6498  df-isom 6499  df-riota 7313  df-ov 7359  df-om 7807  df-2nd 7932  df-frecs 8221  df-wrecs 8252  df-recs 8301  df-rdg 8339  df-en 8882  df-r1 9674  df-rank 9675  df-card 9849  df-ac 10024

This theorem is referenced by:  ac6n  10393  ac6s2  10394  ac6sg  10396  ac6sf  10397  nmounbseqiALT  30802  ac6sf2  32649  acunirnmpt2  32687  fedgmul  33737  pibt2  37561