Theorem php3 8706

Description: Corollary of Pigeonhole Principle. If 𝐴 is finite and 𝐵 is a proper subset of 𝐴, the 𝐵 is strictly less numerous than 𝐴. Stronger version of Corollary 6C of [Enderton] p. 135. (Contributed by NM, 22-Aug-2008.)

Assertion

Ref	Expression
php3	⊢ ((𝐴 ∈ Fin ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≺ 𝐴)

Proof of Theorem php3

Dummy variables 𝑥 𝑓 𝑦 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		isfi 8536	. . 3 ⊢ (𝐴 ∈ Fin ↔ ∃𝑥 ∈ ω 𝐴 ≈ 𝑥)
2		relen 8517	. . . . . . . . 9 ⊢ Rel ≈
3	2	brrelex1i 5611	. . . . . . . 8 ⊢ (𝐴 ≈ 𝑥 → 𝐴 ∈ V)
4		pssss 4075	. . . . . . . 8 ⊢ (𝐵 ⊊ 𝐴 → 𝐵 ⊆ 𝐴)
5		ssdomg 8558	. . . . . . . . 9 ⊢ (𝐴 ∈ V → (𝐵 ⊆ 𝐴 → 𝐵 ≼ 𝐴))
6	5	imp 409	. . . . . . . 8 ⊢ ((𝐴 ∈ V ∧ 𝐵 ⊆ 𝐴) → 𝐵 ≼ 𝐴)
7	3, 4, 6	syl2an 597	. . . . . . 7 ⊢ ((𝐴 ≈ 𝑥 ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≼ 𝐴)
8	7	adantll 712	. . . . . 6 ⊢ (((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥) ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≼ 𝐴)
9		bren 8521	. . . . . . . . 9 ⊢ (𝐴 ≈ 𝑥 ↔ ∃𝑓 𝑓:𝐴–1-1-onto→𝑥)
10		imass2 5968	. . . . . . . . . . . . . . . . 17 ⊢ (𝐵 ⊆ 𝐴 → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
11	4, 10	syl 17	. . . . . . . . . . . . . . . 16 ⊢ (𝐵 ⊊ 𝐴 → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
12	11	adantl 484	. . . . . . . . . . . . . . 15 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
13		pssnel 4423	. . . . . . . . . . . . . . . . 17 ⊢ (𝐵 ⊊ 𝐴 → ∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵))
14		eldif 3949	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑦 ∈ (𝐴 ∖ 𝐵) ↔ (𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵))
15		f1ofn 6619	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → 𝑓 Fn 𝐴)
16		difss 4111	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (𝐴 ∖ 𝐵) ⊆ 𝐴
17		fnfvima 6998	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ ((𝑓 Fn 𝐴 ∧ (𝐴 ∖ 𝐵) ⊆ 𝐴 ∧ 𝑦 ∈ (𝐴 ∖ 𝐵)) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵)))
18	17	3expia 1117	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑓 Fn 𝐴 ∧ (𝐴 ∖ 𝐵) ⊆ 𝐴) → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵))))
19	15, 16, 18	sylancl 588	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵))))
20		dff1o3 6624	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (𝑓:𝐴–1-1-onto→𝑥 ↔ (𝑓:𝐴–onto→𝑥 ∧ Fun ◡𝑓))
21		imadif 6441	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (Fun ◡𝑓 → (𝑓 “ (𝐴 ∖ 𝐵)) = ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)))
22	20, 21	simplbiim 507	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑓 “ (𝐴 ∖ 𝐵)) = ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)))
23	22	eleq2d 2901	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → ((𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵)) ↔ (𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵))))
24	19, 23	sylibd 241	. . . . . . . . . . . . . . . . . . . . 21 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵))))
25		n0i 4302	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
26	24, 25	syl6 35	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
27	14, 26	syl5bir 245	. . . . . . . . . . . . . . . . . . 19 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → ((𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
28	27	exlimdv 1933	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
29	28	imp 409	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ ∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵)) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
30	13, 29	sylan2 594	. . . . . . . . . . . . . . . 16 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
31		ssdif0 4326	. . . . . . . . . . . . . . . 16 ⊢ ((𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵) ↔ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
32	30, 31	sylnibr 331	. . . . . . . . . . . . . . 15 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → ¬ (𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵))
33		dfpss3 4066	. . . . . . . . . . . . . . 15 ⊢ ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ ((𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴) ∧ ¬ (𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵)))
34	12, 32, 33	sylanbrc 585	. . . . . . . . . . . . . 14 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴))
35		imadmrn 5942	. . . . . . . . . . . . . . . . 17 ⊢ (𝑓 “ dom 𝑓) = ran 𝑓
36		f1odm 6622	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → dom 𝑓 = 𝐴)
37	36	imaeq2d 5932	. . . . . . . . . . . . . . . . 17 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑓 “ dom 𝑓) = (𝑓 “ 𝐴))
38		f1ofo 6625	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → 𝑓:𝐴–onto→𝑥)
39		forn 6596	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑓:𝐴–onto→𝑥 → ran 𝑓 = 𝑥)
40	38, 39	syl 17	. . . . . . . . . . . . . . . . 17 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → ran 𝑓 = 𝑥)
41	35, 37, 40	3eqtr3a 2883	. . . . . . . . . . . . . . . 16 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → (𝑓 “ 𝐴) = 𝑥)
42	41	psseq2d 4073	. . . . . . . . . . . . . . 15 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ (𝑓 “ 𝐵) ⊊ 𝑥))
43	42	adantr 483	. . . . . . . . . . . . . 14 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ (𝑓 “ 𝐵) ⊊ 𝑥))
44	34, 43	mpbid 234	. . . . . . . . . . . . 13 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊊ 𝑥)
45		php 8704	. . . . . . . . . . . . 13 ⊢ ((𝑥 ∈ ω ∧ (𝑓 “ 𝐵) ⊊ 𝑥) → ¬ 𝑥 ≈ (𝑓 “ 𝐵))
46	44, 45	sylan2 594	. . . . . . . . . . . 12 ⊢ ((𝑥 ∈ ω ∧ (𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴)) → ¬ 𝑥 ≈ (𝑓 “ 𝐵))
47		f1of1 6617	. . . . . . . . . . . . . . . 16 ⊢ (𝑓:𝐴–1-1-onto→𝑥 → 𝑓:𝐴–1-1→𝑥)
48		f1ores 6632	. . . . . . . . . . . . . . . 16 ⊢ ((𝑓:𝐴–1-1→𝑥 ∧ 𝐵 ⊆ 𝐴) → (𝑓 ↾ 𝐵):𝐵–1-1-onto→(𝑓 “ 𝐵))
49	47, 4, 48	syl2an 597	. . . . . . . . . . . . . . 15 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 ↾ 𝐵):𝐵–1-1-onto→(𝑓 “ 𝐵))
50		vex 3500	. . . . . . . . . . . . . . . . . 18 ⊢ 𝑓 ∈ V
51	50	resex 5902	. . . . . . . . . . . . . . . . 17 ⊢ (𝑓 ↾ 𝐵) ∈ V
52		f1oeq1 6607	. . . . . . . . . . . . . . . . 17 ⊢ (𝑦 = (𝑓 ↾ 𝐵) → (𝑦:𝐵–1-1-onto→(𝑓 “ 𝐵) ↔ (𝑓 ↾ 𝐵):𝐵–1-1-onto→(𝑓 “ 𝐵)))
53	51, 52	spcev 3610	. . . . . . . . . . . . . . . 16 ⊢ ((𝑓 ↾ 𝐵):𝐵–1-1-onto→(𝑓 “ 𝐵) → ∃𝑦 𝑦:𝐵–1-1-onto→(𝑓 “ 𝐵))
54		bren 8521	. . . . . . . . . . . . . . . 16 ⊢ (𝐵 ≈ (𝑓 “ 𝐵) ↔ ∃𝑦 𝑦:𝐵–1-1-onto→(𝑓 “ 𝐵))
55	53, 54	sylibr 236	. . . . . . . . . . . . . . 15 ⊢ ((𝑓 ↾ 𝐵):𝐵–1-1-onto→(𝑓 “ 𝐵) → 𝐵 ≈ (𝑓 “ 𝐵))
56	49, 55	syl 17	. . . . . . . . . . . . . 14 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≈ (𝑓 “ 𝐵))
57		entr 8564	. . . . . . . . . . . . . . 15 ⊢ ((𝑥 ≈ 𝐵 ∧ 𝐵 ≈ (𝑓 “ 𝐵)) → 𝑥 ≈ (𝑓 “ 𝐵))
58	57	expcom 416	. . . . . . . . . . . . . 14 ⊢ (𝐵 ≈ (𝑓 “ 𝐵) → (𝑥 ≈ 𝐵 → 𝑥 ≈ (𝑓 “ 𝐵)))
59	56, 58	syl 17	. . . . . . . . . . . . 13 ⊢ ((𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑥 ≈ 𝐵 → 𝑥 ≈ (𝑓 “ 𝐵)))
60	59	adantl 484	. . . . . . . . . . . 12 ⊢ ((𝑥 ∈ ω ∧ (𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴)) → (𝑥 ≈ 𝐵 → 𝑥 ≈ (𝑓 “ 𝐵)))
61	46, 60	mtod 200	. . . . . . . . . . 11 ⊢ ((𝑥 ∈ ω ∧ (𝑓:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊊ 𝐴)) → ¬ 𝑥 ≈ 𝐵)
62	61	exp32 423	. . . . . . . . . 10 ⊢ (𝑥 ∈ ω → (𝑓:𝐴–1-1-onto→𝑥 → (𝐵 ⊊ 𝐴 → ¬ 𝑥 ≈ 𝐵)))
63	62	exlimdv 1933	. . . . . . . . 9 ⊢ (𝑥 ∈ ω → (∃𝑓 𝑓:𝐴–1-1-onto→𝑥 → (𝐵 ⊊ 𝐴 → ¬ 𝑥 ≈ 𝐵)))
64	9, 63	syl5bi 244	. . . . . . . 8 ⊢ (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → ¬ 𝑥 ≈ 𝐵)))
65	64	imp31 420	. . . . . . 7 ⊢ (((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥) ∧ 𝐵 ⊊ 𝐴) → ¬ 𝑥 ≈ 𝐵)
66		entr 8564	. . . . . . . . . 10 ⊢ ((𝐵 ≈ 𝐴 ∧ 𝐴 ≈ 𝑥) → 𝐵 ≈ 𝑥)
67	66	ex 415	. . . . . . . . 9 ⊢ (𝐵 ≈ 𝐴 → (𝐴 ≈ 𝑥 → 𝐵 ≈ 𝑥))
68		ensym 8561	. . . . . . . . 9 ⊢ (𝐵 ≈ 𝑥 → 𝑥 ≈ 𝐵)
69	67, 68	syl6com 37	. . . . . . . 8 ⊢ (𝐴 ≈ 𝑥 → (𝐵 ≈ 𝐴 → 𝑥 ≈ 𝐵))
70	69	ad2antlr 725	. . . . . . 7 ⊢ (((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥) ∧ 𝐵 ⊊ 𝐴) → (𝐵 ≈ 𝐴 → 𝑥 ≈ 𝐵))
71	65, 70	mtod 200	. . . . . 6 ⊢ (((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥) ∧ 𝐵 ⊊ 𝐴) → ¬ 𝐵 ≈ 𝐴)
72		brsdom 8535	. . . . . 6 ⊢ (𝐵 ≺ 𝐴 ↔ (𝐵 ≼ 𝐴 ∧ ¬ 𝐵 ≈ 𝐴))
73	8, 71, 72	sylanbrc 585	. . . . 5 ⊢ (((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥) ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≺ 𝐴)
74	73	exp31 422	. . . 4 ⊢ (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴)))
75	74	rexlimiv 3283	. . 3 ⊢ (∃𝑥 ∈ ω 𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴))
76	1, 75	sylbi 219	. 2 ⊢ (𝐴 ∈ Fin → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴))
77	76	imp 409	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≺ 𝐴)

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 208   ∧ wa 398   = wceq 1536  ∃wex 1779   ∈ wcel 2113  ∃wrex 3142  Vcvv 3497   ∖ cdif 3936   ⊆ wss 3939   ⊊ wpss 3940  ∅c0 4294   class class class wbr 5069  ^◡ccnv 5557  dom cdm 5558  ran crn 5559   ↾ cres 5560   “ cima 5561  Fun wfun 6352   Fn wfn 6353  –1-1→wf1 6355  –onto→wfo 6356  –1-1-onto→wf1o 6357  ‘cfv 6358  ωcom 7583   ≈ cen 8509   ≼ cdom 8510   ≺ csdm 8511  Fincfn 8512

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1795  ax-4 1809  ax-5 1910  ax-6 1969  ax-7 2014  ax-8 2115  ax-9 2123  ax-10 2144  ax-11 2160  ax-12 2176  ax-ext 2796  ax-sep 5206  ax-nul 5213  ax-pow 5269  ax-pr 5333  ax-un 7464

This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1539  df-ex 1780  df-nf 1784  df-sb 2069  df-mo 2621  df-eu 2653  df-clab 2803  df-cleq 2817  df-clel 2896  df-nfc 2966  df-ne 3020  df-ral 3146  df-rex 3147  df-rab 3150  df-v 3499  df-sbc 3776  df-dif 3942  df-un 3944  df-in 3946  df-ss 3955  df-pss 3957  df-nul 4295  df-if 4471  df-pw 4544  df-sn 4571  df-pr 4573  df-tp 4575  df-op 4577  df-uni 4842  df-br 5070  df-opab 5132  df-tr 5176  df-id 5463  df-eprel 5468  df-po 5477  df-so 5478  df-fr 5517  df-we 5519  df-xp 5564  df-rel 5565  df-cnv 5566  df-co 5567  df-dm 5568  df-rn 5569  df-res 5570  df-ima 5571  df-ord 6197  df-on 6198  df-lim 6199  df-suc 6200  df-iota 6317  df-fun 6360  df-fn 6361  df-f 6362  df-f1 6363  df-fo 6364  df-f1o 6365  df-fv 6366  df-om 7584  df-er 8292  df-en 8513  df-dom 8514  df-sdom 8515  df-fin 8516

This theorem is referenced by:  phpeqd  8709  pssinf  8731  f1finf1o  8748  findcard3  8764  fofinf1o  8802  ackbij1b  9664  fincssdom  9748  fin23lem25  9749  canthp1lem2  10078  pwfseqlem4  10087  uzindi  13353  symggen  18601  pgpssslw  18742  pgpfaclem2  19207  ppiltx  25757  finminlem  33670  lindsenlbs  34891