Theorem findcard2s 6374

Description: Variation of findcard2 6373 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 6264	. . 3 |- ( x e. Fin <-> E. w e. om x ~~ w )
3		breq2 3789	. . . . . . . 8 |- ( w = (/) -> ( x ~~ w <-> x ~~ (/) ) )
4	3	imbi1d 229	. . . . . . 7 |- ( w = (/) -> ( ( x ~~ w -> ph ) <-> ( x ~~ (/) -> ph ) ) )
5	4	albidv 1745	. . . . . 6 |- ( w = (/) -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ (/) -> ph ) ) )
6		breq2 3789	. . . . . . . 8 |- ( w = v -> ( x ~~ w <-> x ~~ v ) )
7	6	imbi1d 229	. . . . . . 7 |- ( w = v -> ( ( x ~~ w -> ph ) <-> ( x ~~ v -> ph ) ) )
8	7	albidv 1745	. . . . . 6 |- ( w = v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ v -> ph ) ) )
9		breq2 3789	. . . . . . . 8 |- ( w = suc v -> ( x ~~ w <-> x ~~ suc v ) )
10	9	imbi1d 229	. . . . . . 7 |- ( w = suc v -> ( ( x ~~ w -> ph ) <-> ( x ~~ suc v -> ph ) ) )
11	10	albidv 1745	. . . . . 6 |- ( w = suc v -> ( A. x ( x ~~ w -> ph ) <-> A. x ( x ~~ suc v -> ph ) ) )
12		en0 6298	. . . . . . . 8 |- ( x ~~ (/) <-> x = (/) )
13		findcard2s.5	. . . . . . . . 9 |- ps
14		findcard2s.1	. . . . . . . . 9 |- ( x = (/) -> ( ph <-> ps ) )
15	13, 14	mpbiri 166	. . . . . . . 8 |- ( x = (/) -> ph )
16	12, 15	sylbi 119	. . . . . . 7 |- ( x ~~ (/) -> ph )
17	16	ax-gen 1378	. . . . . 6 |- A. x ( x ~~ (/) -> ph )
18		peano3 4337	. . . . . . . . . . . . 13 |- ( v e. om -> suc v =/= (/) )
19	18	adantr 270	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> suc v =/= (/) )
20		breq1 3788	. . . . . . . . . . . . . . . 16 |- ( w = (/) -> ( w ~~ suc v <-> (/) ~~ suc v ) )
21	20	anbi2d 451	. . . . . . . . . . . . . . 15 |- ( w = (/) -> ( ( v e. om /\ w ~~ suc v ) <-> ( v e. om /\ (/) ~~ suc v ) ) )
22		peano1 4335	. . . . . . . . . . . . . . . . . 18 |- (/) e. om
23		peano2 4336	. . . . . . . . . . . . . . . . . 18 |- ( v e. om -> suc v e. om )
24		nneneq 6343	. . . . . . . . . . . . . . . . . 18 |- ( ( (/) e. om /\ suc v e. om ) -> ( (/) ~~ suc v <-> (/) = suc v ) )
25	22, 23, 24	sylancr 405	. . . . . . . . . . . . . . . . 17 |- ( v e. om -> ( (/) ~~ suc v <-> (/) = suc v ) )
26	25	biimpa 290	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ (/) ~~ suc v ) -> (/) = suc v )
27	26	eqcomd 2086	. . . . . . . . . . . . . . 15 |- ( ( v e. om /\ (/) ~~ suc v ) -> suc v = (/) )
28	21, 27	syl6bi 161	. . . . . . . . . . . . . 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 2289	. . . . . . . . . . . 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 113	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> w =/= (/) ) )
33		nnfi 6357	. . . . . . . . . . . . . . . 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 270	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> suc v e. Fin )
36		enfi 6358	. . . . . . . . . . . . . . 15 |- ( w ~~ suc v -> ( w e. Fin <-> suc v e. Fin ) )
37	36	adantl 271	. . . . . . . . . . . . . 14 |- ( ( v e. om /\ w ~~ suc v ) -> ( w e. Fin <-> suc v e. Fin ) )
38	35, 37	mpbird 165	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> w e. Fin )
39		fin0 6369	. . . . . . . . . . . . 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 495	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> v e. om )
42		dif1en 6364	. . . . . . . . . . . . . . . 16 |- ( ( v e. om /\ w ~~ suc v /\ z e. w ) -> ( w \ { z } ) ~~ v )
43	42	3expa 1138	. . . . . . . . . . . . . . 15 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( w \ { z } ) ~~ v )
44		fidifsnid 6356	. . . . . . . . . . . . . . . . 17 |- ( ( w e. Fin /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
45	38, 44	sylan 277	. . . . . . . . . . . . . . . 16 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( ( w \ { z } ) u. { z } ) = w )
46		neldifsn 3519	. . . . . . . . . . . . . . . . . 18 |- -. z e. ( w \ { z } )
47		vex 2604	. . . . . . . . . . . . . . . . . . . 20 |- w e. _V
48		difexg 3919	. . . . . . . . . . . . . . . . . . . 20 |- ( w e. _V -> ( w \ { z } ) e. _V )
49	47, 48	ax-mp 7	. . . . . . . . . . . . . . . . . . 19 |- ( w \ { z } ) e. _V
50		breq1 3788	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y ~~ v <-> ( w \ { z } ) ~~ v ) )
51	50	anbi2d 451	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( ( v e. om /\ y ~~ v ) <-> ( v e. om /\ ( w \ { z } ) ~~ v ) ) )
52		eleq2 2142	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( z e. y <-> z e. ( w \ { z } ) ) )
53	52	notbid 624	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( -. z e. y <-> -. z e. ( w \ { z } ) ) )
54	51, 53	anbi12d 456	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( w \ { z } ) -> ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) <-> ( ( v e. om /\ ( w \ { z } ) ~~ v ) /\ -. z e. ( w \ { z } ) ) ) )
55		uneq1 3119	. . . . . . . . . . . . . . . . . . . . . 22 |- ( y = ( w \ { z } ) -> ( y u. { z } ) = ( ( w \ { z } ) u. { z } ) )
56	55	sbceq1d 2820	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( w \ { z } ) -> ( [. ( y u. { z } ) / x ]. ph <-> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
57	56	imbi2d 228	. . . . . . . . . . . . . . . . . . . 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 232	. . . . . . . . . . . . . . . . . . 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 3788	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( x ~~ v <-> y ~~ v ) )
60		findcard2s.2	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( x = y -> ( ph <-> ch ) )
61	59, 60	imbi12d 232	. . . . . . . . . . . . . . . . . . . . . 22 |- ( x = y -> ( ( x ~~ v -> ph ) <-> ( y ~~ v -> ch ) ) )
62	61	spv 1781	. . . . . . . . . . . . . . . . . . . . 21 |- ( A. x ( x ~~ v -> ph ) -> ( y ~~ v -> ch ) )
63		pm2.27 39	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y ~~ v -> ( ( y ~~ v -> ch ) -> ch ) )
64	63	adantl 271	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( v e. om /\ y ~~ v ) -> ( ( y ~~ v -> ch ) -> ch ) )
65	64	adantr 270	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ( y ~~ v -> ch ) -> ch ) )
66		rspe 2412	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( v e. om /\ y ~~ v ) -> E. v e. om y ~~ v )
67		isfi 6264	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( y e. Fin <-> E. v e. om y ~~ v )
68	66, 67	sylibr 132	. . . . . . . . . . . . . . . . . . . . . . 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 277	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( ch -> th ) )
71	65, 70	syld 44	. . . . . . . . . . . . . . . . . . . . 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 2604	. . . . . . . . . . . . . . . . . . . . . 22 |- y e. _V
74		vex 2604	. . . . . . . . . . . . . . . . . . . . . . 23 |- z e. _V
75	74	snex 3957	. . . . . . . . . . . . . . . . . . . . . 22 |- { z } e. _V
76	73, 75	unex 4194	. . . . . . . . . . . . . . . . . . . . 21 |- ( y u. { z } ) e. _V
77		findcard2s.3	. . . . . . . . . . . . . . . . . . . . 21 |- ( x = ( y u. { z } ) -> ( ph <-> th ) )
78	76, 77	sbcie 2848	. . . . . . . . . . . . . . . . . . . 20 |- ( [. ( y u. { z } ) / x ]. ph <-> th )
79	72, 78	syl6ibr 160	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( v e. om /\ y ~~ v ) /\ -. z e. y ) -> ( A. x ( x ~~ v -> ph ) -> [. ( y u. { z } ) / x ]. ph ) )
80	49, 58, 79	vtocl 2653	. . . . . . . . . . . . . . . . . 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 415	. . . . . . . . . . . . . . . . 17 |- ( ( v e. om /\ ( w \ { z } ) ~~ v ) -> ( A. x ( x ~~ v -> ph ) -> [. ( ( w \ { z } ) u. { z } ) / x ]. ph ) )
82		dfsbcq 2817	. . . . . . . . . . . . . . . . . 18 |- ( ( ( w \ { z } ) u. { z } ) = w -> ( [. ( ( w \ { z } ) u. { z } ) / x ]. ph <-> [. w / x ]. ph ) )
83	82	imbi2d 228	. . . . . . . . . . . . . . . . 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 152	. . . . . . . . . . . . . . . 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 423	. . . . . . . . . . . . . 14 |- ( ( ( v e. om /\ w ~~ suc v ) /\ z e. w ) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) )
87	86	ex 113	. . . . . . . . . . . . 13 |- ( ( v e. om /\ w ~~ suc v ) -> ( z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
88	87	exlimdv 1740	. . . . . . . . . . . 12 |- ( ( v e. om /\ w ~~ suc v ) -> ( E. z z e. w -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
89	40, 88	sylbid 148	. . . . . . . . . . 11 |- ( ( v e. om /\ w ~~ suc v ) -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
90	89	ex 113	. . . . . . . . . 10 |- ( v e. om -> ( w ~~ suc v -> ( w =/= (/) -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) ) )
91	32, 90	mpdd 40	. . . . . . . . 9 |- ( v e. om -> ( w ~~ suc v -> ( A. x ( x ~~ v -> ph ) -> [. w / x ]. ph ) ) )
92	91	com23 77	. . . . . . . 8 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> ( w ~~ suc v -> [. w / x ]. ph ) ) )
93	92	alrimdv 1797	. . . . . . 7 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. w ( w ~~ suc v -> [. w / x ]. ph ) ) )
94		nfv 1461	. . . . . . . 8 |- F/ w ( x ~~ suc v -> ph )
95		nfv 1461	. . . . . . . . 9 |- F/ x w ~~ suc v
96		nfsbc1v 2833	. . . . . . . . 9 |- F/ x [. w / x ]. ph
97	95, 96	nfim 1504	. . . . . . . 8 |- F/ x ( w ~~ suc v -> [. w / x ]. ph )
98		breq1 3788	. . . . . . . . 9 |- ( x = w -> ( x ~~ suc v <-> w ~~ suc v ) )
99		sbceq1a 2824	. . . . . . . . 9 |- ( x = w -> ( ph <-> [. w / x ]. ph ) )
100	98, 99	imbi12d 232	. . . . . . . 8 |- ( x = w -> ( ( x ~~ suc v -> ph ) <-> ( w ~~ suc v -> [. w / x ]. ph ) ) )
101	94, 97, 100	cbval 1677	. . . . . . 7 |- ( A. x ( x ~~ suc v -> ph ) <-> A. w ( w ~~ suc v -> [. w / x ]. ph ) )
102	93, 101	syl6ibr 160	. . . . . 6 |- ( v e. om -> ( A. x ( x ~~ v -> ph ) -> A. x ( x ~~ suc v -> ph ) ) )
103	5, 8, 11, 17, 102	finds1 4343	. . . . 5 |- ( w e. om -> A. x ( x ~~ w -> ph ) )
104	103	19.21bi 1490	. . . 4 |- ( w e. om -> ( x ~~ w -> ph ) )
105	104	rexlimiv 2471	. . 3 |- ( E. w e. om x ~~ w -> ph )
106	2, 105	sylbi 119	. 2 |- ( x e. Fin -> ph )
107	1, 106	vtoclga 2664	1 |- ( A e. Fin -> ta )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 102   <-> wb 103   A.wal 1282   = wceq 1284   E.wex 1421   e. wcel 1433   =/= wne 2245   E.wrex 2349   _Vcvv 2601   [.wsbc 2815   \ cdif 2970   u. cun 2971   (/)c0 3251   {csn 3398   class class class wbr 3785   suc csuc 4120   omcom 4331   ~~ cen 6242   Fincfn 6244

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 576  ax-in2 577  ax-io 662  ax-5 1376  ax-7 1377  ax-gen 1378  ax-ie1 1422  ax-ie2 1423  ax-8 1435  ax-10 1436  ax-11 1437  ax-i12 1438  ax-bndl 1439  ax-4 1440  ax-13 1444  ax-14 1445  ax-17 1459  ax-i9 1463  ax-ial 1467  ax-i5r 1468  ax-ext 2063  ax-coll 3893  ax-sep 3896  ax-nul 3904  ax-pow 3948  ax-pr 3964  ax-un 4188  ax-setind 4280  ax-iinf 4329

This theorem depends on definitions:  df-bi 115  df-dc 776  df-3or 920  df-3an 921  df-tru 1287  df-fal 1290  df-nf 1390  df-sb 1686  df-eu 1944  df-mo 1945  df-clab 2068  df-cleq 2074  df-clel 2077  df-nfc 2208  df-ne 2246  df-ral 2353  df-rex 2354  df-reu 2355  df-rab 2357  df-v 2603  df-sbc 2816  df-csb 2909  df-dif 2975  df-un 2977  df-in 2979  df-ss 2986  df-nul 3252  df-if 3352  df-pw 3384  df-sn 3404  df-pr 3405  df-op 3407  df-uni 3602  df-int 3637  df-iun 3680  df-br 3786  df-opab 3840  df-mpt 3841  df-tr 3876  df-id 4048  df-iord 4121  df-on 4123  df-suc 4126  df-iom 4332  df-xp 4369  df-rel 4370  df-cnv 4371  df-co 4372  df-dm 4373  df-rn 4374  df-res 4375  df-ima 4376  df-iota 4887  df-fun 4924  df-fn 4925  df-f 4926  df-f1 4927  df-fo 4928  df-f1o 4929  df-fv 4930  df-er 6129  df-en 6245  df-fin 6247

This theorem is referenced by:  findcard2d  6375  findcard2sd  6376  diffifi  6378  ac6sfi  6379