Theorem phpm 6859

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 6846 through phplem4 6849, nneneq 6851, 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.

Step	Hyp	Ref	Expression
1		simpr 110	. . . . . 6 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝐴 = ∅) → 𝐴 = ∅)
2		eldifi 3257	. . . . . . . . 9 ⊢ (𝑥 ∈ (𝐴 ∖ 𝐵) → 𝑥 ∈ 𝐴)
3		ne0i 3429	. . . . . . . . 9 ⊢ (𝑥 ∈ 𝐴 → 𝐴 ≠ ∅)
4	2, 3	syl 14	. . . . . . . 8 ⊢ (𝑥 ∈ (𝐴 ∖ 𝐵) → 𝐴 ≠ ∅)
5	4	neneqd 2368	. . . . . . 7 ⊢ (𝑥 ∈ (𝐴 ∖ 𝐵) → ¬ 𝐴 = ∅)
6	5	ad2antlr 489	. . . . . 6 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝐴 = ∅) → ¬ 𝐴 = ∅)
7	1, 6	pm2.21dd 620	. . . . 5 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝐴 = ∅) → ¬ 𝐴 ≈ 𝐵)
8		php5dom 6857	. . . . . . . . . 10 ⊢ (𝑦 ∈ ω → ¬ suc 𝑦 ≼ 𝑦)
9	8	ad2antlr 489	. . . . . . . . 9 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ suc 𝑦 ≼ 𝑦)
10		simplr 528	. . . . . . . . . 10 ⊢ ((((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴 ≈ 𝐵) → 𝐴 = suc 𝑦)
11		simpr 110	. . . . . . . . . . 11 ⊢ ((((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴 ≈ 𝐵) → 𝐴 ≈ 𝐵)
12		vex 2740	. . . . . . . . . . . . . . . 16 ⊢ 𝑦 ∈ V
13	12	sucex 4495	. . . . . . . . . . . . . . 15 ⊢ suc 𝑦 ∈ V
14		difss 3261	. . . . . . . . . . . . . . 15 ⊢ (suc 𝑦 ∖ {𝑥}) ⊆ suc 𝑦
15	13, 14	ssexi 4138	. . . . . . . . . . . . . 14 ⊢ (suc 𝑦 ∖ {𝑥}) ∈ V
16		eldifn 3258	. . . . . . . . . . . . . . . 16 ⊢ (𝑥 ∈ (𝐴 ∖ 𝐵) → ¬ 𝑥 ∈ 𝐵)
17	16	ad3antlr 493	. . . . . . . . . . . . . . 15 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ 𝑥 ∈ 𝐵)
18		simpllr 534	. . . . . . . . . . . . . . . . 17 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) → 𝐵 ⊆ 𝐴)
19	18	adantr 276	. . . . . . . . . . . . . . . 16 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ⊆ 𝐴)
20		simpr 110	. . . . . . . . . . . . . . . 16 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐴 = suc 𝑦)
21	19, 20	sseqtrd 3193	. . . . . . . . . . . . . . 15 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ⊆ suc 𝑦)
22		ssdif 3270	. . . . . . . . . . . . . . . 16 ⊢ (𝐵 ⊆ suc 𝑦 → (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥}))
23		disjsn 3653	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝐵 ∩ {𝑥}) = ∅ ↔ ¬ 𝑥 ∈ 𝐵)
24		disj3 3475	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝐵 ∩ {𝑥}) = ∅ ↔ 𝐵 = (𝐵 ∖ {𝑥}))
25	23, 24	bitr3i 186	. . . . . . . . . . . . . . . . 17 ⊢ (¬ 𝑥 ∈ 𝐵 ↔ 𝐵 = (𝐵 ∖ {𝑥}))
26		sseq1 3178	. . . . . . . . . . . . . . . . 17 ⊢ (𝐵 = (𝐵 ∖ {𝑥}) → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) ↔ (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥})))
27	25, 26	sylbi 121	. . . . . . . . . . . . . . . 16 ⊢ (¬ 𝑥 ∈ 𝐵 → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) ↔ (𝐵 ∖ {𝑥}) ⊆ (suc 𝑦 ∖ {𝑥})))
28	22, 27	syl5ibr 156	. . . . . . . . . . . . . . 15 ⊢ (¬ 𝑥 ∈ 𝐵 → (𝐵 ⊆ suc 𝑦 → 𝐵 ⊆ (suc 𝑦 ∖ {𝑥})))
29	17, 21, 28	sylc 62	. . . . . . . . . . . . . 14 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ⊆ (suc 𝑦 ∖ {𝑥}))
30		ssdomg 6772	. . . . . . . . . . . . . 14 ⊢ ((suc 𝑦 ∖ {𝑥}) ∈ V → (𝐵 ⊆ (suc 𝑦 ∖ {𝑥}) → 𝐵 ≼ (suc 𝑦 ∖ {𝑥})))
31	15, 29, 30	mpsyl 65	. . . . . . . . . . . . 13 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ≼ (suc 𝑦 ∖ {𝑥}))
32		simplr 528	. . . . . . . . . . . . . 14 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑦 ∈ ω)
33	2	ad3antlr 493	. . . . . . . . . . . . . . 15 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑥 ∈ 𝐴)
34	33, 20	eleqtrd 2256	. . . . . . . . . . . . . 14 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝑥 ∈ suc 𝑦)
35		phplem3g 6850	. . . . . . . . . . . . . . 15 ⊢ ((𝑦 ∈ ω ∧ 𝑥 ∈ suc 𝑦) → 𝑦 ≈ (suc 𝑦 ∖ {𝑥}))
36	35	ensymd 6777	. . . . . . . . . . . . . 14 ⊢ ((𝑦 ∈ ω ∧ 𝑥 ∈ suc 𝑦) → (suc 𝑦 ∖ {𝑥}) ≈ 𝑦)
37	32, 34, 36	syl2anc 411	. . . . . . . . . . . . 13 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → (suc 𝑦 ∖ {𝑥}) ≈ 𝑦)
38		domentr 6785	. . . . . . . . . . . . 13 ⊢ ((𝐵 ≼ (suc 𝑦 ∖ {𝑥}) ∧ (suc 𝑦 ∖ {𝑥}) ≈ 𝑦) → 𝐵 ≼ 𝑦)
39	31, 37, 38	syl2anc 411	. . . . . . . . . . . 12 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → 𝐵 ≼ 𝑦)
40	39	adantr 276	. . . . . . . . . . 11 ⊢ ((((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴 ≈ 𝐵) → 𝐵 ≼ 𝑦)
41		endomtr 6784	. . . . . . . . . . 11 ⊢ ((𝐴 ≈ 𝐵 ∧ 𝐵 ≼ 𝑦) → 𝐴 ≼ 𝑦)
42	11, 40, 41	syl2anc 411	. . . . . . . . . 10 ⊢ ((((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴 ≈ 𝐵) → 𝐴 ≼ 𝑦)
43	10, 42	eqbrtrrd 4024	. . . . . . . . 9 ⊢ ((((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) ∧ 𝐴 ≈ 𝐵) → suc 𝑦 ≼ 𝑦)
44	9, 43	mtand 665	. . . . . . . 8 ⊢ (((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) ∧ 𝐴 = suc 𝑦) → ¬ 𝐴 ≈ 𝐵)
45	44	ex 115	. . . . . . 7 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ 𝑦 ∈ ω) → (𝐴 = suc 𝑦 → ¬ 𝐴 ≈ 𝐵))
46	45	rexlimdva 2594	. . . . . 6 ⊢ (((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) → (∃𝑦 ∈ ω 𝐴 = suc 𝑦 → ¬ 𝐴 ≈ 𝐵))
47	46	imp 124	. . . . 5 ⊢ ((((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) ∧ ∃𝑦 ∈ ω 𝐴 = suc 𝑦) → ¬ 𝐴 ≈ 𝐵)
48		nn0suc 4600	. . . . . 6 ⊢ (𝐴 ∈ ω → (𝐴 = ∅ ∨ ∃𝑦 ∈ ω 𝐴 = suc 𝑦))
49	48	ad2antrr 488	. . . . 5 ⊢ (((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) → (𝐴 = ∅ ∨ ∃𝑦 ∈ ω 𝐴 = suc 𝑦))
50	7, 47, 49	mpjaodan 798	. . . 4 ⊢ (((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ∈ (𝐴 ∖ 𝐵)) → ¬ 𝐴 ≈ 𝐵)
51	50	ex 115	. . 3 ⊢ ((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) → (𝑥 ∈ (𝐴 ∖ 𝐵) → ¬ 𝐴 ≈ 𝐵))
52	51	exlimdv 1819	. 2 ⊢ ((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴) → (∃𝑥 𝑥 ∈ (𝐴 ∖ 𝐵) → ¬ 𝐴 ≈ 𝐵))
53	52	3impia 1200	1 ⊢ ((𝐴 ∈ ω ∧ 𝐵 ⊆ 𝐴 ∧ ∃𝑥 𝑥 ∈ (𝐴 ∖ 𝐵)) → ¬ 𝐴 ≈ 𝐵)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 104   ↔ wb 105   ∨ wo 708   ∧ w3a 978   = wceq 1353  ∃wex 1492   ∈ wcel 2148   ≠ wne 2347  ∃wrex 2456  Vcvv 2737   ∖ cdif 3126   ∩ cin 3128   ⊆ wss 3129  ∅c0 3422  {csn 3591   class class class wbr 4000  suc csuc 4362  ωcom 4586   ≈ cen 6732   ≼ cdom 6733

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 614  ax-in2 615  ax-io 709  ax-5 1447  ax-7 1448  ax-gen 1449  ax-ie1 1493  ax-ie2 1494  ax-8 1504  ax-10 1505  ax-11 1506  ax-i12 1507  ax-bndl 1509  ax-4 1510  ax-17 1526  ax-i9 1530  ax-ial 1534  ax-i5r 1535  ax-13 2150  ax-14 2151  ax-ext 2159  ax-sep 4118  ax-nul 4126  ax-pow 4171  ax-pr 4206  ax-un 4430  ax-setind 4533  ax-iinf 4584

This theorem depends on definitions:  df-bi 117  df-dc 835  df-3or 979  df-3an 980  df-tru 1356  df-fal 1359  df-nf 1461  df-sb 1763  df-eu 2029  df-mo 2030  df-clab 2164  df-cleq 2170  df-clel 2173  df-nfc 2308  df-ne 2348  df-ral 2460  df-rex 2461  df-rab 2464  df-v 2739  df-sbc 2963  df-dif 3131  df-un 3133  df-in 3135  df-ss 3142  df-nul 3423  df-pw 3576  df-sn 3597  df-pr 3598  df-op 3600  df-uni 3808  df-int 3843  df-br 4001  df-opab 4062  df-tr 4099  df-id 4290  df-iord 4363  df-on 4365  df-suc 4368  df-iom 4587  df-xp 4629  df-rel 4630  df-cnv 4631  df-co 4632  df-dm 4633  df-rn 4634  df-res 4635  df-ima 4636  df-iota 5174  df-fun 5214  df-fn 5215  df-f 5216  df-f1 5217  df-fo 5218  df-f1o 5219  df-fv 5220  df-er 6529  df-en 6735  df-dom 6736

This theorem is referenced by:  phpelm  6860