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

Theorem php 9206
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 9203, phplem2 9204, nneneq 9205, and this final piece of the proof. (Contributed by NM, 29-May-1998.) Avoid ax-pow 5353. (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 4388 . . . . . 6 ∅ ⊆ 𝐵
2 sspsstr 4097 . . . . . 6 ((∅ ⊆ 𝐵𝐵𝐴) → ∅ ⊊ 𝐴)
31, 2mpan 687 . . . . 5 (𝐵𝐴 → ∅ ⊊ 𝐴)
4 0pss 4436 . . . . . 6 (∅ ⊊ 𝐴𝐴 ≠ ∅)
5 df-ne 2933 . . . . . 6 (𝐴 ≠ ∅ ↔ ¬ 𝐴 = ∅)
64, 5bitri 275 . . . . 5 (∅ ⊊ 𝐴 ↔ ¬ 𝐴 = ∅)
73, 6sylib 217 . . . 4 (𝐵𝐴 → ¬ 𝐴 = ∅)
8 nn0suc 7879 . . . . 5 (𝐴 ∈ ω → (𝐴 = ∅ ∨ ∃𝑥 ∈ ω 𝐴 = suc 𝑥))
98orcanai 999 . . . 4 ((𝐴 ∈ ω ∧ ¬ 𝐴 = ∅) → ∃𝑥 ∈ ω 𝐴 = suc 𝑥)
107, 9sylan2 592 . . 3 ((𝐴 ∈ ω ∧ 𝐵𝐴) → ∃𝑥 ∈ ω 𝐴 = suc 𝑥)
11 pssnel 4462 . . . . . . . 8 (𝐵 ⊊ suc 𝑥 → ∃𝑦(𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵))
12 pssss 4087 . . . . . . . . . . . . . . . . . . 19 (𝐵 ⊊ suc 𝑥𝐵 ⊆ suc 𝑥)
13 ssdif 4131 . . . . . . . . . . . . . . . . . . . 20 (𝐵 ⊆ suc 𝑥 → (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦}))
14 disjsn 4707 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐵 ∩ {𝑦}) = ∅ ↔ ¬ 𝑦𝐵)
15 disj3 4445 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐵 ∩ {𝑦}) = ∅ ↔ 𝐵 = (𝐵 ∖ {𝑦}))
1614, 15bitr3i 277 . . . . . . . . . . . . . . . . . . . . 21 𝑦𝐵𝐵 = (𝐵 ∖ {𝑦}))
17 sseq1 3999 . . . . . . . . . . . . . . . . . . . . 21 (𝐵 = (𝐵 ∖ {𝑦}) → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) ↔ (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦})))
1816, 17sylbi 216 . . . . . . . . . . . . . . . . . . . 20 𝑦𝐵 → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) ↔ (𝐵 ∖ {𝑦}) ⊆ (suc 𝑥 ∖ {𝑦})))
1913, 18imbitrrid 245 . . . . . . . . . . . . . . . . . . 19 𝑦𝐵 → (𝐵 ⊆ suc 𝑥𝐵 ⊆ (suc 𝑥 ∖ {𝑦})))
2012, 19syl5 34 . . . . . . . . . . . . . . . . . 18 𝑦𝐵 → (𝐵 ⊊ suc 𝑥𝐵 ⊆ (suc 𝑥 ∖ {𝑦})))
21 peano2 7874 . . . . . . . . . . . . . . . . . . . 20 (𝑥 ∈ ω → suc 𝑥 ∈ ω)
22 nnfi 9163 . . . . . . . . . . . . . . . . . . . 20 (suc 𝑥 ∈ ω → suc 𝑥 ∈ Fin)
23 diffi 9175 . . . . . . . . . . . . . . . . . . . 20 (suc 𝑥 ∈ Fin → (suc 𝑥 ∖ {𝑦}) ∈ Fin)
2421, 22, 233syl 18 . . . . . . . . . . . . . . . . . . 19 (𝑥 ∈ ω → (suc 𝑥 ∖ {𝑦}) ∈ Fin)
25 ssdomfi 9195 . . . . . . . . . . . . . . . . . . 19 ((suc 𝑥 ∖ {𝑦}) ∈ Fin → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
2624, 25syl 17 . . . . . . . . . . . . . . . . . 18 (𝑥 ∈ ω → (𝐵 ⊆ (suc 𝑥 ∖ {𝑦}) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
2720, 26sylan9 507 . . . . . . . . . . . . . . . . 17 ((¬ 𝑦𝐵𝑥 ∈ ω) → (𝐵 ⊊ suc 𝑥𝐵 ≼ (suc 𝑥 ∖ {𝑦})))
28273impia 1114 . . . . . . . . . . . . . . . 16 ((¬ 𝑦𝐵𝑥 ∈ ω ∧ 𝐵 ⊊ suc 𝑥) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
29283com23 1123 . . . . . . . . . . . . . . 15 ((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥𝑥 ∈ ω) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
30293expa 1115 . . . . . . . . . . . . . 14 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ 𝑥 ∈ ω) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
3130adantrr 714 . . . . . . . . . . . . 13 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
32 nnfi 9163 . . . . . . . . . . . . . . 15 (𝑥 ∈ ω → 𝑥 ∈ Fin)
3332ad2antrl 725 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝑥 ∈ Fin)
34 simpl 482 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵 ≼ (suc 𝑥 ∖ {𝑦}))
35 simpr 484 . . . . . . . . . . . . . 14 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥))
36 phplem1 9203 . . . . . . . . . . . . . . . . 17 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → 𝑥 ≈ (suc 𝑥 ∖ {𝑦}))
37 ensymfib 9183 . . . . . . . . . . . . . . . . . . 19 (𝑥 ∈ Fin → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
3832, 37syl 17 . . . . . . . . . . . . . . . . . 18 (𝑥 ∈ ω → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
3938adantr 480 . . . . . . . . . . . . . . . . 17 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (𝑥 ≈ (suc 𝑥 ∖ {𝑦}) ↔ (suc 𝑥 ∖ {𝑦}) ≈ 𝑥))
4036, 39mpbid 231 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (suc 𝑥 ∖ {𝑦}) ≈ 𝑥)
41 endom 8971 . . . . . . . . . . . . . . . 16 ((suc 𝑥 ∖ {𝑦}) ≈ 𝑥 → (suc 𝑥 ∖ {𝑦}) ≼ 𝑥)
4240, 41syl 17 . . . . . . . . . . . . . . 15 ((𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥) → (suc 𝑥 ∖ {𝑦}) ≼ 𝑥)
43 domtrfir 9193 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (suc 𝑥 ∖ {𝑦}) ≼ 𝑥) → 𝐵𝑥)
4442, 43syl3an3 1162 . . . . . . . . . . . . . 14 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4533, 34, 35, 44syl3anc 1368 . . . . . . . . . . . . 13 ((𝐵 ≼ (suc 𝑥 ∖ {𝑦}) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4631, 45sylancom 587 . . . . . . . . . . . 12 (((¬ 𝑦𝐵𝐵 ⊊ suc 𝑥) ∧ (𝑥 ∈ ω ∧ 𝑦 ∈ suc 𝑥)) → 𝐵𝑥)
4746exp43 436 . . . . . . . . . . 11 𝑦𝐵 → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → (𝑦 ∈ suc 𝑥𝐵𝑥))))
4847com4r 94 . . . . . . . . . 10 (𝑦 ∈ suc 𝑥 → (¬ 𝑦𝐵 → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥))))
4948imp 406 . . . . . . . . 9 ((𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵) → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥)))
5049exlimiv 1925 . . . . . . . 8 (∃𝑦(𝑦 ∈ suc 𝑥 ∧ ¬ 𝑦𝐵) → (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥)))
5111, 50mpcom 38 . . . . . . 7 (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → 𝐵𝑥))
52 simp1 1133 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → 𝑥 ∈ ω)
53 endom 8971 . . . . . . . . . . . . . . 15 (suc 𝑥𝐵 → suc 𝑥𝐵)
54 domtrfir 9193 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
5553, 54syl3an2 1161 . . . . . . . . . . . . . 14 ((𝑥 ∈ Fin ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
5632, 55syl3an1 1160 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
57 sssucid 6434 . . . . . . . . . . . . . . . . 17 𝑥 ⊆ suc 𝑥
58 ssdomfi 9195 . . . . . . . . . . . . . . . . 17 (suc 𝑥 ∈ Fin → (𝑥 ⊆ suc 𝑥𝑥 ≼ suc 𝑥))
5922, 57, 58mpisyl 21 . . . . . . . . . . . . . . . 16 (suc 𝑥 ∈ ω → 𝑥 ≼ suc 𝑥)
6021, 59syl 17 . . . . . . . . . . . . . . 15 (𝑥 ∈ ω → 𝑥 ≼ suc 𝑥)
6160adantr 480 . . . . . . . . . . . . . 14 ((𝑥 ∈ ω ∧ suc 𝑥𝑥) → 𝑥 ≼ suc 𝑥)
62 sbthfi 9198 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ suc 𝑥𝑥𝑥 ≼ suc 𝑥) → suc 𝑥𝑥)
6332, 62syl3an1 1160 . . . . . . . . . . . . . 14 ((𝑥 ∈ ω ∧ suc 𝑥𝑥𝑥 ≼ suc 𝑥) → suc 𝑥𝑥)
6461, 63mpd3an3 1458 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ suc 𝑥𝑥) → suc 𝑥𝑥)
6552, 56, 64syl2anc 583 . . . . . . . . . . . 12 ((𝑥 ∈ ω ∧ suc 𝑥𝐵𝐵𝑥) → suc 𝑥𝑥)
66653com23 1123 . . . . . . . . . . 11 ((𝑥 ∈ ω ∧ 𝐵𝑥 ∧ suc 𝑥𝐵) → suc 𝑥𝑥)
67663expia 1118 . . . . . . . . . 10 ((𝑥 ∈ ω ∧ 𝐵𝑥) → (suc 𝑥𝐵 → suc 𝑥𝑥))
68 peano2b 7865 . . . . . . . . . . . . 13 (𝑥 ∈ ω ↔ suc 𝑥 ∈ ω)
69 nnord 7856 . . . . . . . . . . . . 13 (suc 𝑥 ∈ ω → Ord suc 𝑥)
7068, 69sylbi 216 . . . . . . . . . . . 12 (𝑥 ∈ ω → Ord suc 𝑥)
71 vex 3470 . . . . . . . . . . . . 13 𝑥 ∈ V
7271sucid 6436 . . . . . . . . . . . 12 𝑥 ∈ suc 𝑥
73 nordeq 6373 . . . . . . . . . . . 12 ((Ord suc 𝑥𝑥 ∈ suc 𝑥) → suc 𝑥𝑥)
7470, 72, 73sylancl 585 . . . . . . . . . . 11 (𝑥 ∈ ω → suc 𝑥𝑥)
75 nneneq 9205 . . . . . . . . . . . . . 14 ((suc 𝑥 ∈ ω ∧ 𝑥 ∈ ω) → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7668, 75sylanb 580 . . . . . . . . . . . . 13 ((𝑥 ∈ ω ∧ 𝑥 ∈ ω) → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7776anidms 566 . . . . . . . . . . . 12 (𝑥 ∈ ω → (suc 𝑥𝑥 ↔ suc 𝑥 = 𝑥))
7877necon3bbid 2970 . . . . . . . . . . 11 (𝑥 ∈ ω → (¬ suc 𝑥𝑥 ↔ suc 𝑥𝑥))
7974, 78mpbird 257 . . . . . . . . . 10 (𝑥 ∈ ω → ¬ suc 𝑥𝑥)
8067, 79nsyli 157 . . . . . . . . 9 ((𝑥 ∈ ω ∧ 𝐵𝑥) → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8180expcom 413 . . . . . . . 8 (𝐵𝑥 → (𝑥 ∈ ω → (𝑥 ∈ ω → ¬ suc 𝑥𝐵)))
8281pm2.43d 53 . . . . . . 7 (𝐵𝑥 → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8351, 82syli 39 . . . . . 6 (𝐵 ⊊ suc 𝑥 → (𝑥 ∈ ω → ¬ suc 𝑥𝐵))
8483com12 32 . . . . 5 (𝑥 ∈ ω → (𝐵 ⊊ suc 𝑥 → ¬ suc 𝑥𝐵))
85 psseq2 4080 . . . . . 6 (𝐴 = suc 𝑥 → (𝐵𝐴𝐵 ⊊ suc 𝑥))
86 breq1 5141 . . . . . . 7 (𝐴 = suc 𝑥 → (𝐴𝐵 ↔ suc 𝑥𝐵))
8786notbid 318 . . . . . 6 (𝐴 = suc 𝑥 → (¬ 𝐴𝐵 ↔ ¬ suc 𝑥𝐵))
8885, 87imbi12d 344 . . . . 5 (𝐴 = suc 𝑥 → ((𝐵𝐴 → ¬ 𝐴𝐵) ↔ (𝐵 ⊊ suc 𝑥 → ¬ suc 𝑥𝐵)))
8984, 88syl5ibrcom 246 . . . 4 (𝑥 ∈ ω → (𝐴 = suc 𝑥 → (𝐵𝐴 → ¬ 𝐴𝐵)))
9089rexlimiv 3140 . . 3 (∃𝑥 ∈ ω 𝐴 = suc 𝑥 → (𝐵𝐴 → ¬ 𝐴𝐵))
9110, 90syl 17 . 2 ((𝐴 ∈ ω ∧ 𝐵𝐴) → (𝐵𝐴 → ¬ 𝐴𝐵))
9291syldbl2 838 1 ((𝐴 ∈ ω ∧ 𝐵𝐴) → ¬ 𝐴𝐵)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 205  wa 395  w3a 1084   = wceq 1533  wex 1773  wcel 2098  wne 2932  wrex 3062  cdif 3937  cin 3939  wss 3940  wpss 3941  c0 4314  {csn 4620   class class class wbr 5138  Ord word 6353  suc csuc 6356  ωcom 7848  cen 8932  cdom 8933  Fincfn 8935
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1905  ax-6 1963  ax-7 2003  ax-8 2100  ax-9 2108  ax-10 2129  ax-11 2146  ax-12 2163  ax-ext 2695  ax-sep 5289  ax-nul 5296  ax-pr 5417  ax-un 7718
This theorem depends on definitions:  df-bi 206  df-an 396  df-or 845  df-3or 1085  df-3an 1086  df-tru 1536  df-fal 1546  df-ex 1774  df-nf 1778  df-sb 2060  df-mo 2526  df-eu 2555  df-clab 2702  df-cleq 2716  df-clel 2802  df-nfc 2877  df-ne 2933  df-ral 3054  df-rex 3063  df-reu 3369  df-rab 3425  df-v 3468  df-sbc 3770  df-csb 3886  df-dif 3943  df-un 3945  df-in 3947  df-ss 3957  df-pss 3959  df-nul 4315  df-if 4521  df-pw 4596  df-sn 4621  df-pr 4623  df-op 4627  df-uni 4900  df-br 5139  df-opab 5201  df-mpt 5222  df-tr 5256  df-id 5564  df-eprel 5570  df-po 5578  df-so 5579  df-fr 5621  df-we 5623  df-xp 5672  df-rel 5673  df-cnv 5674  df-co 5675  df-dm 5676  df-rn 5677  df-res 5678  df-ima 5679  df-ord 6357  df-on 6358  df-lim 6359  df-suc 6360  df-iota 6485  df-fun 6535  df-fn 6536  df-f 6537  df-f1 6538  df-fo 6539  df-f1o 6540  df-fv 6541  df-om 7849  df-1o 8461  df-en 8936  df-dom 8937  df-fin 8939
This theorem is referenced by:  php2  9207  php2OLD  9219  php3OLD  9220  omssrncard  42780  rr-phpd  43451
  Copyright terms: Public domain W3C validator