Theorem findcard2 7796

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.)

Hypotheses

Ref	Expression
findcard2.1	|- ( x = (/) -> ( ph <-> ps ) )
findcard2.2	|- ( x = y -> ( ph <-> ch ) )
findcard2.3	|- ( x = ( y u. { z } ) -> ( ph <-> th ) )
findcard2.4	|- ( x = A -> ( ph <-> ta ) )
findcard2.5	|- ps
findcard2.6	|- ( y e. Fin -> ( ch -> th ) )

Assertion

Ref	Expression
findcard2	|- ( A e. Fin -> ta )

Distinct variable groups:   x, y, z, A   ps, x   ch, x   th, x   ta, x   ph, y, z

Allowed substitution hints:   ph( x)   ps( y, z)   ch( y, z)   th( y, z)   ta( y, z)

Proof of Theorem findcard2

Dummy variables w v are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		findcard2.4	. 2 |- ( x = A -> ( ph <-> ta ) )
2		isfi 7579	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4401	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 317	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1736	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4401	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 317	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1736	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4401	. . . . . . . 8 |- ( w = suc v -> ( x ~~ w <-> x ~~ suc v ) )
10	9	imbi1d 317	. . . . . . 7 |- ( w = suc v -> ( ( x ~~ w -> ph ) <-> ( x ~~ suc v -> ph ) ) )
11	10	albidv 1736	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 7618	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2.5	. . . . . . . . 9 |- ps
14		findcard2.1	. . . . . . . . 9 |- ( x = (/) -> ( ph <-> ps ) )
15	13, 14	mpbiri 235	. . . . . . . 8 |- ( x = (/) -> ph )
16	12, 15	sylbi 197	. . . . . . 7 |- ( x ~~ (/) -> ph )
17	16	ax-gen 1641	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		nsuceq0 5492	. . . . . . . . . . . 12 |- suc v =/= (/)
19		breq1 4400	. . . . . . . . . . . . . . . 16 |- ( w = (/) -> ( w ~~ suc v <-> (/) ~~ suc v ) )
20	19	anbi2d 704	. . . . . . . . . . . . . . 15 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) <-> ( v e. om /\ (/) ~~ suc v ) ) )
21		peano1 6705	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
22		peano2 6706	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
23		nneneq 7740	. . . . . . . . . . . . . . . . . 18 |- ( ( (/) e. om /\ suc v e. om ) -> ( (/) ~~ suc v <-> (/) = suc v ) )
24	21, 22, 23	sylancr 663	. . . . . . . . . . . . . . . . 17 |- ( v e. om -> ( (/) ~~ suc v <-> (/) = suc v ) )
25	24	biimpa 484	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ (/) ~~ suc v ) -> (/) = suc v )
26	25	eqcomd 2412	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ (/) ~~ suc v ) -> suc v = (/) )
27	20, 26	syl6bi 230	. . . . . . . . . . . . . 14 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) -> suc v = (/) ) )
28	27	com12 31	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( w = (/) -> suc v = (/) ) )
29	28	necon3d 2629	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( suc v =/= (/) -> w =/= (/) ) )
30	18, 29	mpi 21	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> w =/= (/) )
31	30	ex 434	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> w =/= (/) ) )
32		n0 3750	. . . . . . . . . . . 12 |- ( w =/= (/) <-> E. z z e. w )
33		dif1en 7789	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
34	33	3expia 1201	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( w \ { z } ) ~~ v ) )
35		snssi 4118	. . . . . . . . . . . . . . . . . 18 |- ( z e. w -> { z } C_ w )
36		uncom 3589	. . . . . . . . . . . . . . . . . . 19 |- ( ( w \ { z } ) u. { z } ) = ( { z } u. ( w \ { z } ) )
37		undif 3854	. . . . . . . . . . . . . . . . . . . 20 |- ( { z } C_ w <-> ( { z } u. ( w \ { z } ) ) = w )
38	37	biimpi 196	. . . . . . . . . . . . . . . . . . 19 |- ( { z } C_ w -> ( { z } u. ( w \ { z } ) ) = w )
39	36, 38	syl5eq 2457	. . . . . . . . . . . . . . . . . 18 |- ( { z } C_ w -> ( ( w \ { z } ) u. { z } ) = w )
40		vex 3064	. . . . . . . . . . . . . . . . . . . . 21 |- w e. _V
41		difexg 4544	. . . . . . . . . . . . . . . . . . . . 21 |- ( w e. _V -> ( w \ { z } ) e. _V )
42	40, 41	ax-mp 5	. . . . . . . . . . . . . . . . . . . 20 |- ( w \ { z } ) e. _V
43		breq1 4400	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
44	43	anbi2d 704	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
45		uneq1 3592	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
46	45	sbceq1d 3284	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
47	46	imbi2d 316	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) <-> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) ) )
48	44, 47	imbi12d 320	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) ) <-> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) ) ) )
49		breq1 4400	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
50		findcard2.2	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( x = y -> ( ph <-> ch ) )
51	49, 50	imbi12d 320	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
52	51	spv 2040	. . . . . . . . . . . . . . . . . . . . . 22 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
53		rspe 2864	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
54		isfi 7579	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y e. Fin <-> E. v e. om y ~~ v )
55	53, 54	sylibr 214	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> y e. Fin )
56		pm2.27 39	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
57	56	adantl 466	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
58		findcard2.6	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( y e. Fin -> ( ch -> th ) )
59	55, 57, 58	sylsyld 57	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> th ) )
60	52, 59	syl5 32	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> th ) )
61		vex 3064	. . . . . . . . . . . . . . . . . . . . . . 23 |- y e. _V
62		snex 4634	. . . . . . . . . . . . . . . . . . . . . . 23 |- { z } e. _V
63	61, 62	unex 6582	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y u. { z } ) e. _V
64		findcard2.3	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
65	63, 64	sbcie 3314	. . . . . . . . . . . . . . . . . . . . 21 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
66	60, 65	syl6ibr 229	. . . . . . . . . . . . . . . . . . . 20 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
67	42, 48, 66	vtocl 3113	. . . . . . . . . . . . . . . . . . 19 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
68		dfsbcq 3281	. . . . . . . . . . . . . . . . . . . 20 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
69	68	imbi2d 316	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) <-> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
70	67, 69	syl5ib 221	. . . . . . . . . . . . . . . . . 18 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
71	35, 39, 70	3syl 18	. . . . . . . . . . . . . . . . 17 |- ( z e. w -> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
72	71	expd 436	. . . . . . . . . . . . . . . 16 |- ( z e. w -> ( v e. om -> ( ( w \ { z } ) ~~ v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
73	72	com12 31	. . . . . . . . . . . . . . 15 |- ( v e. om -> ( z e. w -> ( ( w \ { z } ) ~~ v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
74	73	adantr 465	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( ( w \ { z } ) ~~ v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
75	34, 74	mpdd 40	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
76	75	exlimdv 1747	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
77	32, 76	syl5bi 219	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
78	77	ex 434	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
79	31, 78	mpdd 40	. . . . . . . . 9 |- ( v e. om -> ( w ~~ suc v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
80	79	com23 80	. . . . . . . 8 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> ( w ~~ suc v -> [. w / x ]. ph ) ) )
81	80	alrimdv 1744	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
82		nfv 1730	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
83		nfv 1730	. . . . . . . . 9 |- F/ x w ~~ suc v
84		nfsbc1v 3299	. . . . . . . . 9 |- F/ x [. w / x ]. ph
85	83, 84	nfim 1950	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
86		breq1 4400	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
87		sbceq1a 3290	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
88	86, 87	imbi12d 320	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
89	82, 85, 88	cbval 2050	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
90	81, 89	syl6ibr 229	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
91	5, 8, 11, 17, 90	finds1 6715	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
92	91	19.21bi 1895	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
93	92	rexlimiv 2892	. . 3 |- ( E. w e. om x ~~ w -> ph )
94	2, 93	sylbi 197	. 2 |- ( x e. Fin -> ph )
95	1, 94	vtoclga 3125	1 |- ( A e. Fin -> ta )

Syntax hints:   -> wi 4   <-> wb 186   /\ wa 369   A.wal 1405   = wceq 1407   E.wex 1635   e. wcel 1844   =/= wne 2600   E.wrex 2757   _Vcvv 3061   [.wsbc 3279   \ cdif 3413   u. cun 3414   C_ wss 3416   (/)c0 3740   {csn 3974   class class class wbr 4397   suc csuc 5414   omcom 6685   ~~ cen 7553   Fincfn 7556

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1641  ax-4 1654  ax-5 1727  ax-6 1773  ax-7 1816  ax-8 1846  ax-9 1848  ax-10 1863  ax-11 1868  ax-12 1880  ax-13 2028  ax-ext 2382  ax-sep 4519  ax-nul 4527  ax-pow 4574  ax-pr 4632  ax-un 6576

This theorem depends on definitions:  df-bi 187  df-or 370  df-an 371  df-3or 977  df-3an 978  df-tru 1410  df-ex 1636  df-nf 1640  df-sb 1766  df-eu 2244  df-mo 2245  df-clab 2390  df-cleq 2396  df-clel 2399  df-nfc 2554  df-ne 2602  df-ral 2761  df-rex 2762  df-rab 2765  df-v 3063  df-sbc 3280  df-dif 3419  df-un 3421  df-in 3423  df-ss 3430  df-pss 3432  df-nul 3741  df-if 3888  df-pw 3959  df-sn 3975  df-pr 3977  df-tp 3979  df-op 3981  df-uni 4194  df-br 4398  df-opab 4456  df-tr 4492  df-eprel 4736  df-id 4740  df-po 4746  df-so 4747  df-fr 4784  df-we 4786  df-xp 4831  df-rel 4832  df-cnv 4833  df-co 4834  df-dm 4835  df-rn 4836  df-res 4837  df-ima 4838  df-ord 5415  df-on 5416  df-lim 5417  df-suc 5418  df-iota 5535  df-fun 5573  df-fn 5574  df-f 5575  df-f1 5576  df-fo 5577  df-f1o 5578  df-fv 5579  df-om 6686  df-1o 7169  df-er 7350  df-en 7557  df-fin 7560

This theorem is referenced by:  findcard2s  7797  frfi  7801  fnfi  7834  iunfi  7844  finsschain  7863  infdiffi  8109  fin1a2lem10  8823  wunfi  9131  rexfiuz  13331  modfsummod  13761  drsdirfi  15893  fiuncmp  20199  finiunmbl  22248  mbfresfi  31446  heibor1lem  31600  pclfinclN  32980