Metamath Proof Explorer


Theorem enfin2i

Description: II-finiteness is a cardinal property. (Contributed by Mario Carneiro, 18-May-2015)

Ref Expression
Assertion enfin2i ⊢ A ≈ B → A ∈ FinII → B ∈ FinII

Proof

Step Hyp Ref Expression
1 bren ⊢ A ≈ B ↔ ∃ f f : A ⟶ 1-1 onto B
2 elpwi ⊢ x ∈ 𝒫 𝒫 B → x ⊆ 𝒫 B
3 imauni ⊢ f ⋃ y ∈ 𝒫 A | f y ∈ x = ⋃ z ∈ y ∈ 𝒫 A | f y ∈ x f z
4 vex ⊢ f ∈ V
5 4 imaex ⊢ f z ∈ V
6 5 dfiun2 ⊢ ⋃ z ∈ y ∈ 𝒫 A | f y ∈ x f z = ⋃ w | ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z
7 3 6 eqtri ⊢ f ⋃ y ∈ 𝒫 A | f y ∈ x = ⋃ w | ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z
8 imaeq2 ⊢ y = z → f y = f z
9 8 eleq1d ⊢ y = z → f y ∈ x ↔ f z ∈ x
10 9 rexrab ⊢ ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z ↔ ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z
11 eleq1 ⊢ w = f z → w ∈ x ↔ f z ∈ x
12 11 biimparc ⊢ f z ∈ x ∧ w = f z → w ∈ x
13 12 rexlimivw ⊢ ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z → w ∈ x
14 cnvimass ⊢ f -1 w ⊆ dom ⁡ f
15 f1odm ⊢ f : A ⟶ 1-1 onto B → dom ⁡ f = A
16 15 ad3antrrr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → dom ⁡ f = A
17 14 16 sseqtrid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → f -1 w ⊆ A
18 4 cnvex ⊢ f -1 ∈ V
19 18 imaex ⊢ f -1 w ∈ V
20 19 elpw ⊢ f -1 w ∈ 𝒫 A ↔ f -1 w ⊆ A
21 17 20 sylibr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → f -1 w ∈ 𝒫 A
22 f1ofo ⊢ f : A ⟶ 1-1 onto B → f : A ⟶ onto B
23 22 ad3antrrr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → f : A ⟶ onto B
24 simprl ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → x ⊆ 𝒫 B
25 24 sselda ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → w ∈ 𝒫 B
26 25 elpwid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → w ⊆ B
27 foimacnv ⊢ f : A ⟶ onto B ∧ w ⊆ B → f f -1 w = w
28 23 26 27 syl2anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → f f -1 w = w
29 28 eqcomd ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → w = f f -1 w
30 simpr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → w ∈ x
31 29 30 eqeltrrd ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → f f -1 w ∈ x
32 imaeq2 ⊢ z = f -1 w → f z = f f -1 w
33 32 eleq1d ⊢ z = f -1 w → f z ∈ x ↔ f f -1 w ∈ x
34 32 eqeq2d ⊢ z = f -1 w → w = f z ↔ w = f f -1 w
35 33 34 anbi12d ⊢ z = f -1 w → f z ∈ x ∧ w = f z ↔ f f -1 w ∈ x ∧ w = f f -1 w
36 35 rspcev ⊢ f -1 w ∈ 𝒫 A ∧ f f -1 w ∈ x ∧ w = f f -1 w → ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z
37 21 31 29 36 syl12anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z
38 37 ex ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → w ∈ x → ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z
39 13 38 impbid2 ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ∃ z ∈ 𝒫 A f z ∈ x ∧ w = f z ↔ w ∈ x
40 10 39 bitrid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z ↔ w ∈ x
41 40 eqabcdv ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → w | ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z = x
42 41 unieqd ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ⋃ w | ∃ z ∈ y ∈ 𝒫 A | f y ∈ x w = f z = ⋃ x
43 7 42 eqtrid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → f ⋃ y ∈ 𝒫 A | f y ∈ x = ⋃ x
44 simplr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → A ∈ FinII
45 ssrab2 ⊢ y ∈ 𝒫 A | f y ∈ x ⊆ 𝒫 A
46 45 a1i ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → y ∈ 𝒫 A | f y ∈ x ⊆ 𝒫 A
47 simprrl ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → x ≠ ∅
48 n0 ⊢ x ≠ ∅ ↔ ∃ w w ∈ x
49 47 48 sylib ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ∃ w w ∈ x
50 imaeq2 ⊢ y = f -1 w → f y = f f -1 w
51 50 eleq1d ⊢ y = f -1 w → f y ∈ x ↔ f f -1 w ∈ x
52 51 rspcev ⊢ f -1 w ∈ 𝒫 A ∧ f f -1 w ∈ x → ∃ y ∈ 𝒫 A f y ∈ x
53 21 31 52 syl2anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ w ∈ x → ∃ y ∈ 𝒫 A f y ∈ x
54 49 53 exlimddv ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ∃ y ∈ 𝒫 A f y ∈ x
55 rabn0 ⊢ y ∈ 𝒫 A | f y ∈ x ≠ ∅ ↔ ∃ y ∈ 𝒫 A f y ∈ x
56 54 55 sylibr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → y ∈ 𝒫 A | f y ∈ x ≠ ∅
57 9 elrab ⊢ z ∈ y ∈ 𝒫 A | f y ∈ x ↔ z ∈ 𝒫 A ∧ f z ∈ x
58 imaeq2 ⊢ y = w → f y = f w
59 58 eleq1d ⊢ y = w → f y ∈ x ↔ f w ∈ x
60 59 elrab ⊢ w ∈ y ∈ 𝒫 A | f y ∈ x ↔ w ∈ 𝒫 A ∧ f w ∈ x
61 57 60 anbi12i ⊢ z ∈ y ∈ 𝒫 A | f y ∈ x ∧ w ∈ y ∈ 𝒫 A | f y ∈ x ↔ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x
62 simprrr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → [⊂] Or x
63 62 adantr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → [⊂] Or x
64 simprlr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f z ∈ x
65 simprrr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f w ∈ x
66 sorpssi ⊢ [⊂] Or x ∧ f z ∈ x ∧ f w ∈ x → f z ⊆ f w ∨ f w ⊆ f z
67 63 64 65 66 syl12anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f z ⊆ f w ∨ f w ⊆ f z
68 f1of1 ⊢ f : A ⟶ 1-1 onto B → f : A ⟶ 1-1 B
69 68 ad3antrrr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f : A ⟶ 1-1 B
70 simprll ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → z ∈ 𝒫 A
71 70 elpwid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → z ⊆ A
72 simprrl ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → w ∈ 𝒫 A
73 72 elpwid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → w ⊆ A
74 f1imass ⊢ f : A ⟶ 1-1 B ∧ z ⊆ A ∧ w ⊆ A → f z ⊆ f w ↔ z ⊆ w
75 69 71 73 74 syl12anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f z ⊆ f w ↔ z ⊆ w
76 f1imass ⊢ f : A ⟶ 1-1 B ∧ w ⊆ A ∧ z ⊆ A → f w ⊆ f z ↔ w ⊆ z
77 69 73 71 76 syl12anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f w ⊆ f z ↔ w ⊆ z
78 75 77 orbi12d ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → f z ⊆ f w ∨ f w ⊆ f z ↔ z ⊆ w ∨ w ⊆ z
79 67 78 mpbid ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ 𝒫 A ∧ f z ∈ x ∧ w ∈ 𝒫 A ∧ f w ∈ x → z ⊆ w ∨ w ⊆ z
80 61 79 sylan2b ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x ∧ z ∈ y ∈ 𝒫 A | f y ∈ x ∧ w ∈ y ∈ 𝒫 A | f y ∈ x → z ⊆ w ∨ w ⊆ z
81 80 ralrimivva ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ∀ z ∈ y ∈ 𝒫 A | f y ∈ x ∀ w ∈ y ∈ 𝒫 A | f y ∈ x z ⊆ w ∨ w ⊆ z
82 sorpss ⊢ [⊂] Or y ∈ 𝒫 A | f y ∈ x ↔ ∀ z ∈ y ∈ 𝒫 A | f y ∈ x ∀ w ∈ y ∈ 𝒫 A | f y ∈ x z ⊆ w ∨ w ⊆ z
83 81 82 sylibr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → [⊂] Or y ∈ 𝒫 A | f y ∈ x
84 fin2i ⊢ A ∈ FinII ∧ y ∈ 𝒫 A | f y ∈ x ⊆ 𝒫 A ∧ y ∈ 𝒫 A | f y ∈ x ≠ ∅ ∧ [⊂] Or y ∈ 𝒫 A | f y ∈ x → ⋃ y ∈ 𝒫 A | f y ∈ x ∈ y ∈ 𝒫 A | f y ∈ x
85 44 46 56 83 84 syl22anc ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ⋃ y ∈ 𝒫 A | f y ∈ x ∈ y ∈ 𝒫 A | f y ∈ x
86 imaeq2 ⊢ z = ⋃ y ∈ 𝒫 A | f y ∈ x → f z = f ⋃ y ∈ 𝒫 A | f y ∈ x
87 86 eleq1d ⊢ z = ⋃ y ∈ 𝒫 A | f y ∈ x → f z ∈ x ↔ f ⋃ y ∈ 𝒫 A | f y ∈ x ∈ x
88 9 cbvrabv ⊢ y ∈ 𝒫 A | f y ∈ x = z ∈ 𝒫 A | f z ∈ x
89 87 88 elrab2 ⊢ ⋃ y ∈ 𝒫 A | f y ∈ x ∈ y ∈ 𝒫 A | f y ∈ x ↔ ⋃ y ∈ 𝒫 A | f y ∈ x ∈ 𝒫 A ∧ f ⋃ y ∈ 𝒫 A | f y ∈ x ∈ x
90 89 simprbi ⊢ ⋃ y ∈ 𝒫 A | f y ∈ x ∈ y ∈ 𝒫 A | f y ∈ x → f ⋃ y ∈ 𝒫 A | f y ∈ x ∈ x
91 85 90 syl ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → f ⋃ y ∈ 𝒫 A | f y ∈ x ∈ x
92 43 91 eqeltrrd ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B ∧ x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
93 92 expr ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ⊆ 𝒫 B → x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
94 2 93 sylan2 ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII ∧ x ∈ 𝒫 𝒫 B → x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
95 94 ralrimiva ⊢ f : A ⟶ 1-1 onto B ∧ A ∈ FinII → ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
96 95 ex ⊢ f : A ⟶ 1-1 onto B → A ∈ FinII → ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
97 96 exlimiv ⊢ ∃ f f : A ⟶ 1-1 onto B → A ∈ FinII → ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
98 1 97 sylbi ⊢ A ≈ B → A ∈ FinII → ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
99 relen ⊢ Rel ⁡ ≈
100 99 brrelex2i ⊢ A ≈ B → B ∈ V
101 isfin2 ⊢ B ∈ V → B ∈ FinII ↔ ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
102 100 101 syl ⊢ A ≈ B → B ∈ FinII ↔ ∀ x ∈ 𝒫 𝒫 B x ≠ ∅ ∧ [⊂] Or x → ⋃ x ∈ x
103 98 102 sylibrd ⊢ A ≈ B → A ∈ FinII → B ∈ FinII