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

Theorem php3 9262
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.) Avoid ax-pow 5334. (Revised by BTernaryTau, 26-Nov-2024.)
Assertion
Ref Expression
php3 ((𝐴 ∈ Fin ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≺ 𝐴)

Proof of Theorem php3
Dummy variables 𝑓 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 9040 . . 3 (𝐴 ∈ Fin ↔ ∃𝑥 ∈ ω 𝐴 ≈ 𝑥)
2 bren 9021 . . . . . 6 (𝐴 ≈ 𝑥 ↔ ∃𝑓 𝑓:𝐴⟶1-1onto𝑥)
3 pssss 4028 . . . . . . . . . . . . . 14 (𝐵 ⊊ 𝐴 → 𝐵 ⊆ 𝐴)
4 imass2 6073 . . . . . . . . . . . . . 14 (𝐵 ⊆ 𝐴 → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
53, 4syl 18 . . . . . . . . . . . . 13 (𝐵 ⊊ 𝐴 → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
65adantl 487 . . . . . . . . . . . 12 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴))
7 pssnel 4427 . . . . . . . . . . . . . 14 (𝐵 ⊊ 𝐴 → ∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵))
8 eldif 4052 . . . . . . . . . . . . . . . . 17 (𝑦 ∈ (𝐴 ∖ 𝐵) ↔ (𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵))
9 f1ofn 6855 . . . . . . . . . . . . . . . . . . . 20 (𝑓:𝐴⟶1-1onto𝑥 → 𝑓 Fn 𝐴)
10 difss 4075 . . . . . . . . . . . . . . . . . . . 20 (𝐴 ∖ 𝐵) ⊆ 𝐴
11 fnfvima 7270 . . . . . . . . . . . . . . . . . . . . 21 ((𝑓 Fn 𝐴 ∧ (𝐴 ∖ 𝐵) ⊆ 𝐴 ∧ 𝑦 ∈ (𝐴 ∖ 𝐵)) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵)))
12113expia 1139 . . . . . . . . . . . . . . . . . . . 20 ((𝑓 Fn 𝐴 ∧ (𝐴 ∖ 𝐵) ⊆ 𝐴) → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵))))
139, 10, 12sylancl 598 . . . . . . . . . . . . . . . . . . 19 (𝑓:𝐴⟶1-1onto𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵))))
14 dff1o3 6861 . . . . . . . . . . . . . . . . . . . . 21 (𝑓:𝐴⟶1-1onto𝑥 ↔ (𝑓:𝐴⟶onto𝑥 ∧ Fun ◡𝑓))
15 imadif 6654 . . . . . . . . . . . . . . . . . . . . 21 (Fun ◡𝑓 → (𝑓 “ (𝐴 ∖ 𝐵)) = ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)))
1614, 15simplbiim 514 . . . . . . . . . . . . . . . . . . . 20 (𝑓:𝐴⟶1-1onto𝑥 → (𝑓 “ (𝐴 ∖ 𝐵)) = ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)))
1716eleq2d 2850 . . . . . . . . . . . . . . . . . . 19 (𝑓:𝐴⟶1-1onto𝑥 → ((𝑓‘𝑦) ∈ (𝑓 “ (𝐴 ∖ 𝐵)) ↔ (𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵))))
1813, 17sylibd 242 . . . . . . . . . . . . . . . . . 18 (𝑓:𝐴⟶1-1onto𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → (𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵))))
19 n0i 4289 . . . . . . . . . . . . . . . . . 18 ((𝑓‘𝑦) ∈ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
2018, 19syl6 36 . . . . . . . . . . . . . . . . 17 (𝑓:𝐴⟶1-1onto𝑥 → (𝑦 ∈ (𝐴 ∖ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
218, 20biimtrrid 246 . . . . . . . . . . . . . . . 16 (𝑓:𝐴⟶1-1onto𝑥 → ((𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
2221exlimdv 1968 . . . . . . . . . . . . . . 15 (𝑓:𝐴⟶1-1onto𝑥 → (∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅))
2322imp 412 . . . . . . . . . . . . . 14 ((𝑓:𝐴⟶1-1onto𝑥 ∧ ∃𝑦(𝑦 ∈ 𝐴 ∧ ¬ 𝑦 ∈ 𝐵)) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
247, 23sylan2 605 . . . . . . . . . . . . 13 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → ¬ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
25 ssdif0 4317 . . . . . . . . . . . . 13 ((𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵) ↔ ((𝑓 “ 𝐴) ∖ (𝑓 “ 𝐵)) = ∅)
2624, 25sylnibr 332 . . . . . . . . . . . 12 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → ¬ (𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵))
27 dfpss3 4019 . . . . . . . . . . . 12 ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ ((𝑓 “ 𝐵) ⊆ (𝑓 “ 𝐴) ∧ ¬ (𝑓 “ 𝐴) ⊆ (𝑓 “ 𝐵)))
286, 26, 27sylanbrc 595 . . . . . . . . . . 11 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴))
29 imadmrn 6085 . . . . . . . . . . . . . 14 (𝑓 “ dom 𝑓) = ran 𝑓
30 f1odm 6858 . . . . . . . . . . . . . . 15 (𝑓:𝐴⟶1-1onto𝑥 → dom 𝑓 = 𝐴)
3130imaeq2d 6070 . . . . . . . . . . . . . 14 (𝑓:𝐴⟶1-1onto𝑥 → (𝑓 “ dom 𝑓) = (𝑓 “ 𝐴))
32 f1ofo 6862 . . . . . . . . . . . . . . 15 (𝑓:𝐴⟶1-1onto𝑥 → 𝑓:𝐴⟶onto𝑥)
33 forn 6829 . . . . . . . . . . . . . . 15 (𝑓:𝐴⟶onto𝑥 → ran 𝑓 = 𝑥)
3432, 33syl 18 . . . . . . . . . . . . . 14 (𝑓:𝐴⟶1-1onto𝑥 → ran 𝑓 = 𝑥)
3529, 31, 343eqtr3a 2822 . . . . . . . . . . . . 13 (𝑓:𝐴⟶1-1onto𝑥 → (𝑓 “ 𝐴) = 𝑥)
3635psseq2d 4026 . . . . . . . . . . . 12 (𝑓:𝐴⟶1-1onto𝑥 → ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ (𝑓 “ 𝐵) ⊊ 𝑥))
3736adantr 486 . . . . . . . . . . 11 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → ((𝑓 “ 𝐵) ⊊ (𝑓 “ 𝐴) ↔ (𝑓 “ 𝐵) ⊊ 𝑥))
3828, 37mpbid 235 . . . . . . . . . 10 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 “ 𝐵) ⊊ 𝑥)
39 php2 9261 . . . . . . . . . 10 ((𝑥 ∈ ω ∧ (𝑓 “ 𝐵) ⊊ 𝑥) → (𝑓 “ 𝐵) ≺ 𝑥)
4038, 39sylan2 605 . . . . . . . . 9 ((𝑥 ∈ ω ∧ (𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴)) → (𝑓 “ 𝐵) ≺ 𝑥)
41 nnfi 9221 . . . . . . . . . 10 (𝑥 ∈ ω → 𝑥 ∈ Fin)
42 f1of1 6853 . . . . . . . . . . . 12 (𝑓:𝐴⟶1-1onto𝑥 → 𝑓:𝐴⟶1-1𝑥)
43 f1ores 6869 . . . . . . . . . . . 12 ((𝑓:𝐴⟶1-1𝑥 ∧ 𝐵 ⊆ 𝐴) → (𝑓 ↾ 𝐵):𝐵⟶1-1onto(𝑓 “ 𝐵))
4442, 3, 43syl2an 608 . . . . . . . . . . 11 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → (𝑓 ↾ 𝐵):𝐵⟶1-1onto(𝑓 “ 𝐵))
45 vex 3458 . . . . . . . . . . . . . 14 𝑓 ∈ V
4645resex 6036 . . . . . . . . . . . . 13 (𝑓 ↾ 𝐵) ∈ V
47 f1oeq1 6842 . . . . . . . . . . . . 13 (𝑦 = (𝑓 ↾ 𝐵) → (𝑦:𝐵⟶1-1onto(𝑓 “ 𝐵) ↔ (𝑓 ↾ 𝐵):𝐵⟶1-1onto(𝑓 “ 𝐵)))
4846, 47spcev 3564 . . . . . . . . . . . 12 ((𝑓 ↾ 𝐵):𝐵⟶1-1onto(𝑓 “ 𝐵) → ∃𝑦 𝑦:𝐵⟶1-1onto(𝑓 “ 𝐵))
49 bren 9021 . . . . . . . . . . . 12 (𝐵 ≈ (𝑓 “ 𝐵) ↔ ∃𝑦 𝑦:𝐵⟶1-1onto(𝑓 “ 𝐵))
5048, 49sylibr 237 . . . . . . . . . . 11 ((𝑓 ↾ 𝐵):𝐵⟶1-1onto(𝑓 “ 𝐵) → 𝐵 ≈ (𝑓 “ 𝐵))
5144, 50syl 18 . . . . . . . . . 10 ((𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≈ (𝑓 “ 𝐵))
52 endom 9044 . . . . . . . . . . . 12 (𝐵 ≈ (𝑓 “ 𝐵) → 𝐵 ≼ (𝑓 “ 𝐵))
53 sdomdom 9045 . . . . . . . . . . . . . . 15 ((𝑓 “ 𝐵) ≺ 𝑥 → (𝑓 “ 𝐵) ≼ 𝑥)
54 domfi 9242 . . . . . . . . . . . . . . 15 ((𝑥 ∈ Fin ∧ (𝑓 “ 𝐵) ≼ 𝑥) → (𝑓 “ 𝐵) ∈ Fin)
5553, 54sylan2 605 . . . . . . . . . . . . . 14 ((𝑥 ∈ Fin ∧ (𝑓 “ 𝐵) ≺ 𝑥) → (𝑓 “ 𝐵) ∈ Fin)
56553adant2 1149 . . . . . . . . . . . . 13 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → (𝑓 “ 𝐵) ∈ Fin)
57 domfi 9242 . . . . . . . . . . . . . . 15 (((𝑓 “ 𝐵) ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵)) → 𝐵 ∈ Fin)
58573adant3 1150 . . . . . . . . . . . . . 14 (((𝑓 “ 𝐵) ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → 𝐵 ∈ Fin)
59 domsdomtrfi 9255 . . . . . . . . . . . . . 14 ((𝐵 ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → 𝐵 ≺ 𝑥)
6058, 59syld3an1 1438 . . . . . . . . . . . . 13 (((𝑓 “ 𝐵) ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → 𝐵 ≺ 𝑥)
6156, 60syld3an1 1438 . . . . . . . . . . . 12 ((𝑥 ∈ Fin ∧ 𝐵 ≼ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → 𝐵 ≺ 𝑥)
6252, 61syl3an2 1182 . . . . . . . . . . 11 ((𝑥 ∈ Fin ∧ 𝐵 ≈ (𝑓 “ 𝐵) ∧ (𝑓 “ 𝐵) ≺ 𝑥) → 𝐵 ≺ 𝑥)
63623expia 1139 . . . . . . . . . 10 ((𝑥 ∈ Fin ∧ 𝐵 ≈ (𝑓 “ 𝐵)) → ((𝑓 “ 𝐵) ≺ 𝑥 → 𝐵 ≺ 𝑥))
6441, 51, 63syl2an 608 . . . . . . . . 9 ((𝑥 ∈ ω ∧ (𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴)) → ((𝑓 “ 𝐵) ≺ 𝑥 → 𝐵 ≺ 𝑥))
6540, 64mpd 16 . . . . . . . 8 ((𝑥 ∈ ω ∧ (𝑓:𝐴⟶1-1onto𝑥 ∧ 𝐵 ⊊ 𝐴)) → 𝐵 ≺ 𝑥)
6665exp32 426 . . . . . . 7 (𝑥 ∈ ω → (𝑓:𝐴⟶1-1onto𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝑥)))
6766exlimdv 1968 . . . . . 6 (𝑥 ∈ ω → (∃𝑓 𝑓:𝐴⟶1-1onto𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝑥)))
682, 67biimtrid 245 . . . . 5 (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝑥)))
69 ensymfib 9237 . . . . . . . . . . 11 (𝑥 ∈ Fin → (𝑥 ≈ 𝐴 ↔ 𝐴 ≈ 𝑥))
7069adantr 486 . . . . . . . . . 10 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥) → (𝑥 ≈ 𝐴 ↔ 𝐴 ≈ 𝑥))
7170biimp3ar 1500 . . . . . . . . 9 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝐴 ≈ 𝑥) → 𝑥 ≈ 𝐴)
72 endom 9044 . . . . . . . . . 10 (𝑥 ≈ 𝐴 → 𝑥 ≼ 𝐴)
73 sdomdom 9045 . . . . . . . . . . . . 13 (𝐵 ≺ 𝑥 → 𝐵 ≼ 𝑥)
74 domfi 9242 . . . . . . . . . . . . 13 ((𝑥 ∈ Fin ∧ 𝐵 ≼ 𝑥) → 𝐵 ∈ Fin)
7573, 74sylan2 605 . . . . . . . . . . . 12 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥) → 𝐵 ∈ Fin)
76753adant3 1150 . . . . . . . . . . 11 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝑥 ≼ 𝐴) → 𝐵 ∈ Fin)
77 sdomdomtrfi 9254 . . . . . . . . . . 11 ((𝐵 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝑥 ≼ 𝐴) → 𝐵 ≺ 𝐴)
7876, 77syld3an1 1438 . . . . . . . . . 10 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝑥 ≼ 𝐴) → 𝐵 ≺ 𝐴)
7972, 78syl3an3 1183 . . . . . . . . 9 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝑥 ≈ 𝐴) → 𝐵 ≺ 𝐴)
8071, 79syld3an3 1437 . . . . . . . 8 ((𝑥 ∈ Fin ∧ 𝐵 ≺ 𝑥 ∧ 𝐴 ≈ 𝑥) → 𝐵 ≺ 𝐴)
8141, 80syl3an1 1181 . . . . . . 7 ((𝑥 ∈ ω ∧ 𝐵 ≺ 𝑥 ∧ 𝐴 ≈ 𝑥) → 𝐵 ≺ 𝐴)
82813com23 1144 . . . . . 6 ((𝑥 ∈ ω ∧ 𝐴 ≈ 𝑥 ∧ 𝐵 ≺ 𝑥) → 𝐵 ≺ 𝐴)
83823exp 1137 . . . . 5 (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ≺ 𝑥 → 𝐵 ≺ 𝐴)))
8468, 83syldd 73 . . . 4 (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴)))
8584rexlimiv 3160 . . 3 (∃𝑥 ∈ ω 𝐴 ≈ 𝑥 → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴))
861, 85sylbi 220 . 2 (𝐴 ∈ Fin → (𝐵 ⊊ 𝐴 → 𝐵 ≺ 𝐴))
8786imp 412 1 ((𝐴 ∈ Fin ∧ 𝐵 ⊊ 𝐴) → 𝐵 ≺ 𝐴)
Colors of variables:    wff setvar class
This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 401   = wceq 1570  ∃wex 1812   ∈ wcel 2147  ∃wrex 3090   ⊆ wss 3900   ⊊ wpss 4016   ∖ cdif 4048  ∅c0 4281   class class class wbr 5108  ◡ccnv 5657  dom cdm 5658  ran crn 5659   ↾ cres 5660   “ cima 5661  Fun wfun 6560   Fn wfn 6561  ⟶1-1wf1 6563  ⟶ontowfo 6564  ⟶1-1ontowf1o 6565  ‘cfv 6566  ωcom 7911   ≈ cen 9008   ≼ cdom 9009   ≺ csdm 9010  Fincfn 9011
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pr 5398  ax-un 7783
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-reu 3370  df-rab 3417  df-v 3456  df-sbc 3743  df-csb 3852  df-ss 3901  df-pss 4017  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-br 5109  df-opab 5174  df-mpt 5193  df-tr 5219  df-id 5553  df-eprel 5558  df-po 5566  df-so 5567  df-fr 5611  df-we 5613  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-ord 6391  df-on 6392  df-lim 6393  df-suc 6394  df-iota 6520  df-fun 6568  df-fn 6569  df-f 6570  df-f1 6571  df-fo 6572  df-f1o 6573  df-fv 6574  df-om 7912  df-1o 8514  df-en 9012  df-dom 9013  df-sdom 9014  df-fin 9015
This theorem is used by:  phpeqd  9265  onomeneq  9267  pssinf  9291  f1finf1o  9302  findcard3  9312  fofinf1o  9359  ackbij1b  10355  fincssdom  10440  fin23lem25  10441  canthp1lem2  10777  pwfseqlem4  10786  uzindi  14165  symggen  19735  pgpssslw  19879  pgpfaclem2  20349  lindsenlbs  22212  ppiltx  27561  finminlem  37321
  Copyright terms: Public domain W3C validator