MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  findcard2 Structured version   Visualization version   GIF version

Theorem findcard2 9166
Description: Schema for induction on the cardinality of a finite set. The inductive step shows that the result is true if one more element is added to the set. The result is then proven to be true for all finite sets. (Contributed by Jeff Madsen, 8-Jul-2010.) Avoid ax-pow 5363. (Revised by BTernaryTau, 26-Aug-2024.)
Hypotheses
Ref Expression
findcard2.1 (𝑥 = ∅ → (𝜑𝜓))
findcard2.2 (𝑥 = 𝑦 → (𝜑𝜒))
findcard2.3 (𝑥 = (𝑦 ∪ {𝑧}) → (𝜑𝜃))
findcard2.4 (𝑥 = 𝐴 → (𝜑𝜏))
findcard2.5 𝜓
findcard2.6 (𝑦 ∈ Fin → (𝜒𝜃))
Assertion
Ref Expression
findcard2 (𝐴 ∈ Fin → 𝜏)
Distinct variable groups:   𝜒,𝑥   𝜃,𝑥   𝜏,𝑥   𝑥,𝐴   𝜑,𝑦,𝑧   𝑥,𝑦,𝑧
Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑥,𝑦,𝑧)   𝜒(𝑦,𝑧)   𝜃(𝑦,𝑧)   𝜏(𝑦,𝑧)   𝐴(𝑦,𝑧)

Proof of Theorem findcard2
Dummy variables 𝑣 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 findcard2.4 . 2 (𝑥 = 𝐴 → (𝜑𝜏))
2 isfi 8974 . . 3 (𝑥 ∈ Fin ↔ ∃𝑤 ∈ ω 𝑥𝑤)
3 breq2 5152 . . . . . . . 8 (𝑤 = ∅ → (𝑥𝑤𝑥 ≈ ∅))
43imbi1d 341 . . . . . . 7 (𝑤 = ∅ → ((𝑥𝑤𝜑) ↔ (𝑥 ≈ ∅ → 𝜑)))
54albidv 1923 . . . . . 6 (𝑤 = ∅ → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥 ≈ ∅ → 𝜑)))
6 breq2 5152 . . . . . . . 8 (𝑤 = 𝑣 → (𝑥𝑤𝑥𝑣))
76imbi1d 341 . . . . . . 7 (𝑤 = 𝑣 → ((𝑥𝑤𝜑) ↔ (𝑥𝑣𝜑)))
87albidv 1923 . . . . . 6 (𝑤 = 𝑣 → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥𝑣𝜑)))
9 breq2 5152 . . . . . . . 8 (𝑤 = suc 𝑣 → (𝑥𝑤𝑥 ≈ suc 𝑣))
109imbi1d 341 . . . . . . 7 (𝑤 = suc 𝑣 → ((𝑥𝑤𝜑) ↔ (𝑥 ≈ suc 𝑣𝜑)))
1110albidv 1923 . . . . . 6 (𝑤 = suc 𝑣 → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥 ≈ suc 𝑣𝜑)))
12 en0 9015 . . . . . . . 8 (𝑥 ≈ ∅ ↔ 𝑥 = ∅)
13 findcard2.5 . . . . . . . . 9 𝜓
14 findcard2.1 . . . . . . . . 9 (𝑥 = ∅ → (𝜑𝜓))
1513, 14mpbiri 257 . . . . . . . 8 (𝑥 = ∅ → 𝜑)
1612, 15sylbi 216 . . . . . . 7 (𝑥 ≈ ∅ → 𝜑)
1716ax-gen 1797 . . . . . 6 𝑥(𝑥 ≈ ∅ → 𝜑)
18 nnon 7863 . . . . . . . . . . . 12 (𝑣 ∈ ω → 𝑣 ∈ On)
19 rexdif1en 9160 . . . . . . . . . . . 12 ((𝑣 ∈ On ∧ 𝑤 ≈ suc 𝑣) → ∃𝑧𝑤 (𝑤 ∖ {𝑧}) ≈ 𝑣)
2018, 19sylan 580 . . . . . . . . . . 11 ((𝑣 ∈ ω ∧ 𝑤 ≈ suc 𝑣) → ∃𝑧𝑤 (𝑤 ∖ {𝑧}) ≈ 𝑣)
21 snssi 4811 . . . . . . . . . . . . . . . 16 (𝑧𝑤 → {𝑧} ⊆ 𝑤)
22 uncom 4153 . . . . . . . . . . . . . . . . 17 ((𝑤 ∖ {𝑧}) ∪ {𝑧}) = ({𝑧} ∪ (𝑤 ∖ {𝑧}))
23 undif 4481 . . . . . . . . . . . . . . . . . 18 ({𝑧} ⊆ 𝑤 ↔ ({𝑧} ∪ (𝑤 ∖ {𝑧})) = 𝑤)
2423biimpi 215 . . . . . . . . . . . . . . . . 17 ({𝑧} ⊆ 𝑤 → ({𝑧} ∪ (𝑤 ∖ {𝑧})) = 𝑤)
2522, 24eqtrid 2784 . . . . . . . . . . . . . . . 16 ({𝑧} ⊆ 𝑤 → ((𝑤 ∖ {𝑧}) ∪ {𝑧}) = 𝑤)
26 vex 3478 . . . . . . . . . . . . . . . . . . 19 𝑤 ∈ V
2726difexi 5328 . . . . . . . . . . . . . . . . . 18 (𝑤 ∖ {𝑧}) ∈ V
28 breq1 5151 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = (𝑤 ∖ {𝑧}) → (𝑦𝑣 ↔ (𝑤 ∖ {𝑧}) ≈ 𝑣))
2928anbi2d 629 . . . . . . . . . . . . . . . . . . 19 (𝑦 = (𝑤 ∖ {𝑧}) → ((𝑣 ∈ ω ∧ 𝑦𝑣) ↔ (𝑣 ∈ ω ∧ (𝑤 ∖ {𝑧}) ≈ 𝑣)))
30 uneq1 4156 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 = (𝑤 ∖ {𝑧}) → (𝑦 ∪ {𝑧}) = ((𝑤 ∖ {𝑧}) ∪ {𝑧}))
3130sbceq1d 3782 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = (𝑤 ∖ {𝑧}) → ([(𝑦 ∪ {𝑧}) / 𝑥]𝜑[((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑))
3231imbi2d 340 . . . . . . . . . . . . . . . . . . 19 (𝑦 = (𝑤 ∖ {𝑧}) → ((∀𝑥(𝑥𝑣𝜑) → [(𝑦 ∪ {𝑧}) / 𝑥]𝜑) ↔ (∀𝑥(𝑥𝑣𝜑) → [((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑)))
3329, 32imbi12d 344 . . . . . . . . . . . . . . . . . 18 (𝑦 = (𝑤 ∖ {𝑧}) → (((𝑣 ∈ ω ∧ 𝑦𝑣) → (∀𝑥(𝑥𝑣𝜑) → [(𝑦 ∪ {𝑧}) / 𝑥]𝜑)) ↔ ((𝑣 ∈ ω ∧ (𝑤 ∖ {𝑧}) ≈ 𝑣) → (∀𝑥(𝑥𝑣𝜑) → [((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑))))
34 breq1 5151 . . . . . . . . . . . . . . . . . . . . . 22 (𝑥 = 𝑦 → (𝑥𝑣𝑦𝑣))
35 findcard2.2 . . . . . . . . . . . . . . . . . . . . . 22 (𝑥 = 𝑦 → (𝜑𝜒))
3634, 35imbi12d 344 . . . . . . . . . . . . . . . . . . . . 21 (𝑥 = 𝑦 → ((𝑥𝑣𝜑) ↔ (𝑦𝑣𝜒)))
3736spvv 2000 . . . . . . . . . . . . . . . . . . . 20 (∀𝑥(𝑥𝑣𝜑) → (𝑦𝑣𝜒))
38 rspe 3246 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑣 ∈ ω ∧ 𝑦𝑣) → ∃𝑣 ∈ ω 𝑦𝑣)
39 isfi 8974 . . . . . . . . . . . . . . . . . . . . . 22 (𝑦 ∈ Fin ↔ ∃𝑣 ∈ ω 𝑦𝑣)
4038, 39sylibr 233 . . . . . . . . . . . . . . . . . . . . 21 ((𝑣 ∈ ω ∧ 𝑦𝑣) → 𝑦 ∈ Fin)
41 pm2.27 42 . . . . . . . . . . . . . . . . . . . . . 22 (𝑦𝑣 → ((𝑦𝑣𝜒) → 𝜒))
4241adantl 482 . . . . . . . . . . . . . . . . . . . . 21 ((𝑣 ∈ ω ∧ 𝑦𝑣) → ((𝑦𝑣𝜒) → 𝜒))
43 findcard2.6 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 ∈ Fin → (𝜒𝜃))
4440, 42, 43sylsyld 61 . . . . . . . . . . . . . . . . . . . 20 ((𝑣 ∈ ω ∧ 𝑦𝑣) → ((𝑦𝑣𝜒) → 𝜃))
4537, 44syl5 34 . . . . . . . . . . . . . . . . . . 19 ((𝑣 ∈ ω ∧ 𝑦𝑣) → (∀𝑥(𝑥𝑣𝜑) → 𝜃))
46 vex 3478 . . . . . . . . . . . . . . . . . . . . 21 𝑦 ∈ V
47 vsnex 5429 . . . . . . . . . . . . . . . . . . . . 21 {𝑧} ∈ V
4846, 47unex 7735 . . . . . . . . . . . . . . . . . . . 20 (𝑦 ∪ {𝑧}) ∈ V
49 findcard2.3 . . . . . . . . . . . . . . . . . . . 20 (𝑥 = (𝑦 ∪ {𝑧}) → (𝜑𝜃))
5048, 49sbcie 3820 . . . . . . . . . . . . . . . . . . 19 ([(𝑦 ∪ {𝑧}) / 𝑥]𝜑𝜃)
5145, 50imbitrrdi 251 . . . . . . . . . . . . . . . . . 18 ((𝑣 ∈ ω ∧ 𝑦𝑣) → (∀𝑥(𝑥𝑣𝜑) → [(𝑦 ∪ {𝑧}) / 𝑥]𝜑))
5227, 33, 51vtocl 3549 . . . . . . . . . . . . . . . . 17 ((𝑣 ∈ ω ∧ (𝑤 ∖ {𝑧}) ≈ 𝑣) → (∀𝑥(𝑥𝑣𝜑) → [((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑))
53 dfsbcq 3779 . . . . . . . . . . . . . . . . . 18 (((𝑤 ∖ {𝑧}) ∪ {𝑧}) = 𝑤 → ([((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑[𝑤 / 𝑥]𝜑))
5453imbi2d 340 . . . . . . . . . . . . . . . . 17 (((𝑤 ∖ {𝑧}) ∪ {𝑧}) = 𝑤 → ((∀𝑥(𝑥𝑣𝜑) → [((𝑤 ∖ {𝑧}) ∪ {𝑧}) / 𝑥]𝜑) ↔ (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
5552, 54imbitrid 243 . . . . . . . . . . . . . . . 16 (((𝑤 ∖ {𝑧}) ∪ {𝑧}) = 𝑤 → ((𝑣 ∈ ω ∧ (𝑤 ∖ {𝑧}) ≈ 𝑣) → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
5621, 25, 553syl 18 . . . . . . . . . . . . . . 15 (𝑧𝑤 → ((𝑣 ∈ ω ∧ (𝑤 ∖ {𝑧}) ≈ 𝑣) → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
5756expd 416 . . . . . . . . . . . . . 14 (𝑧𝑤 → (𝑣 ∈ ω → ((𝑤 ∖ {𝑧}) ≈ 𝑣 → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑))))
5857com12 32 . . . . . . . . . . . . 13 (𝑣 ∈ ω → (𝑧𝑤 → ((𝑤 ∖ {𝑧}) ≈ 𝑣 → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑))))
5958rexlimdv 3153 . . . . . . . . . . . 12 (𝑣 ∈ ω → (∃𝑧𝑤 (𝑤 ∖ {𝑧}) ≈ 𝑣 → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
6059adantr 481 . . . . . . . . . . 11 ((𝑣 ∈ ω ∧ 𝑤 ≈ suc 𝑣) → (∃𝑧𝑤 (𝑤 ∖ {𝑧}) ≈ 𝑣 → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
6120, 60mpd 15 . . . . . . . . . 10 ((𝑣 ∈ ω ∧ 𝑤 ≈ suc 𝑣) → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑))
6261ex 413 . . . . . . . . 9 (𝑣 ∈ ω → (𝑤 ≈ suc 𝑣 → (∀𝑥(𝑥𝑣𝜑) → [𝑤 / 𝑥]𝜑)))
6362com23 86 . . . . . . . 8 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → (𝑤 ≈ suc 𝑣[𝑤 / 𝑥]𝜑)))
6463alrimdv 1932 . . . . . . 7 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → ∀𝑤(𝑤 ≈ suc 𝑣[𝑤 / 𝑥]𝜑)))
65 nfv 1917 . . . . . . . 8 𝑤(𝑥 ≈ suc 𝑣𝜑)
66 nfv 1917 . . . . . . . . 9 𝑥 𝑤 ≈ suc 𝑣
67 nfsbc1v 3797 . . . . . . . . 9 𝑥[𝑤 / 𝑥]𝜑
6866, 67nfim 1899 . . . . . . . 8 𝑥(𝑤 ≈ suc 𝑣[𝑤 / 𝑥]𝜑)
69 breq1 5151 . . . . . . . . 9 (𝑥 = 𝑤 → (𝑥 ≈ suc 𝑣𝑤 ≈ suc 𝑣))
70 sbceq1a 3788 . . . . . . . . 9 (𝑥 = 𝑤 → (𝜑[𝑤 / 𝑥]𝜑))
7169, 70imbi12d 344 . . . . . . . 8 (𝑥 = 𝑤 → ((𝑥 ≈ suc 𝑣𝜑) ↔ (𝑤 ≈ suc 𝑣[𝑤 / 𝑥]𝜑)))
7265, 68, 71cbvalv1 2337 . . . . . . 7 (∀𝑥(𝑥 ≈ suc 𝑣𝜑) ↔ ∀𝑤(𝑤 ≈ suc 𝑣[𝑤 / 𝑥]𝜑))
7364, 72imbitrrdi 251 . . . . . 6 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → ∀𝑥(𝑥 ≈ suc 𝑣𝜑)))
745, 8, 11, 17, 73finds1 7894 . . . . 5 (𝑤 ∈ ω → ∀𝑥(𝑥𝑤𝜑))
757419.21bi 2182 . . . 4 (𝑤 ∈ ω → (𝑥𝑤𝜑))
7675rexlimiv 3148 . . 3 (∃𝑤 ∈ ω 𝑥𝑤𝜑)
772, 76sylbi 216 . 2 (𝑥 ∈ Fin → 𝜑)
781, 77vtoclga 3565 1 (𝐴 ∈ Fin → 𝜏)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 396  wal 1539   = wceq 1541  wcel 2106  wrex 3070  [wsbc 3777  cdif 3945  cun 3946  wss 3948  c0 4322  {csn 4628   class class class wbr 5148  Oncon0 6364  suc csuc 6366  ωcom 7857  cen 8938  Fincfn 8941
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2703  ax-sep 5299  ax-nul 5306  ax-pr 5427  ax-un 7727
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3or 1088  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2534  df-eu 2563  df-clab 2710  df-cleq 2724  df-clel 2810  df-nfc 2885  df-ne 2941  df-ral 3062  df-rex 3071  df-reu 3377  df-rab 3433  df-v 3476  df-sbc 3778  df-dif 3951  df-un 3953  df-in 3955  df-ss 3965  df-pss 3967  df-nul 4323  df-if 4529  df-pw 4604  df-sn 4629  df-pr 4631  df-op 4635  df-uni 4909  df-br 5149  df-opab 5211  df-tr 5266  df-id 5574  df-eprel 5580  df-po 5588  df-so 5589  df-fr 5631  df-we 5633  df-xp 5682  df-rel 5683  df-cnv 5684  df-co 5685  df-dm 5686  df-rn 5687  df-res 5688  df-ima 5689  df-ord 6367  df-on 6368  df-lim 6369  df-suc 6370  df-iota 6495  df-fun 6545  df-fn 6546  df-f 6547  df-f1 6548  df-fo 6549  df-f1o 6550  df-fv 6551  df-om 7858  df-en 8942  df-fin 8945
This theorem is referenced by:  findcard2s  9167  ssfi  9175  imafi  9177  pwfi  9180  cnvfi  9182  fnfi  9183  frfi  9290  iunfi  9342  finsschain  9361  infdiffi  9655  fin1a2lem10  10406  wunfi  10718  rexfiuz  15296  modfsummod  15742  lcmfunsnlem  16580  lcmfun  16584  drsdirfi  18260  fiuncmp  22915  finiunmbl  25068  fineqvac  34166  mbfresfi  36620  heibor1lem  36763  pclfinclN  38907
  Copyright terms: Public domain W3C validator