Theorem findcard2s 6969

Description: Variation of findcard2 6968 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 6838	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 4047	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 231	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1846	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 4047	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 231	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1846	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 4047	. . . . . . . 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 1846	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6872	. . . . . . . 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 1471	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4642	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 276	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 4046	. . . . . . . . . . . . . . . 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 4640	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4641	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 6936	. . . . . . . . . . . . . . . . . 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 2210	. . . . . . . . . . . . . . 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 2419	. . . . . . . . . . . 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 6951	. . . . . . . . . . . . . . . 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 6952	. . . . . . . . . . . . . . 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 6964	. . . . . . . . . . . . 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 6958	. . . . . . . . . . . . . . . 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 6950	. . . . . . . . . . . . . . . . 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 3762	. . . . . . . . . . . . . . . . . 18 |- -. z e. ( w \ { z } )
47		vex 2774	. . . . . . . . . . . . . . . . . . . 20 |- w e. _V
48		difexg 4184	. . . . . . . . . . . . . . . . . . . 20 |- ( w e. _V -> ( w \ { z } ) e. _V )
49	47, 48	ax-mp 5	. . . . . . . . . . . . . . . . . . 19 |- ( w \ { z } ) e. _V
50		breq1 4046	. . . . . . . . . . . . . . . . . . . . . 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 2268	. . . . . . . . . . . . . . . . . . . . . 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 3319	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
56	55	sbceq1d 3002	. . . . . . . . . . . . . . . . . . . . 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 4046	. . . . . . . . . . . . . . . . . . . . . . 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 1882	. . . . . . . . . . . . . . . . . . . . 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 2554	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
67		isfi 6838	. . . . . . . . . . . . . . . . . . . . . . . 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 2774	. . . . . . . . . . . . . . . . . . . . . 22 |- y e. _V
74		vex 2774	. . . . . . . . . . . . . . . . . . . . . . 23 |- z e. _V
75	74	snex 4228	. . . . . . . . . . . . . . . . . . . . . 22 |- { z } e. _V
76	73, 75	unex 4486	. . . . . . . . . . . . . . . . . . . . 21 |- ( y u. { z } ) e. _V
77		findcard2s.3	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
78	76, 77	sbcie 3032	. . . . . . . . . . . . . . . . . . . 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 2826	. . . . . . . . . . . . . . . . . 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 2999	. . . . . . . . . . . . . . . . . 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 1841	. . . . . . . . . . . 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 1898	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
94		nfv 1550	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
95		nfv 1550	. . . . . . . . 9 |- F/ x w ~~ suc v
96		nfsbc1v 3016	. . . . . . . . 9 |- F/ x [. w / x ]. ph
97	95, 96	nfim 1594	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
98		breq1 4046	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
99		sbceq1a 3007	. . . . . . . . 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 1776	. . . . . . 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 4648	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
104	103	19.21bi 1580	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
105	104	rexlimiv 2616	. . 3 |- ( E. w e. om x ~~ w -> ph )
106	2, 105	sylbi 121	. 2 |- ( x e. Fin -> ph )
107	1, 106	vtoclga 2838	1 |- ( A e. Fin -> ta )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 104   <-> wb 105   A.wal 1370   = wceq 1372   E.wex 1514   e. wcel 2175   =/= wne 2375   E.wrex 2484   _Vcvv 2771   [.wsbc 2997   \ cdif 3162   u. cun 3163   (/)c0 3459   {csn 3632   class class class wbr 4043   suc csuc 4410   omcom 4636   ~~ cen 6815   Fincfn 6817

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 1469  ax-7 1470  ax-gen 1471  ax-ie1 1515  ax-ie2 1516  ax-8 1526  ax-10 1527  ax-11 1528  ax-i12 1529  ax-bndl 1531  ax-4 1532  ax-17 1548  ax-i9 1552  ax-ial 1556  ax-i5r 1557  ax-13 2177  ax-14 2178  ax-ext 2186  ax-coll 4158  ax-sep 4161  ax-nul 4169  ax-pow 4217  ax-pr 4252  ax-un 4478  ax-setind 4583  ax-iinf 4634

This theorem depends on definitions:  df-bi 117  df-dc 836  df-3or 981  df-3an 982  df-tru 1375  df-fal 1378  df-nf 1483  df-sb 1785  df-eu 2056  df-mo 2057  df-clab 2191  df-cleq 2197  df-clel 2200  df-nfc 2336  df-ne 2376  df-ral 2488  df-rex 2489  df-reu 2490  df-rab 2492  df-v 2773  df-sbc 2998  df-csb 3093  df-dif 3167  df-un 3169  df-in 3171  df-ss 3178  df-nul 3460  df-if 3571  df-pw 3617  df-sn 3638  df-pr 3639  df-op 3641  df-uni 3850  df-int 3885  df-iun 3928  df-br 4044  df-opab 4105  df-mpt 4106  df-tr 4142  df-id 4338  df-iord 4411  df-on 4413  df-suc 4416  df-iom 4637  df-xp 4679  df-rel 4680  df-cnv 4681  df-co 4682  df-dm 4683  df-rn 4684  df-res 4685  df-ima 4686  df-iota 5229  df-fun 5270  df-fn 5271  df-f 5272  df-f1 5273  df-fo 5274  df-f1o 5275  df-fv 5276  df-er 6610  df-en 6818  df-fin 6820

This theorem is referenced by:  findcard2d  6970  findcard2sd  6971  diffifi  6973  ac6sfi  6977  fisseneq  7013  fsum2d  11665  modfsummod  11688  fsumabs  11695  fsumiun  11707  fprod2d  11853  dvmptfsum  15115