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

Theorem php 8993
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 phplem1 8990, phplem2 8991, nneneq 8992, and this final piece of the proof. (Contributed by NM, 29-May-1998.) Avoid ax-pow 5288. (Revised by BTernaryTau, 18-Nov-2024.)
Assertion
Ref Expression
php ((𝐴 ∈ ω ∧ 𝐵𝐴) → ¬ 𝐴𝐵)

Proof of Theorem php
Dummy variables 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 0ss 4330 . . . . . 6 ∅ ⊆ 𝐵
2 sspsstr 4040 . . . . . 6 ((∅ ⊆ 𝐵𝐵𝐴) → ∅ ⊊ 𝐴)
31, 2mpan 687 . . . . 5 (𝐵𝐴 → ∅ ⊊ 𝐴)
4 0pss 4378 . . . . . 6 (∅ ⊊ 𝐴𝐴 ≠ ∅)
5 df-ne 2944 . . . . . 6 (𝐴 ≠ ∅ ↔ ¬ 𝐴 = ∅)
64, 5bitri 274 . . . . 5 (∅ ⊊ 𝐴 ↔ ¬ 𝐴 = ∅)
73, 6sylib 217 . . . 4 (𝐵𝐴 → ¬ 𝐴 = ∅)
8 nn0suc 7742 . . . . 5 (𝐴 ∈ ω → (𝐴 = ∅ ∨ ∃𝑥 ∈ ω 𝐴 = suc 𝑥))
98orcanai 1000 . . . 4 ((𝐴 ∈ ω ∧ ¬ 𝐴 = ∅) → ∃𝑥 ∈ ω 𝐴 = suc 𝑥)
107, 9sylan2 593 . . 3 ((𝐴 ∈ ω ∧ 𝐵𝐴) → ∃𝑥 ∈ ω 𝐴 = suc 𝑥)
11 pssnel 4404 . . . . . . . 8 (𝐵 ⊊ suc 𝑥 → ∃𝑦(𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵))
12 pssss 4030 . . . . . . . . . . . . . . . . . . 19 (𝐵 ⊊ suc 𝑥𝐵 ⊆ suc 𝑥)
13 ssdif 4074 . . . . . . . . . . . . . . . . . . . 20 (𝐵 ⊆ suc 𝑥 → (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦}))
14 disjsn 4647 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐵 ∩ {𝑦}) = ∅ ↔ ¬ 𝑦𝐵)
15 disj3 4387 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐵 ∩ {𝑦}) = ∅ ↔ 𝐵 = (𝐵 ∖ {𝑦}))
1614, 15bitr3i 276 . . . . . . . . . . . . . . . . . . . . 21 𝑦𝐵𝐵 = (𝐵 ∖ {𝑦}))
17 sseq1 3946 . . . . . . . . . . . . . . . . . . . . 21 (𝐵 = (𝐵 ∖ {𝑦}) → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) ↔ (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦})))
1816, 17sylbi 216 . . . . . . . . . . . . . . . . . . . 20 𝑦𝐵 → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) ↔ (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦})))
1913, 18syl5ibr 245 . . . . . . . . . . . . . . . . . . 19 𝑦𝐵 → (𝐵 ⊆ suc 𝑥𝐵 ⊆ (suc 𝑥 ∖ {𝑦})))
2012, 19syl5 34 . . . . . . . . . . . . . . . . . 18 𝑦𝐵 → (𝐵 ⊊ suc 𝑥𝐵 ⊆ (suc 𝑥 ∖ {𝑦})))
21 peano2 7737 . . . . . . . . . . . . . . . . . . . 20 (𝑥 ∈ ω → suc 𝑥 ∈ ω)
22 nnfi 8950 . . . . . . . . . . . . . . . . . . . 20 (suc 𝑥 ∈ ω → suc 𝑥 ∈ Fin)
23 diffi 8962 . . . . . . . . . . . . . . . . . . . 20 (suc 𝑥 ∈ Fin → (suc 𝑥 ∖ {𝑦}) ∈ Fin)
2421, 22, 233syl 18 . . . . . . . . . . . . . . . . . . 19 (𝑥 ∈ ω → (suc 𝑥 ∖ {𝑦}) ∈ Fin)
25 ssdomfi 8982 . . . . . . . . . . . . . . . . . . 19 ((suc 𝑥 ∖ {𝑦}) ∈ Fin → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
2624, 25syl 17 . . . . . . . . . . . . . . . . . 18 (𝑥 ∈ ω → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
2720, 26sylan9 508 . . . . . . . . . . . . . . . . 17 ((¬ 𝑦𝐵𝑥 ∈ ω) → (𝐵 ⊊ suc 𝑥𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
28273impia 1116 . . . . . . . . . . . . . . . 16 ((¬ 𝑦𝐵𝑥 ∈ ω ∧ 𝐵 ⊊ suc 𝑥) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
29283com23 1125 . . . . . . . . . . . . . . 15 ((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥𝑥 ∈ ω) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
30293expa 1117 . . . . . . . . . . . . . 14 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ 𝑥 ∈ ω) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
3130adantrr 714 . . . . . . . . . . . . 13 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
32 nnfi 8950 . . . . . . . . . . . . . . 15 (𝑥 ∈ ω → 𝑥 ∈ Fin)
3332ad2antrl 725 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝑥 ∈ Fin)
34 simpl 483 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
35 simpr 485 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥))
36 phplem1 8990 . . . . . . . . . . . . . . . . 17 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → 𝑥 ≈ (suc 𝑥 ∖ {𝑦}))
37 ensymfib 8970 . . . . . . . . . . . . . . . . . . 19 (𝑥 ∈ Fin → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
3832, 37syl 17 . . . . . . . . . . . . . . . . . 18 (𝑥 ∈ ω → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
3938adantr 481 . . . . . . . . . . . . . . . . 17 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
4036, 39mpbid 231 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (suc 𝑥 ∖ {𝑦}) ≈ 𝑥)
41 endom 8767 . . . . . . . . . . . . . . . 16 ((suc 𝑥 ∖ {𝑦}) ≈ 𝑥 → (suc 𝑥 ∖ {𝑦}) ≼ 𝑥)
4240, 41syl 17 . . . . . . . . . . . . . . 15 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (suc 𝑥 ∖ {𝑦}) ≼ 𝑥)
43 domtrfir 8980 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (suc 𝑥 ∖ {𝑦}) ≼ 𝑥) → 𝐵𝑥)
4442, 43syl3an3 1164 . . . . . . . . . . . . . 14 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4533, 34, 35, 44syl3anc 1370 . . . . . . . . . . . . 13 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4631, 45sylancom 588 . . . . . . . . . . . 12 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4746exp43 437 . . . . . . . . . . 11 𝑦𝐵 → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → (𝑦 ∈ suc 𝑥𝐵𝑥))))
4847com4r 94 . . . . . . . . . 10 (𝑦 ∈ suc 𝑥 → (¬ 𝑦𝐵 → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥))))
4948imp 407 . . . . . . . . 9 ((𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵) → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥)))
5049exlimiv 1933 . . . . . . . 8 (∃𝑦(𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵) → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥)))
5111, 50mpcom 38 . . . . . . 7 (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥))
52 simp1 1135 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → 𝑥 ∈ ω)
53 endom 8767 . . . . . . . . . . . . . . 15 (suc 𝑥𝐵 → suc 𝑥𝐵)
54 domtrfir 8980 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
5553, 54syl3an2 1163 . . . . . . . . . . . . . 14 ((𝑥 ∈ Fin ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
5632, 55syl3an1 1162 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
57 sssucid 6343 . . . . . . . . . . . . . . . . 17 𝑥 ⊆ suc 𝑥
58 ssdomfi 8982 . . . . . . . . . . . . . . . . 17 (suc 𝑥 ∈ Fin → (𝑥 ⊆ suc 𝑥𝑥 ≼ suc 𝑥))
5922, 57, 58mpisyl 21 . . . . . . . . . . . . . . . 16 (suc 𝑥 ∈ ω → 𝑥 ≼ suc 𝑥)
6021, 59syl 17 . . . . . . . . . . . . . . 15 (𝑥 ∈ ω → 𝑥 ≼ suc 𝑥)
6160adantr 481 . . . . . . . . . . . . . 14 ((𝑥 ∈ ω ∧ suc 𝑥𝑥) → 𝑥 ≼ suc 𝑥)
62 sbthfi 8985 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ suc 𝑥𝑥𝑥 ≼ suc 𝑥) → suc 𝑥𝑥)
6332, 62syl3an1 1162 . . . . . . . . . . . . . 14 ((𝑥 ∈ ω ∧ suc 𝑥𝑥𝑥 ≼ suc 𝑥) → suc 𝑥𝑥)
6461, 63mpd3an3 1461 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝑥) → suc 𝑥𝑥)
6552, 56, 64syl2anc 584 . . . . . . . . . . . 12 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
66653com23 1125 . . . . . . . . . . 11 ((𝑥 ∈ ω ∧ 𝐵𝑥 ∧ suc 𝑥𝐵) → suc 𝑥𝑥)
67663expia 1120 . . . . . . . . . 10 ((𝑥 ∈ ω ∧ 𝐵𝑥) → (suc 𝑥𝐵 → suc 𝑥𝑥))
68 peano2b 7729 . . . . . . . . . . . . 13 (𝑥 ∈ ω ↔ suc 𝑥 ∈ ω)
69 nnord 7720 . . . . . . . . . . . . 13 (suc 𝑥 ∈ ω → Ord suc 𝑥)
7068, 69sylbi 216 . . . . . . . . . . . 12 (𝑥 ∈ ω → Ord suc 𝑥)
71 vex 3436 . . . . . . . . . . . . 13 𝑥 ∈ V
7271sucid 6345 . . . . . . . . . . . 12 𝑥 ∈ suc 𝑥
73 nordeq 6285 . . . . . . . . . . . 12 ((Ord suc 𝑥𝑥 ∈ suc 𝑥) → suc 𝑥𝑥)
7470, 72, 73sylancl 586 . . . . . . . . . . 11 (𝑥 ∈ ω → suc 𝑥𝑥)
75 nneneq 8992 . . . . . . . . . . . . . 14 ((suc 𝑥 ∈ ω ∧ 𝑥 ∈ ω) → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7668, 75sylanb 581 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ 𝑥 ∈ ω) → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7776anidms 567 . . . . . . . . . . . 12 (𝑥 ∈ ω → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7877necon3bbid 2981 . . . . . . . . . . 11 (𝑥 ∈ ω → (¬ suc 𝑥𝑥 ↔ suc 𝑥𝑥))
7974, 78mpbird 256 . . . . . . . . . 10 (𝑥 ∈ ω → ¬ suc 𝑥𝑥)
8067, 79nsyli 157 . . . . . . . . 9 ((𝑥 ∈ ω ∧ 𝐵𝑥) → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8180expcom 414 . . . . . . . 8 (𝐵𝑥 → (𝑥 ∈ ω → (𝑥 ∈ ω → ¬ suc 𝑥𝐵)))
8281pm2.43d 53 . . . . . . 7 (𝐵𝑥 → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8351, 82syli 39 . . . . . 6 (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8483com12 32 . . . . 5 (𝑥 ∈ ω → (𝐵 ⊊ suc 𝑥 → ¬ suc 𝑥𝐵))
85 psseq2 4023 . . . . . 6 (𝐴 = suc 𝑥 → (𝐵𝐴𝐵 ⊊ suc 𝑥))
86 breq1 5077 . . . . . . 7 (𝐴 = suc 𝑥 → (𝐴𝐵 ↔ suc 𝑥𝐵))
8786notbid 318 . . . . . 6 (𝐴 = suc 𝑥 → (¬ 𝐴𝐵 ↔ ¬ suc 𝑥𝐵))
8885, 87imbi12d 345 . . . . 5 (𝐴 = suc 𝑥 → ((𝐵𝐴 → ¬ 𝐴𝐵) ↔ (𝐵 ⊊ suc 𝑥 → ¬ suc 𝑥𝐵)))
8984, 88syl5ibrcom 246 . . . 4 (𝑥 ∈ ω → (𝐴 = suc 𝑥 → (𝐵𝐴 → ¬ 𝐴𝐵)))
9089rexlimiv 3209 . . 3 (∃𝑥 ∈ ω 𝐴 = suc 𝑥 → (𝐵𝐴 → ¬ 𝐴𝐵))
9110, 90syl 17 . 2 ((𝐴 ∈ ω ∧ 𝐵𝐴) → (𝐵𝐴 → ¬ 𝐴𝐵))
9291syldbl2 838 1 ((𝐴 ∈ ω ∧ 𝐵𝐴) → ¬ 𝐴𝐵)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 205  wa 396  w3a 1086   = wceq 1539  wex 1782  wcel 2106  wne 2943  wrex 3065  cdif 3884  cin 3886  wss 3887  wpss 3888  c0 4256  {csn 4561   class class class wbr 5074  Ord word 6265  suc csuc 6268  ωcom 7712  cen 8730  cdom 8731  Fincfn 8733
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2709  ax-sep 5223  ax-nul 5230  ax-pr 5352  ax-un 7588
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1783  df-nf 1787  df-sb 2068  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2816  df-nfc 2889  df-ne 2944  df-ral 3069  df-rex 3070  df-reu 3072  df-rab 3073  df-v 3434  df-sbc 3717  df-csb 3833  df-dif 3890  df-un 3892  df-in 3894  df-ss 3904  df-pss 3906  df-nul 4257  df-if 4460  df-pw 4535  df-sn 4562  df-pr 4564  df-op 4568  df-uni 4840  df-br 5075  df-opab 5137  df-mpt 5158  df-tr 5192  df-id 5489  df-eprel 5495  df-po 5503  df-so 5504  df-fr 5544  df-we 5546  df-xp 5595  df-rel 5596  df-cnv 5597  df-co 5598  df-dm 5599  df-rn 5600  df-res 5601  df-ima 5602  df-ord 6269  df-on 6270  df-lim 6271  df-suc 6272  df-iota 6391  df-fun 6435  df-fn 6436  df-f 6437  df-f1 6438  df-fo 6439  df-f1o 6440  df-fv 6441  df-om 7713  df-1o 8297  df-en 8734  df-dom 8735  df-fin 8737
This theorem is referenced by:  php2  8994  php2OLD  9006  php3OLD  9007  omssrncard  41147  rr-phpd  41821
  Copyright terms: Public domain W3C validator