Metamath Proof Explorer


Theorem exsslsb

Description: Any finite generating set S of a vector space W contains a basis. (Contributed by Thierry Arnoux, 13-Oct-2025)

Ref Expression
Hypotheses exsslsb.b ⊢ B = Base W
exsslsb.j ⊢ J = LBasis ⁡ W
exsslsb.k ⊢ K = LSpan ⁡ W
exsslsb.w ⊢ φ → W ∈ LVec
exsslsb.s ⊢ φ → S ∈ Fin
exsslsb.1 ⊢ φ → S ⊆ B
exsslsb.2 ⊢ φ → K ⁡ S = B
Assertion exsslsb ⊢ φ → ∃ s ∈ J s ⊆ S

Proof

Step Hyp Ref Expression
1 exsslsb.b ⊢ B = Base W
2 exsslsb.j ⊢ J = LBasis ⁡ W
3 exsslsb.k ⊢ K = LSpan ⁡ W
4 exsslsb.w ⊢ φ → W ∈ LVec
5 exsslsb.s ⊢ φ → S ∈ Fin
6 exsslsb.1 ⊢ φ → S ⊆ B
7 exsslsb.2 ⊢ φ → K ⁡ S = B
8 nfv ⊢ Ⅎ s φ
9 4 ad2antrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → W ∈ LVec
10 simplr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ∈ V ∩ 𝒫 S ∩ K -1 B
11 10 elin2d ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ∈ 𝒫 S ∩ K -1 B
12 11 elin1d ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ∈ 𝒫 S
13 12 elpwid ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ⊆ S
14 6 ad2antrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → S ⊆ B
15 13 14 sstrd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ⊆ B
16 lveclmod ⊢ W ∈ LVec → W ∈ LMod
17 eqid ⊢ LSubSp ⁡ W = LSubSp ⁡ W
18 1 17 3 lspf ⊢ W ∈ LMod → K : 𝒫 B ⟶ LSubSp ⁡ W
19 4 16 18 3syl ⊢ φ → K : 𝒫 B ⟶ LSubSp ⁡ W
20 19 ffnd ⊢ φ → K Fn 𝒫 B
21 20 ad2antrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → K Fn 𝒫 B
22 11 elin2d ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ∈ K -1 B
23 fniniseg ⊢ K Fn 𝒫 B → s ∈ K -1 B ↔ s ∈ 𝒫 B ∧ K ⁡ s = B
24 23 simplbda ⊢ K Fn 𝒫 B ∧ s ∈ K -1 B → K ⁡ s = B
25 21 22 24 syl2anc ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → K ⁡ s = B
26 4 16 syl ⊢ φ → W ∈ LMod
27 26 ad3antrrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → W ∈ LMod
28 simpr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ⊂ s
29 28 pssssd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ⊆ s
30 13 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → s ⊆ S
31 29 30 sstrd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ⊆ S
32 14 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → S ⊆ B
33 31 32 sstrd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ⊆ B
34 1 3 lspssv ⊢ W ∈ LMod ∧ u ⊆ B → K ⁡ u ⊆ B
35 27 33 34 syl2anc ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → K ⁡ u ⊆ B
36 hashf ⊢ . : V ⟶ ℕ 0 ∪ +∞
37 ffun ⊢ . : V ⟶ ℕ 0 ∪ +∞ → Fun ⁡ .
38 36 37 mp1i ⊢ φ → Fun ⁡ .
39 pwssfi ⊢ S ∈ Fin → S ∈ Fin ↔ 𝒫 S ⊆ Fin
40 39 ibi ⊢ S ∈ Fin → 𝒫 S ⊆ Fin
41 5 40 syl ⊢ φ → 𝒫 S ⊆ Fin
42 41 ssinss1d ⊢ φ → 𝒫 S ∩ K -1 B ⊆ Fin
43 42 sselda ⊢ φ ∧ s ∈ 𝒫 S ∩ K -1 B → s ∈ Fin
44 hashcl ⊢ s ∈ Fin → s ∈ ℕ 0
45 43 44 syl ⊢ φ ∧ s ∈ 𝒫 S ∩ K -1 B → s ∈ ℕ 0
46 nn0uz ⊢ ℕ 0 = ℤ ≥ 0
47 45 46 eleqtrdi ⊢ φ ∧ s ∈ 𝒫 S ∩ K -1 B → s ∈ ℤ ≥ 0
48 8 38 47 funimassd ⊢ φ → . 𝒫 S ∩ K -1 B ⊆ ℤ ≥ 0
49 48 ad3antrrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → . 𝒫 S ∩ K -1 B ⊆ ℤ ≥ 0
50 36 a1i ⊢ φ → . : V ⟶ ℕ 0 ∪ +∞
51 50 ffnd ⊢ φ → . Fn V
52 51 ad3antrrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → . Fn V
53 52 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → . Fn V
54 vex ⊢ u ∈ V
55 54 a1i ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ V
56 5 ad3antrrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → S ∈ Fin
57 56 31 sselpwd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ∈ 𝒫 S
58 57 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ 𝒫 S
59 21 ad2antrr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → K Fn 𝒫 B
60 1 fvexi ⊢ B ∈ V
61 60 a1i ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → B ∈ V
62 61 33 sselpwd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → u ∈ 𝒫 B
63 62 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ 𝒫 B
64 simpr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → K ⁡ u = B
65 fvex ⊢ K ⁡ u ∈ V
66 65 elsn ⊢ K ⁡ u ∈ B ↔ K ⁡ u = B
67 64 66 sylibr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → K ⁡ u ∈ B
68 59 63 67 elpreimad ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ K -1 B
69 58 68 elind ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ 𝒫 S ∩ K -1 B
70 53 55 69 fnfvimad ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ . 𝒫 S ∩ K -1 B
71 infssuzle ⊢ . 𝒫 S ∩ K -1 B ⊆ ℤ ≥ 0 ∧ u ∈ . 𝒫 S ∩ K -1 B → inf . 𝒫 S ∩ K -1 B ℝ < ≤ u
72 49 70 71 syl2an2r ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → inf . 𝒫 S ∩ K -1 B ℝ < ≤ u
73 56 30 ssfid ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → s ∈ Fin
74 73 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → s ∈ Fin
75 simplr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ⊂ s
76 hashpss ⊢ s ∈ Fin ∧ u ⊂ s → u < s
77 74 75 76 syl2anc ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u < s
78 simpllr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → s = inf . 𝒫 S ∩ K -1 B ℝ <
79 77 78 breqtrd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u < inf . 𝒫 S ∩ K -1 B ℝ <
80 29 adantr ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ⊆ s
81 74 80 ssfid ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ Fin
82 hashcl ⊢ u ∈ Fin → u ∈ ℕ 0
83 81 82 syl ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ ℕ 0
84 83 nn0red ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u ∈ ℝ
85 74 44 syl ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → s ∈ ℕ 0
86 85 nn0red ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → s ∈ ℝ
87 78 86 eqeltrrd ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → inf . 𝒫 S ∩ K -1 B ℝ < ∈ ℝ
88 84 87 ltnled ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → u < inf . 𝒫 S ∩ K -1 B ℝ < ↔ ¬ inf . 𝒫 S ∩ K -1 B ℝ < ≤ u
89 79 88 mpbid ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s ∧ K ⁡ u = B → ¬ inf . 𝒫 S ∩ K -1 B ℝ < ≤ u
90 72 89 pm2.65da ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → ¬ K ⁡ u = B
91 90 neqned ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → K ⁡ u ≠ B
92 df-pss ⊢ K ⁡ u ⊂ B ↔ K ⁡ u ⊆ B ∧ K ⁡ u ≠ B
93 35 91 92 sylanbrc ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < ∧ u ⊂ s → K ⁡ u ⊂ B
94 93 ex ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → u ⊂ s → K ⁡ u ⊂ B
95 94 alrimiv ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → ∀ u u ⊂ s → K ⁡ u ⊂ B
96 1 2 3 islbs3 ⊢ W ∈ LVec → s ∈ J ↔ s ⊆ B ∧ K ⁡ s = B ∧ ∀ u u ⊂ s → K ⁡ u ⊂ B
97 96 biimpar ⊢ W ∈ LVec ∧ s ⊆ B ∧ K ⁡ s = B ∧ ∀ u u ⊂ s → K ⁡ u ⊂ B → s ∈ J
98 9 15 25 95 97 syl13anc ⊢ φ ∧ s ∈ V ∩ 𝒫 S ∩ K -1 B ∧ s = inf . 𝒫 S ∩ K -1 B ℝ < → s ∈ J
99 5 elexd ⊢ φ → S ∈ V
100 pwidg ⊢ S ∈ Fin → S ∈ 𝒫 S
101 5 100 syl ⊢ φ → S ∈ 𝒫 S
102 5 6 elpwd ⊢ φ → S ∈ 𝒫 B
103 fvex ⊢ K ⁡ S ∈ V
104 103 elsn ⊢ K ⁡ S ∈ B ↔ K ⁡ S = B
105 7 104 sylibr ⊢ φ → K ⁡ S ∈ B
106 20 102 105 elpreimad ⊢ φ → S ∈ K -1 B
107 101 106 elind ⊢ φ → S ∈ 𝒫 S ∩ K -1 B
108 51 99 107 fnfvimad ⊢ φ → S ∈ . 𝒫 S ∩ K -1 B
109 108 ne0d ⊢ φ → . 𝒫 S ∩ K -1 B ≠ ∅
110 infssuzcl ⊢ . 𝒫 S ∩ K -1 B ⊆ ℤ ≥ 0 ∧ . 𝒫 S ∩ K -1 B ≠ ∅ → inf . 𝒫 S ∩ K -1 B ℝ < ∈ . 𝒫 S ∩ K -1 B
111 48 109 110 syl2anc ⊢ φ → inf . 𝒫 S ∩ K -1 B ℝ < ∈ . 𝒫 S ∩ K -1 B
112 fvelima2 ⊢ . Fn V ∧ inf . 𝒫 S ∩ K -1 B ℝ < ∈ . 𝒫 S ∩ K -1 B → ∃ s ∈ V ∩ 𝒫 S ∩ K -1 B s = inf . 𝒫 S ∩ K -1 B ℝ <
113 51 111 112 syl2anc ⊢ φ → ∃ s ∈ V ∩ 𝒫 S ∩ K -1 B s = inf . 𝒫 S ∩ K -1 B ℝ <
114 8 98 13 113 reximd2a ⊢ φ → ∃ s ∈ J s ⊆ S