ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  phpm Unicode version

Theorem phpm 6535
Description: Pigeonhole Principle. A natural number is not equinumerous to a proper subset of itself. By "proper subset" here we mean that there is an element which is in the natural number and not in the subset, or in symbols  E. x x  e.  ( A  \  B
) (which is stronger than not being equal in the absence of excluded middle). 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 6522 through phplem4 6525, nneneq 6527, and this final piece of the proof. (Contributed by NM, 29-May-1998.)
Assertion
Ref Expression
phpm  |-  ( ( A  e.  om  /\  B  C_  A  /\  E. x  x  e.  ( A  \  B ) )  ->  -.  A  ~~  B )
Distinct variable groups:    x, A    x, B

Proof of Theorem phpm
Dummy variable  y is distinct from all other variables.
StepHypRef Expression
1 simpr 108 . . . . . 6  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  A  =  (/) )  ->  A  =  (/) )
2 eldifi 3111 . . . . . . . . 9  |-  ( x  e.  ( A  \  B )  ->  x  e.  A )
3 ne0i 3281 . . . . . . . . 9  |-  ( x  e.  A  ->  A  =/=  (/) )
42, 3syl 14 . . . . . . . 8  |-  ( x  e.  ( A  \  B )  ->  A  =/=  (/) )
54neneqd 2272 . . . . . . 7  |-  ( x  e.  ( A  \  B )  ->  -.  A  =  (/) )
65ad2antlr 473 . . . . . 6  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  A  =  (/) )  ->  -.  A  =  (/) )
71, 6pm2.21dd 583 . . . . 5  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  A  =  (/) )  ->  -.  A  ~~  B )
8 php5dom 6533 . . . . . . . . . 10  |-  ( y  e.  om  ->  -.  suc  y  ~<_  y )
98ad2antlr 473 . . . . . . . . 9  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  -.  suc  y  ~<_  y )
10 simplr 497 . . . . . . . . . 10  |-  ( ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  /\  y  e.  om )  /\  A  =  suc  y )  /\  A  ~~  B )  ->  A  =  suc  y )
11 simpr 108 . . . . . . . . . . 11  |-  ( ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  /\  y  e.  om )  /\  A  =  suc  y )  /\  A  ~~  B )  ->  A  ~~  B )
12 vex 2618 . . . . . . . . . . . . . . . 16  |-  y  e. 
_V
1312sucex 4291 . . . . . . . . . . . . . . 15  |-  suc  y  e.  _V
14 difss 3115 . . . . . . . . . . . . . . 15  |-  ( suc  y  \  { x } )  C_  suc  y
1513, 14ssexi 3954 . . . . . . . . . . . . . 14  |-  ( suc  y  \  { x } )  e.  _V
16 eldifn 3112 . . . . . . . . . . . . . . . 16  |-  ( x  e.  ( A  \  B )  ->  -.  x  e.  B )
1716ad3antlr 477 . . . . . . . . . . . . . . 15  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  -.  x  e.  B
)
18 simpllr 501 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  y  e. 
om )  ->  B  C_  A )
1918adantr 270 . . . . . . . . . . . . . . . 16  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  B  C_  A )
20 simpr 108 . . . . . . . . . . . . . . . 16  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  A  =  suc  y )
2119, 20sseqtrd 3051 . . . . . . . . . . . . . . 15  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  B  C_  suc  y )
22 ssdif 3124 . . . . . . . . . . . . . . . 16  |-  ( B 
C_  suc  y  ->  ( B  \  { x } )  C_  ( suc  y  \  { x } ) )
23 disjsn 3489 . . . . . . . . . . . . . . . . . 18  |-  ( ( B  i^i  { x } )  =  (/)  <->  -.  x  e.  B )
24 disj3 3323 . . . . . . . . . . . . . . . . . 18  |-  ( ( B  i^i  { x } )  =  (/)  <->  B  =  ( B  \  { x } ) )
2523, 24bitr3i 184 . . . . . . . . . . . . . . . . 17  |-  ( -.  x  e.  B  <->  B  =  ( B  \  { x } ) )
26 sseq1 3036 . . . . . . . . . . . . . . . . 17  |-  ( B  =  ( B  \  { x } )  ->  ( B  C_  ( suc  y  \  {
x } )  <->  ( B  \  { x } ) 
C_  ( suc  y  \  { x } ) ) )
2725, 26sylbi 119 . . . . . . . . . . . . . . . 16  |-  ( -.  x  e.  B  -> 
( B  C_  ( suc  y  \  { x } )  <->  ( B  \  { x } ) 
C_  ( suc  y  \  { x } ) ) )
2822, 27syl5ibr 154 . . . . . . . . . . . . . . 15  |-  ( -.  x  e.  B  -> 
( B  C_  suc  y  ->  B  C_  ( suc  y  \  { x } ) ) )
2917, 21, 28sylc 61 . . . . . . . . . . . . . 14  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  B  C_  ( suc  y  \  { x } ) )
30 ssdomg 6449 . . . . . . . . . . . . . 14  |-  ( ( suc  y  \  {
x } )  e. 
_V  ->  ( B  C_  ( suc  y  \  {
x } )  ->  B  ~<_  ( suc  y  \  { x } ) ) )
3115, 29, 30mpsyl 64 . . . . . . . . . . . . 13  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  B  ~<_  ( suc  y  \  { x } ) )
32 simplr 497 . . . . . . . . . . . . . 14  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  -> 
y  e.  om )
332ad3antlr 477 . . . . . . . . . . . . . . 15  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  x  e.  A )
3433, 20eleqtrd 2163 . . . . . . . . . . . . . 14  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  x  e.  suc  y )
35 phplem3g 6526 . . . . . . . . . . . . . . 15  |-  ( ( y  e.  om  /\  x  e.  suc  y )  ->  y  ~~  ( suc  y  \  { x } ) )
3635ensymd 6454 . . . . . . . . . . . . . 14  |-  ( ( y  e.  om  /\  x  e.  suc  y )  ->  ( suc  y  \  { x } ) 
~~  y )
3732, 34, 36syl2anc 403 . . . . . . . . . . . . 13  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  -> 
( suc  y  \  { x } ) 
~~  y )
38 domentr 6462 . . . . . . . . . . . . 13  |-  ( ( B  ~<_  ( suc  y  \  { x } )  /\  ( suc  y  \  { x } ) 
~~  y )  ->  B  ~<_  y )
3931, 37, 38syl2anc 403 . . . . . . . . . . . 12  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  B  ~<_  y )
4039adantr 270 . . . . . . . . . . 11  |-  ( ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  /\  y  e.  om )  /\  A  =  suc  y )  /\  A  ~~  B )  ->  B  ~<_  y )
41 endomtr 6461 . . . . . . . . . . 11  |-  ( ( A  ~~  B  /\  B  ~<_  y )  ->  A  ~<_  y )
4211, 40, 41syl2anc 403 . . . . . . . . . 10  |-  ( ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  /\  y  e.  om )  /\  A  =  suc  y )  /\  A  ~~  B )  ->  A  ~<_  y )
4310, 42eqbrtrrd 3844 . . . . . . . . 9  |-  ( ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  /\  y  e.  om )  /\  A  =  suc  y )  /\  A  ~~  B )  ->  suc  y  ~<_  y )
449, 43mtand 624 . . . . . . . 8  |-  ( ( ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B
) )  /\  y  e.  om )  /\  A  =  suc  y )  ->  -.  A  ~~  B )
4544ex 113 . . . . . . 7  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  y  e. 
om )  ->  ( A  =  suc  y  ->  -.  A  ~~  B ) )
4645rexlimdva 2485 . . . . . 6  |-  ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  ->  ( E. y  e.  om  A  =  suc  y  ->  -.  A  ~~  B ) )
4746imp 122 . . . . 5  |-  ( ( ( ( A  e. 
om  /\  B  C_  A
)  /\  x  e.  ( A  \  B ) )  /\  E. y  e.  om  A  =  suc  y )  ->  -.  A  ~~  B )
48 nn0suc 4394 . . . . . 6  |-  ( A  e.  om  ->  ( A  =  (/)  \/  E. y  e.  om  A  =  suc  y ) )
4948ad2antrr 472 . . . . 5  |-  ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  ->  ( A  =  (/)  \/  E. y  e. 
om  A  =  suc  y ) )
507, 47, 49mpjaodan 745 . . . 4  |-  ( ( ( A  e.  om  /\  B  C_  A )  /\  x  e.  ( A  \  B ) )  ->  -.  A  ~~  B )
5150ex 113 . . 3  |-  ( ( A  e.  om  /\  B  C_  A )  -> 
( x  e.  ( A  \  B )  ->  -.  A  ~~  B ) )
5251exlimdv 1744 . 2  |-  ( ( A  e.  om  /\  B  C_  A )  -> 
( E. x  x  e.  ( A  \  B )  ->  -.  A  ~~  B ) )
53523impia 1138 1  |-  ( ( A  e.  om  /\  B  C_  A  /\  E. x  x  e.  ( A  \  B ) )  ->  -.  A  ~~  B )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    /\ wa 102    <-> wb 103    \/ wo 662    /\ w3a 922    = wceq 1287   E.wex 1424    e. wcel 1436    =/= wne 2251   E.wrex 2356   _Vcvv 2615    \ cdif 2985    i^i cin 2987    C_ wss 2988   (/)c0 3275   {csn 3431   class class class wbr 3822   suc csuc 4168   omcom 4380    ~~ cen 6409    ~<_ cdom 6410
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 577  ax-in2 578  ax-io 663  ax-5 1379  ax-7 1380  ax-gen 1381  ax-ie1 1425  ax-ie2 1426  ax-8 1438  ax-10 1439  ax-11 1440  ax-i12 1441  ax-bndl 1442  ax-4 1443  ax-13 1447  ax-14 1448  ax-17 1462  ax-i9 1466  ax-ial 1470  ax-i5r 1471  ax-ext 2067  ax-sep 3934  ax-nul 3942  ax-pow 3986  ax-pr 4012  ax-un 4236  ax-setind 4328  ax-iinf 4378
This theorem depends on definitions:  df-bi 115  df-dc 779  df-3or 923  df-3an 924  df-tru 1290  df-fal 1293  df-nf 1393  df-sb 1690  df-eu 1948  df-mo 1949  df-clab 2072  df-cleq 2078  df-clel 2081  df-nfc 2214  df-ne 2252  df-ral 2360  df-rex 2361  df-rab 2364  df-v 2617  df-sbc 2830  df-dif 2990  df-un 2992  df-in 2994  df-ss 3001  df-nul 3276  df-pw 3417  df-sn 3437  df-pr 3438  df-op 3440  df-uni 3639  df-int 3674  df-br 3823  df-opab 3877  df-tr 3914  df-id 4096  df-iord 4169  df-on 4171  df-suc 4174  df-iom 4381  df-xp 4419  df-rel 4420  df-cnv 4421  df-co 4422  df-dm 4423  df-rn 4424  df-res 4425  df-ima 4426  df-iota 4948  df-fun 4985  df-fn 4986  df-f 4987  df-f1 4988  df-fo 4989  df-f1o 4990  df-fv 4991  df-er 6246  df-en 6412  df-dom 6413
This theorem is referenced by:  phpelm  6536
  Copyright terms: Public domain W3C validator