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

Theorem php 7493
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 7488 through phplem4 7491, nneneq 7492, 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 3664 . . . . . . . 8  |-  (/)  C_  B
2 sspsstr 3459 . . . . . . . 8  |-  ( (
(/)  C_  B  /\  B  C.  A )  ->  (/)  C.  A
)
31, 2mpan 670 . . . . . . 7  |-  ( B 
C.  A  ->  (/)  C.  A
)
4 0pss 3714 . . . . . . . 8  |-  ( (/)  C.  A  <->  A  =/=  (/) )
5 df-ne 2606 . . . . . . . 8  |-  ( A  =/=  (/)  <->  -.  A  =  (/) )
64, 5bitri 249 . . . . . . 7  |-  ( (/)  C.  A  <->  -.  A  =  (/) )
73, 6sylib 196 . . . . . 6  |-  ( B 
C.  A  ->  -.  A  =  (/) )
8 nn0suc 6498 . . . . . . 7  |-  ( A  e.  om  ->  ( A  =  (/)  \/  E. x  e.  om  A  =  suc  x ) )
98orcanai 904 . . . . . 6  |-  ( ( A  e.  om  /\  -.  A  =  (/) )  ->  E. x  e.  om  A  =  suc  x )
107, 9sylan2 474 . . . . 5  |-  ( ( A  e.  om  /\  B  C.  A )  ->  E. x  e.  om  A  =  suc  x )
11 pssnel 3742 . . . . . . . . . 10  |-  ( B 
C.  suc  x  ->  E. y ( y  e. 
suc  x  /\  -.  y  e.  B )
)
12 pssss 3449 . . . . . . . . . . . . . . . . 17  |-  ( B 
C.  suc  x  ->  B 
C_  suc  x )
13 ssdif 3489 . . . . . . . . . . . . . . . . . 18  |-  ( B 
C_  suc  x  ->  ( B  \  { y } )  C_  ( suc  x  \  { y } ) )
14 disjsn 3934 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  -.  y  e.  B )
15 disj3 3721 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  B  =  ( B  \  { y } ) )
1614, 15bitr3i 251 . . . . . . . . . . . . . . . . . . 19  |-  ( -.  y  e.  B  <->  B  =  ( B  \  { y } ) )
17 sseq1 3375 . . . . . . . . . . . . . . . . . . 19  |-  ( B  =  ( B  \  { y } )  ->  ( B  C_  ( suc  x  \  {
y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1816, 17sylbi 195 . . . . . . . . . . . . . . . . . 18  |-  ( -.  y  e.  B  -> 
( B  C_  ( suc  x  \  { y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1913, 18syl5ibr 221 . . . . . . . . . . . . . . . . 17  |-  ( -.  y  e.  B  -> 
( B  C_  suc  x  ->  B  C_  ( suc  x  \  { y } ) ) )
20 vex 2973 . . . . . . . . . . . . . . . . . . . 20  |-  x  e. 
_V
2120sucex 6420 . . . . . . . . . . . . . . . . . . 19  |-  suc  x  e.  _V
22 difss 3481 . . . . . . . . . . . . . . . . . . 19  |-  ( suc  x  \  { y } )  C_  suc  x
2321, 22ssexi 4435 . . . . . . . . . . . . . . . . . 18  |-  ( suc  x  \  { y } )  e.  _V
24 ssdomg 7353 . . . . . . . . . . . . . . . . . 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 34 . . . . . . . . . . . . . . . 16  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  B  ~<_  ( suc  x  \  { y } ) ) )
2726imp 429 . . . . . . . . . . . . . . 15  |-  ( ( -.  y  e.  B  /\  B  C.  suc  x
)  ->  B  ~<_  ( suc  x  \  { y } ) )
28 vex 2973 . . . . . . . . . . . . . . . . 17  |-  y  e. 
_V
2920, 28phplem3 7490 . . . . . . . . . . . . . . . 16  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  x  ~~  ( suc  x  \  { y } ) )
3029ensymd 7358 . . . . . . . . . . . . . . 15  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  ( suc  x  \  { y } ) 
~~  x )
31 domentr 7366 . . . . . . . . . . . . . . 15  |-  ( ( B  ~<_  ( suc  x  \  { y } )  /\  ( suc  x  \  { y } ) 
~~  x )  ->  B  ~<_  x )
3227, 30, 31syl2an 477 . . . . . . . . . . . . . 14  |-  ( ( ( -.  y  e.  B  /\  B  C.  suc  x )  /\  (
x  e.  om  /\  y  e.  suc  x ) )  ->  B  ~<_  x )
3332exp43 612 . . . . . . . . . . . . 13  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  ( x  e.  om  ->  ( y  e.  suc  x  ->  B  ~<_  x ) ) ) )
3433com4r 86 . . . . . . . . . . . 12  |-  ( y  e.  suc  x  -> 
( -.  y  e.  B  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) ) )
3534imp 429 . . . . . . . . . . 11  |-  ( ( y  e.  suc  x  /\  -.  y  e.  B
)  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) )
3635exlimiv 1688 . . . . . . . . . 10  |-  ( E. y ( y  e. 
suc  x  /\  -.  y  e.  B )  ->  ( B  C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) ) )
3711, 36mpcom 36 . . . . . . . . 9  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) )
38 endomtr 7365 . . . . . . . . . . . 12  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~<_  x )
39 sssucid 4794 . . . . . . . . . . . . 13  |-  x  C_  suc  x
40 ssdomg 7353 . . . . . . . . . . . . 13  |-  ( suc  x  e.  _V  ->  ( x  C_  suc  x  ->  x  ~<_  suc  x )
)
4121, 39, 40mp2 9 . . . . . . . . . . . 12  |-  x  ~<_  suc  x
42 sbth 7429 . . . . . . . . . . . 12  |-  ( ( suc  x  ~<_  x  /\  x  ~<_  suc  x )  ->  suc  x  ~~  x
)
4338, 41, 42sylancl 662 . . . . . . . . . . 11  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~~  x
)
4443expcom 435 . . . . . . . . . 10  |-  ( B  ~<_  x  ->  ( suc  x  ~~  B  ->  suc  x  ~~  x ) )
45 peano2b 6490 . . . . . . . . . . . . 13  |-  ( x  e.  om  <->  suc  x  e. 
om )
46 nnord 6482 . . . . . . . . . . . . 13  |-  ( suc  x  e.  om  ->  Ord 
suc  x )
4745, 46sylbi 195 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  Ord  suc  x )
4820sucid 4796 . . . . . . . . . . . 12  |-  x  e. 
suc  x
49 nordeq 4736 . . . . . . . . . . . 12  |-  ( ( Ord  suc  x  /\  x  e.  suc  x )  ->  suc  x  =/=  x )
5047, 48, 49sylancl 662 . . . . . . . . . . 11  |-  ( x  e.  om  ->  suc  x  =/=  x )
51 nneneq 7492 . . . . . . . . . . . . . 14  |-  ( ( suc  x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5245, 51sylanb 472 . . . . . . . . . . . . 13  |-  ( ( x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5352anidms 645 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  ( suc  x  ~~  x  <->  suc  x  =  x ) )
5453necon3bbid 2640 . . . . . . . . . . 11  |-  ( x  e.  om  ->  ( -.  suc  x  ~~  x  <->  suc  x  =/=  x ) )
5550, 54mpbird 232 . . . . . . . . . 10  |-  ( x  e.  om  ->  -.  suc  x  ~~  x )
5644, 55nsyli 141 . . . . . . . . 9  |-  ( B  ~<_  x  ->  ( x  e.  om  ->  -.  suc  x  ~~  B ) )
5737, 56syli 37 . . . . . . . 8  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  -. 
suc  x  ~~  B
) )
5857com12 31 . . . . . . 7  |-  ( x  e.  om  ->  ( B  C.  suc  x  ->  -.  suc  x  ~~  B
) )
59 psseq2 3442 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( B  C.  A  <->  B 
C.  suc  x )
)
60 breq1 4293 . . . . . . . . 9  |-  ( A  =  suc  x  -> 
( A  ~~  B  <->  suc  x  ~~  B ) )
6160notbid 294 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( -.  A  ~~  B 
<->  -.  suc  x  ~~  B ) )
6259, 61imbi12d 320 . . . . . . 7  |-  ( A  =  suc  x  -> 
( ( B  C.  A  ->  -.  A  ~~  B )  <->  ( B  C. 
suc  x  ->  -.  suc  x  ~~  B ) ) )
6358, 62syl5ibrcom 222 . . . . . 6  |-  ( x  e.  om  ->  ( A  =  suc  x  -> 
( B  C.  A  ->  -.  A  ~~  B
) ) )
6463rexlimiv 2833 . . . . 5  |-  ( E. x  e.  om  A  =  suc  x  ->  ( B  C.  A  ->  -.  A  ~~  B ) )
6510, 64syl 16 . . . 4  |-  ( ( A  e.  om  /\  B  C.  A )  -> 
( B  C.  A  ->  -.  A  ~~  B
) )
6665ex 434 . . 3  |-  ( A  e.  om  ->  ( B  C.  A  ->  ( B  C.  A  ->  -.  A  ~~  B ) ) )
6766pm2.43d 48 . 2  |-  ( A  e.  om  ->  ( B  C.  A  ->  -.  A  ~~  B ) )
6867imp 429 1  |-  ( ( A  e.  om  /\  B  C.  A )  ->  -.  A  ~~  B )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 184    /\ wa 369    = wceq 1369   E.wex 1586    e. wcel 1756    =/= wne 2604   E.wrex 2714   _Vcvv 2970    \ cdif 3323    i^i cin 3325    C_ wss 3326    C. wpss 3327   (/)c0 3635   {csn 3875   class class class wbr 4290   Ord word 4716   suc csuc 4719   omcom 6474    ~~ cen 7305    ~<_ cdom 7306
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 2422  ax-sep 4411  ax-nul 4419  ax-pow 4468  ax-pr 4529  ax-un 6370
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 2428  df-cleq 2434  df-clel 2437  df-nfc 2566  df-ne 2606  df-ral 2718  df-rex 2719  df-rab 2722  df-v 2972  df-sbc 3185  df-dif 3329  df-un 3331  df-in 3333  df-ss 3340  df-pss 3342  df-nul 3636  df-if 3790  df-pw 3860  df-sn 3876  df-pr 3878  df-tp 3880  df-op 3882  df-uni 4090  df-br 4291  df-opab 4349  df-tr 4384  df-eprel 4630  df-id 4634  df-po 4639  df-so 4640  df-fr 4677  df-we 4679  df-ord 4720  df-on 4721  df-lim 4722  df-suc 4723  df-xp 4844  df-rel 4845  df-cnv 4846  df-co 4847  df-dm 4848  df-rn 4849  df-res 4850  df-ima 4851  df-iota 5379  df-fun 5418  df-fn 5419  df-f 5420  df-f1 5421  df-fo 5422  df-f1o 5423  df-fv 5424  df-om 6475  df-er 7099  df-en 7309  df-dom 7310
This theorem is referenced by:  php2  7494  php3  7495
  Copyright terms: Public domain W3C validator