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

Theorem php 7760
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 7755 through phplem4 7758, nneneq 7759, 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 3792 . . . . . . . 8  |-  (/)  C_  B
2 sspsstr 3571 . . . . . . . 8  |-  ( (
(/)  C_  B  /\  B  C.  A )  ->  (/)  C.  A
)
31, 2mpan 675 . . . . . . 7  |-  ( B 
C.  A  ->  (/)  C.  A
)
4 0pss 3831 . . . . . . . 8  |-  ( (/)  C.  A  <->  A  =/=  (/) )
5 df-ne 2621 . . . . . . . 8  |-  ( A  =/=  (/)  <->  -.  A  =  (/) )
64, 5bitri 253 . . . . . . 7  |-  ( (/)  C.  A  <->  -.  A  =  (/) )
73, 6sylib 200 . . . . . 6  |-  ( B 
C.  A  ->  -.  A  =  (/) )
8 nn0suc 6729 . . . . . . 7  |-  ( A  e.  om  ->  ( A  =  (/)  \/  E. x  e.  om  A  =  suc  x ) )
98orcanai 922 . . . . . 6  |-  ( ( A  e.  om  /\  -.  A  =  (/) )  ->  E. x  e.  om  A  =  suc  x )
107, 9sylan2 477 . . . . 5  |-  ( ( A  e.  om  /\  B  C.  A )  ->  E. x  e.  om  A  =  suc  x )
11 pssnel 3861 . . . . . . . . . 10  |-  ( B 
C.  suc  x  ->  E. y ( y  e. 
suc  x  /\  -.  y  e.  B )
)
12 pssss 3561 . . . . . . . . . . . . . . . . 17  |-  ( B 
C.  suc  x  ->  B 
C_  suc  x )
13 ssdif 3601 . . . . . . . . . . . . . . . . . 18  |-  ( B 
C_  suc  x  ->  ( B  \  { y } )  C_  ( suc  x  \  { y } ) )
14 disjsn 4058 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  -.  y  e.  B )
15 disj3 3838 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( B  i^i  { y } )  =  (/)  <->  B  =  ( B  \  { y } ) )
1614, 15bitr3i 255 . . . . . . . . . . . . . . . . . . 19  |-  ( -.  y  e.  B  <->  B  =  ( B  \  { y } ) )
17 sseq1 3486 . . . . . . . . . . . . . . . . . . 19  |-  ( B  =  ( B  \  { y } )  ->  ( B  C_  ( suc  x  \  {
y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1816, 17sylbi 199 . . . . . . . . . . . . . . . . . 18  |-  ( -.  y  e.  B  -> 
( B  C_  ( suc  x  \  { y } )  <->  ( B  \  { y } ) 
C_  ( suc  x  \  { y } ) ) )
1913, 18syl5ibr 225 . . . . . . . . . . . . . . . . 17  |-  ( -.  y  e.  B  -> 
( B  C_  suc  x  ->  B  C_  ( suc  x  \  { y } ) ) )
20 vex 3085 . . . . . . . . . . . . . . . . . . . 20  |-  x  e. 
_V
2120sucex 6650 . . . . . . . . . . . . . . . . . . 19  |-  suc  x  e.  _V
22 difss 3593 . . . . . . . . . . . . . . . . . . 19  |-  ( suc  x  \  { y } )  C_  suc  x
2321, 22ssexi 4567 . . . . . . . . . . . . . . . . . 18  |-  ( suc  x  \  { y } )  e.  _V
24 ssdomg 7620 . . . . . . . . . . . . . . . . . 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 36 . . . . . . . . . . . . . . . 16  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  B  ~<_  ( suc  x  \  { y } ) ) )
2726imp 431 . . . . . . . . . . . . . . 15  |-  ( ( -.  y  e.  B  /\  B  C.  suc  x
)  ->  B  ~<_  ( suc  x  \  { y } ) )
28 vex 3085 . . . . . . . . . . . . . . . . 17  |-  y  e. 
_V
2920, 28phplem3 7757 . . . . . . . . . . . . . . . 16  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  x  ~~  ( suc  x  \  { y } ) )
3029ensymd 7625 . . . . . . . . . . . . . . 15  |-  ( ( x  e.  om  /\  y  e.  suc  x )  ->  ( suc  x  \  { y } ) 
~~  x )
31 domentr 7633 . . . . . . . . . . . . . . 15  |-  ( ( B  ~<_  ( suc  x  \  { y } )  /\  ( suc  x  \  { y } ) 
~~  x )  ->  B  ~<_  x )
3227, 30, 31syl2an 480 . . . . . . . . . . . . . 14  |-  ( ( ( -.  y  e.  B  /\  B  C.  suc  x )  /\  (
x  e.  om  /\  y  e.  suc  x ) )  ->  B  ~<_  x )
3332exp43 616 . . . . . . . . . . . . 13  |-  ( -.  y  e.  B  -> 
( B  C.  suc  x  ->  ( x  e.  om  ->  ( y  e.  suc  x  ->  B  ~<_  x ) ) ) )
3433com4r 90 . . . . . . . . . . . 12  |-  ( y  e.  suc  x  -> 
( -.  y  e.  B  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) ) )
3534imp 431 . . . . . . . . . . 11  |-  ( ( y  e.  suc  x  /\  -.  y  e.  B
)  ->  ( B  C. 
suc  x  ->  (
x  e.  om  ->  B  ~<_  x ) ) )
3635exlimiv 1767 . . . . . . . . . 10  |-  ( E. y ( y  e. 
suc  x  /\  -.  y  e.  B )  ->  ( B  C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) ) )
3711, 36mpcom 38 . . . . . . . . 9  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  B  ~<_  x ) )
38 endomtr 7632 . . . . . . . . . . . 12  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~<_  x )
39 sssucid 5517 . . . . . . . . . . . . 13  |-  x  C_  suc  x
40 ssdomg 7620 . . . . . . . . . . . . 13  |-  ( suc  x  e.  _V  ->  ( x  C_  suc  x  ->  x  ~<_  suc  x )
)
4121, 39, 40mp2 9 . . . . . . . . . . . 12  |-  x  ~<_  suc  x
42 sbth 7696 . . . . . . . . . . . 12  |-  ( ( suc  x  ~<_  x  /\  x  ~<_  suc  x )  ->  suc  x  ~~  x
)
4338, 41, 42sylancl 667 . . . . . . . . . . 11  |-  ( ( suc  x  ~~  B  /\  B  ~<_  x )  ->  suc  x  ~~  x
)
4443expcom 437 . . . . . . . . . 10  |-  ( B  ~<_  x  ->  ( suc  x  ~~  B  ->  suc  x  ~~  x ) )
45 peano2b 6720 . . . . . . . . . . . . 13  |-  ( x  e.  om  <->  suc  x  e. 
om )
46 nnord 6712 . . . . . . . . . . . . 13  |-  ( suc  x  e.  om  ->  Ord 
suc  x )
4745, 46sylbi 199 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  Ord  suc  x )
4820sucid 5519 . . . . . . . . . . . 12  |-  x  e. 
suc  x
49 nordeq 5459 . . . . . . . . . . . 12  |-  ( ( Ord  suc  x  /\  x  e.  suc  x )  ->  suc  x  =/=  x )
5047, 48, 49sylancl 667 . . . . . . . . . . 11  |-  ( x  e.  om  ->  suc  x  =/=  x )
51 nneneq 7759 . . . . . . . . . . . . . 14  |-  ( ( suc  x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5245, 51sylanb 475 . . . . . . . . . . . . 13  |-  ( ( x  e.  om  /\  x  e.  om )  ->  ( suc  x  ~~  x 
<->  suc  x  =  x ) )
5352anidms 650 . . . . . . . . . . . 12  |-  ( x  e.  om  ->  ( suc  x  ~~  x  <->  suc  x  =  x ) )
5453necon3bbid 2672 . . . . . . . . . . 11  |-  ( x  e.  om  ->  ( -.  suc  x  ~~  x  <->  suc  x  =/=  x ) )
5550, 54mpbird 236 . . . . . . . . . 10  |-  ( x  e.  om  ->  -.  suc  x  ~~  x )
5644, 55nsyli 147 . . . . . . . . 9  |-  ( B  ~<_  x  ->  ( x  e.  om  ->  -.  suc  x  ~~  B ) )
5737, 56syli 39 . . . . . . . 8  |-  ( B 
C.  suc  x  ->  ( x  e.  om  ->  -. 
suc  x  ~~  B
) )
5857com12 33 . . . . . . 7  |-  ( x  e.  om  ->  ( B  C.  suc  x  ->  -.  suc  x  ~~  B
) )
59 psseq2 3554 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( B  C.  A  <->  B 
C.  suc  x )
)
60 breq1 4424 . . . . . . . . 9  |-  ( A  =  suc  x  -> 
( A  ~~  B  <->  suc  x  ~~  B ) )
6160notbid 296 . . . . . . . 8  |-  ( A  =  suc  x  -> 
( -.  A  ~~  B 
<->  -.  suc  x  ~~  B ) )
6259, 61imbi12d 322 . . . . . . 7  |-  ( A  =  suc  x  -> 
( ( B  C.  A  ->  -.  A  ~~  B )  <->  ( B  C. 
suc  x  ->  -.  suc  x  ~~  B ) ) )
6358, 62syl5ibrcom 226 . . . . . 6  |-  ( x  e.  om  ->  ( A  =  suc  x  -> 
( B  C.  A  ->  -.  A  ~~  B
) ) )
6463rexlimiv 2912 . . . . 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 436 . . 3  |-  ( A  e.  om  ->  ( B  C.  A  ->  ( B  C.  A  ->  -.  A  ~~  B ) ) )
6766pm2.43d 51 . 2  |-  ( A  e.  om  ->  ( B  C.  A  ->  -.  A  ~~  B ) )
6867imp 431 1  |-  ( ( A  e.  om  /\  B  C.  A )  ->  -.  A  ~~  B )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 188    /\ wa 371    = wceq 1438   E.wex 1660    e. wcel 1869    =/= wne 2619   E.wrex 2777   _Vcvv 3082    \ cdif 3434    i^i cin 3436    C_ wss 3437    C. wpss 3438   (/)c0 3762   {csn 3997   class class class wbr 4421   Ord word 5439   suc csuc 5442   omcom 6704    ~~ cen 7572    ~<_ cdom 7573
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1666  ax-4 1679  ax-5 1749  ax-6 1795  ax-7 1840  ax-8 1871  ax-9 1873  ax-10 1888  ax-11 1893  ax-12 1906  ax-13 2054  ax-ext 2401  ax-sep 4544  ax-nul 4553  ax-pow 4600  ax-pr 4658  ax-un 6595
This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3or 984  df-3an 985  df-tru 1441  df-ex 1661  df-nf 1665  df-sb 1788  df-eu 2270  df-mo 2271  df-clab 2409  df-cleq 2415  df-clel 2418  df-nfc 2573  df-ne 2621  df-ral 2781  df-rex 2782  df-rab 2785  df-v 3084  df-sbc 3301  df-dif 3440  df-un 3442  df-in 3444  df-ss 3451  df-pss 3453  df-nul 3763  df-if 3911  df-pw 3982  df-sn 3998  df-pr 4000  df-tp 4002  df-op 4004  df-uni 4218  df-br 4422  df-opab 4481  df-tr 4517  df-eprel 4762  df-id 4766  df-po 4772  df-so 4773  df-fr 4810  df-we 4812  df-xp 4857  df-rel 4858  df-cnv 4859  df-co 4860  df-dm 4861  df-rn 4862  df-res 4863  df-ima 4864  df-ord 5443  df-on 5444  df-lim 5445  df-suc 5446  df-iota 5563  df-fun 5601  df-fn 5602  df-f 5603  df-f1 5604  df-fo 5605  df-f1o 5606  df-fv 5607  df-om 6705  df-er 7369  df-en 7576  df-dom 7577
This theorem is referenced by:  php2  7761  php3  7762
  Copyright terms: Public domain W3C validator