Theorem findcard2 7808

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 7590	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4405	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 319	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1766	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4405	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 319	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1766	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4405	. . . . . . . 8 |- ( w = suc v -> ( x ~~ w <-> x ~~ suc v ) )
10	9	imbi1d 319	. . . . . . 7 |- ( w = suc v -> ( ( x ~~ w -> ph ) <-> ( x ~~ suc v -> ph ) ) )
11	10	albidv 1766	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 7629	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2.5	. . . . . . . . 9 |- ps
14		findcard2.1	. . . . . . . . 9 |- ( x = (/) -> ( ph <-> ps ) )
15	13, 14	mpbiri 237	. . . . . . . 8 |- ( x = (/) -> ph )
16	12, 15	sylbi 199	. . . . . . 7 |- ( x ~~ (/) -> ph )
17	16	ax-gen 1668	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		nsuceq0 5502	. . . . . . . . . . . 12 |- suc v =/= (/)
19		breq1 4404	. . . . . . . . . . . . . . . 16 |- ( w = (/) -> ( w ~~ suc v <-> (/) ~~ suc v ) )
20	19	anbi2d 709	. . . . . . . . . . . . . . 15 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) <-> ( v e. om /\ (/) ~~ suc v ) ) )
21		peano1 6709	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
22		peano2 6710	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
23		nneneq 7752	. . . . . . . . . . . . . . . . . 18 |- ( ( (/) e. om /\ suc v e. om ) -> ( (/) ~~ suc v <-> (/) = suc v ) )
24	21, 22, 23	sylancr 668	. . . . . . . . . . . . . . . . 17 |- ( v e. om -> ( (/) ~~ suc v <-> (/) = suc v ) )
25	24	biimpa 487	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ (/) ~~ suc v ) -> (/) = suc v )
26	25	eqcomd 2456	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ (/) ~~ suc v ) -> suc v = (/) )
27	20, 26	syl6bi 232	. . . . . . . . . . . . . 14 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) -> suc v = (/) ) )
28	27	com12 32	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( w = (/) -> suc v = (/) ) )
29	28	necon3d 2644	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( suc v =/= (/) -> w =/= (/) ) )
30	18, 29	mpi 20	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> w =/= (/) )
31	30	ex 436	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> w =/= (/) ) )
32		n0 3740	. . . . . . . . . . . 12 |- ( w =/= (/) <-> E. z z e. w )
33		dif1en 7801	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
34	33	3expia 1209	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( w \ { z } ) ~~ v ) )
35		snssi 4115	. . . . . . . . . . . . . . . . . 18 |- ( z e. w -> { z } C_ w )
36		uncom 3577	. . . . . . . . . . . . . . . . . . 19 |- ( ( w \ { z } ) u. { z } ) = ( { z } u. ( w \ { z } ) )
37		undif 3847	. . . . . . . . . . . . . . . . . . . 20 |- ( { z } C_ w <-> ( { z } u. ( w \ { z } ) ) = w )
38	37	biimpi 198	. . . . . . . . . . . . . . . . . . 19 |- ( { z } C_ w -> ( { z } u. ( w \ { z } ) ) = w )
39	36, 38	syl5eq 2496	. . . . . . . . . . . . . . . . . 18 |- ( { z } C_ w -> ( ( w \ { z } ) u. { z } ) = w )
40		vex 3047	. . . . . . . . . . . . . . . . . . . . 21 |- w e. _V
41		difexg 4550	. . . . . . . . . . . . . . . . . . . . 21 |- ( w e. _V -> ( w \ { z } ) e. _V )
42	40, 41	ax-mp 5	. . . . . . . . . . . . . . . . . . . 20 |- ( w \ { z } ) e. _V
43		breq1 4404	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
44	43	anbi2d 709	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
45		uneq1 3580	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
46	45	sbceq1d 3271	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
47	46	imbi2d 318	. . . . . . . . . . . . . . . . . . . . 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 322	. . . . . . . . . . . . . . . . . . . 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 4404	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
50		findcard2.2	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( x = y -> ( ph <-> ch ) )
51	49, 50	imbi12d 322	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
52	51	spv 2103	. . . . . . . . . . . . . . . . . . . . . 22 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
53		rspe 2844	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
54		isfi 7590	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y e. Fin <-> E. v e. om y ~~ v )
55	53, 54	sylibr 216	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> y e. Fin )
56		pm2.27 40	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
57	56	adantl 468	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
58		findcard2.6	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( y e. Fin -> ( ch -> th ) )
59	55, 57, 58	sylsyld 58	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> th ) )
60	52, 59	syl5 33	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> th ) )
61		vex 3047	. . . . . . . . . . . . . . . . . . . . . . 23 |- y e. _V
62		snex 4640	. . . . . . . . . . . . . . . . . . . . . . 23 |- { z } e. _V
63	61, 62	unex 6586	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y u. { z } ) e. _V
64		findcard2.3	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
65	63, 64	sbcie 3301	. . . . . . . . . . . . . . . . . . . . 21 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
66	60, 65	syl6ibr 231	. . . . . . . . . . . . . . . . . . . 20 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
67	42, 48, 66	vtocl 3099	. . . . . . . . . . . . . . . . . . 19 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
68		dfsbcq 3268	. . . . . . . . . . . . . . . . . . . 20 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
69	68	imbi2d 318	. . . . . . . . . . . . . . . . . . 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 223	. . . . . . . . . . . . . . . . . 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 438	. . . . . . . . . . . . . . . 16 |- ( z e. w -> ( v e. om -> ( ( w \ { z } ) ~~ v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
73	72	com12 32	. . . . . . . . . . . . . . 15 |- ( v e. om -> ( z e. w -> ( ( w \ { z } ) ~~ v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
74	73	adantr 467	. . . . . . . . . . . . . 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 41	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
76	75	exlimdv 1778	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
77	32, 76	syl5bi 221	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
78	77	ex 436	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
79	31, 78	mpdd 41	. . . . . . . . 9 |- ( v e. om -> ( w ~~ suc v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
80	79	com23 81	. . . . . . . 8 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> ( w ~~ suc v -> [. w / x ]. ph ) ) )
81	80	alrimdv 1774	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
82		nfv 1760	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
83		nfv 1760	. . . . . . . . 9 |- F/ x w ~~ suc v
84		nfsbc1v 3286	. . . . . . . . 9 |- F/ x [. w / x ]. ph
85	83, 84	nfim 2002	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
86		breq1 4404	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
87		sbceq1a 3277	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
88	86, 87	imbi12d 322	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
89	82, 85, 88	cbval 2113	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
90	81, 89	syl6ibr 231	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
91	5, 8, 11, 17, 90	finds1 6719	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
92	91	19.21bi 1946	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
93	92	rexlimiv 2872	. . 3 |- ( E. w e. om x ~~ w -> ph )
94	2, 93	sylbi 199	. 2 |- ( x e. Fin -> ph )
95	1, 94	vtoclga 3112	1 |- ( A e. Fin -> ta )

Syntax hints:   -> wi 4   <-> wb 188   /\ wa 371   A.wal 1441   = wceq 1443   E.wex 1662   e. wcel 1886   =/= wne 2621   E.wrex 2737   _Vcvv 3044   [.wsbc 3266   \ cdif 3400   u. cun 3401   C_ wss 3403   (/)c0 3730   {csn 3967   class class class wbr 4401   suc csuc 5424   omcom 6689   ~~ cen 7563   Fincfn 7566

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1668  ax-4 1681  ax-5 1757  ax-6 1804  ax-7 1850  ax-8 1888  ax-9 1895  ax-10 1914  ax-11 1919  ax-12 1932  ax-13 2090  ax-ext 2430  ax-sep 4524  ax-nul 4533  ax-pow 4580  ax-pr 4638  ax-un 6580

This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3or 985  df-3an 986  df-tru 1446  df-ex 1663  df-nf 1667  df-sb 1797  df-eu 2302  df-mo 2303  df-clab 2437  df-cleq 2443  df-clel 2446  df-nfc 2580  df-ne 2623  df-ral 2741  df-rex 2742  df-rab 2745  df-v 3046  df-sbc 3267  df-dif 3406  df-un 3408  df-in 3410  df-ss 3417  df-pss 3419  df-nul 3731  df-if 3881  df-pw 3952  df-sn 3968  df-pr 3970  df-tp 3972  df-op 3974  df-uni 4198  df-br 4402  df-opab 4461  df-tr 4497  df-eprel 4744  df-id 4748  df-po 4754  df-so 4755  df-fr 4792  df-we 4794  df-xp 4839  df-rel 4840  df-cnv 4841  df-co 4842  df-dm 4843  df-rn 4844  df-res 4845  df-ima 4846  df-ord 5425  df-on 5426  df-lim 5427  df-suc 5428  df-iota 5545  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-om 6690  df-1o 7179  df-er 7360  df-en 7567  df-fin 7570

This theorem is referenced by:  findcard2s  7809  frfi  7813  fnfi  7846  iunfi  7859  finsschain  7878  infdiffi  8160  fin1a2lem10  8836  wunfi  9143  rexfiuz  13403  modfsummod  13847  lcmfunsnlem  14607  lcmfun  14611  drsdirfi  16176  fiuncmp  20412  finiunmbl  22490  mbfresfi  31980  heibor1lem  32134  pclfinclN  33509