Theorem findcard2 6947

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 6817	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4034	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 231	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1835	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4034	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 231	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1835	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4034	. . . . . . . 8 |- ( w = suc v -> ( x ~~ w <-> x ~~ suc v ) )
10	9	imbi1d 231	. . . . . . 7 |- ( w = suc v -> ( ( x ~~ w -> ph ) <-> ( x ~~ suc v -> ph ) ) )
11	10	albidv 1835	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6851	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2.5	. . . . . . . . 9 |- ps
14		findcard2.1	. . . . . . . . 9 |- ( x = (/) -> ( ph <-> ps ) )
15	13, 14	mpbiri 168	. . . . . . . 8 |- ( x = (/) -> ph )
16	12, 15	sylbi 121	. . . . . . 7 |- ( x ~~ (/) -> ph )
17	16	ax-gen 1460	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4629	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 276	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 4033	. . . . . . . . . . . . . . . 16 |- ( w = (/) -> ( w ~~ suc v <-> (/) ~~ suc v ) )
21	20	anbi2d 464	. . . . . . . . . . . . . . 15 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) <-> ( v e. om /\ (/) ~~ suc v ) ) )
22		peano1 4627	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4628	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 6915	. . . . . . . . . . . . . . . . . 18 |- ( ( (/) e. om /\ suc v e. om ) -> ( (/) ~~ suc v <-> (/) = suc v ) )
25	22, 23, 24	sylancr 414	. . . . . . . . . . . . . . . . 17 |- ( v e. om -> ( (/) ~~ suc v <-> (/) = suc v ) )
26	25	biimpa 296	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ (/) ~~ suc v ) -> (/) = suc v )
27	26	eqcomd 2199	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ (/) ~~ suc v ) -> suc v = (/) )
28	21, 27	biimtrdi 163	. . . . . . . . . . . . . 14 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) -> suc v = (/) ) )
29	28	com12 30	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( w = (/) -> suc v = (/) ) )
30	29	necon3d 2408	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( suc v =/= (/) -> w =/= (/) ) )
31	19, 30	mpd 13	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> w =/= (/) )
32	31	ex 115	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> w =/= (/) ) )
33		nnfi 6930	. . . . . . . . . . . . . . . 16 |- ( suc v e. om -> suc v e. Fin )
34	23, 33	syl 14	. . . . . . . . . . . . . . 15 |- ( v e. om -> suc v e. Fin )
35	34	adantr 276	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> suc v e. Fin )
36		enfi 6931	. . . . . . . . . . . . . . 15 |- ( w ~~ suc v -> ( w e. Fin <-> suc v e. Fin ) )
37	36	adantl 277	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( w e. Fin <-> suc v e. Fin ) )
38	35, 37	mpbird 167	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> w e. Fin )
39		fin0 6943	. . . . . . . . . . . . 13 |- ( w e. Fin -> ( w =/= (/) <-> E. z z e. w ) )
40	38, 39	syl 14	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) <-> E. z z e. w ) )
41		simpll 527	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> v e. om )
42		dif1en 6937	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
43	42	3expa 1205	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( w \ { z } ) ~~ v )
44		fidifsnid 6929	. . . . . . . . . . . . . . . . 17 |- ( ( w e. Fin /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
45	38, 44	sylan 283	. . . . . . . . . . . . . . . 16 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
46		vex 2763	. . . . . . . . . . . . . . . . . . 19 |- w e. _V
47		difexg 4171	. . . . . . . . . . . . . . . . . . 19 |- ( w e. _V -> ( w \ { z } ) e. _V )
48	46, 47	ax-mp 5	. . . . . . . . . . . . . . . . . 18 |- ( w \ { z } ) e. _V
49		breq1 4033	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
50	49	anbi2d 464	. . . . . . . . . . . . . . . . . . 19 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
51		uneq1 3307	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
52	51	sbceq1d 2991	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
53	52	imbi2d 230	. . . . . . . . . . . . . . . . . . 19 |- ( y = ( w \ { z } ) -> ( ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) <-> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) ) )
54	50, 53	imbi12d 234	. . . . . . . . . . . . . . . . . 18 |- ( 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 ) ) ) )
55		breq1 4033	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
56		findcard2.2	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = y -> ( ph <-> ch ) )
57	55, 56	imbi12d 234	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
58	57	spv 1871	. . . . . . . . . . . . . . . . . . . 20 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
59		rspe 2543	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
60		isfi 6817	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y e. Fin <-> E. v e. om y ~~ v )
61	59, 60	sylibr 134	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( v e. om /\ y ~~ v ) -> y e. Fin )
62		pm2.27 40	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
63	62	adantl 277	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
64		findcard2.6	. . . . . . . . . . . . . . . . . . . . 21 |- ( y e. Fin -> ( ch -> th ) )
65	61, 63, 64	sylsyld 58	. . . . . . . . . . . . . . . . . . . 20 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> th ) )
66	58, 65	syl5 32	. . . . . . . . . . . . . . . . . . 19 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> th ) )
67		vex 2763	. . . . . . . . . . . . . . . . . . . . 21 |- y e. _V
68		vex 2763	. . . . . . . . . . . . . . . . . . . . . 22 |- z e. _V
69	68	snex 4215	. . . . . . . . . . . . . . . . . . . . 21 |- { z } e. _V
70	67, 69	unex 4473	. . . . . . . . . . . . . . . . . . . 20 |- ( y u. { z } ) e. _V
71		findcard2.3	. . . . . . . . . . . . . . . . . . . 20 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
72	70, 71	sbcie 3021	. . . . . . . . . . . . . . . . . . 19 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
73	66, 72	imbitrrdi 162	. . . . . . . . . . . . . . . . . 18 |- ( ( v e. om /\ y ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
74	48, 54, 73	vtocl 2815	. . . . . . . . . . . . . . . . 17 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
75		dfsbcq 2988	. . . . . . . . . . . . . . . . . 18 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
76	75	imbi2d 230	. . . . . . . . . . . . . . . . 17 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) <-> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
77	74, 76	imbitrid 154	. . . . . . . . . . . . . . . 16 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
78	45, 77	syl 14	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
79	41, 43, 78	mp2and 433	. . . . . . . . . . . . . 14 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) )
80	79	ex 115	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
81	80	exlimdv 1830	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
82	40, 81	sylbid 150	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
83	82	ex 115	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
84	32, 83	mpdd 41	. . . . . . . . 9 |- ( v e. om -> ( w ~~ suc v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
85	84	com23 78	. . . . . . . 8 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> ( w ~~ suc v -> [. w / x ]. ph ) ) )
86	85	alrimdv 1887	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
87		nfv 1539	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
88		nfv 1539	. . . . . . . . 9 |- F/ x w ~~ suc v
89		nfsbc1v 3005	. . . . . . . . 9 |- F/ x [. w / x ]. ph
90	88, 89	nfim 1583	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
91		breq1 4033	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
92		sbceq1a 2996	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
93	91, 92	imbi12d 234	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
94	87, 90, 93	cbval 1765	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
95	86, 94	imbitrrdi 162	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
96	5, 8, 11, 17, 95	finds1 4635	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
97	96	19.21bi 1569	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
98	97	rexlimiv 2605	. . 3 |- ( E. w e. om x ~~ w -> ph )
99	2, 98	sylbi 121	. 2 |- ( x e. Fin -> ph )
100	1, 99	vtoclga 2827	1 |- ( A e. Fin -> ta )

Syntax hints:   -> wi 4   /\ wa 104   <-> wb 105   A.wal 1362   = wceq 1364   E.wex 1503   e. wcel 2164   =/= wne 2364   E.wrex 2473   _Vcvv 2760   [.wsbc 2986   \ cdif 3151   u. cun 3152   (/)c0 3447   {csn 3619   class class class wbr 4030   suc csuc 4397   omcom 4623   ~~ cen 6794   Fincfn 6796

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 615  ax-in2 616  ax-io 710  ax-5 1458  ax-7 1459  ax-gen 1460  ax-ie1 1504  ax-ie2 1505  ax-8 1515  ax-10 1516  ax-11 1517  ax-i12 1518  ax-bndl 1520  ax-4 1521  ax-17 1537  ax-i9 1541  ax-ial 1545  ax-i5r 1546  ax-13 2166  ax-14 2167  ax-ext 2175  ax-coll 4145  ax-sep 4148  ax-nul 4156  ax-pow 4204  ax-pr 4239  ax-un 4465  ax-setind 4570  ax-iinf 4621

This theorem depends on definitions:  df-bi 117  df-dc 836  df-3or 981  df-3an 982  df-tru 1367  df-fal 1370  df-nf 1472  df-sb 1774  df-eu 2045  df-mo 2046  df-clab 2180  df-cleq 2186  df-clel 2189  df-nfc 2325  df-ne 2365  df-ral 2477  df-rex 2478  df-reu 2479  df-rab 2481  df-v 2762  df-sbc 2987  df-csb 3082  df-dif 3156  df-un 3158  df-in 3160  df-ss 3167  df-nul 3448  df-if 3559  df-pw 3604  df-sn 3625  df-pr 3626  df-op 3628  df-uni 3837  df-int 3872  df-iun 3915  df-br 4031  df-opab 4092  df-mpt 4093  df-tr 4129  df-id 4325  df-iord 4398  df-on 4400  df-suc 4403  df-iom 4624  df-xp 4666  df-rel 4667  df-cnv 4668  df-co 4669  df-dm 4670  df-rn 4671  df-res 4672  df-ima 4673  df-iota 5216  df-fun 5257  df-fn 5258  df-f 5259  df-f1 5260  df-fo 5261  df-f1o 5262  df-fv 5263  df-er 6589  df-en 6797  df-fin 6799

This theorem is referenced by:  finomni  7201  rexfiuz  11136  fimaxre2  11373