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

Theorem php 7781
Description: Pigeonhole Principle. A natural number is not equinumerous to a proper subset of itself. Theorem (Pigeonhole Principle) of [Enderton] p. 134. The theorem is so-called because you can't put n + 1 pigeons into n holes (if each hole holds only one pigeon). The proof consists of lemmas phplem1 7776 through phplem4 7779, nneneq 7780, and this final piece of the proof. (Contributed by NM, 29-May-1998.)
Assertion
Ref Expression
php  |-  ( ( A  e.  om  /\  B  C.  A )  ->  -.  A  ~~  B )

Proof of Theorem php
Dummy variables  x  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 0ss 3774 . . . . . . . 8  |-  (/)  C_  B
2 sspsstr 3549 . . . . . . . 8  |-  ( (
(/)  C_  B  /\  B  C.  A )  ->  (/)  C.  A
)
31, 2mpan 681 . . . . . . 7  |-  ( B 
C.  A  ->  (/)  C.  A
)
4 0pss 3813 . . . . . . . 8  |-  ( (/)  C.  A  <->  A  =/=  (/) )
5 df-ne 2634 . . . . . . . 8  |-  ( A  =/=  (/)  <->  -.  A  =  (/) )
64, 5bitri 257 . . . . . . 7  |-  ( (/)  C.  A  <->  -.  A  =  (/) )
73, 6sylib 201 . . . . . 6  |-  ( B 
C.  A  ->  -.  A  =  (/) )
8 nn0suc 6743 . . . . . . 7  |-  ( A  e.  om  ->  ( A  =  (/)  \/  E. x  e.  om  A  =  suc  x ) )
98orcanai 929 . . . . . 6  |-  ( ( A  e.  om  /\  -.  A  =  (/) )  ->  E. x  e.  om  A  =  suc  x )
107, 9sylan2 481 . . . . 5  |-  ( ( A  e.  om  /\  B  C.  A )  ->  E. x  e.  om  A  =  suc  x )
11 pssnel 3843 . . . . . . . . . 10  |-  ( B 
C.  suc  x  ->  E. y ( y  e. 
suc  x  /\  -.  y  e.  B )
)
12 pssss 3539 . . . . . . . . . . . . . . . . 17  |-  ( B 
C.  suc  x  ->  B 
C_  suc  x )
13 ssdif 3579 . . . . . . . . . . . . . . . . . 18  |-  ( B 
C_  suc  x  ->  ( B  \  { y } )  C_  ( suc  x  \  { y } ) )
14 disjsn 4043 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  -.  y  e.  B )
15 disj3 3820 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  B  =  ( B  \  { y } ) )
1614, 15bitr3i 259 . . . . . . . . . . . . . . . . . . 19  |-  ( -.  y  e.  B  <->  B  =  ( B  \  { y } ) )
17 sseq1 3464 . . . . . . . . . . . . . . . . . . 19  |-  ( B  =  ( B  \  { y } )  ->  ( B  C_  ( suc  x  \  {
y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1816, 17sylbi 200 . . . . . . . . . . . . . . . . . 18  |-  ( -.  y  e.  B  -> 
( B  C_  ( suc  x  \  { y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1913, 18syl5ibr 229 . . . . . . . . . . . . . . . . 17  |-  ( -.  y  e.  B  -> 
( B  C_  suc  x  ->  B  C_  ( suc  x  \  { y } ) ) )
20 vex 3059 . . . . . . . . . . . . . . . . . . . 20  |-  x  e. 
_V
2120sucex 6664 . . . . . . . . . . . . . . . . . . 19  |-  suc  x  e.  _V
22 difss 3571 . . . . . . . . . . . . . . . . . . 19  |-  ( suc  x  \  { y } )  C_  suc  x
2321, 22ssexi 4561 . . . . . . . . . . . . . . . . . 18  |-  ( suc  x  \  { y } )  e.  _V
24 ssdomg 7640 . . . . . . . . . . . . . . . . . 18  |-  ( ( suc  x  \  {
y } )  e. 
_V  ->  ( B  C_  ( suc  x  \  {
y } )  ->  B  ~<_  ( suc  x  \  { y } ) ) )
2523, 24ax-mp 5 . . . . . . . . . . . . . . . . 17  |-  ( B 
C_  ( suc  x  \  { y } )  ->  B  ~<_  ( suc  x  \  { y } ) )
2612, 19, 25syl56 35 . . . . . . . . . . . . . . . 16  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  B  ~<_  ( suc  x  \  { y } ) ) )
2726imp 435 . . . . . . . . . . . . . . 15  |-  ( ( -.  y  e.  B  /\  B  C.  suc  x
)  ->  B  ~<_  ( suc  x  \  { y } ) )
28 vex 3059 . . . . . . . . . . . . . . . . 17  |-  y  e. 
_V
2920, 28phplem3 7778 . . . . . . . . . . . . . . . 16  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  x  ~~  ( suc  x  \  { y } ) )
3029ensymd 7645 . . . . . . . . . . . . . . 15  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  ( suc  x  \  { y } ) 
~~  x )
31 domentr 7653 . . . . . . . . . . . . . . 15  |-  ( ( B  ~<_  ( suc  x  \  { y } )  /\  ( suc  x  \  { y } ) 
~~  x )  ->  B  ~<_  x )
3227, 30, 31syl2an 484 . . . . . . . . . . . . . 14  |-  ( ( ( -.  y  e.  B  /\  B  C.  suc  x )  /\  (
x  e.  om  /\  y  e.  suc  x ) )  ->  B  ~<_  x )
3332exp43 621 . . . . . . . . . . . . 13  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  ( x  e.  om  ->  ( y  e.  suc  x  ->  B  ~<_  x ) ) ) )
3433com4r 89 . . . . . . . . . . . 12  |-  ( y  e.  suc  x  -> 
( -.  y  e.  B  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) ) )
3534imp 435 . . . . . . . . . . 11  |-  ( ( y  e.  suc  x  /\  -.  y  e.  B
)  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) )
3635exlimiv 1786 . . . . . . . . . 10  |-  ( E. y ( y  e. 
suc  x  /\  -.  y  e.  B )  ->  ( B  C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) ) )
3711, 36mpcom 37 . . . . . . . . 9  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) )
38 endomtr 7652 . . . . . . . . . . . 12  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~<_  x )
39 sssucid 5518 . . . . . . . . . . . . 13  |-  x  C_  suc  x
40 ssdomg 7640 . . . . . . . . . . . . 13  |-  ( suc  x  e.  _V  ->  ( x  C_  suc  x  ->  x  ~<_  suc  x )
)
4121, 39, 40mp2 9 . . . . . . . . . . . 12  |-  x  ~<_  suc  x
42 sbth 7717 . . . . . . . . . . . 12  |-  ( ( suc  x  ~<_  x  /\  x  ~<_  suc  x )  ->  suc  x  ~~  x
)
4338, 41, 42sylancl 673 . . . . . . . . . . 11  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~~  x
)
4443expcom 441 . . . . . . . . . 10  |-  ( B  ~<_  x  ->  ( suc  x  ~~  B  ->  suc  x  ~~  x ) )
45 peano2b 6734 . . . . . . . . . . . . 13  |-  ( x  e.  om  <->  suc  x  e. 
om )
46 nnord 6726 . . . . . . . . . . . . 13  |-  ( suc  x  e.  om  ->  Ord 
suc  x )
4745, 46sylbi 200 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  Ord  suc  x )
4820sucid 5520 . . . . . . . . . . . 12  |-  x  e. 
suc  x
49 nordeq 5460 . . . . . . . . . . . 12  |-  ( ( Ord  suc  x  /\  x  e.  suc  x )  ->  suc  x  =/=  x )
5047, 48, 49sylancl 673 . . . . . . . . . . 11  |-  ( x  e.  om  ->  suc  x  =/=  x )
51 nneneq 7780 . . . . . . . . . . . . . 14  |-  ( ( suc  x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5245, 51sylanb 479 . . . . . . . . . . . . 13  |-  ( ( x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5352anidms 655 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  ( suc  x  ~~  x  <->  suc  x  =  x ) )
5453necon3bbid 2672 . . . . . . . . . . 11  |-  ( x  e.  om  ->  ( -.  suc  x  ~~  x  <->  suc  x  =/=  x ) )
5550, 54mpbird 240 . . . . . . . . . 10  |-  ( x  e.  om  ->  -.  suc  x  ~~  x )
5644, 55nsyli 148 . . . . . . . . 9  |-  ( B  ~<_  x  ->  ( x  e.  om  ->  -.  suc  x  ~~  B ) )
5737, 56syli 38 . . . . . . . 8  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  -. 
suc  x  ~~  B
) )
5857com12 32 . . . . . . 7  |-  ( x  e.  om  ->  ( B  C.  suc  x  ->  -.  suc  x  ~~  B
) )
59 psseq2 3532 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( B  C.  A  <->  B 
C.  suc  x )
)
60 breq1 4418 . . . . . . . . 9  |-  ( A  =  suc  x  -> 
( A  ~~  B  <->  suc  x  ~~  B ) )
6160notbid 300 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( -.  A  ~~  B 
<->  -.  suc  x  ~~  B ) )
6259, 61imbi12d 326 . . . . . . 7  |-  ( A  =  suc  x  -> 
( ( B  C.  A  ->  -.  A  ~~  B )  <->  ( B  C. 
suc  x  ->  -.  suc  x  ~~  B ) ) )
6358, 62syl5ibrcom 230 . . . . . 6  |-  ( x  e.  om  ->  ( A  =  suc  x  -> 
( B  C.  A  ->  -.  A  ~~  B
) ) )
6463rexlimiv 2884 . . . . 5  |-  ( E. x  e.  om  A  =  suc  x  ->  ( B  C.  A  ->  -.  A  ~~  B ) )
6510, 64syl 17 . . . 4  |-  ( ( A  e.  om  /\  B  C.  A )  -> 
( B  C.  A  ->  -.  A  ~~  B
) )
6665ex 440 . . 3  |-  ( A  e.  om  ->  ( B  C.  A  ->  ( B  C.  A  ->  -.  A  ~~  B ) ) )
6766pm2.43d 50 . 2  |-  ( A  e.  om  ->  ( B  C.  A  ->  -.  A  ~~  B ) )
6867imp 435 1  |-  ( ( A  e.  om  /\  B  C.  A )  ->  -.  A  ~~  B )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 189    /\ wa 375    = wceq 1454   E.wex 1673    e. wcel 1897    =/= wne 2632   E.wrex 2749   _Vcvv 3056    \ cdif 3412    i^i cin 3414    C_ wss 3415    C. wpss 3416   (/)c0 3742   {csn 3979   class class class wbr 4415   Ord word 5440   suc csuc 5443   omcom 6718    ~~ cen 7591    ~<_ cdom 7592
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1679  ax-4 1692  ax-5 1768  ax-6 1815  ax-7 1861  ax-8 1899  ax-9 1906  ax-10 1925  ax-11 1930  ax-12 1943  ax-13 2101  ax-ext 2441  ax-sep 4538  ax-nul 4547  ax-pow 4594  ax-pr 4652  ax-un 6609
This theorem depends on definitions:  df-bi 190  df-or 376  df-an 377  df-3or 992  df-3an 993  df-tru 1457  df-ex 1674  df-nf 1678  df-sb 1808  df-eu 2313  df-mo 2314  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2591  df-ne 2634  df-ral 2753  df-rex 2754  df-rab 2757  df-v 3058  df-sbc 3279  df-dif 3418  df-un 3420  df-in 3422  df-ss 3429  df-pss 3431  df-nul 3743  df-if 3893  df-pw 3964  df-sn 3980  df-pr 3982  df-tp 3984  df-op 3986  df-uni 4212  df-br 4416  df-opab 4475  df-tr 4511  df-eprel 4763  df-id 4767  df-po 4773  df-so 4774  df-fr 4811  df-we 4813  df-xp 4858  df-rel 4859  df-cnv 4860  df-co 4861  df-dm 4862  df-rn 4863  df-res 4864  df-ima 4865  df-ord 5444  df-on 5445  df-lim 5446  df-suc 5447  df-iota 5564  df-fun 5602  df-fn 5603  df-f 5604  df-f1 5605  df-fo 5606  df-f1o 5607  df-fv 5608  df-om 6719  df-er 7388  df-en 7595  df-dom 7596
This theorem is referenced by:  php2  7782  php3  7783
  Copyright terms: Public domain W3C validator