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

Theorem unfi 7575
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 7539 . 2  |-  ( B  e.  Fin  ->  ( B  \  A )  e. 
Fin )
2 reeanv 2886 . . . 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 7329 . . . . 5  |-  ( A  e.  Fin  <->  E. x  e.  om  A  ~~  x
)
4 isfi 7329 . . . . 5  |-  ( ( B  \  A )  e.  Fin  <->  E. y  e.  om  ( B  \  A )  ~~  y
)
53, 4anbi12i 692 . . . 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 7046 . . . . 5  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( x  +o  y
)  e.  om )
8 unfilem3 7574 . . . . . . 7  |-  ( ( x  e.  om  /\  y  e.  om )  ->  y  ~~  ( ( x  +o  y ) 
\  x ) )
9 entr 7357 . . . . . . . 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 3748 . . . . . . . 8  |-  ( A  i^i  ( B  \  A ) )  =  (/)
13 disjdif 3748 . . . . . . . 8  |-  ( x  i^i  ( ( x  +o  y )  \  x ) )  =  (/)
14 unen 7388 . . . . . . . 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 680 . . . . . . 7  |-  ( ( A  ~~  x  /\  ( B  \  A ) 
~~  ( ( x  +o  y )  \  x ) )  -> 
( A  u.  ( B  \  A ) ) 
~~  ( x  u.  ( ( x  +o  y )  \  x
) ) )
16 undif2 3752 . . . . . . . . 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 7064 . . . . . . . . 9  |-  ( ( x  e.  om  /\  y  e.  om )  ->  x  C_  ( x  +o  y ) )
19 undif 3756 . . . . . . . . 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 4302 . . . . . . 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 479 . . . . 5  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  ~~  x  /\  ( B  \  A )  ~~  y
)  ->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
24 breq2 4293 . . . . . . 7  |-  ( z  =  ( x  +o  y )  ->  (
( A  u.  B
)  ~~  z  <->  ( A  u.  B )  ~~  (
x  +o  y ) ) )
2524rspcev 3070 . . . . . 6  |-  ( ( ( x  +o  y
)  e.  om  /\  ( A  u.  B
)  ~~  ( x  +o  y ) )  ->  E. z  e.  om  ( A  u.  B
)  ~~  z )
26 isfi 7329 . . . . . 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 542 . . . 4  |-  ( ( x  e.  om  /\  y  e.  om )  ->  ( ( A  ~~  x  /\  ( B  \  A )  ~~  y
)  ->  ( A  u.  B )  e.  Fin ) )
2928rexlimivv 2844 . . 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 471 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 1364    e. wcel 1761   E.wrex 2714    \ cdif 3322    u. cun 3323    i^i cin 3324    C_ wss 3325   (/)c0 3634   class class class wbr 4289  (class class class)co 6090   omcom 6475    +o coa 6913    ~~ cen 7303   Fincfn 7306
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1713  ax-7 1733  ax-8 1763  ax-9 1765  ax-10 1780  ax-11 1785  ax-12 1797  ax-13 1948  ax-ext 2422  ax-sep 4410  ax-nul 4418  ax-pow 4467  ax-pr 4528  ax-un 6371
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 961  df-3an 962  df-tru 1367  df-ex 1592  df-nf 1595  df-sb 1706  df-eu 2263  df-mo 2264  df-clab 2428  df-cleq 2434  df-clel 2437  df-nfc 2566  df-ne 2606  df-ral 2718  df-rex 2719  df-reu 2720  df-rab 2722  df-v 2972  df-sbc 3184  df-csb 3286  df-dif 3328  df-un 3330  df-in 3332  df-ss 3339  df-pss 3341  df-nul 3635  df-if 3789  df-pw 3859  df-sn 3875  df-pr 3877  df-tp 3879  df-op 3881  df-uni 4089  df-int 4126  df-iun 4170  df-br 4290  df-opab 4348  df-mpt 4349  df-tr 4383  df-eprel 4628  df-id 4632  df-po 4637  df-so 4638  df-fr 4675  df-we 4677  df-ord 4718  df-on 4719  df-lim 4720  df-suc 4721  df-xp 4842  df-rel 4843  df-cnv 4844  df-co 4845  df-dm 4846  df-rn 4847  df-res 4848  df-ima 4849  df-iota 5378  df-fun 5417  df-fn 5418  df-f 5419  df-f1 5420  df-fo 5421  df-f1o 5422  df-fv 5423  df-ov 6093  df-oprab 6094  df-mpt2 6095  df-om 6476  df-recs 6828  df-rdg 6862  df-oadd 6920  df-er 7097  df-en 7307  df-fin 7310
This theorem is referenced by:  unfi2  7577  difinf  7578  xpfi  7579  prfi  7582  tpfi  7583  fnfi  7585  iunfi  7595  pwfilem  7601  fsuppun  7635  fsuppunfi  7636  ressuppfi  7642  fiin  7668  wemapso2OLD  7762  cantnfp1lem1  7882  cantnfp1lem1OLD  7908  ficardun2  8368  ackbij1lem6  8390  ackbij1lem16  8400  fin23lem28  8505  fin23lem30  8507  isfin1-3  8551  axcclem  8622  hashun  12141  hashunlei  12171  hashmap  12193  hashbclem  12201  hashf1lem1  12204  hashf1lem2  12205  hashf1  12206  incexclem  13295  isumltss  13307  ramub1lem1  14083  fpwipodrs  15330  acsfiindd  15343  symgfisg  15967  gsumzaddlemOLD  16403  gsumunsnd  16443  dprdfaddOLD  16507  psrbagaddcl  17428  psrbagaddclOLD  17429  mplsubg  17505  mpllss  17506  funsnfsupOLD  17625  dsmmacl  18066  fctop  18508  uncmp  18906  bwth  18913  1stckgenlem  19026  ptbasin  19050  cfinfil  19366  fin1aufil  19405  alexsubALTlem3  19521  tmdgsum  19566  tsmsfbas  19598  tsmsgsum  19609  tsmsgsumOLD  19612  tsmsresOLD  19617  tsmsres  19618  tsmsxplem1  19627  prdsmet  19845  prdsbl  19966  icccmplem2  20300  rrxmval  20804  rrxmet  20807  rrxdstprj1  20808  ovolfiniun  20884  volfiniun  20928  fta1glem2  21581  fta1lem  21716  aannenlem2  21738  aalioulem2  21742  dchrfi  22537  usgrafilem2  23244  vdgrfiun  23491  konigsberg  23527  ffsrn  25948  gsumunsnf  26164  eulerpartlemt  26668  ballotlemgun  26821  itg2addnclem2  28353  ftc1anclem7  28382  ftc1anc  28384  locfincmp  28485  comppfsc  28488  prdsbnd  28601  elrfi  28939  mzpcompact2lem  28997  eldioph2  29009  lsmfgcl  29336  fiuneneq  29471  fsummsnunz  30150  fsumsplitsnun  30151  fsummmodsnunre  30152  mndpsuppfi  30688  pclfinN  33232
  Copyright terms: Public domain W3C validator