Theorem cover2 37755

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 4025	. . . 4 ⊢ {𝑦 ∈ 𝐵 ∣ 𝜑} ⊆ 𝐵
3	1, 2	elpwi2 5268	. . 3 ⊢ {𝑦 ∈ 𝐵 ∣ 𝜑} ∈ 𝒫 𝐵
4		nfra1 3256	. . . . 5 ⊢ Ⅎ𝑥∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)
5	2	unissi 4863	. . . . . . . 8 ⊢ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ⊆ ∪ 𝐵
6	5	sseli 3925	. . . . . . 7 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝑥 ∈ ∪ 𝐵)
7		cover2.2	. . . . . . 7 ⊢ 𝐴 = ∪ 𝐵
8	6, 7	eleqtrrdi 2842	. . . . . 6 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝑥 ∈ 𝐴)
9		rsp 3220	. . . . . . 7 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ 𝐴 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
10		elunirab 4869	. . . . . . 7 ⊢ (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
11	9, 10	imbitrrdi 252	. . . . . 6 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ 𝐴 → 𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑}))
12	8, 11	impbid2 226	. . . . 5 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → (𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
13	4, 12	alrimi 2216	. . . 4 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∀𝑥(𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
14		dfcleq 2724	. . . 4 ⊢ (∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴 ↔ ∀𝑥(𝑥 ∈ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ 𝑥 ∈ 𝐴))
15	13, 14	sylibr 234	. . 3 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴)
16		nfrab1 3415	. . . . . . 7 ⊢ Ⅎ𝑦{𝑦 ∈ 𝐵 ∣ 𝜑}
17	16	nfeq2 2912	. . . . . 6 ⊢ Ⅎ𝑦 𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑}
18		eleq2 2820	. . . . . . 7 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (𝑦 ∈ 𝑧 ↔ 𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑}))
19		rabid 3416	. . . . . . . 8 ⊢ (𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑} ↔ (𝑦 ∈ 𝐵 ∧ 𝜑))
20	19	simprbi 496	. . . . . . 7 ⊢ (𝑦 ∈ {𝑦 ∈ 𝐵 ∣ 𝜑} → 𝜑)
21	18, 20	biimtrdi 253	. . . . . 6 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (𝑦 ∈ 𝑧 → 𝜑))
22	17, 21	ralrimi 3230	. . . . 5 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ∀𝑦 ∈ 𝑧 𝜑)
23		unieq 4865	. . . . . . 7 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ∪ 𝑧 = ∪ {𝑦 ∈ 𝐵 ∣ 𝜑})
24	23	eqeq1d 2733	. . . . . 6 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → (∪ 𝑧 = 𝐴 ↔ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴))
25	24	anbi1d 631	. . . . 5 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ((∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) ↔ (∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑)))
26	22, 25	mpbiran2d 708	. . . 4 ⊢ (𝑧 = {𝑦 ∈ 𝐵 ∣ 𝜑} → ((∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) ↔ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴))
27	26	rspcev 3572	. . 3 ⊢ (({𝑦 ∈ 𝐵 ∣ 𝜑} ∈ 𝒫 𝐵 ∧ ∪ {𝑦 ∈ 𝐵 ∣ 𝜑} = 𝐴) → ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))
28	3, 15, 27	sylancr 587	. 2 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))
29		elpwi 4552	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝒫 𝐵 → 𝑧 ⊆ 𝐵)
30		r19.29r 3096	. . . . . . . . . . 11 ⊢ ((∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 ∧ ∀𝑦 ∈ 𝑧 𝜑) → ∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑))
31	30	expcom 413	. . . . . . . . . 10 ⊢ (∀𝑦 ∈ 𝑧 𝜑 → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑)))
32		ssrexv 3999	. . . . . . . . . 10 ⊢ (𝑧 ⊆ 𝐵 → (∃𝑦 ∈ 𝑧 (𝑥 ∈ 𝑦 ∧ 𝜑) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
33	31, 32	sylan9r 508	. . . . . . . . 9 ⊢ ((𝑧 ⊆ 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
34	29, 33	sylan 580	. . . . . . . 8 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) → (∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦 → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑)))
35		eleq2 2820	. . . . . . . . . 10 ⊢ (∪ 𝑧 = 𝐴 → (𝑥 ∈ ∪ 𝑧 ↔ 𝑥 ∈ 𝐴))
36	35	biimpar 477	. . . . . . . . 9 ⊢ ((∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴) → 𝑥 ∈ ∪ 𝑧)
37		eluni2 4858	. . . . . . . . 9 ⊢ (𝑥 ∈ ∪ 𝑧 ↔ ∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦)
38	36, 37	sylib 218	. . . . . . . 8 ⊢ ((∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴) → ∃𝑦 ∈ 𝑧 𝑥 ∈ 𝑦)
39	34, 38	impel 505	. . . . . . 7 ⊢ (((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ (∪ 𝑧 = 𝐴 ∧ 𝑥 ∈ 𝐴)) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
40	39	anassrs 467	. . . . . 6 ⊢ ((((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ ∪ 𝑧 = 𝐴) ∧ 𝑥 ∈ 𝐴) → ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
41	40	ralrimiva 3124	. . . . 5 ⊢ (((𝑧 ∈ 𝒫 𝐵 ∧ ∀𝑦 ∈ 𝑧 𝜑) ∧ ∪ 𝑧 = 𝐴) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
42	41	anasss 466	. . . 4 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ (∀𝑦 ∈ 𝑧 𝜑 ∧ ∪ 𝑧 = 𝐴)) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
43	42	ancom2s 650	. . 3 ⊢ ((𝑧 ∈ 𝒫 𝐵 ∧ (∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑)) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
44	43	rexlimiva 3125	. 2 ⊢ (∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑) → ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑))
45	28, 44	impbii 209	1 ⊢ (∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 (𝑥 ∈ 𝑦 ∧ 𝜑) ↔ ∃𝑧 ∈ 𝒫 𝐵(∪ 𝑧 = 𝐴 ∧ ∀𝑦 ∈ 𝑧 𝜑))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395  ∀wal 1539   = wceq 1541   ∈ wcel 2111  ∀wral 3047  ∃wrex 3056  {crab 3395  Vcvv 3436   ⊆ wss 3897  𝒫 cpw 4545  ∪ cuni 4854

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 2113  ax-9 2121  ax-10 2144  ax-11 2160  ax-12 2180  ax-ext 2703  ax-sep 5229

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3an 1088  df-tru 1544  df-ex 1781  df-nf 1785  df-sb 2068  df-clab 2710  df-cleq 2723  df-clel 2806  df-nfc 2881  df-ral 3048  df-rex 3057  df-rab 3396  df-v 3438  df-in 3904  df-ss 3914  df-pw 4547  df-uni 4855

This theorem is referenced by:  cover2g  37756