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

Theorem hashge3el3dif 13931
Description: A set with size at least 3 has at least 3 different elements. In contrast to hashge2el2dif 13925, which has an elementary proof, the dominance relation and 1-1 functions from a set with three elements which are known to be different are used to prove this theorem. Although there is also an elementary proof for this theorem, it might be much longer. After all, this proof should be kept because it can be used as template for proofs for higher cardinalities. (Contributed by AV, 20-Mar-2019.) (Proof modification is discouraged.)
Assertion
Ref Expression
hashge3el3dif ((𝐷𝑉 ∧ 3 ≤ (♯‘𝐷)) → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧))
Distinct variable group:   𝑥,𝐷,𝑦,𝑧
Allowed substitution hints:   𝑉(𝑥,𝑦,𝑧)

Proof of Theorem hashge3el3dif
Dummy variable 𝑓 is distinct from all other variables.
StepHypRef Expression
1 0nep0 5221 . . . . . . . . 9 ∅ ≠ {∅}
2 0ex 5172 . . . . . . . . . . . 12 ∅ ∈ V
32sneqr 4723 . . . . . . . . . . 11 ({∅} = {{∅}} → ∅ = {∅})
43necon3i 2966 . . . . . . . . . 10 (∅ ≠ {∅} → {∅} ≠ {{∅}})
51, 4ax-mp 5 . . . . . . . . 9 {∅} ≠ {{∅}}
6 snex 5295 . . . . . . . . . 10 {∅} ∈ V
7 snnzg 4662 . . . . . . . . . 10 ({∅} ∈ V → {{∅}} ≠ ∅)
86, 7ax-mp 5 . . . . . . . . 9 {{∅}} ≠ ∅
91, 5, 83pm3.2i 1340 . . . . . . . 8 (∅ ≠ {∅} ∧ {∅} ≠ {{∅}} ∧ {{∅}} ≠ ∅)
10 snex 5295 . . . . . . . . . 10 {{∅}} ∈ V
112, 6, 103pm3.2i 1340 . . . . . . . . 9 (∅ ∈ V ∧ {∅} ∈ V ∧ {{∅}} ∈ V)
12 hashtpg 13930 . . . . . . . . 9 ((∅ ∈ V ∧ {∅} ∈ V ∧ {{∅}} ∈ V) → ((∅ ≠ {∅} ∧ {∅} ≠ {{∅}} ∧ {{∅}} ≠ ∅) ↔ (♯‘{∅, {∅}, {{∅}}}) = 3))
1311, 12ax-mp 5 . . . . . . . 8 ((∅ ≠ {∅} ∧ {∅} ≠ {{∅}} ∧ {{∅}} ≠ ∅) ↔ (♯‘{∅, {∅}, {{∅}}}) = 3)
149, 13mpbi 233 . . . . . . 7 (♯‘{∅, {∅}, {{∅}}}) = 3
1514eqcomi 2747 . . . . . 6 3 = (♯‘{∅, {∅}, {{∅}}})
1615a1i 11 . . . . 5 (𝐷𝑉 → 3 = (♯‘{∅, {∅}, {{∅}}}))
1716breq1d 5037 . . . 4 (𝐷𝑉 → (3 ≤ (♯‘𝐷) ↔ (♯‘{∅, {∅}, {{∅}}}) ≤ (♯‘𝐷)))
18 tpfi 8861 . . . . 5 {∅, {∅}, {{∅}}} ∈ Fin
19 hashdom 13825 . . . . 5 (({∅, {∅}, {{∅}}} ∈ Fin ∧ 𝐷𝑉) → ((♯‘{∅, {∅}, {{∅}}}) ≤ (♯‘𝐷) ↔ {∅, {∅}, {{∅}}} ≼ 𝐷))
2018, 19mpan 690 . . . 4 (𝐷𝑉 → ((♯‘{∅, {∅}, {{∅}}}) ≤ (♯‘𝐷) ↔ {∅, {∅}, {{∅}}} ≼ 𝐷))
2117, 20bitrd 282 . . 3 (𝐷𝑉 → (3 ≤ (♯‘𝐷) ↔ {∅, {∅}, {{∅}}} ≼ 𝐷))
22 brdomg 8558 . . . 4 (𝐷𝑉 → ({∅, {∅}, {{∅}}} ≼ 𝐷 ↔ ∃𝑓 𝑓:{∅, {∅}, {{∅}}}–1-1𝐷))
2311a1i 11 . . . . . . . 8 ((𝐷𝑉𝑓:{∅, {∅}, {{∅}}}–1-1𝐷) → (∅ ∈ V ∧ {∅} ∈ V ∧ {{∅}} ∈ V))
247necomd 2989 . . . . . . . . . . 11 ({∅} ∈ V → ∅ ≠ {{∅}})
256, 24ax-mp 5 . . . . . . . . . 10 ∅ ≠ {{∅}}
261, 25, 53pm3.2i 1340 . . . . . . . . 9 (∅ ≠ {∅} ∧ ∅ ≠ {{∅}} ∧ {∅} ≠ {{∅}})
2726a1i 11 . . . . . . . 8 ((𝐷𝑉𝑓:{∅, {∅}, {{∅}}}–1-1𝐷) → (∅ ≠ {∅} ∧ ∅ ≠ {{∅}} ∧ {∅} ≠ {{∅}}))
28 simpr 488 . . . . . . . 8 ((𝐷𝑉𝑓:{∅, {∅}, {{∅}}}–1-1𝐷) → 𝑓:{∅, {∅}, {{∅}}}–1-1𝐷)
2923, 27, 28f1dom3el3dif 7032 . . . . . . 7 ((𝐷𝑉𝑓:{∅, {∅}, {{∅}}}–1-1𝐷) → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧))
3029expcom 417 . . . . . 6 (𝑓:{∅, {∅}, {{∅}}}–1-1𝐷 → (𝐷𝑉 → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧)))
3130exlimiv 1936 . . . . 5 (∃𝑓 𝑓:{∅, {∅}, {{∅}}}–1-1𝐷 → (𝐷𝑉 → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧)))
3231com12 32 . . . 4 (𝐷𝑉 → (∃𝑓 𝑓:{∅, {∅}, {{∅}}}–1-1𝐷 → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧)))
3322, 32sylbid 243 . . 3 (𝐷𝑉 → ({∅, {∅}, {{∅}}} ≼ 𝐷 → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧)))
3421, 33sylbid 243 . 2 (𝐷𝑉 → (3 ≤ (♯‘𝐷) → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧)))
3534imp 410 1 ((𝐷𝑉 ∧ 3 ≤ (♯‘𝐷)) → ∃𝑥𝐷𝑦𝐷𝑧𝐷 (𝑥𝑦𝑥𝑧𝑦𝑧))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 209  wa 399  w3a 1088   = wceq 1542  wex 1786  wcel 2113  wne 2934  wrex 3054  Vcvv 3397  c0 4209  {csn 4513  {ctp 4517   class class class wbr 5027  1-1wf1 6330  cfv 6333  cdom 8546  Fincfn 8548  cle 10747  3c3 11765  chash 13775
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1916  ax-6 1974  ax-7 2019  ax-8 2115  ax-9 2123  ax-10 2144  ax-11 2161  ax-12 2178  ax-ext 2710  ax-sep 5164  ax-nul 5171  ax-pow 5229  ax-pr 5293  ax-un 7473  ax-cnex 10664  ax-resscn 10665  ax-1cn 10666  ax-icn 10667  ax-addcl 10668  ax-addrcl 10669  ax-mulcl 10670  ax-mulrcl 10671  ax-mulcom 10672  ax-addass 10673  ax-mulass 10674  ax-distr 10675  ax-i2m1 10676  ax-1ne0 10677  ax-1rid 10678  ax-rnegex 10679  ax-rrecex 10680  ax-cnre 10681  ax-pre-lttri 10682  ax-pre-lttrn 10683  ax-pre-ltadd 10684  ax-pre-mulgt0 10685
This theorem depends on definitions:  df-bi 210  df-an 400  df-or 847  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1787  df-nf 1791  df-sb 2074  df-mo 2540  df-eu 2570  df-clab 2717  df-cleq 2730  df-clel 2811  df-nfc 2881  df-ne 2935  df-nel 3039  df-ral 3058  df-rex 3059  df-reu 3060  df-rab 3062  df-v 3399  df-sbc 3680  df-csb 3789  df-dif 3844  df-un 3846  df-in 3848  df-ss 3858  df-pss 3860  df-nul 4210  df-if 4412  df-pw 4487  df-sn 4514  df-pr 4516  df-tp 4518  df-op 4520  df-uni 4794  df-int 4834  df-iun 4880  df-br 5028  df-opab 5090  df-mpt 5108  df-tr 5134  df-id 5425  df-eprel 5430  df-po 5438  df-so 5439  df-fr 5478  df-we 5480  df-xp 5525  df-rel 5526  df-cnv 5527  df-co 5528  df-dm 5529  df-rn 5530  df-res 5531  df-ima 5532  df-pred 6123  df-ord 6169  df-on 6170  df-lim 6171  df-suc 6172  df-iota 6291  df-fun 6335  df-fn 6336  df-f 6337  df-f1 6338  df-fo 6339  df-f1o 6340  df-fv 6341  df-riota 7121  df-ov 7167  df-oprab 7168  df-mpo 7169  df-om 7594  df-1st 7707  df-2nd 7708  df-wrecs 7969  df-recs 8030  df-rdg 8068  df-1o 8124  df-oadd 8128  df-er 8313  df-en 8549  df-dom 8550  df-sdom 8551  df-fin 8552  df-dju 9396  df-card 9434  df-pnf 10748  df-mnf 10749  df-xr 10750  df-ltxr 10751  df-le 10752  df-sub 10943  df-neg 10944  df-nn 11710  df-2 11772  df-3 11773  df-n0 11970  df-xnn0 12042  df-z 12056  df-uz 12318  df-fz 12975  df-hash 13776
This theorem is referenced by:  pmtr3ncom  18714
  Copyright terms: Public domain W3C validator