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

Theorem phpm 6661
 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 ∃𝑥𝑥 ∈ (𝐴 ∖ 𝐵) (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 6648 through phplem4 6651, nneneq 6653, and this final piece of the proof. (Contributed by NM, 29-May-1998.)
Assertion
Ref Expression
phpm ((𝐴 ∈ ω ∧ 𝐵𝐴 ∧ ∃𝑥 𝑥 ∈ (𝐴𝐵)) → ¬ 𝐴𝐵)
Distinct variable groups:   𝑥,𝐴   𝑥,𝐵

Proof of Theorem phpm
Dummy variable 𝑦 is distinct from all other variables.
StepHypRef Expression
1 simpr 109 . . . . . 6 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝐴 = ∅) → 𝐴 = ∅)
2 eldifi 3137 . . . . . . . . 9 (𝑥 ∈ (𝐴𝐵) → 𝑥𝐴)
3 ne0i 3308 . . . . . . . . 9 (𝑥𝐴𝐴 ≠ ∅)
42, 3syl 14 . . . . . . . 8 (𝑥 ∈ (𝐴𝐵) → 𝐴 ≠ ∅)
54neneqd 2283 . . . . . . 7 (𝑥 ∈ (𝐴𝐵) → ¬ 𝐴 = ∅)
65ad2antlr 474 . . . . . 6 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝐴 = ∅) → ¬ 𝐴 = ∅)
71, 6pm2.21dd 588 . . . . 5 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝐴 = ∅) → ¬ 𝐴𝐵)
8 php5dom 6659 . . . . . . . . . 10 (𝑦 ∈ ω → ¬ suc 𝑦𝑦)
98ad2antlr 474 . . . . . . . . 9 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ suc 𝑦𝑦)
10 simplr 498 . . . . . . . . . 10 ((((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴𝐵) → 𝐴 = suc 𝑦)
11 simpr 109 . . . . . . . . . . 11 ((((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴𝐵) → 𝐴𝐵)
12 vex 2636 . . . . . . . . . . . . . . . 16 𝑦 ∈ V
1312sucex 4344 . . . . . . . . . . . . . . 15 suc 𝑦 ∈ V
14 difss 3141 . . . . . . . . . . . . . . 15 (suc 𝑦 ∖ {𝑥}) ⊆ suc 𝑦
1513, 14ssexi 3998 . . . . . . . . . . . . . 14 (suc 𝑦 ∖ {𝑥}) ∈ V
16 eldifn 3138 . . . . . . . . . . . . . . . 16 (𝑥 ∈ (𝐴𝐵) → ¬ 𝑥𝐵)
1716ad3antlr 478 . . . . . . . . . . . . . . 15 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ 𝑥𝐵)
18 simpllr 502 . . . . . . . . . . . . . . . . 17 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) → 𝐵𝐴)
1918adantr 271 . . . . . . . . . . . . . . . 16 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵𝐴)
20 simpr 109 . . . . . . . . . . . . . . . 16 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐴 = suc 𝑦)
2119, 20sseqtrd 3077 . . . . . . . . . . . . . . 15 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ⊆ suc 𝑦)
22 ssdif 3150 . . . . . . . . . . . . . . . 16 (𝐵 ⊆ suc 𝑦 → (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥}))
23 disjsn 3524 . . . . . . . . . . . . . . . . . 18 ((𝐵 ∩ {𝑥}) = ∅ ↔ ¬ 𝑥𝐵)
24 disj3 3354 . . . . . . . . . . . . . . . . . 18 ((𝐵 ∩ {𝑥}) = ∅ ↔ 𝐵 = (𝐵 ∖ {𝑥}))
2523, 24bitr3i 185 . . . . . . . . . . . . . . . . 17 𝑥𝐵𝐵 = (𝐵 ∖ {𝑥}))
26 sseq1 3062 . . . . . . . . . . . . . . . . 17 (𝐵 = (𝐵 ∖ {𝑥}) → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) ↔ (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥})))
2725, 26sylbi 120 . . . . . . . . . . . . . . . 16 𝑥𝐵 → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) ↔ (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥})))
2822, 27syl5ibr 155 . . . . . . . . . . . . . . 15 𝑥𝐵 → (𝐵 ⊆ suc 𝑦𝐵 ⊆ (suc 𝑦 ∖ {𝑥})))
2917, 21, 28sylc 62 . . . . . . . . . . . . . 14 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ⊆ (suc 𝑦 ∖ {𝑥}))
30 ssdomg 6575 . . . . . . . . . . . . . 14 ((suc 𝑦 ∖ {𝑥}) ∈ V → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) → 𝐵 ≼ (suc 𝑦 ∖ {𝑥})))
3115, 29, 30mpsyl 65 . . . . . . . . . . . . 13 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ≼ (suc 𝑦 ∖ {𝑥}))
32 simplr 498 . . . . . . . . . . . . . 14 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑦 ∈ ω)
332ad3antlr 478 . . . . . . . . . . . . . . 15 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑥𝐴)
3433, 20eleqtrd 2173 . . . . . . . . . . . . . 14 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑥 ∈ suc 𝑦)
35 phplem3g 6652 . . . . . . . . . . . . . . 15 ((𝑦 ∈ ω ∧ 𝑥 ∈ suc 𝑦) → 𝑦 ≈ (suc 𝑦 ∖ {𝑥}))
3635ensymd 6580 . . . . . . . . . . . . . 14 ((𝑦 ∈ ω ∧ 𝑥 ∈ suc 𝑦) → (suc 𝑦 ∖ {𝑥}) ≈ 𝑦)
3732, 34, 36syl2anc 404 . . . . . . . . . . . . 13 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → (suc 𝑦 ∖ {𝑥}) ≈ 𝑦)
38 domentr 6588 . . . . . . . . . . . . 13 ((𝐵 ≼ (suc 𝑦 ∖ {𝑥}) ∧ (suc 𝑦 ∖ {𝑥}) ≈ 𝑦) → 𝐵𝑦)
3931, 37, 38syl2anc 404 . . . . . . . . . . . 12 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵𝑦)
4039adantr 271 . . . . . . . . . . 11 ((((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴𝐵) → 𝐵𝑦)
41 endomtr 6587 . . . . . . . . . . 11 ((𝐴𝐵𝐵𝑦) → 𝐴𝑦)
4211, 40, 41syl2anc 404 . . . . . . . . . 10 ((((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴𝐵) → 𝐴𝑦)
4310, 42eqbrtrrd 3889 . . . . . . . . 9 ((((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴𝐵) → suc 𝑦𝑦)
449, 43mtand 629 . . . . . . . 8 (((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ 𝐴𝐵)
4544ex 114 . . . . . . 7 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ 𝑦 ∈ ω) → (𝐴 = suc 𝑦 → ¬ 𝐴𝐵))
4645rexlimdva 2502 . . . . . 6 (((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) → (∃𝑦 ∈ ω 𝐴 = suc 𝑦 → ¬ 𝐴𝐵))
4746imp 123 . . . . 5 ((((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) ∧ ∃𝑦 ∈ ω 𝐴 = suc 𝑦) → ¬ 𝐴𝐵)
48 nn0suc 4447 . . . . . 6 (𝐴 ∈ ω → (𝐴 = ∅ ∨ ∃𝑦 ∈ ω 𝐴 = suc 𝑦))
4948ad2antrr 473 . . . . 5 (((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) → (𝐴 = ∅ ∨ ∃𝑦 ∈ ω 𝐴 = suc 𝑦))
507, 47, 49mpjaodan 750 . . . 4 (((𝐴 ∈ ω ∧ 𝐵𝐴) ∧ 𝑥 ∈ (𝐴𝐵)) → ¬ 𝐴𝐵)
5150ex 114 . . 3 ((𝐴 ∈ ω ∧ 𝐵𝐴) → (𝑥 ∈ (𝐴𝐵) → ¬ 𝐴𝐵))
5251exlimdv 1754 . 2 ((𝐴 ∈ ω ∧ 𝐵𝐴) → (∃𝑥 𝑥 ∈ (𝐴𝐵) → ¬ 𝐴𝐵))
53523impia 1143 1 ((𝐴 ∈ ω ∧ 𝐵𝐴 ∧ ∃𝑥 𝑥 ∈ (𝐴𝐵)) → ¬ 𝐴𝐵)
 Colors of variables: wff set class Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 103   ↔ wb 104   ∨ wo 667   ∧ w3a 927   = wceq 1296  ∃wex 1433   ∈ wcel 1445   ≠ wne 2262  ∃wrex 2371  Vcvv 2633   ∖ cdif 3010   ∩ cin 3012   ⊆ wss 3013  ∅c0 3302  {csn 3466   class class class wbr 3867  suc csuc 4216  ωcom 4433   ≈ cen 6535   ≼ cdom 6536 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 582  ax-in2 583  ax-io 668  ax-5 1388  ax-7 1389  ax-gen 1390  ax-ie1 1434  ax-ie2 1435  ax-8 1447  ax-10 1448  ax-11 1449  ax-i12 1450  ax-bndl 1451  ax-4 1452  ax-13 1456  ax-14 1457  ax-17 1471  ax-i9 1475  ax-ial 1479  ax-i5r 1480  ax-ext 2077  ax-sep 3978  ax-nul 3986  ax-pow 4030  ax-pr 4060  ax-un 4284  ax-setind 4381  ax-iinf 4431 This theorem depends on definitions:  df-bi 116  df-dc 784  df-3or 928  df-3an 929  df-tru 1299  df-fal 1302  df-nf 1402  df-sb 1700  df-eu 1958  df-mo 1959  df-clab 2082  df-cleq 2088  df-clel 2091  df-nfc 2224  df-ne 2263  df-ral 2375  df-rex 2376  df-rab 2379  df-v 2635  df-sbc 2855  df-dif 3015  df-un 3017  df-in 3019  df-ss 3026  df-nul 3303  df-pw 3451  df-sn 3472  df-pr 3473  df-op 3475  df-uni 3676  df-int 3711  df-br 3868  df-opab 3922  df-tr 3959  df-id 4144  df-iord 4217  df-on 4219  df-suc 4222  df-iom 4434  df-xp 4473  df-rel 4474  df-cnv 4475  df-co 4476  df-dm 4477  df-rn 4478  df-res 4479  df-ima 4480  df-iota 5014  df-fun 5051  df-fn 5052  df-f 5053  df-f1 5054  df-fo 5055  df-f1o 5056  df-fv 5057  df-er 6332  df-en 6538  df-dom 6539 This theorem is referenced by:  phpelm  6662
 Copyright terms: Public domain W3C validator