Theorem hashprg 14398

Description: The size of an unordered pair. (Contributed by Mario Carneiro, 27-Sep-2013.) (Revised by Mario Carneiro, 5-May-2016.) (Revised by AV, 18-Sep-2021.)

Assertion

Ref	Expression
hashprg	⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → (𝐴 ≠ 𝐵 ↔ (♯‘{𝐴, 𝐵}) = 2))

Proof of Theorem hashprg

Step	Hyp	Ref	Expression
1		simpr 487	. . . . 5 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → 𝐵 ∈ 𝑊)
2		elsni 4593	. . . . . . 7 ⊢ (𝐵 ∈ {𝐴} → 𝐵 = 𝐴)
3	2	eqcomd 2762	. . . . . 6 ⊢ (𝐵 ∈ {𝐴} → 𝐴 = 𝐵)
4	3	necon3ai 2976	. . . . 5 ⊢ (𝐴 ≠ 𝐵 → ¬ 𝐵 ∈ {𝐴})
5		snfi 9013	. . . . . 6 ⊢ {𝐴} ∈ Fin
6		hashunsng 14395	. . . . . . 7 ⊢ (𝐵 ∈ 𝑊 → (({𝐴} ∈ Fin ∧ ¬ 𝐵 ∈ {𝐴}) → (♯‘({𝐴} ∪ {𝐵})) = ((♯‘{𝐴}) + 1)))
7	6	imp 409	. . . . . 6 ⊢ ((𝐵 ∈ 𝑊 ∧ ({𝐴} ∈ Fin ∧ ¬ 𝐵 ∈ {𝐴})) → (♯‘({𝐴} ∪ {𝐵})) = ((♯‘{𝐴}) + 1))
8	5, 7	mpanr1 711	. . . . 5 ⊢ ((𝐵 ∈ 𝑊 ∧ ¬ 𝐵 ∈ {𝐴}) → (♯‘({𝐴} ∪ {𝐵})) = ((♯‘{𝐴}) + 1))
9	1, 4, 8	syl2an 604	. . . 4 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ 𝐴 ≠ 𝐵) → (♯‘({𝐴} ∪ {𝐵})) = ((♯‘{𝐴}) + 1))
10		hashsng 14372	. . . . . . 7 ⊢ (𝐴 ∈ 𝑉 → (♯‘{𝐴}) = 1)
11	10	adantr 483	. . . . . 6 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → (♯‘{𝐴}) = 1)
12	11	adantr 483	. . . . 5 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ 𝐴 ≠ 𝐵) → (♯‘{𝐴}) = 1)
13	12	oveq1d 7400	. . . 4 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ 𝐴 ≠ 𝐵) → ((♯‘{𝐴}) + 1) = (1 + 1))
14	9, 13	eqtrd 2791	. . 3 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ 𝐴 ≠ 𝐵) → (♯‘({𝐴} ∪ {𝐵})) = (1 + 1))
15		df-pr 4579	. . . 4 ⊢ {𝐴, 𝐵} = ({𝐴} ∪ {𝐵})
16	15	fveq2i 6859	. . 3 ⊢ (♯‘{𝐴, 𝐵}) = (♯‘({𝐴} ∪ {𝐵}))
17		df-2 12270	. . 3 ⊢ 2 = (1 + 1)
18	14, 16, 17	3eqtr4g 2816	. 2 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ 𝐴 ≠ 𝐵) → (♯‘{𝐴, 𝐵}) = 2)
19		1ne2 12418	. . . . . . 7 ⊢ 1 ≠ 2
20	19	a1i 11	. . . . . 6 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → 1 ≠ 2)
21	11, 20	eqnetrd 3018	. . . . 5 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → (♯‘{𝐴}) ≠ 2)
22		dfsn2 4589	. . . . . . . 8 ⊢ {𝐴} = {𝐴, 𝐴}
23		preq2 4687	. . . . . . . 8 ⊢ (𝐴 = 𝐵 → {𝐴, 𝐴} = {𝐴, 𝐵})
24	22, 23	eqtr2id 2804	. . . . . . 7 ⊢ (𝐴 = 𝐵 → {𝐴, 𝐵} = {𝐴})
25	24	fveq2d 6860	. . . . . 6 ⊢ (𝐴 = 𝐵 → (♯‘{𝐴, 𝐵}) = (♯‘{𝐴}))
26	25	neeq1d 3010	. . . . 5 ⊢ (𝐴 = 𝐵 → ((♯‘{𝐴, 𝐵}) ≠ 2 ↔ (♯‘{𝐴}) ≠ 2))
27	21, 26	syl5ibrcom 249	. . . 4 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → (𝐴 = 𝐵 → (♯‘{𝐴, 𝐵}) ≠ 2))
28	27	necon2d 2974	. . 3 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → ((♯‘{𝐴, 𝐵}) = 2 → 𝐴 ≠ 𝐵))
29	28	imp 409	. 2 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) ∧ (♯‘{𝐴, 𝐵}) = 2) → 𝐴 ≠ 𝐵)
30	18, 29	impbida 808	1 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑊) → (𝐴 ≠ 𝐵 ↔ (♯‘{𝐴, 𝐵}) = 2))

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 208   ∧ wa 398   = wceq 1554   ∈ wcel 2136   ≠ wne 2951   ∪ cun 3897  {csn 4576  {cpr 4578  ‘cfv 6510  (class class class)co 7385  Fincfn 8916  1c1 11064   + caddc 11066  2c2 12262  ♯chash 14333

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1809  ax-4 1823  ax-5 1924  ax-6 1981  ax-7 2022  ax-8 2138  ax-9 2146  ax-10 2169  ax-11 2185  ax-12 2206  ax-ext 2728  ax-sep 5240  ax-nul 5250  ax-pow 5316  ax-pr 5384  ax-un 7707  ax-cnex 11119  ax-resscn 11120  ax-1cn 11121  ax-icn 11122  ax-addcl 11123  ax-addrcl 11124  ax-mulcl 11125  ax-mulrcl 11126  ax-mulcom 11127  ax-addass 11128  ax-mulass 11129  ax-distr 11130  ax-i2m1 11131  ax-1ne0 11132  ax-1rid 11133  ax-rnegex 11134  ax-rrecex 11135  ax-cnre 11136  ax-pre-lttri 11137  ax-pre-lttrn 11138  ax-pre-ltadd 11139  ax-pre-mulgt0 11140

This theorem depends on definitions:  df-bi 209  df-an 399  df-or 857  df-3or 1096  df-3an 1097  df-tru 1557  df-fal 1567  df-ex 1794  df-nf 1798  df-sb 2085  df-mo 2560  df-eu 2590  df-clab 2735  df-cleq 2748  df-clel 2831  df-nfc 2905  df-ne 2952  df-nel 3056  df-ral 3071  df-rex 3081  df-reu 3362  df-rab 3409  df-v 3450  df-sbc 3740  df-csb 3848  df-dif 3902  df-un 3904  df-in 3906  df-ss 3916  df-pss 3919  df-nul 4281  df-if 4475  df-pw 4551  df-sn 4577  df-pr 4579  df-op 4583  df-uni 4860  df-int 4900  df-iun 4945  df-br 5095  df-opab 5157  df-mpt 5176  df-tr 5202  df-id 5535  df-eprel 5540  df-po 5548  df-so 5549  df-fr 5593  df-we 5595  df-xp 5646  df-rel 5647  df-cnv 5648  df-co 5649  df-dm 5650  df-rn 5651  df-res 5652  df-ima 5653  df-pred 6277  df-ord 6338  df-on 6339  df-lim 6340  df-suc 6341  df-iota 6466  df-fun 6512  df-fn 6513  df-f 6514  df-f1 6515  df-fo 6516  df-f1o 6517  df-fv 6518  df-riota 7342  df-ov 7388  df-oprab 7389  df-mpo 7390  df-om 7836  df-1st 7959  df-2nd 7960  df-frecs 8250  df-wrecs 8281  df-recs 8330  df-rdg 8369  df-1o 8425  df-oadd 8429  df-er 8666  df-en 8917  df-dom 8918  df-sdom 8919  df-fin 8920  df-dju 9849  df-card 9887  df-pnf 11208  df-mnf 11209  df-xr 11210  df-ltxr 11211  df-le 11212  df-sub 11406  df-neg 11407  df-nn 12201  df-2 12270  df-n0 12472  df-z 12559  df-uz 12830  df-fz 13503  df-hash 14334

This theorem is referenced by:  hashprb  14400  prhash2ex  14402  hashfun  14440  hash2exprb  14474  nehash2  14477  hashtpg  14488  elss2prb  14491  hash3tpexb  14497  wrdlen2i  14945  isnzr2hash  20541  upgrex  29232  umgrbi  29241  usgr1e  29385  usgrexmplef  29399  cusgrexilem2  29582  cusgrfilem1  29595  umgr2v2e  29665  vdegp1bi  29677  eulerpathpr  30381  drngidlhash  33574  ccfldextdgrr  33923  coinflipprob  34731  cusgredgex  35420  subfacp1lem1  35477  poimirlem9  38076  fourierdlem54  46682  fourierdlem102  46730  fourierdlem103  46731  fourierdlem104  46732  fourierdlem114  46742  prpair  48055  prproropf1olem1  48057  paireqne  48065  prprspr2  48072  reuprpr  48077  stgrusgra  48529  gpgusgralem  48626