Theorem findcard2s 6856

Description: Variation of findcard2 6855 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 6727	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 3986	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 230	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1812	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 3986	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 230	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1812	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 3986	. . . . . . . 8 |- ( w = suc v -> ( x ~~ w <-> x ~~ suc v ) )
10	9	imbi1d 230	. . . . . . 7 |- ( w = suc v -> ( ( x ~~ w -> ph ) <-> ( x ~~ suc v -> ph ) ) )
11	10	albidv 1812	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6761	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2s.5	. . . . . . . . 9 |- ps
14		findcard2s.1	. . . . . . . . 9 |- ( x = (/) -> ( ph <-> ps ) )
15	13, 14	mpbiri 167	. . . . . . . 8 |- ( x = (/) -> ph )
16	12, 15	sylbi 120	. . . . . . 7 |- ( x ~~ (/) -> ph )
17	16	ax-gen 1437	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4573	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 274	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 3985	. . . . . . . . . . . . . . . 16 |- ( w = (/) -> ( w ~~ suc v <-> (/) ~~ suc v ) )
21	20	anbi2d 460	. . . . . . . . . . . . . . 15 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) <-> ( v e. om /\ (/) ~~ suc v ) ) )
22		peano1 4571	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4572	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 6823	. . . . . . . . . . . . . . . . . 18 |- ( ( (/) e. om /\ suc v e. om ) -> ( (/) ~~ suc v <-> (/) = suc v ) )
25	22, 23, 24	sylancr 411	. . . . . . . . . . . . . . . . 17 |- ( v e. om -> ( (/) ~~ suc v <-> (/) = suc v ) )
26	25	biimpa 294	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ (/) ~~ suc v ) -> (/) = suc v )
27	26	eqcomd 2171	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ (/) ~~ suc v ) -> suc v = (/) )
28	21, 27	syl6bi 162	. . . . . . . . . . . . . 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 2380	. . . . . . . . . . . 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 114	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> w =/= (/) ) )
33		nnfi 6838	. . . . . . . . . . . . . . . 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 274	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> suc v e. Fin )
36		enfi 6839	. . . . . . . . . . . . . . 15 |- ( w ~~ suc v -> ( w e. Fin <-> suc v e. Fin ) )
37	36	adantl 275	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( w e. Fin <-> suc v e. Fin ) )
38	35, 37	mpbird 166	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> w e. Fin )
39		fin0 6851	. . . . . . . . . . . . 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 519	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> v e. om )
42		dif1en 6845	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
43	42	3expa 1193	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( w \ { z } ) ~~ v )
44		fidifsnid 6837	. . . . . . . . . . . . . . . . 17 |- ( ( w e. Fin /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
45	38, 44	sylan 281	. . . . . . . . . . . . . . . 16 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
46		neldifsn 3706	. . . . . . . . . . . . . . . . . 18 |- -. z e. ( w \ { z } )
47		vex 2729	. . . . . . . . . . . . . . . . . . . 20 |- w e. _V
48		difexg 4123	. . . . . . . . . . . . . . . . . . . 20 |- ( w e. _V -> ( w \ { z } ) e. _V )
49	47, 48	ax-mp 5	. . . . . . . . . . . . . . . . . . 19 |- ( w \ { z } ) e. _V
50		breq1 3985	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
51	50	anbi2d 460	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
52		eleq2 2230	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( z e. y <-> z e. ( w \ { z } ) ) )
53	52	notbid 657	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( -. z e. y <-> -. z e. ( w \ { z } ) ) )
54	51, 53	anbi12d 465	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) <-> ( ( v e. om /\ ( w \ { z } ) ~~ v ) /\ -. z e. ( w \ { z } ) ) ) )
55		uneq1 3269	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
56	55	sbceq1d 2956	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
57	56	imbi2d 229	. . . . . . . . . . . . . . . . . . . 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 233	. . . . . . . . . . . . . . . . . . 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 3985	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
60		findcard2s.2	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( ph <-> ch ) )
61	59, 60	imbi12d 233	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
62	61	spv 1848	. . . . . . . . . . . . . . . . . . . . 21 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
63		pm2.27 40	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
64	63	adantl 275	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
65	64	adantr 274	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ( y ~~ v -> ch ) -> ch ) )
66		rspe 2515	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
67		isfi 6727	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y e. Fin <-> E. v e. om y ~~ v )
68	66, 67	sylibr 133	. . . . . . . . . . . . . . . . . . . . . . 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 281	. . . . . . . . . . . . . . . . . . . . . 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 2729	. . . . . . . . . . . . . . . . . . . . . 22 |- y e. _V
74		vex 2729	. . . . . . . . . . . . . . . . . . . . . . 23 |- z e. _V
75	74	snex 4164	. . . . . . . . . . . . . . . . . . . . . 22 |- { z } e. _V
76	73, 75	unex 4419	. . . . . . . . . . . . . . . . . . . . 21 |- ( y u. { z } ) e. _V
77		findcard2s.3	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
78	76, 77	sbcie 2985	. . . . . . . . . . . . . . . . . . . 20 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
79	72, 78	syl6ibr 161	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
80	49, 58, 79	vtocl 2780	. . . . . . . . . . . . . . . . . 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 422	. . . . . . . . . . . . . . . . 17 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
82		dfsbcq 2953	. . . . . . . . . . . . . . . . . 18 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
83	82	imbi2d 229	. . . . . . . . . . . . . . . . 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	syl5ib 153	. . . . . . . . . . . . . . . 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 430	. . . . . . . . . . . . . 14 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) )
87	86	ex 114	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
88	87	exlimdv 1807	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
89	40, 88	sylbid 149	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
90	89	ex 114	. . . . . . . . . 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 1864	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
94		nfv 1516	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
95		nfv 1516	. . . . . . . . 9 |- F/ x w ~~ suc v
96		nfsbc1v 2969	. . . . . . . . 9 |- F/ x [. w / x ]. ph
97	95, 96	nfim 1560	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
98		breq1 3985	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
99		sbceq1a 2960	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
100	98, 99	imbi12d 233	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
101	94, 97, 100	cbval 1742	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
102	93, 101	syl6ibr 161	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
103	5, 8, 11, 17, 102	finds1 4579	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
104	103	19.21bi 1546	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
105	104	rexlimiv 2577	. . 3 |- ( E. w e. om x ~~ w -> ph )
106	2, 105	sylbi 120	. 2 |- ( x e. Fin -> ph )
107	1, 106	vtoclga 2792	1 |- ( A e. Fin -> ta )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 103   <-> wb 104   A.wal 1341   = wceq 1343   E.wex 1480   e. wcel 2136   =/= wne 2336   E.wrex 2445   _Vcvv 2726   [.wsbc 2951   \ cdif 3113   u. cun 3114   (/)c0 3409   {csn 3576   class class class wbr 3982   suc csuc 4343   omcom 4567   ~~ cen 6704   Fincfn 6706

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1435  ax-7 1436  ax-gen 1437  ax-ie1 1481  ax-ie2 1482  ax-8 1492  ax-10 1493  ax-11 1494  ax-i12 1495  ax-bndl 1497  ax-4 1498  ax-17 1514  ax-i9 1518  ax-ial 1522  ax-i5r 1523  ax-13 2138  ax-14 2139  ax-ext 2147  ax-coll 4097  ax-sep 4100  ax-nul 4108  ax-pow 4153  ax-pr 4187  ax-un 4411  ax-setind 4514  ax-iinf 4565

This theorem depends on definitions:  df-bi 116  df-dc 825  df-3or 969  df-3an 970  df-tru 1346  df-fal 1349  df-nf 1449  df-sb 1751  df-eu 2017  df-mo 2018  df-clab 2152  df-cleq 2158  df-clel 2161  df-nfc 2297  df-ne 2337  df-ral 2449  df-rex 2450  df-reu 2451  df-rab 2453  df-v 2728  df-sbc 2952  df-csb 3046  df-dif 3118  df-un 3120  df-in 3122  df-ss 3129  df-nul 3410  df-if 3521  df-pw 3561  df-sn 3582  df-pr 3583  df-op 3585  df-uni 3790  df-int 3825  df-iun 3868  df-br 3983  df-opab 4044  df-mpt 4045  df-tr 4081  df-id 4271  df-iord 4344  df-on 4346  df-suc 4349  df-iom 4568  df-xp 4610  df-rel 4611  df-cnv 4612  df-co 4613  df-dm 4614  df-rn 4615  df-res 4616  df-ima 4617  df-iota 5153  df-fun 5190  df-fn 5191  df-f 5192  df-f1 5193  df-fo 5194  df-f1o 5195  df-fv 5196  df-er 6501  df-en 6707  df-fin 6709

This theorem is referenced by:  findcard2d  6857  findcard2sd  6858  diffifi  6860  ac6sfi  6864  fisseneq  6897  fsum2d  11376  modfsummod  11399  fsumabs  11406  fsumiun  11418  fprod2d  11564