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

Theorem findcard 8745
 Description: Schema for induction on the cardinality of a finite set. The inductive hypothesis is that the result is true on the given set with any one element removed. The result is then proven to be true for all finite sets. (Contributed by Jeff Madsen, 2-Sep-2009.)
Hypotheses
Ref Expression
findcard.1 (𝑥 = ∅ → (𝜑𝜓))
findcard.2 (𝑥 = (𝑦 ∖ {𝑧}) → (𝜑𝜒))
findcard.3 (𝑥 = 𝑦 → (𝜑𝜃))
findcard.4 (𝑥 = 𝐴 → (𝜑𝜏))
findcard.5 𝜓
findcard.6 (𝑦 ∈ Fin → (∀𝑧𝑦 𝜒𝜃))
Assertion
Ref Expression
findcard (𝐴 ∈ Fin → 𝜏)
Distinct variable groups:   𝑥,𝑦,𝑧,𝐴   𝜓,𝑥   𝜒,𝑥   𝜃,𝑥   𝜏,𝑥   𝜑,𝑦,𝑧
Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑦,𝑧)   𝜒(𝑦,𝑧)   𝜃(𝑦,𝑧)   𝜏(𝑦,𝑧)

Proof of Theorem findcard
Dummy variables 𝑤 𝑣 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 findcard.4 . 2 (𝑥 = 𝐴 → (𝜑𝜏))
2 isfi 8520 . . 3 (𝑥 ∈ Fin ↔ ∃𝑤 ∈ ω 𝑥𝑤)
3 breq2 5037 . . . . . . . 8 (𝑤 = ∅ → (𝑥𝑤𝑥 ≈ ∅))
43imbi1d 345 . . . . . . 7 (𝑤 = ∅ → ((𝑥𝑤𝜑) ↔ (𝑥 ≈ ∅ → 𝜑)))
54albidv 1921 . . . . . 6 (𝑤 = ∅ → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥 ≈ ∅ → 𝜑)))
6 breq2 5037 . . . . . . . 8 (𝑤 = 𝑣 → (𝑥𝑤𝑥𝑣))
76imbi1d 345 . . . . . . 7 (𝑤 = 𝑣 → ((𝑥𝑤𝜑) ↔ (𝑥𝑣𝜑)))
87albidv 1921 . . . . . 6 (𝑤 = 𝑣 → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥𝑣𝜑)))
9 breq2 5037 . . . . . . . 8 (𝑤 = suc 𝑣 → (𝑥𝑤𝑥 ≈ suc 𝑣))
109imbi1d 345 . . . . . . 7 (𝑤 = suc 𝑣 → ((𝑥𝑤𝜑) ↔ (𝑥 ≈ suc 𝑣𝜑)))
1110albidv 1921 . . . . . 6 (𝑤 = suc 𝑣 → (∀𝑥(𝑥𝑤𝜑) ↔ ∀𝑥(𝑥 ≈ suc 𝑣𝜑)))
12 en0 8559 . . . . . . . 8 (𝑥 ≈ ∅ ↔ 𝑥 = ∅)
13 findcard.5 . . . . . . . . 9 𝜓
14 findcard.1 . . . . . . . . 9 (𝑥 = ∅ → (𝜑𝜓))
1513, 14mpbiri 261 . . . . . . . 8 (𝑥 = ∅ → 𝜑)
1612, 15sylbi 220 . . . . . . 7 (𝑥 ≈ ∅ → 𝜑)
1716ax-gen 1797 . . . . . 6 𝑥(𝑥 ≈ ∅ → 𝜑)
18 peano2 7586 . . . . . . . . . . . . 13 (𝑣 ∈ ω → suc 𝑣 ∈ ω)
19 breq2 5037 . . . . . . . . . . . . . 14 (𝑤 = suc 𝑣 → (𝑦𝑤𝑦 ≈ suc 𝑣))
2019rspcev 3574 . . . . . . . . . . . . 13 ((suc 𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) → ∃𝑤 ∈ ω 𝑦𝑤)
2118, 20sylan 583 . . . . . . . . . . . 12 ((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) → ∃𝑤 ∈ ω 𝑦𝑤)
22 isfi 8520 . . . . . . . . . . . 12 (𝑦 ∈ Fin ↔ ∃𝑤 ∈ ω 𝑦𝑤)
2321, 22sylibr 237 . . . . . . . . . . 11 ((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) → 𝑦 ∈ Fin)
24233adant2 1128 . . . . . . . . . 10 ((𝑣 ∈ ω ∧ ∀𝑥(𝑥𝑣𝜑) ∧ 𝑦 ≈ suc 𝑣) → 𝑦 ∈ Fin)
25 dif1en 8739 . . . . . . . . . . . . . . . 16 ((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣𝑧𝑦) → (𝑦 ∖ {𝑧}) ≈ 𝑣)
26253expa 1115 . . . . . . . . . . . . . . 15 (((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) ∧ 𝑧𝑦) → (𝑦 ∖ {𝑧}) ≈ 𝑣)
27 vex 3447 . . . . . . . . . . . . . . . . 17 𝑦 ∈ V
2827difexi 5199 . . . . . . . . . . . . . . . 16 (𝑦 ∖ {𝑧}) ∈ V
29 breq1 5036 . . . . . . . . . . . . . . . . 17 (𝑥 = (𝑦 ∖ {𝑧}) → (𝑥𝑣 ↔ (𝑦 ∖ {𝑧}) ≈ 𝑣))
30 findcard.2 . . . . . . . . . . . . . . . . 17 (𝑥 = (𝑦 ∖ {𝑧}) → (𝜑𝜒))
3129, 30imbi12d 348 . . . . . . . . . . . . . . . 16 (𝑥 = (𝑦 ∖ {𝑧}) → ((𝑥𝑣𝜑) ↔ ((𝑦 ∖ {𝑧}) ≈ 𝑣𝜒)))
3228, 31spcv 3557 . . . . . . . . . . . . . . 15 (∀𝑥(𝑥𝑣𝜑) → ((𝑦 ∖ {𝑧}) ≈ 𝑣𝜒))
3326, 32syl5com 31 . . . . . . . . . . . . . 14 (((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) ∧ 𝑧𝑦) → (∀𝑥(𝑥𝑣𝜑) → 𝜒))
3433ralrimdva 3157 . . . . . . . . . . . . 13 ((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) → (∀𝑥(𝑥𝑣𝜑) → ∀𝑧𝑦 𝜒))
3534imp 410 . . . . . . . . . . . 12 (((𝑣 ∈ ω ∧ 𝑦 ≈ suc 𝑣) ∧ ∀𝑥(𝑥𝑣𝜑)) → ∀𝑧𝑦 𝜒)
3635an32s 651 . . . . . . . . . . 11 (((𝑣 ∈ ω ∧ ∀𝑥(𝑥𝑣𝜑)) ∧ 𝑦 ≈ suc 𝑣) → ∀𝑧𝑦 𝜒)
37363impa 1107 . . . . . . . . . 10 ((𝑣 ∈ ω ∧ ∀𝑥(𝑥𝑣𝜑) ∧ 𝑦 ≈ suc 𝑣) → ∀𝑧𝑦 𝜒)
38 findcard.6 . . . . . . . . . 10 (𝑦 ∈ Fin → (∀𝑧𝑦 𝜒𝜃))
3924, 37, 38sylc 65 . . . . . . . . 9 ((𝑣 ∈ ω ∧ ∀𝑥(𝑥𝑣𝜑) ∧ 𝑦 ≈ suc 𝑣) → 𝜃)
40393exp 1116 . . . . . . . 8 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → (𝑦 ≈ suc 𝑣𝜃)))
4140alrimdv 1930 . . . . . . 7 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → ∀𝑦(𝑦 ≈ suc 𝑣𝜃)))
42 breq1 5036 . . . . . . . . 9 (𝑥 = 𝑦 → (𝑥 ≈ suc 𝑣𝑦 ≈ suc 𝑣))
43 findcard.3 . . . . . . . . 9 (𝑥 = 𝑦 → (𝜑𝜃))
4442, 43imbi12d 348 . . . . . . . 8 (𝑥 = 𝑦 → ((𝑥 ≈ suc 𝑣𝜑) ↔ (𝑦 ≈ suc 𝑣𝜃)))
4544cbvalvw 2043 . . . . . . 7 (∀𝑥(𝑥 ≈ suc 𝑣𝜑) ↔ ∀𝑦(𝑦 ≈ suc 𝑣𝜃))
4641, 45syl6ibr 255 . . . . . 6 (𝑣 ∈ ω → (∀𝑥(𝑥𝑣𝜑) → ∀𝑥(𝑥 ≈ suc 𝑣𝜑)))
475, 8, 11, 17, 46finds1 7596 . . . . 5 (𝑤 ∈ ω → ∀𝑥(𝑥𝑤𝜑))
484719.21bi 2187 . . . 4 (𝑤 ∈ ω → (𝑥𝑤𝜑))
4948rexlimiv 3242 . . 3 (∃𝑤 ∈ ω 𝑥𝑤𝜑)
502, 49sylbi 220 . 2 (𝑥 ∈ Fin → 𝜑)
511, 50vtoclga 3525 1 (𝐴 ∈ Fin → 𝜏)
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 209   ∧ wa 399   ∧ w3a 1084  ∀wal 1536   = wceq 1538   ∈ wcel 2112  ∀wral 3109  ∃wrex 3110   ∖ cdif 3881  ∅c0 4246  {csn 4528   class class class wbr 5033  suc csuc 6165  ωcom 7564   ≈ cen 8493  Fincfn 8496 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 1911  ax-6 1970  ax-7 2015  ax-8 2114  ax-9 2122  ax-10 2143  ax-11 2159  ax-12 2176  ax-ext 2773  ax-sep 5170  ax-nul 5177  ax-pow 5234  ax-pr 5298  ax-un 7445 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2601  df-eu 2632  df-clab 2780  df-cleq 2794  df-clel 2873  df-nfc 2941  df-ne 2991  df-ral 3114  df-rex 3115  df-rab 3118  df-v 3446  df-sbc 3724  df-dif 3887  df-un 3889  df-in 3891  df-ss 3901  df-pss 3903  df-nul 4247  df-if 4429  df-pw 4502  df-sn 4529  df-pr 4531  df-tp 4533  df-op 4535  df-uni 4804  df-br 5034  df-opab 5096  df-tr 5140  df-id 5428  df-eprel 5433  df-po 5442  df-so 5443  df-fr 5482  df-we 5484  df-xp 5529  df-rel 5530  df-cnv 5531  df-co 5532  df-dm 5533  df-rn 5534  df-res 5535  df-ima 5536  df-ord 6166  df-on 6167  df-lim 6168  df-suc 6169  df-iota 6287  df-fun 6330  df-fn 6331  df-f 6332  df-f1 6333  df-fo 6334  df-f1o 6335  df-fv 6336  df-om 7565  df-1o 8089  df-er 8276  df-en 8497  df-fin 8500 This theorem is referenced by:  xpfi  8777
 Copyright terms: Public domain W3C validator