Theorem findcard2s 6951

Description: Variation of findcard2 6950 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 6820	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4037	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 231	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1838	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4037	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 231	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1838	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4037	. . . . . . . 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 1838	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6854	. . . . . . . 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 1463	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4632	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 276	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 4036	. . . . . . . . . . . . . . . 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 4630	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4631	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 6918	. . . . . . . . . . . . . . . . . 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 2202	. . . . . . . . . . . . . . 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 2411	. . . . . . . . . . . 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 6933	. . . . . . . . . . . . . . . 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 6934	. . . . . . . . . . . . . . 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 6946	. . . . . . . . . . . . 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 6940	. . . . . . . . . . . . . . . 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 6932	. . . . . . . . . . . . . . . . 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 3752	. . . . . . . . . . . . . . . . . 18 |- -. z e. ( w \ { z } )
47		vex 2766	. . . . . . . . . . . . . . . . . . . 20 |- w e. _V
48		difexg 4174	. . . . . . . . . . . . . . . . . . . 20 |- ( w e. _V -> ( w \ { z } ) e. _V )
49	47, 48	ax-mp 5	. . . . . . . . . . . . . . . . . . 19 |- ( w \ { z } ) e. _V
50		breq1 4036	. . . . . . . . . . . . . . . . . . . . . 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 2260	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( z e. y <-> z e. ( w \ { z } ) ) )
53	52	notbid 668	. . . . . . . . . . . . . . . . . . . . 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 3310	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
56	55	sbceq1d 2994	. . . . . . . . . . . . . . . . . . . . 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 4036	. . . . . . . . . . . . . . . . . . . . . . 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 1874	. . . . . . . . . . . . . . . . . . . . 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 2546	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
67		isfi 6820	. . . . . . . . . . . . . . . . . . . . . . . 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 2766	. . . . . . . . . . . . . . . . . . . . . 22 |- y e. _V
74		vex 2766	. . . . . . . . . . . . . . . . . . . . . . 23 |- z e. _V
75	74	snex 4218	. . . . . . . . . . . . . . . . . . . . . 22 |- { z } e. _V
76	73, 75	unex 4476	. . . . . . . . . . . . . . . . . . . . 21 |- ( y u. { z } ) e. _V
77		findcard2s.3	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
78	76, 77	sbcie 3024	. . . . . . . . . . . . . . . . . . . 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 2818	. . . . . . . . . . . . . . . . . 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 2991	. . . . . . . . . . . . . . . . . 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 1833	. . . . . . . . . . . 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 1890	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
94		nfv 1542	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
95		nfv 1542	. . . . . . . . 9 |- F/ x w ~~ suc v
96		nfsbc1v 3008	. . . . . . . . 9 |- F/ x [. w / x ]. ph
97	95, 96	nfim 1586	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
98		breq1 4036	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
99		sbceq1a 2999	. . . . . . . . 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 1768	. . . . . . 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 4638	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
104	103	19.21bi 1572	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
105	104	rexlimiv 2608	. . 3 |- ( E. w e. om x ~~ w -> ph )
106	2, 105	sylbi 121	. 2 |- ( x e. Fin -> ph )
107	1, 106	vtoclga 2830	1 |- ( A e. Fin -> ta )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 104   <-> wb 105   A.wal 1362   = wceq 1364   E.wex 1506   e. wcel 2167   =/= wne 2367   E.wrex 2476   _Vcvv 2763   [.wsbc 2989   \ cdif 3154   u. cun 3155   (/)c0 3450   {csn 3622   class class class wbr 4033   suc csuc 4400   omcom 4626   ~~ cen 6797   Fincfn 6799

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 1461  ax-7 1462  ax-gen 1463  ax-ie1 1507  ax-ie2 1508  ax-8 1518  ax-10 1519  ax-11 1520  ax-i12 1521  ax-bndl 1523  ax-4 1524  ax-17 1540  ax-i9 1544  ax-ial 1548  ax-i5r 1549  ax-13 2169  ax-14 2170  ax-ext 2178  ax-coll 4148  ax-sep 4151  ax-nul 4159  ax-pow 4207  ax-pr 4242  ax-un 4468  ax-setind 4573  ax-iinf 4624

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 1475  df-sb 1777  df-eu 2048  df-mo 2049  df-clab 2183  df-cleq 2189  df-clel 2192  df-nfc 2328  df-ne 2368  df-ral 2480  df-rex 2481  df-reu 2482  df-rab 2484  df-v 2765  df-sbc 2990  df-csb 3085  df-dif 3159  df-un 3161  df-in 3163  df-ss 3170  df-nul 3451  df-if 3562  df-pw 3607  df-sn 3628  df-pr 3629  df-op 3631  df-uni 3840  df-int 3875  df-iun 3918  df-br 4034  df-opab 4095  df-mpt 4096  df-tr 4132  df-id 4328  df-iord 4401  df-on 4403  df-suc 4406  df-iom 4627  df-xp 4669  df-rel 4670  df-cnv 4671  df-co 4672  df-dm 4673  df-rn 4674  df-res 4675  df-ima 4676  df-iota 5219  df-fun 5260  df-fn 5261  df-f 5262  df-f1 5263  df-fo 5264  df-f1o 5265  df-fv 5266  df-er 6592  df-en 6800  df-fin 6802

This theorem is referenced by:  findcard2d  6952  findcard2sd  6953  diffifi  6955  ac6sfi  6959  fisseneq  6995  fsum2d  11600  modfsummod  11623  fsumabs  11630  fsumiun  11642  fprod2d  11788  dvmptfsum  14961