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

Theorem xpfi 7345
Description: The Cartesian product of two finite sets is finite. (Contributed by Jeff Madsen, 2-Sep-2009.) (Revised by Mario Carneiro, 12-Mar-2015.)
Assertion
Ref Expression
xpfi  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( A  X.  B
)  e.  Fin )

Proof of Theorem xpfi
Dummy variables  w  x  y  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 xpeq1 4859 . . . . 5  |-  ( x  =  (/)  ->  ( x  X.  B )  =  ( (/)  X.  B
) )
21eleq1d 2478 . . . 4  |-  ( x  =  (/)  ->  ( ( x  X.  B )  e.  Fin  <->  ( (/)  X.  B
)  e.  Fin )
)
32imbi2d 308 . . 3  |-  ( x  =  (/)  ->  ( ( B  e.  Fin  ->  ( x  X.  B )  e.  Fin )  <->  ( B  e.  Fin  ->  ( (/)  X.  B
)  e.  Fin )
) )
4 xpeq1 4859 . . . . 5  |-  ( x  =  ( y  \  { z } )  ->  ( x  X.  B )  =  ( ( y  \  {
z } )  X.  B ) )
54eleq1d 2478 . . . 4  |-  ( x  =  ( y  \  { z } )  ->  ( ( x  X.  B )  e. 
Fin 
<->  ( ( y  \  { z } )  X.  B )  e. 
Fin ) )
65imbi2d 308 . . 3  |-  ( x  =  ( y  \  { z } )  ->  ( ( B  e.  Fin  ->  (
x  X.  B )  e.  Fin )  <->  ( B  e.  Fin  ->  ( (
y  \  { z } )  X.  B
)  e.  Fin )
) )
7 xpeq1 4859 . . . . 5  |-  ( x  =  y  ->  (
x  X.  B )  =  ( y  X.  B ) )
87eleq1d 2478 . . . 4  |-  ( x  =  y  ->  (
( x  X.  B
)  e.  Fin  <->  ( y  X.  B )  e.  Fin ) )
98imbi2d 308 . . 3  |-  ( x  =  y  ->  (
( B  e.  Fin  ->  ( x  X.  B
)  e.  Fin )  <->  ( B  e.  Fin  ->  ( y  X.  B )  e.  Fin ) ) )
10 xpeq1 4859 . . . . 5  |-  ( x  =  A  ->  (
x  X.  B )  =  ( A  X.  B ) )
1110eleq1d 2478 . . . 4  |-  ( x  =  A  ->  (
( x  X.  B
)  e.  Fin  <->  ( A  X.  B )  e.  Fin ) )
1211imbi2d 308 . . 3  |-  ( x  =  A  ->  (
( B  e.  Fin  ->  ( x  X.  B
)  e.  Fin )  <->  ( B  e.  Fin  ->  ( A  X.  B )  e.  Fin ) ) )
13 xp0r 4923 . . . . 5  |-  ( (/)  X.  B )  =  (/)
14 0fin 7303 . . . . 5  |-  (/)  e.  Fin
1513, 14eqeltri 2482 . . . 4  |-  ( (/)  X.  B )  e.  Fin
1615a1i 11 . . 3  |-  ( B  e.  Fin  ->  ( (/) 
X.  B )  e. 
Fin )
17 neq0 3606 . . . . . . 7  |-  ( -.  y  =  (/)  <->  E. w  w  e.  y )
18 sneq 3793 . . . . . . . . . . . . . . . 16  |-  ( z  =  w  ->  { z }  =  { w } )
1918difeq2d 3433 . . . . . . . . . . . . . . 15  |-  ( z  =  w  ->  (
y  \  { z } )  =  ( y  \  { w } ) )
2019xpeq1d 4868 . . . . . . . . . . . . . 14  |-  ( z  =  w  ->  (
( y  \  {
z } )  X.  B )  =  ( ( y  \  {
w } )  X.  B ) )
2120eleq1d 2478 . . . . . . . . . . . . 13  |-  ( z  =  w  ->  (
( ( y  \  { z } )  X.  B )  e. 
Fin 
<->  ( ( y  \  { w } )  X.  B )  e. 
Fin ) )
2221imbi2d 308 . . . . . . . . . . . 12  |-  ( z  =  w  ->  (
( B  e.  Fin  ->  ( ( y  \  { z } )  X.  B )  e. 
Fin )  <->  ( B  e.  Fin  ->  ( (
y  \  { w } )  X.  B
)  e.  Fin )
) )
2322rspcv 3016 . . . . . . . . . . 11  |-  ( w  e.  y  ->  ( A. z  e.  y 
( B  e.  Fin  ->  ( ( y  \  { z } )  X.  B )  e. 
Fin )  ->  ( B  e.  Fin  ->  (
( y  \  {
w } )  X.  B )  e.  Fin ) ) )
2423adantl 453 . . . . . . . . . 10  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( A. z  e.  y  ( B  e.  Fin  ->  (
( y  \  {
z } )  X.  B )  e.  Fin )  ->  ( B  e. 
Fin  ->  ( ( y 
\  { w }
)  X.  B )  e.  Fin ) ) )
25 pm2.27 37 . . . . . . . . . . 11  |-  ( B  e.  Fin  ->  (
( B  e.  Fin  ->  ( ( y  \  { w } )  X.  B )  e. 
Fin )  ->  (
( y  \  {
w } )  X.  B )  e.  Fin ) )
2625ad2antlr 708 . . . . . . . . . 10  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( ( B  e.  Fin  ->  (
( y  \  {
w } )  X.  B )  e.  Fin )  ->  ( ( y 
\  { w }
)  X.  B )  e.  Fin ) )
27 snex 4373 . . . . . . . . . . . . . . 15  |-  { w }  e.  _V
28 xpexg 4956 . . . . . . . . . . . . . . 15  |-  ( ( { w }  e.  _V  /\  B  e.  Fin )  ->  ( { w }  X.  B )  e. 
_V )
2927, 28mpan 652 . . . . . . . . . . . . . 14  |-  ( B  e.  Fin  ->  ( { w }  X.  B )  e.  _V )
30 id 20 . . . . . . . . . . . . . 14  |-  ( B  e.  Fin  ->  B  e.  Fin )
31 vex 2927 . . . . . . . . . . . . . . 15  |-  w  e. 
_V
32 2ndconst 6403 . . . . . . . . . . . . . . 15  |-  ( w  e.  _V  ->  ( 2nd  |`  ( { w }  X.  B ) ) : ( { w }  X.  B ) -1-1-onto-> B )
3331, 32mp1i 12 . . . . . . . . . . . . . 14  |-  ( B  e.  Fin  ->  ( 2nd  |`  ( { w }  X.  B ) ) : ( { w }  X.  B ) -1-1-onto-> B )
34 f1oen2g 7091 . . . . . . . . . . . . . 14  |-  ( ( ( { w }  X.  B )  e.  _V  /\  B  e.  Fin  /\  ( 2nd  |`  ( {
w }  X.  B
) ) : ( { w }  X.  B ) -1-1-onto-> B )  ->  ( { w }  X.  B )  ~~  B
)
3529, 30, 33, 34syl3anc 1184 . . . . . . . . . . . . 13  |-  ( B  e.  Fin  ->  ( { w }  X.  B )  ~~  B
)
36 enfii 7293 . . . . . . . . . . . . 13  |-  ( ( B  e.  Fin  /\  ( { w }  X.  B )  ~~  B
)  ->  ( {
w }  X.  B
)  e.  Fin )
3735, 36mpdan 650 . . . . . . . . . . . 12  |-  ( B  e.  Fin  ->  ( { w }  X.  B )  e.  Fin )
3837ad2antlr 708 . . . . . . . . . . 11  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( {
w }  X.  B
)  e.  Fin )
39 unfi 7341 . . . . . . . . . . . 12  |-  ( ( ( ( y  \  { w } )  X.  B )  e. 
Fin  /\  ( {
w }  X.  B
)  e.  Fin )  ->  ( ( ( y 
\  { w }
)  X.  B )  u.  ( { w }  X.  B ) )  e.  Fin )
40 xpundir 4898 . . . . . . . . . . . . . . . 16  |-  ( ( ( y  \  {
w } )  u. 
{ w } )  X.  B )  =  ( ( ( y 
\  { w }
)  X.  B )  u.  ( { w }  X.  B ) )
41 difsnid 3912 . . . . . . . . . . . . . . . . 17  |-  ( w  e.  y  ->  (
( y  \  {
w } )  u. 
{ w } )  =  y )
4241xpeq1d 4868 . . . . . . . . . . . . . . . 16  |-  ( w  e.  y  ->  (
( ( y  \  { w } )  u.  { w }
)  X.  B )  =  ( y  X.  B ) )
4340, 42syl5eqr 2458 . . . . . . . . . . . . . . 15  |-  ( w  e.  y  ->  (
( ( y  \  { w } )  X.  B )  u.  ( { w }  X.  B ) )  =  ( y  X.  B
) )
4443eleq1d 2478 . . . . . . . . . . . . . 14  |-  ( w  e.  y  ->  (
( ( ( y 
\  { w }
)  X.  B )  u.  ( { w }  X.  B ) )  e.  Fin  <->  ( y  X.  B )  e.  Fin ) )
4544biimpd 199 . . . . . . . . . . . . 13  |-  ( w  e.  y  ->  (
( ( ( y 
\  { w }
)  X.  B )  u.  ( { w }  X.  B ) )  e.  Fin  ->  (
y  X.  B )  e.  Fin ) )
4645adantl 453 . . . . . . . . . . . 12  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( (
( ( y  \  { w } )  X.  B )  u.  ( { w }  X.  B ) )  e. 
Fin  ->  ( y  X.  B )  e.  Fin ) )
4739, 46syl5 30 . . . . . . . . . . 11  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( (
( ( y  \  { w } )  X.  B )  e. 
Fin  /\  ( {
w }  X.  B
)  e.  Fin )  ->  ( y  X.  B
)  e.  Fin )
)
4838, 47mpan2d 656 . . . . . . . . . 10  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( (
( y  \  {
w } )  X.  B )  e.  Fin  ->  ( y  X.  B
)  e.  Fin )
)
4924, 26, 483syld 53 . . . . . . . . 9  |-  ( ( ( y  e.  Fin  /\  B  e.  Fin )  /\  w  e.  y
)  ->  ( A. z  e.  y  ( B  e.  Fin  ->  (
( y  \  {
z } )  X.  B )  e.  Fin )  ->  ( y  X.  B )  e.  Fin ) )
5049ex 424 . . . . . . . 8  |-  ( ( y  e.  Fin  /\  B  e.  Fin )  ->  ( w  e.  y  ->  ( A. z  e.  y  ( B  e.  Fin  ->  ( (
y  \  { z } )  X.  B
)  e.  Fin )  ->  ( y  X.  B
)  e.  Fin )
) )
5150exlimdv 1643 . . . . . . 7  |-  ( ( y  e.  Fin  /\  B  e.  Fin )  ->  ( E. w  w  e.  y  ->  ( A. z  e.  y 
( B  e.  Fin  ->  ( ( y  \  { z } )  X.  B )  e. 
Fin )  ->  (
y  X.  B )  e.  Fin ) ) )
5217, 51syl5bi 209 . . . . . 6  |-  ( ( y  e.  Fin  /\  B  e.  Fin )  ->  ( -.  y  =  (/)  ->  ( A. z  e.  y  ( B  e.  Fin  ->  ( (
y  \  { z } )  X.  B
)  e.  Fin )  ->  ( y  X.  B
)  e.  Fin )
) )
53 xpeq1 4859 . . . . . . . 8  |-  ( y  =  (/)  ->  ( y  X.  B )  =  ( (/)  X.  B
) )
5453, 15syl6eqel 2500 . . . . . . 7  |-  ( y  =  (/)  ->  ( y  X.  B )  e. 
Fin )
5554a1d 23 . . . . . 6  |-  ( y  =  (/)  ->  ( A. z  e.  y  ( B  e.  Fin  ->  (
( y  \  {
z } )  X.  B )  e.  Fin )  ->  ( y  X.  B )  e.  Fin ) )
5652, 55pm2.61d2 154 . . . . 5  |-  ( ( y  e.  Fin  /\  B  e.  Fin )  ->  ( A. z  e.  y  ( B  e. 
Fin  ->  ( ( y 
\  { z } )  X.  B )  e.  Fin )  -> 
( y  X.  B
)  e.  Fin )
)
5756ex 424 . . . 4  |-  ( y  e.  Fin  ->  ( B  e.  Fin  ->  ( A. z  e.  y 
( B  e.  Fin  ->  ( ( y  \  { z } )  X.  B )  e. 
Fin )  ->  (
y  X.  B )  e.  Fin ) ) )
5857com23 74 . . 3  |-  ( y  e.  Fin  ->  ( A. z  e.  y 
( B  e.  Fin  ->  ( ( y  \  { z } )  X.  B )  e. 
Fin )  ->  ( B  e.  Fin  ->  (
y  X.  B )  e.  Fin ) ) )
593, 6, 9, 12, 16, 58findcard 7314 . 2  |-  ( A  e.  Fin  ->  ( B  e.  Fin  ->  ( A  X.  B )  e. 
Fin ) )
6059imp 419 1  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( A  X.  B
)  e.  Fin )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    /\ wa 359   E.wex 1547    = wceq 1649    e. wcel 1721   A.wral 2674   _Vcvv 2924    \ cdif 3285    u. cun 3286   (/)c0 3596   {csn 3782   class class class wbr 4180    X. cxp 4843    |` cres 4847   -1-1-onto->wf1o 5420   2ndc2nd 6315    ~~ cen 7073   Fincfn 7076
This theorem is referenced by:  mapfi  7369  infxpenlem  7859  ackbij1lem9  8072  ackbij1lem10  8073  hashxplem  11659  hashmap  11661  fsum2dlem  12517  fsumcom2  12521  ackbijnn  12570  rexpen  12790  crt  13130  phimullem  13131  prmreclem3  13249  ablfaclem3  15608  gsumdixp  15678  gsumbagdiag  16404  psrass1lem  16405  mplsubrglem  16465  evlslem2  16531  tsmsxplem1  18143  tsmsxplem2  18144  tsmsxp  18145  i1fadd  19548  i1fmul  19549  itg1addlem4  19552  fsumdvdsmul  20941  fsumvma  20958  lgsquadlem1  21099  lgsquadlem2  21100  lgsquadlem3  21101  sibfof  24615  erdszelem10  24847  fprod2dlem  25265  fprodcom2  25269  cntotbnd  26403  pellex  26796  gsumcom3fi  27331  mamucl  27332  mamudiagcl  27333  mamudi  27337  mamudir  27338  mamuvs1  27339  mamuvs2  27340  matsca2  27350  matbas2  27351  matplusg2  27353  matvsca2  27354  3xpfi  27975  2spotfi  28097
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 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2393  ax-sep 4298  ax-nul 4306  ax-pow 4345  ax-pr 4371  ax-un 4668
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 2266  df-mo 2267  df-clab 2399  df-cleq 2405  df-clel 2408  df-nfc 2537  df-ne 2577  df-ral 2679  df-rex 2680  df-reu 2681  df-rab 2683  df-v 2926  df-sbc 3130  df-csb 3220  df-dif 3291  df-un 3293  df-in 3295  df-ss 3302  df-pss 3304  df-nul 3597  df-if 3708  df-pw 3769  df-sn 3788  df-pr 3789  df-tp 3790  df-op 3791  df-uni 3984  df-int 4019  df-iun 4063  df-br 4181  df-opab 4235  df-mpt 4236  df-tr 4271  df-eprel 4462  df-id 4466  df-po 4471  df-so 4472  df-fr 4509  df-we 4511  df-ord 4552  df-on 4553  df-lim 4554  df-suc 4555  df-om 4813  df-xp 4851  df-rel 4852  df-cnv 4853  df-co 4854  df-dm 4855  df-rn 4856  df-res 4857  df-ima 4858  df-iota 5385  df-fun 5423  df-fn 5424  df-f 5425  df-f1 5426  df-fo 5427  df-f1o 5428  df-fv 5429  df-ov 6051  df-oprab 6052  df-mpt2 6053  df-1st 6316  df-2nd 6317  df-recs 6600  df-rdg 6635  df-1o 6691  df-oadd 6695  df-er 6872  df-en 7077  df-fin 7080
  Copyright terms: Public domain W3C validator