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

Theorem infdif 9325
Description: The cardinality of an infinite set does not change after subtracting a strictly smaller one. Example in [Enderton] p. 164. (Contributed by NM, 22-Oct-2004.) (Revised by Mario Carneiro, 29-Apr-2015.)
Assertion
Ref Expression
infdif ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ≈ 𝐴)

Proof of Theorem infdif
StepHypRef Expression
1 simp1 1159 . . 3 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐴 ∈ dom card)
2 difss 3947 . . 3 (𝐴𝐵) ⊆ 𝐴
3 ssdomg 8247 . . 3 (𝐴 ∈ dom card → ((𝐴𝐵) ⊆ 𝐴 → (𝐴𝐵) ≼ 𝐴))
41, 2, 3mpisyl 21 . 2 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ≼ 𝐴)
5 sdomdom 8229 . . . . . . . . 9 (𝐵𝐴𝐵𝐴)
653ad2ant3 1158 . . . . . . . 8 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐵𝐴)
7 numdom 9153 . . . . . . . 8 ((𝐴 ∈ dom card ∧ 𝐵𝐴) → 𝐵 ∈ dom card)
81, 6, 7syl2anc 575 . . . . . . 7 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐵 ∈ dom card)
9 unnum 9316 . . . . . . 7 ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → (𝐴𝐵) ∈ dom card)
101, 8, 9syl2anc 575 . . . . . 6 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ∈ dom card)
11 ssun1 3986 . . . . . 6 𝐴 ⊆ (𝐴𝐵)
12 ssdomg 8247 . . . . . 6 ((𝐴𝐵) ∈ dom card → (𝐴 ⊆ (𝐴𝐵) → 𝐴 ≼ (𝐴𝐵)))
1310, 11, 12mpisyl 21 . . . . 5 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐴 ≼ (𝐴𝐵))
14 undif1 4250 . . . . . 6 ((𝐴𝐵) ∪ 𝐵) = (𝐴𝐵)
15 ssnum 9154 . . . . . . . 8 ((𝐴 ∈ dom card ∧ (𝐴𝐵) ⊆ 𝐴) → (𝐴𝐵) ∈ dom card)
161, 2, 15sylancl 576 . . . . . . 7 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ∈ dom card)
17 uncdadom 9287 . . . . . . 7 (((𝐴𝐵) ∈ dom card ∧ 𝐵 ∈ dom card) → ((𝐴𝐵) ∪ 𝐵) ≼ ((𝐴𝐵) +𝑐 𝐵))
1816, 8, 17syl2anc 575 . . . . . 6 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ((𝐴𝐵) ∪ 𝐵) ≼ ((𝐴𝐵) +𝑐 𝐵))
1914, 18syl5eqbrr 4891 . . . . 5 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ≼ ((𝐴𝐵) +𝑐 𝐵))
20 domtr 8254 . . . . 5 ((𝐴 ≼ (𝐴𝐵) ∧ (𝐴𝐵) ≼ ((𝐴𝐵) +𝑐 𝐵)) → 𝐴 ≼ ((𝐴𝐵) +𝑐 𝐵))
2113, 19, 20syl2anc 575 . . . 4 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐴 ≼ ((𝐴𝐵) +𝑐 𝐵))
22 simp3 1161 . . . . . . 7 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐵𝐴)
23 sdomdom 8229 . . . . . . . . 9 ((𝐴𝐵) ≺ 𝐵 → (𝐴𝐵) ≼ 𝐵)
24 cdadom1 9302 . . . . . . . . 9 ((𝐴𝐵) ≼ 𝐵 → ((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵))
2523, 24syl 17 . . . . . . . 8 ((𝐴𝐵) ≺ 𝐵 → ((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵))
26 domtr 8254 . . . . . . . . . . 11 ((𝐴 ≼ ((𝐴𝐵) +𝑐 𝐵) ∧ ((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵)) → 𝐴 ≼ (𝐵 +𝑐 𝐵))
2726ex 399 . . . . . . . . . 10 (𝐴 ≼ ((𝐴𝐵) +𝑐 𝐵) → (((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵) → 𝐴 ≼ (𝐵 +𝑐 𝐵)))
2821, 27syl 17 . . . . . . . . 9 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵) → 𝐴 ≼ (𝐵 +𝑐 𝐵)))
29 simp2 1160 . . . . . . . . . . . 12 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ω ≼ 𝐴)
30 domtr 8254 . . . . . . . . . . . . 13 ((ω ≼ 𝐴𝐴 ≼ (𝐵 +𝑐 𝐵)) → ω ≼ (𝐵 +𝑐 𝐵))
3130ex 399 . . . . . . . . . . . 12 (ω ≼ 𝐴 → (𝐴 ≼ (𝐵 +𝑐 𝐵) → ω ≼ (𝐵 +𝑐 𝐵)))
3229, 31syl 17 . . . . . . . . . . 11 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴 ≼ (𝐵 +𝑐 𝐵) → ω ≼ (𝐵 +𝑐 𝐵)))
33 cdainf 9308 . . . . . . . . . . . . 13 (ω ≼ 𝐵 ↔ ω ≼ (𝐵 +𝑐 𝐵))
3433biimpri 219 . . . . . . . . . . . 12 (ω ≼ (𝐵 +𝑐 𝐵) → ω ≼ 𝐵)
35 domrefg 8236 . . . . . . . . . . . . 13 (𝐵 ∈ dom card → 𝐵𝐵)
36 infcdaabs 9322 . . . . . . . . . . . . . . 15 ((𝐵 ∈ dom card ∧ ω ≼ 𝐵𝐵𝐵) → (𝐵 +𝑐 𝐵) ≈ 𝐵)
37363com23 1149 . . . . . . . . . . . . . 14 ((𝐵 ∈ dom card ∧ 𝐵𝐵 ∧ ω ≼ 𝐵) → (𝐵 +𝑐 𝐵) ≈ 𝐵)
38373expia 1143 . . . . . . . . . . . . 13 ((𝐵 ∈ dom card ∧ 𝐵𝐵) → (ω ≼ 𝐵 → (𝐵 +𝑐 𝐵) ≈ 𝐵))
3935, 38mpdan 670 . . . . . . . . . . . 12 (𝐵 ∈ dom card → (ω ≼ 𝐵 → (𝐵 +𝑐 𝐵) ≈ 𝐵))
408, 34, 39syl2im 40 . . . . . . . . . . 11 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (ω ≼ (𝐵 +𝑐 𝐵) → (𝐵 +𝑐 𝐵) ≈ 𝐵))
4132, 40syld 47 . . . . . . . . . 10 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴 ≼ (𝐵 +𝑐 𝐵) → (𝐵 +𝑐 𝐵) ≈ 𝐵))
42 domen2 8351 . . . . . . . . . . 11 ((𝐵 +𝑐 𝐵) ≈ 𝐵 → (𝐴 ≼ (𝐵 +𝑐 𝐵) ↔ 𝐴𝐵))
4342biimpcd 240 . . . . . . . . . 10 (𝐴 ≼ (𝐵 +𝑐 𝐵) → ((𝐵 +𝑐 𝐵) ≈ 𝐵𝐴𝐵))
4441, 43sylcom 30 . . . . . . . . 9 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴 ≼ (𝐵 +𝑐 𝐵) → 𝐴𝐵))
4528, 44syld 47 . . . . . . . 8 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (((𝐴𝐵) +𝑐 𝐵) ≼ (𝐵 +𝑐 𝐵) → 𝐴𝐵))
46 domnsym 8334 . . . . . . . 8 (𝐴𝐵 → ¬ 𝐵𝐴)
4725, 45, 46syl56 36 . . . . . . 7 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ((𝐴𝐵) ≺ 𝐵 → ¬ 𝐵𝐴))
4822, 47mt2d 133 . . . . . 6 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ¬ (𝐴𝐵) ≺ 𝐵)
49 domtri2 9107 . . . . . . 7 ((𝐵 ∈ dom card ∧ (𝐴𝐵) ∈ dom card) → (𝐵 ≼ (𝐴𝐵) ↔ ¬ (𝐴𝐵) ≺ 𝐵))
508, 16, 49syl2anc 575 . . . . . 6 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐵 ≼ (𝐴𝐵) ↔ ¬ (𝐴𝐵) ≺ 𝐵))
5148, 50mpbird 248 . . . . 5 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐵 ≼ (𝐴𝐵))
52 cdadom2 9303 . . . . 5 (𝐵 ≼ (𝐴𝐵) → ((𝐴𝐵) +𝑐 𝐵) ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
5351, 52syl 17 . . . 4 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ((𝐴𝐵) +𝑐 𝐵) ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
54 domtr 8254 . . . 4 ((𝐴 ≼ ((𝐴𝐵) +𝑐 𝐵) ∧ ((𝐴𝐵) +𝑐 𝐵) ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵))) → 𝐴 ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
5521, 53, 54syl2anc 575 . . 3 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐴 ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
56 domtr 8254 . . . . . 6 ((ω ≼ 𝐴𝐴 ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵))) → ω ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
5729, 55, 56syl2anc 575 . . . . 5 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ω ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
58 cdainf 9308 . . . . 5 (ω ≼ (𝐴𝐵) ↔ ω ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)))
5957, 58sylibr 225 . . . 4 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ω ≼ (𝐴𝐵))
60 domrefg 8236 . . . . 5 ((𝐴𝐵) ∈ dom card → (𝐴𝐵) ≼ (𝐴𝐵))
6116, 60syl 17 . . . 4 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ≼ (𝐴𝐵))
62 infcdaabs 9322 . . . 4 (((𝐴𝐵) ∈ dom card ∧ ω ≼ (𝐴𝐵) ∧ (𝐴𝐵) ≼ (𝐴𝐵)) → ((𝐴𝐵) +𝑐 (𝐴𝐵)) ≈ (𝐴𝐵))
6316, 59, 61, 62syl3anc 1483 . . 3 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → ((𝐴𝐵) +𝑐 (𝐴𝐵)) ≈ (𝐴𝐵))
64 domentr 8260 . . 3 ((𝐴 ≼ ((𝐴𝐵) +𝑐 (𝐴𝐵)) ∧ ((𝐴𝐵) +𝑐 (𝐴𝐵)) ≈ (𝐴𝐵)) → 𝐴 ≼ (𝐴𝐵))
6555, 63, 64syl2anc 575 . 2 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → 𝐴 ≼ (𝐴𝐵))
66 sbth 8328 . 2 (((𝐴𝐵) ≼ 𝐴𝐴 ≼ (𝐴𝐵)) → (𝐴𝐵) ≈ 𝐴)
674, 65, 66syl2anc 575 1 ((𝐴 ∈ dom card ∧ ω ≼ 𝐴𝐵𝐴) → (𝐴𝐵) ≈ 𝐴)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  w3a 1100  wcel 2157  cdif 3777  cun 3778  wss 3780   class class class wbr 4855  dom cdm 5324  (class class class)co 6883  ωcom 7304  cen 8198  cdom 8199  csdm 8200  cardccrd 9053   +𝑐 ccda 9283
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2795  ax-rep 4977  ax-sep 4988  ax-nul 4996  ax-pow 5048  ax-pr 5109  ax-un 7188  ax-inf2 8794
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2062  df-mo 2635  df-eu 2642  df-clab 2804  df-cleq 2810  df-clel 2813  df-nfc 2948  df-ne 2990  df-ral 3112  df-rex 3113  df-reu 3114  df-rmo 3115  df-rab 3116  df-v 3404  df-sbc 3645  df-csb 3740  df-dif 3783  df-un 3785  df-in 3787  df-ss 3794  df-pss 3796  df-nul 4128  df-if 4291  df-pw 4364  df-sn 4382  df-pr 4384  df-tp 4386  df-op 4388  df-uni 4642  df-int 4681  df-iun 4725  df-br 4856  df-opab 4918  df-mpt 4935  df-tr 4958  df-id 5232  df-eprel 5237  df-po 5245  df-so 5246  df-fr 5283  df-se 5284  df-we 5285  df-xp 5330  df-rel 5331  df-cnv 5332  df-co 5333  df-dm 5334  df-rn 5335  df-res 5336  df-ima 5337  df-pred 5906  df-ord 5952  df-on 5953  df-lim 5954  df-suc 5955  df-iota 6073  df-fun 6112  df-fn 6113  df-f 6114  df-f1 6115  df-fo 6116  df-f1o 6117  df-fv 6118  df-isom 6119  df-riota 6844  df-ov 6886  df-oprab 6887  df-mpt2 6888  df-om 7305  df-1st 7407  df-2nd 7408  df-wrecs 7651  df-recs 7713  df-rdg 7751  df-1o 7805  df-2o 7806  df-oadd 7809  df-er 7988  df-en 8202  df-dom 8203  df-sdom 8204  df-fin 8205  df-oi 8663  df-card 9057  df-cda 9284
This theorem is referenced by:  infdif2  9326  alephsuc3  9696  aleph1irr  15214
  Copyright terms: Public domain W3C validator