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

Theorem php 7694
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 7689 through phplem4 7692, nneneq 7693, 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 3813 . . . . . . . 8  |-  (/)  C_  B
2 sspsstr 3595 . . . . . . . 8  |-  ( (
(/)  C_  B  /\  B  C.  A )  ->  (/)  C.  A
)
31, 2mpan 668 . . . . . . 7  |-  ( B 
C.  A  ->  (/)  C.  A
)
4 0pss 3852 . . . . . . . 8  |-  ( (/)  C.  A  <->  A  =/=  (/) )
5 df-ne 2651 . . . . . . . 8  |-  ( A  =/=  (/)  <->  -.  A  =  (/) )
64, 5bitri 249 . . . . . . 7  |-  ( (/)  C.  A  <->  -.  A  =  (/) )
73, 6sylib 196 . . . . . 6  |-  ( B 
C.  A  ->  -.  A  =  (/) )
8 nn0suc 6697 . . . . . . 7  |-  ( A  e.  om  ->  ( A  =  (/)  \/  E. x  e.  om  A  =  suc  x ) )
98orcanai 911 . . . . . 6  |-  ( ( A  e.  om  /\  -.  A  =  (/) )  ->  E. x  e.  om  A  =  suc  x )
107, 9sylan2 472 . . . . 5  |-  ( ( A  e.  om  /\  B  C.  A )  ->  E. x  e.  om  A  =  suc  x )
11 pssnel 3881 . . . . . . . . . 10  |-  ( B 
C.  suc  x  ->  E. y ( y  e. 
suc  x  /\  -.  y  e.  B )
)
12 pssss 3585 . . . . . . . . . . . . . . . . 17  |-  ( B 
C.  suc  x  ->  B 
C_  suc  x )
13 ssdif 3625 . . . . . . . . . . . . . . . . . 18  |-  ( B 
C_  suc  x  ->  ( B  \  { y } )  C_  ( suc  x  \  { y } ) )
14 disjsn 4076 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  -.  y  e.  B )
15 disj3 3859 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  B  =  ( B  \  { y } ) )
1614, 15bitr3i 251 . . . . . . . . . . . . . . . . . . 19  |-  ( -.  y  e.  B  <->  B  =  ( B  \  { y } ) )
17 sseq1 3510 . . . . . . . . . . . . . . . . . . 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 3109 . . . . . . . . . . . . . . . . . . . 20  |-  x  e. 
_V
2120sucex 6619 . . . . . . . . . . . . . . . . . . 19  |-  suc  x  e.  _V
22 difss 3617 . . . . . . . . . . . . . . . . . . 19  |-  ( suc  x  \  { y } )  C_  suc  x
2321, 22ssexi 4582 . . . . . . . . . . . . . . . . . 18  |-  ( suc  x  \  { y } )  e.  _V
24 ssdomg 7554 . . . . . . . . . . . . . . . . . 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 427 . . . . . . . . . . . . . . 15  |-  ( ( -.  y  e.  B  /\  B  C.  suc  x
)  ->  B  ~<_  ( suc  x  \  { y } ) )
28 vex 3109 . . . . . . . . . . . . . . . . 17  |-  y  e. 
_V
2920, 28phplem3 7691 . . . . . . . . . . . . . . . 16  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  x  ~~  ( suc  x  \  { y } ) )
3029ensymd 7559 . . . . . . . . . . . . . . 15  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  ( suc  x  \  { y } ) 
~~  x )
31 domentr 7567 . . . . . . . . . . . . . . 15  |-  ( ( B  ~<_  ( suc  x  \  { y } )  /\  ( suc  x  \  { y } ) 
~~  x )  ->  B  ~<_  x )
3227, 30, 31syl2an 475 . . . . . . . . . . . . . 14  |-  ( ( ( -.  y  e.  B  /\  B  C.  suc  x )  /\  (
x  e.  om  /\  y  e.  suc  x ) )  ->  B  ~<_  x )
3332exp43 610 . . . . . . . . . . . . 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 427 . . . . . . . . . . 11  |-  ( ( y  e.  suc  x  /\  -.  y  e.  B
)  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) )
3635exlimiv 1727 . . . . . . . . . 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 7566 . . . . . . . . . . . 12  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~<_  x )
39 sssucid 4944 . . . . . . . . . . . . 13  |-  x  C_  suc  x
40 ssdomg 7554 . . . . . . . . . . . . 13  |-  ( suc  x  e.  _V  ->  ( x  C_  suc  x  ->  x  ~<_  suc  x )
)
4121, 39, 40mp2 9 . . . . . . . . . . . 12  |-  x  ~<_  suc  x
42 sbth 7630 . . . . . . . . . . . 12  |-  ( ( suc  x  ~<_  x  /\  x  ~<_  suc  x )  ->  suc  x  ~~  x
)
4338, 41, 42sylancl 660 . . . . . . . . . . 11  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~~  x
)
4443expcom 433 . . . . . . . . . 10  |-  ( B  ~<_  x  ->  ( suc  x  ~~  B  ->  suc  x  ~~  x ) )
45 peano2b 6689 . . . . . . . . . . . . 13  |-  ( x  e.  om  <->  suc  x  e. 
om )
46 nnord 6681 . . . . . . . . . . . . 13  |-  ( suc  x  e.  om  ->  Ord 
suc  x )
4745, 46sylbi 195 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  Ord  suc  x )
4820sucid 4946 . . . . . . . . . . . 12  |-  x  e. 
suc  x
49 nordeq 4886 . . . . . . . . . . . 12  |-  ( ( Ord  suc  x  /\  x  e.  suc  x )  ->  suc  x  =/=  x )
5047, 48, 49sylancl 660 . . . . . . . . . . 11  |-  ( x  e.  om  ->  suc  x  =/=  x )
51 nneneq 7693 . . . . . . . . . . . . . 14  |-  ( ( suc  x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5245, 51sylanb 470 . . . . . . . . . . . . 13  |-  ( ( x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5352anidms 643 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  ( suc  x  ~~  x  <->  suc  x  =  x ) )
5453necon3bbid 2701 . . . . . . . . . . 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 3578 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( B  C.  A  <->  B 
C.  suc  x )
)
60 breq1 4442 . . . . . . . . 9  |-  ( A  =  suc  x  -> 
( A  ~~  B  <->  suc  x  ~~  B ) )
6160notbid 292 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( -.  A  ~~  B 
<->  -.  suc  x  ~~  B ) )
6259, 61imbi12d 318 . . . . . . 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 2940 . . . . 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 432 . . 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 427 1  |-  ( ( A  e.  om  /\  B  C.  A )  ->  -.  A  ~~  B )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 184    /\ wa 367    = wceq 1398   E.wex 1617    e. wcel 1823    =/= wne 2649   E.wrex 2805   _Vcvv 3106    \ cdif 3458    i^i cin 3460    C_ wss 3461    C. wpss 3462   (/)c0 3783   {csn 4016   class class class wbr 4439   Ord word 4866   suc csuc 4869   omcom 6673    ~~ cen 7506    ~<_ cdom 7507
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1623  ax-4 1636  ax-5 1709  ax-6 1752  ax-7 1795  ax-8 1825  ax-9 1827  ax-10 1842  ax-11 1847  ax-12 1859  ax-13 2004  ax-ext 2432  ax-sep 4560  ax-nul 4568  ax-pow 4615  ax-pr 4676  ax-un 6565
This theorem depends on definitions:  df-bi 185  df-or 368  df-an 369  df-3or 972  df-3an 973  df-tru 1401  df-ex 1618  df-nf 1622  df-sb 1745  df-eu 2288  df-mo 2289  df-clab 2440  df-cleq 2446  df-clel 2449  df-nfc 2604  df-ne 2651  df-ral 2809  df-rex 2810  df-rab 2813  df-v 3108  df-sbc 3325  df-dif 3464  df-un 3466  df-in 3468  df-ss 3475  df-pss 3477  df-nul 3784  df-if 3930  df-pw 4001  df-sn 4017  df-pr 4019  df-tp 4021  df-op 4023  df-uni 4236  df-br 4440  df-opab 4498  df-tr 4533  df-eprel 4780  df-id 4784  df-po 4789  df-so 4790  df-fr 4827  df-we 4829  df-ord 4870  df-on 4871  df-lim 4872  df-suc 4873  df-xp 4994  df-rel 4995  df-cnv 4996  df-co 4997  df-dm 4998  df-rn 4999  df-res 5000  df-ima 5001  df-iota 5534  df-fun 5572  df-fn 5573  df-f 5574  df-f1 5575  df-fo 5576  df-f1o 5577  df-fv 5578  df-om 6674  df-er 7303  df-en 7510  df-dom 7511
This theorem is referenced by:  php2  7695  php3  7696
  Copyright terms: Public domain W3C validator