MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  findcard3 Unicode version

Theorem findcard3 7288
Description: Schema for strong induction on the cardinality of a finite set. The inductive hypothesis is that the result is true on any proper subset. The result is then proven to be true for all finite sets. (Contributed by Mario Carneiro, 13-Dec-2013.)
Hypotheses
Ref Expression
findcard3.1  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
findcard3.2  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
findcard3.3  |-  ( y  e.  Fin  ->  ( A. x ( x  C.  y  ->  ph )  ->  ch ) )
Assertion
Ref Expression
findcard3  |-  ( A  e.  Fin  ->  ta )
Distinct variable groups:    x, y    ph, y    x, A    ta, x    ch, x
Allowed substitution hints:    ph( x)    ch( y)    ta( y)    A( y)

Proof of Theorem findcard3
Dummy variables  w  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 7069 . . 3  |-  ( A  e.  Fin  <->  E. w  e.  om  A  ~~  w
)
2 nnon 4793 . . . . . 6  |-  ( w  e.  om  ->  w  e.  On )
3 eleq1 2449 . . . . . . . 8  |-  ( w  =  z  ->  (
w  e.  om  <->  z  e.  om ) )
4 breq2 4159 . . . . . . . . . 10  |-  ( w  =  z  ->  (
x  ~~  w  <->  x  ~~  z ) )
54imbi1d 309 . . . . . . . . 9  |-  ( w  =  z  ->  (
( x  ~~  w  ->  ph )  <->  ( x  ~~  z  ->  ph )
) )
65albidv 1632 . . . . . . . 8  |-  ( w  =  z  ->  ( A. x ( x  ~~  w  ->  ph )  <->  A. x
( x  ~~  z  ->  ph ) ) )
73, 6imbi12d 312 . . . . . . 7  |-  ( w  =  z  ->  (
( w  e.  om  ->  A. x ( x 
~~  w  ->  ph )
)  <->  ( z  e. 
om  ->  A. x ( x 
~~  z  ->  ph )
) ) )
8 rspe 2712 . . . . . . . . . . . . . 14  |-  ( ( w  e.  om  /\  y  ~~  w )  ->  E. w  e.  om  y  ~~  w )
9 isfi 7069 . . . . . . . . . . . . . 14  |-  ( y  e.  Fin  <->  E. w  e.  om  y  ~~  w
)
108, 9sylibr 204 . . . . . . . . . . . . 13  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
y  e.  Fin )
11 19.21v 1902 . . . . . . . . . . . . . . . 16  |-  ( A. x ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  <->  ( z  e.  om  ->  A. x
( x  ~~  z  ->  ph ) ) )
1211ralbii 2675 . . . . . . . . . . . . . . 15  |-  ( A. z  e.  w  A. x ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  <->  A. z  e.  w  ( z  e.  om  ->  A. x
( x  ~~  z  ->  ph ) ) )
13 ralcom4 2919 . . . . . . . . . . . . . . 15  |-  ( A. z  e.  w  A. x ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  <->  A. x A. z  e.  w  ( z  e.  om  ->  ( x  ~~  z  ->  ph ) ) )
1412, 13bitr3i 243 . . . . . . . . . . . . . 14  |-  ( A. z  e.  w  (
z  e.  om  ->  A. x ( x  ~~  z  ->  ph ) )  <->  A. x A. z  e.  w  ( z  e.  om  ->  ( x  ~~  z  ->  ph ) ) )
15 pssss 3387 . . . . . . . . . . . . . . . . . . . . 21  |-  ( x 
C.  y  ->  x  C_  y )
16 ssfi 7267 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( y  e.  Fin  /\  x  C_  y )  ->  x  e.  Fin )
17 isfi 7069 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( x  e.  Fin  <->  E. z  e.  om  x  ~~  z
)
1816, 17sylib 189 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( y  e.  Fin  /\  x  C_  y )  ->  E. z  e.  om  x  ~~  z )
1910, 15, 18syl2an 464 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  E. z  e.  om  x  ~~  z
)
20 ensym 7094 . . . . . . . . . . . . . . . . . . . . . . . . . 26  |-  ( x 
~~  z  ->  z  ~~  x )
2120ad2antll 710 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  z  ~~  x
)
22 php3 7231 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28  |-  ( ( y  e.  Fin  /\  x  C.  y )  ->  x  ~<  y )
2310, 22sylan 458 . . . . . . . . . . . . . . . . . . . . . . . . . . 27  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  x  ~<  y )
2423adantr 452 . . . . . . . . . . . . . . . . . . . . . . . . . 26  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  x  ~<  y
)
25 simpllr 736 . . . . . . . . . . . . . . . . . . . . . . . . . 26  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  y  ~~  w
)
26 sdomentr 7179 . . . . . . . . . . . . . . . . . . . . . . . . . 26  |-  ( ( x  ~<  y  /\  y  ~~  w )  ->  x  ~<  w )
2724, 25, 26syl2anc 643 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  x  ~<  w
)
28 ensdomtr 7181 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( z  ~~  x  /\  x  ~<  w )  -> 
z  ~<  w )
2921, 27, 28syl2anc 643 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  z  ~<  w
)
30 nnon 4793 . . . . . . . . . . . . . . . . . . . . . . . . . 26  |-  ( z  e.  om  ->  z  e.  On )
3130ad2antrl 709 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  z  e.  On )
322ad3antrrr 711 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  w  e.  On )
33 sdomel 7192 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( ( z  e.  On  /\  w  e.  On )  ->  ( z  ~<  w  ->  z  e.  w ) )
3431, 32, 33syl2anc 643 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  ( z  ~<  w  ->  z  e.  w
) )
3529, 34mpd 15 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( ( ( w  e. 
om  /\  y  ~~  w )  /\  x  C.  y )  /\  (
z  e.  om  /\  x  ~~  z ) )  ->  z  e.  w
)
3635ex 424 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( (
z  e.  om  /\  x  ~~  z )  -> 
z  e.  w ) )
37 simpr 448 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( z  e.  om  /\  x  ~~  z )  ->  x  ~~  z )
3837a1i 11 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( (
z  e.  om  /\  x  ~~  z )  ->  x  ~~  z ) )
3936, 38jcad 520 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( (
z  e.  om  /\  x  ~~  z )  -> 
( z  e.  w  /\  x  ~~  z ) ) )
4039reximdv2 2760 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( E. z  e.  om  x  ~~  z  ->  E. z  e.  w  x  ~~  z ) )
4119, 40mpd 15 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  E. z  e.  w  x  ~~  z )
42 r19.29 2791 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( A. z  e.  w  ( z  e.  om  ->  ( x  ~~  z  ->  ph ) )  /\  E. z  e.  w  x 
~~  z )  ->  E. z  e.  w  ( ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z ) )
4342expcom 425 . . . . . . . . . . . . . . . . . . 19  |-  ( E. z  e.  w  x 
~~  z  ->  ( A. z  e.  w  ( z  e.  om  ->  ( x  ~~  z  ->  ph ) )  ->  E. z  e.  w  ( ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z ) ) )
4441, 43syl 16 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( A. z  e.  w  (
z  e.  om  ->  ( x  ~~  z  ->  ph ) )  ->  E. z  e.  w  ( (
z  e.  om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z ) ) )
45 ordom 4796 . . . . . . . . . . . . . . . . . . . . . . 23  |-  Ord  om
46 ordelss 4540 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( Ord  om  /\  w  e.  om )  ->  w  C_ 
om )
4745, 46mpan 652 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( w  e.  om  ->  w  C_ 
om )
4847ad2antrr 707 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  w  C_  om )
4948sseld 3292 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( z  e.  w  ->  z  e. 
om ) )
50 pm2.27 37 . . . . . . . . . . . . . . . . . . . . 21  |-  ( z  e.  om  ->  (
( z  e.  om  ->  ( x  ~~  z  ->  ph ) )  -> 
( x  ~~  z  ->  ph ) ) )
5150imp3a 421 . . . . . . . . . . . . . . . . . . . 20  |-  ( z  e.  om  ->  (
( ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z )  ->  ph ) )
5249, 51syl6 31 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( z  e.  w  ->  ( ( ( z  e.  om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z )  ->  ph ) ) )
5352rexlimdv 2774 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( E. z  e.  w  (
( z  e.  om  ->  ( x  ~~  z  ->  ph ) )  /\  x  ~~  z )  ->  ph ) )
5444, 53syld 42 . . . . . . . . . . . . . . . . 17  |-  ( ( ( w  e.  om  /\  y  ~~  w )  /\  x  C.  y
)  ->  ( A. z  e.  w  (
z  e.  om  ->  ( x  ~~  z  ->  ph ) )  ->  ph )
)
5554ex 424 . . . . . . . . . . . . . . . 16  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
( x  C.  y  ->  ( A. z  e.  w  ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  ->  ph ) ) )
5655com23 74 . . . . . . . . . . . . . . 15  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
( A. z  e.  w  ( z  e. 
om  ->  ( x  ~~  z  ->  ph ) )  -> 
( x  C.  y  ->  ph ) ) )
5756alimdv 1628 . . . . . . . . . . . . . 14  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
( A. x A. z  e.  w  (
z  e.  om  ->  ( x  ~~  z  ->  ph ) )  ->  A. x
( x  C.  y  ->  ph ) ) )
5814, 57syl5bi 209 . . . . . . . . . . . . 13  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
( A. z  e.  w  ( z  e. 
om  ->  A. x ( x 
~~  z  ->  ph )
)  ->  A. x
( x  C.  y  ->  ph ) ) )
59 findcard3.3 . . . . . . . . . . . . 13  |-  ( y  e.  Fin  ->  ( A. x ( x  C.  y  ->  ph )  ->  ch ) )
6010, 58, 59sylsyld 54 . . . . . . . . . . . 12  |-  ( ( w  e.  om  /\  y  ~~  w )  -> 
( A. z  e.  w  ( z  e. 
om  ->  A. x ( x 
~~  z  ->  ph )
)  ->  ch )
)
6160impancom 428 . . . . . . . . . . 11  |-  ( ( w  e.  om  /\  A. z  e.  w  ( z  e.  om  ->  A. x ( x  ~~  z  ->  ph ) ) )  ->  ( y  ~~  w  ->  ch ) )
6261alrimiv 1638 . . . . . . . . . 10  |-  ( ( w  e.  om  /\  A. z  e.  w  ( z  e.  om  ->  A. x ( x  ~~  z  ->  ph ) ) )  ->  A. y ( y 
~~  w  ->  ch ) )
6362expcom 425 . . . . . . . . 9  |-  ( A. z  e.  w  (
z  e.  om  ->  A. x ( x  ~~  z  ->  ph ) )  -> 
( w  e.  om  ->  A. y ( y 
~~  w  ->  ch ) ) )
64 breq1 4158 . . . . . . . . . . 11  |-  ( x  =  y  ->  (
x  ~~  w  <->  y  ~~  w ) )
65 findcard3.1 . . . . . . . . . . 11  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
6664, 65imbi12d 312 . . . . . . . . . 10  |-  ( x  =  y  ->  (
( x  ~~  w  ->  ph )  <->  ( y  ~~  w  ->  ch )
) )
6766cbvalv 2038 . . . . . . . . 9  |-  ( A. x ( x  ~~  w  ->  ph )  <->  A. y
( y  ~~  w  ->  ch ) )
6863, 67syl6ibr 219 . . . . . . . 8  |-  ( A. z  e.  w  (
z  e.  om  ->  A. x ( x  ~~  z  ->  ph ) )  -> 
( w  e.  om  ->  A. x ( x 
~~  w  ->  ph )
) )
6968a1i 11 . . . . . . 7  |-  ( w  e.  On  ->  ( A. z  e.  w  ( z  e.  om  ->  A. x ( x 
~~  z  ->  ph )
)  ->  ( w  e.  om  ->  A. x
( x  ~~  w  ->  ph ) ) ) )
707, 69tfis2 4778 . . . . . 6  |-  ( w  e.  On  ->  (
w  e.  om  ->  A. x ( x  ~~  w  ->  ph ) ) )
712, 70mpcom 34 . . . . 5  |-  ( w  e.  om  ->  A. x
( x  ~~  w  ->  ph ) )
7271rgen 2716 . . . 4  |-  A. w  e.  om  A. x ( x  ~~  w  ->  ph )
73 r19.29 2791 . . . 4  |-  ( ( A. w  e.  om  A. x ( x  ~~  w  ->  ph )  /\  E. w  e.  om  A  ~~  w )  ->  E. w  e.  om  ( A. x
( x  ~~  w  ->  ph )  /\  A  ~~  w ) )
7472, 73mpan 652 . . 3  |-  ( E. w  e.  om  A  ~~  w  ->  E. w  e.  om  ( A. x
( x  ~~  w  ->  ph )  /\  A  ~~  w ) )
751, 74sylbi 188 . 2  |-  ( A  e.  Fin  ->  E. w  e.  om  ( A. x
( x  ~~  w  ->  ph )  /\  A  ~~  w ) )
76 breq1 4158 . . . . . 6  |-  ( x  =  A  ->  (
x  ~~  w  <->  A  ~~  w ) )
77 findcard3.2 . . . . . 6  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
7876, 77imbi12d 312 . . . . 5  |-  ( x  =  A  ->  (
( x  ~~  w  ->  ph )  <->  ( A  ~~  w  ->  ta )
) )
7978spcgv 2981 . . . 4  |-  ( A  e.  Fin  ->  ( A. x ( x  ~~  w  ->  ph )  ->  ( A  ~~  w  ->  ta ) ) )
8079imp3a 421 . . 3  |-  ( A  e.  Fin  ->  (
( A. x ( x  ~~  w  ->  ph )  /\  A  ~~  w )  ->  ta ) )
8180rexlimdvw 2778 . 2  |-  ( A  e.  Fin  ->  ( E. w  e.  om  ( A. x ( x 
~~  w  ->  ph )  /\  A  ~~  w )  ->  ta ) )
8275, 81mpd 15 1  |-  ( A  e.  Fin  ->  ta )
Colors of variables: wff set class
Syntax hints:    -> wi 4    <-> wb 177    /\ wa 359   A.wal 1546    = wceq 1649    e. wcel 1717   A.wral 2651   E.wrex 2652    C_ wss 3265    C. wpss 3266   class class class wbr 4155   Ord word 4523   Oncon0 4524   omcom 4787    ~~ cen 7044    ~< csdm 7046   Fincfn 7047
This theorem is referenced by:  marypha1lem  7375  pgpfac1  15567  pgpfac  15571  fbfinnfr  17796  wilthlem3  20722
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2370  ax-sep 4273  ax-nul 4281  ax-pow 4320  ax-pr 4346  ax-un 4643
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2244  df-mo 2245  df-clab 2376  df-cleq 2382  df-clel 2385  df-nfc 2514  df-ne 2554  df-ral 2656  df-rex 2657  df-rab 2660  df-v 2903  df-sbc 3107  df-dif 3268  df-un 3270  df-in 3272  df-ss 3279  df-pss 3281  df-nul 3574  df-if 3685  df-pw 3746  df-sn 3765  df-pr 3766  df-tp 3767  df-op 3768  df-uni 3960  df-br 4156  df-opab 4210  df-tr 4246  df-eprel 4437  df-id 4441  df-po 4446  df-so 4447  df-fr 4484  df-we 4486  df-ord 4527  df-on 4528  df-lim 4529  df-suc 4530  df-om 4788  df-xp 4826  df-rel 4827  df-cnv 4828  df-co 4829  df-dm 4830  df-rn 4831  df-res 4832  df-ima 4833  df-iota 5360  df-fun 5398  df-fn 5399  df-f 5400  df-f1 5401  df-fo 5402  df-f1o 5403  df-fv 5404  df-er 6843  df-en 7048  df-dom 7049  df-sdom 7050  df-fin 7051
  Copyright terms: Public domain W3C validator