Theorem cover2 35799

Description: Two ways of expressing the statement "there is a cover of 𝐴 by elements of 𝐵 such that for each set in the cover, 𝜑". Note that 𝜑 and 𝑥 must be distinct. (Contributed by Jeff Madsen, 20-Jun-2010.)

Hypotheses

Ref	Expression
cover2.1	⊢ 𝐵 ∈ V
cover2.2	⊢ 𝐴 = ∪ 𝐵

Assertion

Ref	Expression
cover2	⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) ↔ ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))

Distinct variable groups:   𝜑,𝑥,𝑧   𝑥,𝐵,𝑦,𝑧   𝑥,𝐴,𝑧

Allowed substitution hints:   𝜑(𝑦)   𝐴(𝑦)

Proof of Theorem cover2

Step	Hyp	Ref	Expression
1		cover2.1	. . . 4 ⊢ 𝐵 ∈ V
2		ssrab2 4009	. . . 4 ⊢ {𝑦 ∈ 𝐵 ∣ 𝜑} ⊆ 𝐵
3	1, 2	elpwi2 5265	. . 3 ⊢ {𝑦 ∈ 𝐵 ∣ 𝜑} ∈ 𝒫 𝐵
4		nfra1 3142	. . . . 5 ⊢ Ⅎ𝑥∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)
5	2	unissi 4845	. . . . . . . 8 ⊢ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ⊆ ∪ 𝐵
6	5	sseli 3913	. . . . . . 7 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝑥 ∈ ∪ 𝐵)
7		cover2.2	. . . . . . 7 ⊢ 𝐴 = ∪ 𝐵
8	6, 7	eleqtrrdi 2850	. . . . . 6 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝑥 ∈ 𝐴)
9		rsp 3129	. . . . . . 7 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ 𝐴 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
10		elunirab 4852	. . . . . . 7 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
11	9, 10	syl6ibr 251	. . . . . 6 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ 𝐴 → 𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑}))
12	8, 11	impbid2 225	. . . . 5 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
13	4, 12	alrimi 2209	. . . 4 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∀𝑥(𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
14		dfcleq 2731	. . . 4 ⊢ (∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴 ↔ ∀𝑥(𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
15	13, 14	sylibr 233	. . 3 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴)
16		nfrab1 3310	. . . . . . 7 ⊢ Ⅎ𝑦{𝑦 ∈ 𝐵 ∣ 𝜑}
17	16	nfeq2 2923	. . . . . 6 ⊢ Ⅎ𝑦 𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑}
18		eleq2 2827	. . . . . . 7 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (𝑦 ∈ 𝑧 ↔ 𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑}))
19		rabid 3304	. . . . . . . 8 ⊢ (𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ (𝑦 ∈ 𝐵 ∧ 𝜑))
20	19	simprbi 496	. . . . . . 7 ⊢ (𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝜑)
21	18, 20	syl6bi 252	. . . . . 6 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (𝑦 ∈ 𝑧 → 𝜑))
22	17, 21	ralrimi 3139	. . . . 5 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ∀𝑦 ∈ 𝑧 𝜑)
23		unieq 4847	. . . . . . 7 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ∪ 𝑧 = ∪ {𝑦 ∈ 𝐵 ∣ 𝜑})
24	23	eqeq1d 2740	. . . . . 6 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (∪ 𝑧 = 𝐴 ↔ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴))
25	24	anbi1d 629	. . . . 5 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ((∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) ↔ (∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑)))
26	22, 25	mpbiran2d 704	. . . 4 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ((∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) ↔ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴))
27	26	rspcev 3552	. . 3 ⊢ (({𝑦 ∈ 𝐵 ∣ 𝜑} ∈ 𝒫 𝐵 ∧ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴) → ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))
28	3, 15, 27	sylancr 586	. 2 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))
29		elpwi 4539	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝒫 𝐵 → 𝑧 ⊆ 𝐵)
30		r19.29r 3184	. . . . . . . . . . 11 ⊢ ((∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 ∧ ∀𝑦 ∈ 𝑧 𝜑) → ∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑))
31	30	expcom 413	. . . . . . . . . 10 ⊢ (∀𝑦 ∈ 𝑧 𝜑 → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑)))
32		ssrexv 3984	. . . . . . . . . 10 ⊢ (𝑧 ⊆ 𝐵 → (∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
33	31, 32	sylan9r 508	. . . . . . . . 9 ⊢ ((𝑧 ⊆ 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
34	29, 33	sylan 579	. . . . . . . 8 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
35		eleq2 2827	. . . . . . . . . 10 ⊢ (∪ 𝑧 = 𝐴 → (𝑥 ∈ ∪ 𝑧 ↔ 𝑥 ∈ 𝐴))
36	35	biimpar 477	. . . . . . . . 9 ⊢ ((∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴) → 𝑥 ∈ ∪ 𝑧)
37		eluni2 4840	. . . . . . . . 9 ⊢ (𝑥 ∈ ∪ 𝑧 ↔ ∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦)
38	36, 37	sylib 217	. . . . . . . 8 ⊢ ((∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴) → ∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦)
39	34, 38	impel 505	. . . . . . 7 ⊢ (((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ (∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴)) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
40	39	anassrs 467	. . . . . 6 ⊢ ((((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ ∪ 𝑧 = 𝐴) ∧ 𝑥 ∈ 𝐴) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
41	40	ralrimiva 3107	. . . . 5 ⊢ (((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ ∪ 𝑧 = 𝐴) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
42	41	anasss 466	. . . 4 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ (∀𝑦 ∈ 𝑧 𝜑 ∧ ∪ 𝑧 = 𝐴)) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
43	42	ancom2s 646	. . 3 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ (∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑)) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
44	43	rexlimiva 3209	. 2 ⊢ (∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
45	28, 44	impbii 208	1 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) ↔ ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))

Syntax hints:   → wi 4   ↔ wb 205   ∧ wa 395  ∀wal 1537   = wceq 1539   ∈ wcel 2108  ∀wral 3063  ∃wrex 3064  {crab 3067  Vcvv 3422   ⊆ wss 3883  𝒫 cpw 4530  ∪ cuni 4836

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1799  ax-4 1813  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2110  ax-9 2118  ax-10 2139  ax-11 2156  ax-12 2173  ax-ext 2709  ax-sep 5218

This theorem depends on definitions:  df-bi 206  df-an 396  df-or 844  df-tru 1542  df-ex 1784  df-nf 1788  df-sb 2069  df-clab 2716  df-cleq 2730  df-clel 2817  df-nfc 2888  df-ral 3068  df-rex 3069  df-rab 3072  df-v 3424  df-in 3890  df-ss 3900  df-pw 4532  df-uni 4837

This theorem is referenced by:  cover2g  35800