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

Theorem unfi 7579
Description: The union of two finite sets is finite. Part of Corollary 6K of [Enderton] p. 144. (Contributed by NM, 16-Nov-2002.)
Assertion
Ref Expression
unfi  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( A  u.  B
)  e.  Fin )

Proof of Theorem unfi
Dummy variables  x  y  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 diffi 7543 . 2  |-  ( B  e.  Fin  ->  ( B  \  A )  e. 
Fin )
2 reeanv 2888 . . . 4  |-  ( E. x  e.  om  E. y  e.  om  ( A  ~~  x  /\  ( B  \  A )  ~~  y )  <->  ( E. x  e.  om  A  ~~  x  /\  E. y  e. 
om  ( B  \  A )  ~~  y
) )
3 isfi 7333 . . . . 5  |-  ( A  e.  Fin  <->  E. x  e.  om  A  ~~  x
)
4 isfi 7333 . . . . 5  |-  ( ( B  \  A )  e.  Fin  <->  E. y  e.  om  ( B  \  A )  ~~  y
)
53, 4anbi12i 697 . . . 4  |-  ( ( A  e.  Fin  /\  ( B  \  A )  e.  Fin )  <->  ( E. x  e.  om  A  ~~  x  /\  E. y  e. 
om  ( B  \  A )  ~~  y
) )
62, 5bitr4i 252 . . 3  |-  ( E. x  e.  om  E. y  e.  om  ( A  ~~  x  /\  ( B  \  A )  ~~  y )  <->  ( A  e.  Fin  /\  ( B 
\  A )  e. 
Fin ) )
7 nnacl 7050 . . . . 5  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( x  +o  y
)  e.  om )
8 unfilem3 7578 . . . . . . 7  |-  ( ( x  e.  om  /\  y  e.  om )  ->  y  ~~  ( ( x  +o  y ) 
\  x ) )
9 entr 7361 . . . . . . . 8  |-  ( ( ( B  \  A
)  ~~  y  /\  y  ~~  ( ( x  +o  y )  \  x ) )  -> 
( B  \  A
)  ~~  ( (
x  +o  y ) 
\  x ) )
109expcom 435 . . . . . . 7  |-  ( y 
~~  ( ( x  +o  y )  \  x )  ->  (
( B  \  A
)  ~~  y  ->  ( B  \  A ) 
~~  ( ( x  +o  y )  \  x ) ) )
118, 10syl 16 . . . . . 6  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( B  \  A )  ~~  y  ->  ( B  \  A
)  ~~  ( (
x  +o  y ) 
\  x ) ) )
12 disjdif 3751 . . . . . . . 8  |-  ( A  i^i  ( B  \  A ) )  =  (/)
13 disjdif 3751 . . . . . . . 8  |-  ( x  i^i  ( ( x  +o  y )  \  x ) )  =  (/)
14 unen 7392 . . . . . . . 8  |-  ( ( ( A  ~~  x  /\  ( B  \  A
)  ~~  ( (
x  +o  y ) 
\  x ) )  /\  ( ( A  i^i  ( B  \  A ) )  =  (/)  /\  ( x  i^i  ( ( x  +o  y )  \  x
) )  =  (/) ) )  ->  ( A  u.  ( B  \  A ) )  ~~  ( x  u.  (
( x  +o  y
)  \  x )
) )
1512, 13, 14mpanr12 685 . . . . . . 7  |-  ( ( A  ~~  x  /\  ( B  \  A ) 
~~  ( ( x  +o  y )  \  x ) )  -> 
( A  u.  ( B  \  A ) ) 
~~  ( x  u.  ( ( x  +o  y )  \  x
) ) )
16 undif2 3755 . . . . . . . . 9  |-  ( A  u.  ( B  \  A ) )  =  ( A  u.  B
)
1716a1i 11 . . . . . . . 8  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( A  u.  ( B  \  A ) )  =  ( A  u.  B ) )
18 nnaword1 7068 . . . . . . . . 9  |-  ( ( x  e.  om  /\  y  e.  om )  ->  x  C_  ( x  +o  y ) )
19 undif 3759 . . . . . . . . 9  |-  ( x 
C_  ( x  +o  y )  <->  ( x  u.  ( ( x  +o  y )  \  x
) )  =  ( x  +o  y ) )
2018, 19sylib 196 . . . . . . . 8  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( x  u.  (
( x  +o  y
)  \  x )
)  =  ( x  +o  y ) )
2117, 20breq12d 4305 . . . . . . 7  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  u.  ( B  \  A ) )  ~~  ( x  u.  ( ( x  +o  y )  \  x ) )  <->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
2215, 21syl5ib 219 . . . . . 6  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  ~~  x  /\  ( B  \  A )  ~~  (
( x  +o  y
)  \  x )
)  ->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
2311, 22sylan2d 482 . . . . 5  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  ~~  x  /\  ( B  \  A )  ~~  y
)  ->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
24 breq2 4296 . . . . . . 7  |-  ( z  =  ( x  +o  y )  ->  (
( A  u.  B
)  ~~  z  <->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
2524rspcev 3073 . . . . . 6  |-  ( ( ( x  +o  y
)  e.  om  /\  ( A  u.  B
)  ~~  ( x  +o  y ) )  ->  E. z  e.  om  ( A  u.  B
)  ~~  z )
26 isfi 7333 . . . . . 6  |-  ( ( A  u.  B )  e.  Fin  <->  E. z  e.  om  ( A  u.  B )  ~~  z
)
2725, 26sylibr 212 . . . . 5  |-  ( ( ( x  +o  y
)  e.  om  /\  ( A  u.  B
)  ~~  ( x  +o  y ) )  -> 
( A  u.  B
)  e.  Fin )
287, 23, 27syl6an 545 . . . 4  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  ~~  x  /\  ( B  \  A )  ~~  y
)  ->  ( A  u.  B )  e.  Fin ) )
2928rexlimivv 2846 . . 3  |-  ( E. x  e.  om  E. y  e.  om  ( A  ~~  x  /\  ( B  \  A )  ~~  y )  ->  ( A  u.  B )  e.  Fin )
306, 29sylbir 213 . 2  |-  ( ( A  e.  Fin  /\  ( B  \  A )  e.  Fin )  -> 
( A  u.  B
)  e.  Fin )
311, 30sylan2 474 1  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( A  u.  B
)  e.  Fin )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 369    = wceq 1369    e. wcel 1756   E.wrex 2716    \ cdif 3325    u. cun 3326    i^i cin 3327    C_ wss 3328   (/)c0 3637   class class class wbr 4292  (class class class)co 6091   omcom 6476    +o coa 6917    ~~ cen 7307   Fincfn 7310
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2423  ax-sep 4413  ax-nul 4421  ax-pow 4470  ax-pr 4531  ax-un 6372
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2568  df-ne 2608  df-ral 2720  df-rex 2721  df-reu 2722  df-rab 2724  df-v 2974  df-sbc 3187  df-csb 3289  df-dif 3331  df-un 3333  df-in 3335  df-ss 3342  df-pss 3344  df-nul 3638  df-if 3792  df-pw 3862  df-sn 3878  df-pr 3880  df-tp 3882  df-op 3884  df-uni 4092  df-int 4129  df-iun 4173  df-br 4293  df-opab 4351  df-mpt 4352  df-tr 4386  df-eprel 4632  df-id 4636  df-po 4641  df-so 4642  df-fr 4679  df-we 4681  df-ord 4722  df-on 4723  df-lim 4724  df-suc 4725  df-xp 4846  df-rel 4847  df-cnv 4848  df-co 4849  df-dm 4850  df-rn 4851  df-res 4852  df-ima 4853  df-iota 5381  df-fun 5420  df-fn 5421  df-f 5422  df-f1 5423  df-fo 5424  df-f1o 5425  df-fv 5426  df-ov 6094  df-oprab 6095  df-mpt2 6096  df-om 6477  df-recs 6832  df-rdg 6866  df-oadd 6924  df-er 7101  df-en 7311  df-fin 7314
This theorem is referenced by:  unfi2  7581  difinf  7582  xpfi  7583  prfi  7586  tpfi  7587  fnfi  7589  iunfi  7599  pwfilem  7605  fsuppun  7639  fsuppunfi  7640  ressuppfi  7646  fiin  7672  wemapso2OLD  7766  cantnfp1lem1  7886  cantnfp1lem1OLD  7912  ficardun2  8372  ackbij1lem6  8394  ackbij1lem16  8404  fin23lem28  8509  fin23lem30  8511  isfin1-3  8555  axcclem  8626  hashun  12145  hashunlei  12175  hashmap  12197  hashbclem  12205  hashf1lem1  12208  hashf1lem2  12209  hashf1  12210  incexclem  13299  isumltss  13311  ramub1lem1  14087  fpwipodrs  15334  acsfiindd  15347  symgfisg  15974  gsumzaddlemOLD  16410  gsumzunsnd  16451  gsumunsnd  16452  dprdfaddOLD  16517  psrbagaddcl  17438  psrbagaddclOLD  17439  mplsubg  17515  mpllss  17516  funsnfsupOLD  17670  dsmmacl  18166  fctop  18608  uncmp  19006  bwth  19013  1stckgenlem  19126  ptbasin  19150  cfinfil  19466  fin1aufil  19505  alexsubALTlem3  19621  tmdgsum  19666  tsmsfbas  19698  tsmsgsum  19709  tsmsgsumOLD  19712  tsmsresOLD  19717  tsmsres  19718  tsmsxplem1  19727  prdsmet  19945  prdsbl  20066  icccmplem2  20400  rrxmval  20904  rrxmet  20907  rrxdstprj1  20908  ovolfiniun  20984  volfiniun  21028  fta1glem2  21638  fta1lem  21773  aannenlem2  21795  aalioulem2  21799  dchrfi  22594  usgrafilem2  23325  vdgrfiun  23572  konigsberg  23608  ffsrn  26029  gsumunsnf  26245  eulerpartlemt  26754  ballotlemgun  26907  itg2addnclem2  28444  ftc1anclem7  28473  ftc1anc  28475  locfincmp  28576  comppfsc  28579  prdsbnd  28692  elrfi  29030  mzpcompact2lem  29088  eldioph2  29100  lsmfgcl  29427  fiuneneq  29562  fsummsnunz  30241  fsumsplitsnun  30242  fsummmodsnunre  30243  mndpsuppfi  30789  pclfinN  33544
  Copyright terms: Public domain W3C validator