Theorem findcard2s 7048

Description: Variation of findcard2 7047 requiring that the element added in the induction step not be a member of the original set. (Contributed by Paul Chapman, 30-Nov-2012.)

Hypotheses

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

Assertion

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

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

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

Proof of Theorem findcard2s

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

Step	Hyp	Ref	Expression
1		findcard2s.4	. 2 |- ( x = A -> ( ph <-> ta ) )
2		isfi 6910	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4086	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 231	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1870	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4086	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 231	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1870	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4086	. . . . . . . 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 1870	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6945	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2s.5	. . . . . . . . 9 |- ps
14		findcard2s.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 1495	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4687	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 276	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 4085	. . . . . . . . . . . . . . . 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 4685	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4686	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 7014	. . . . . . . . . . . . . . . . . 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 2235	. . . . . . . . . . . . . . 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 2444	. . . . . . . . . . . 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 7030	. . . . . . . . . . . . . . . 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 7031	. . . . . . . . . . . . . . 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 7043	. . . . . . . . . . . . 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 7037	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
43	42	3expa 1227	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( w \ { z } ) ~~ v )
44		fidifsnid 7029	. . . . . . . . . . . . . . . . 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		neldifsn 3797	. . . . . . . . . . . . . . . . . 18 |- -. z e. ( w \ { z } )
47		vex 2802	. . . . . . . . . . . . . . . . . . . 20 |- w e. _V
48		difexg 4224	. . . . . . . . . . . . . . . . . . . 20 |- ( w e. _V -> ( w \ { z } ) e. _V )
49	47, 48	ax-mp 5	. . . . . . . . . . . . . . . . . . 19 |- ( w \ { z } ) e. _V
50		breq1 4085	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
51	50	anbi2d 464	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
52		eleq2 2293	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( z e. y <-> z e. ( w \ { z } ) ) )
53	52	notbid 671	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( -. z e. y <-> -. z e. ( w \ { z } ) ) )
54	51, 53	anbi12d 473	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) <-> ( ( v e. om /\ ( w \ { z } ) ~~ v ) /\ -. z e. ( w \ { z } ) ) ) )
55		uneq1 3351	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
56	55	sbceq1d 3033	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
57	56	imbi2d 230	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) <-> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) ) )
58	54, 57	imbi12d 234	. . . . . . . . . . . . . . . . . . 19 |- ( y = ( w \ { z } ) -> ( ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) ) <-> ( ( ( v e. om /\ ( w \ { z } ) ~~ v ) /\ -. z e. ( w \ { z } ) ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) ) ) )
59		breq1 4085	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
60		findcard2s.2	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( ph <-> ch ) )
61	59, 60	imbi12d 234	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
62	61	spv 1906	. . . . . . . . . . . . . . . . . . . . 21 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
63		pm2.27 40	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
64	63	adantl 277	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
65	64	adantr 276	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ( y ~~ v -> ch ) -> ch ) )
66		rspe 2579	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
67		isfi 6910	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y e. Fin <-> E. v e. om y ~~ v )
68	66, 67	sylibr 134	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> y e. Fin )
69		findcard2s.6	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( y e. Fin /\ -. z e. y ) -> ( ch -> th ) )
70	68, 69	sylan 283	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ch -> th ) )
71	65, 70	syld 45	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ( y ~~ v -> ch ) -> th ) )
72	62, 71	syl5 32	. . . . . . . . . . . . . . . . . . . 20 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( A. x ( x ~~ v -> ph ) -> th ) )
73		vex 2802	. . . . . . . . . . . . . . . . . . . . . 22 |- y e. _V
74		vex 2802	. . . . . . . . . . . . . . . . . . . . . . 23 |- z e. _V
75	74	snex 4268	. . . . . . . . . . . . . . . . . . . . . 22 |- { z } e. _V
76	73, 75	unex 4531	. . . . . . . . . . . . . . . . . . . . 21 |- ( y u. { z } ) e. _V
77		findcard2s.3	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
78	76, 77	sbcie 3063	. . . . . . . . . . . . . . . . . . . 20 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
79	72, 78	imbitrrdi 162	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
80	49, 58, 79	vtocl 2855	. . . . . . . . . . . . . . . . . 18 |- ( ( ( v e. om /\ ( w \ { z } ) ~~ v ) /\ -. z e. ( w \ { z } ) ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
81	46, 80	mpan2 425	. . . . . . . . . . . . . . . . 17 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
82		dfsbcq 3030	. . . . . . . . . . . . . . . . . 18 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
83	82	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 ) ) )
84	81, 83	imbitrid 154	. . . . . . . . . . . . . . . 16 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
85	45, 84	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 ) ) )
86	41, 43, 85	mp2and 433	. . . . . . . . . . . . . 14 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) )
87	86	ex 115	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
88	87	exlimdv 1865	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
89	40, 88	sylbid 150	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
90	89	ex 115	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
91	32, 90	mpdd 41	. . . . . . . . 9 |- ( v e. om -> ( w ~~ suc v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
92	91	com23 78	. . . . . . . 8 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> ( w ~~ suc v -> [. w / x ]. ph ) ) )
93	92	alrimdv 1922	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
94		nfv 1574	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
95		nfv 1574	. . . . . . . . 9 |- F/ x w ~~ suc v
96		nfsbc1v 3047	. . . . . . . . 9 |- F/ x [. w / x ]. ph
97	95, 96	nfim 1618	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
98		breq1 4085	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
99		sbceq1a 3038	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
100	98, 99	imbi12d 234	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
101	94, 97, 100	cbval 1800	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
102	93, 101	imbitrrdi 162	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
103	5, 8, 11, 17, 102	finds1 4693	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
104	103	19.21bi 1604	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
105	104	rexlimiv 2642	. . 3 |- ( E. w e. om x ~~ w -> ph )
106	2, 105	sylbi 121	. 2 |- ( x e. Fin -> ph )
107	1, 106	vtoclga 2867	1 |- ( A e. Fin -> ta )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 104   <-> wb 105   A.wal 1393   = wceq 1395   E.wex 1538   e. wcel 2200   =/= wne 2400   E.wrex 2509   _Vcvv 2799   [.wsbc 3028   \ cdif 3194   u. cun 3195   (/)c0 3491   {csn 3666   class class class wbr 4082   suc csuc 4455   omcom 4681   ~~ cen 6883   Fincfn 6885

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 617  ax-in2 618  ax-io 714  ax-5 1493  ax-7 1494  ax-gen 1495  ax-ie1 1539  ax-ie2 1540  ax-8 1550  ax-10 1551  ax-11 1552  ax-i12 1553  ax-bndl 1555  ax-4 1556  ax-17 1572  ax-i9 1576  ax-ial 1580  ax-i5r 1581  ax-13 2202  ax-14 2203  ax-ext 2211  ax-coll 4198  ax-sep 4201  ax-nul 4209  ax-pow 4257  ax-pr 4292  ax-un 4523  ax-setind 4628  ax-iinf 4679

This theorem depends on definitions:  df-bi 117  df-dc 840  df-3or 1003  df-3an 1004  df-tru 1398  df-fal 1401  df-nf 1507  df-sb 1809  df-eu 2080  df-mo 2081  df-clab 2216  df-cleq 2222  df-clel 2225  df-nfc 2361  df-ne 2401  df-ral 2513  df-rex 2514  df-reu 2515  df-rab 2517  df-v 2801  df-sbc 3029  df-csb 3125  df-dif 3199  df-un 3201  df-in 3203  df-ss 3210  df-nul 3492  df-if 3603  df-pw 3651  df-sn 3672  df-pr 3673  df-op 3675  df-uni 3888  df-int 3923  df-iun 3966  df-br 4083  df-opab 4145  df-mpt 4146  df-tr 4182  df-id 4383  df-iord 4456  df-on 4458  df-suc 4461  df-iom 4682  df-xp 4724  df-rel 4725  df-cnv 4726  df-co 4727  df-dm 4728  df-rn 4729  df-res 4730  df-ima 4731  df-iota 5277  df-fun 5319  df-fn 5320  df-f 5321  df-f1 5322  df-fo 5323  df-f1o 5324  df-fv 5325  df-er 6678  df-en 6886  df-fin 6888

This theorem is referenced by:  findcard2d  7049  findcard2sd  7050  diffifi  7052  ac6sfi  7056  fisseneq  7092  fsum2d  11941  modfsummod  11964  fsumabs  11971  fsumiun  11983  fprod2d  12129  dvmptfsum  15393