Users' Mathboxes Mathbox for Glauco Siliprandi < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  disjf1o Structured version   Visualization version   GIF version

Theorem disjf1o 39378
Description: A bijection built from disjoint sets. (Contributed by Glauco Siliprandi, 17-Aug-2020.)
Hypotheses
Ref Expression
disjf1o.xph 𝑥𝜑
disjf1o.f 𝐹 = (𝑥𝐴𝐵)
disjf1o.b ((𝜑𝑥𝐴) → 𝐵𝑉)
disjf1o.dj (𝜑Disj 𝑥𝐴 𝐵)
disjf1o.d 𝐶 = {𝑥𝐴𝐵 ≠ ∅}
disjf1o.e 𝐷 = (ran 𝐹 ∖ {∅})
Assertion
Ref Expression
disjf1o (𝜑 → (𝐹𝐶):𝐶1-1-onto𝐷)
Distinct variable groups:   𝑥,𝐴   𝑥,𝐶   𝑥,𝐷   𝑥,𝑉
Allowed substitution hints:   𝜑(𝑥)   𝐵(𝑥)   𝐹(𝑥)

Proof of Theorem disjf1o
Dummy variable 𝑦 is distinct from all other variables.
StepHypRef Expression
1 disjf1o.xph . . . 4 𝑥𝜑
2 eqid 2622 . . . 4 (𝑥𝐶𝐵) = (𝑥𝐶𝐵)
3 simpl 473 . . . . 5 ((𝜑𝑥𝐶) → 𝜑)
4 disjf1o.d . . . . . . . 8 𝐶 = {𝑥𝐴𝐵 ≠ ∅}
5 ssrab2 3687 . . . . . . . 8 {𝑥𝐴𝐵 ≠ ∅} ⊆ 𝐴
64, 5eqsstri 3635 . . . . . . 7 𝐶𝐴
7 id 22 . . . . . . 7 (𝑥𝐶𝑥𝐶)
86, 7sseldi 3601 . . . . . 6 (𝑥𝐶𝑥𝐴)
98adantl 482 . . . . 5 ((𝜑𝑥𝐶) → 𝑥𝐴)
10 disjf1o.b . . . . 5 ((𝜑𝑥𝐴) → 𝐵𝑉)
113, 9, 10syl2anc 693 . . . 4 ((𝜑𝑥𝐶) → 𝐵𝑉)
127, 4syl6eleq 2711 . . . . . . 7 (𝑥𝐶𝑥 ∈ {𝑥𝐴𝐵 ≠ ∅})
13 rabid 3116 . . . . . . . 8 (𝑥 ∈ {𝑥𝐴𝐵 ≠ ∅} ↔ (𝑥𝐴𝐵 ≠ ∅))
1413a1i 11 . . . . . . 7 (𝑥𝐶 → (𝑥 ∈ {𝑥𝐴𝐵 ≠ ∅} ↔ (𝑥𝐴𝐵 ≠ ∅)))
1512, 14mpbid 222 . . . . . 6 (𝑥𝐶 → (𝑥𝐴𝐵 ≠ ∅))
1615simprd 479 . . . . 5 (𝑥𝐶𝐵 ≠ ∅)
1716adantl 482 . . . 4 ((𝜑𝑥𝐶) → 𝐵 ≠ ∅)
186a1i 11 . . . . 5 (𝜑𝐶𝐴)
19 disjf1o.dj . . . . 5 (𝜑Disj 𝑥𝐴 𝐵)
20 disjss1 4626 . . . . 5 (𝐶𝐴 → (Disj 𝑥𝐴 𝐵Disj 𝑥𝐶 𝐵))
2118, 19, 20sylc 65 . . . 4 (𝜑Disj 𝑥𝐶 𝐵)
221, 2, 11, 17, 21disjf1 39369 . . 3 (𝜑 → (𝑥𝐶𝐵):𝐶1-1𝑉)
23 f1f1orn 6148 . . 3 ((𝑥𝐶𝐵):𝐶1-1𝑉 → (𝑥𝐶𝐵):𝐶1-1-onto→ran (𝑥𝐶𝐵))
2422, 23syl 17 . 2 (𝜑 → (𝑥𝐶𝐵):𝐶1-1-onto→ran (𝑥𝐶𝐵))
25 disjf1o.f . . . . . 6 𝐹 = (𝑥𝐴𝐵)
2625a1i 11 . . . . 5 (𝜑𝐹 = (𝑥𝐴𝐵))
2726reseq1d 5395 . . . 4 (𝜑 → (𝐹𝐶) = ((𝑥𝐴𝐵) ↾ 𝐶))
2818resmptd 5452 . . . 4 (𝜑 → ((𝑥𝐴𝐵) ↾ 𝐶) = (𝑥𝐶𝐵))
2927, 28eqtrd 2656 . . 3 (𝜑 → (𝐹𝐶) = (𝑥𝐶𝐵))
30 eqidd 2623 . . 3 (𝜑𝐶 = 𝐶)
31 simpl 473 . . . . . . 7 ((𝜑𝑦𝐷) → 𝜑)
32 id 22 . . . . . . . . . 10 (𝑦𝐷𝑦𝐷)
33 disjf1o.e . . . . . . . . . 10 𝐷 = (ran 𝐹 ∖ {∅})
3432, 33syl6eleq 2711 . . . . . . . . 9 (𝑦𝐷𝑦 ∈ (ran 𝐹 ∖ {∅}))
35 eldifsni 4320 . . . . . . . . 9 (𝑦 ∈ (ran 𝐹 ∖ {∅}) → 𝑦 ≠ ∅)
3634, 35syl 17 . . . . . . . 8 (𝑦𝐷𝑦 ≠ ∅)
3736adantl 482 . . . . . . 7 ((𝜑𝑦𝐷) → 𝑦 ≠ ∅)
38 eldifi 3732 . . . . . . . . . 10 (𝑦 ∈ (ran 𝐹 ∖ {∅}) → 𝑦 ∈ ran 𝐹)
3934, 38syl 17 . . . . . . . . 9 (𝑦𝐷𝑦 ∈ ran 𝐹)
4025elrnmpt 5372 . . . . . . . . . 10 (𝑦 ∈ ran 𝐹 → (𝑦 ∈ ran 𝐹 ↔ ∃𝑥𝐴 𝑦 = 𝐵))
4139, 40syl 17 . . . . . . . . 9 (𝑦𝐷 → (𝑦 ∈ ran 𝐹 ↔ ∃𝑥𝐴 𝑦 = 𝐵))
4239, 41mpbid 222 . . . . . . . 8 (𝑦𝐷 → ∃𝑥𝐴 𝑦 = 𝐵)
4342adantl 482 . . . . . . 7 ((𝜑𝑦𝐷) → ∃𝑥𝐴 𝑦 = 𝐵)
44 nfv 1843 . . . . . . . . . 10 𝑥 𝑦 ≠ ∅
451, 44nfan 1828 . . . . . . . . 9 𝑥(𝜑𝑦 ≠ ∅)
46 nfcv 2764 . . . . . . . . . 10 𝑥𝑦
47 nfmpt1 4747 . . . . . . . . . . 11 𝑥(𝑥𝐶𝐵)
4847nfrn 5368 . . . . . . . . . 10 𝑥ran (𝑥𝐶𝐵)
4946, 48nfel 2777 . . . . . . . . 9 𝑥 𝑦 ∈ ran (𝑥𝐶𝐵)
50 simp3 1063 . . . . . . . . . . . 12 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑦 = 𝐵)
51 simp2 1062 . . . . . . . . . . . . . . . 16 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑥𝐴)
52 id 22 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵𝑦 = 𝐵)
5352eqcomd 2628 . . . . . . . . . . . . . . . . . . 19 (𝑦 = 𝐵𝐵 = 𝑦)
5453adantl 482 . . . . . . . . . . . . . . . . . 18 ((𝑦 ≠ ∅ ∧ 𝑦 = 𝐵) → 𝐵 = 𝑦)
55 simpl 473 . . . . . . . . . . . . . . . . . 18 ((𝑦 ≠ ∅ ∧ 𝑦 = 𝐵) → 𝑦 ≠ ∅)
5654, 55eqnetrd 2861 . . . . . . . . . . . . . . . . 17 ((𝑦 ≠ ∅ ∧ 𝑦 = 𝐵) → 𝐵 ≠ ∅)
57563adant2 1080 . . . . . . . . . . . . . . . 16 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝐵 ≠ ∅)
5851, 57jca 554 . . . . . . . . . . . . . . 15 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → (𝑥𝐴𝐵 ≠ ∅))
5958, 13sylibr 224 . . . . . . . . . . . . . 14 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑥 ∈ {𝑥𝐴𝐵 ≠ ∅})
604eqcomi 2631 . . . . . . . . . . . . . . 15 {𝑥𝐴𝐵 ≠ ∅} = 𝐶
6160a1i 11 . . . . . . . . . . . . . 14 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → {𝑥𝐴𝐵 ≠ ∅} = 𝐶)
6259, 61eleqtrd 2703 . . . . . . . . . . . . 13 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑥𝐶)
63 eqvisset 3211 . . . . . . . . . . . . . 14 (𝑦 = 𝐵𝐵 ∈ V)
64633ad2ant3 1084 . . . . . . . . . . . . 13 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝐵 ∈ V)
652elrnmpt1 5374 . . . . . . . . . . . . 13 ((𝑥𝐶𝐵 ∈ V) → 𝐵 ∈ ran (𝑥𝐶𝐵))
6662, 64, 65syl2anc 693 . . . . . . . . . . . 12 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝐵 ∈ ran (𝑥𝐶𝐵))
6750, 66eqeltrd 2701 . . . . . . . . . . 11 ((𝑦 ≠ ∅ ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑦 ∈ ran (𝑥𝐶𝐵))
68673adant1l 1318 . . . . . . . . . 10 (((𝜑𝑦 ≠ ∅) ∧ 𝑥𝐴𝑦 = 𝐵) → 𝑦 ∈ ran (𝑥𝐶𝐵))
69683exp 1264 . . . . . . . . 9 ((𝜑𝑦 ≠ ∅) → (𝑥𝐴 → (𝑦 = 𝐵𝑦 ∈ ran (𝑥𝐶𝐵))))
7045, 49, 69rexlimd 3026 . . . . . . . 8 ((𝜑𝑦 ≠ ∅) → (∃𝑥𝐴 𝑦 = 𝐵𝑦 ∈ ran (𝑥𝐶𝐵)))
7170imp 445 . . . . . . 7 (((𝜑𝑦 ≠ ∅) ∧ ∃𝑥𝐴 𝑦 = 𝐵) → 𝑦 ∈ ran (𝑥𝐶𝐵))
7231, 37, 43, 71syl21anc 1325 . . . . . 6 ((𝜑𝑦𝐷) → 𝑦 ∈ ran (𝑥𝐶𝐵))
7372ralrimiva 2966 . . . . 5 (𝜑 → ∀𝑦𝐷 𝑦 ∈ ran (𝑥𝐶𝐵))
74 dfss3 3592 . . . . 5 (𝐷 ⊆ ran (𝑥𝐶𝐵) ↔ ∀𝑦𝐷 𝑦 ∈ ran (𝑥𝐶𝐵))
7573, 74sylibr 224 . . . 4 (𝜑𝐷 ⊆ ran (𝑥𝐶𝐵))
76 simpl 473 . . . . . . 7 ((𝜑𝑦 ∈ ran (𝑥𝐶𝐵)) → 𝜑)
77 vex 3203 . . . . . . . . . 10 𝑦 ∈ V
782elrnmpt 5372 . . . . . . . . . 10 (𝑦 ∈ V → (𝑦 ∈ ran (𝑥𝐶𝐵) ↔ ∃𝑥𝐶 𝑦 = 𝐵))
7977, 78ax-mp 5 . . . . . . . . 9 (𝑦 ∈ ran (𝑥𝐶𝐵) ↔ ∃𝑥𝐶 𝑦 = 𝐵)
8079biimpi 206 . . . . . . . 8 (𝑦 ∈ ran (𝑥𝐶𝐵) → ∃𝑥𝐶 𝑦 = 𝐵)
8180adantl 482 . . . . . . 7 ((𝜑𝑦 ∈ ran (𝑥𝐶𝐵)) → ∃𝑥𝐶 𝑦 = 𝐵)
82 nfv 1843 . . . . . . . . 9 𝑥 𝑦𝐷
83 simpr 477 . . . . . . . . . . . . . 14 ((𝑥𝐶𝑦 = 𝐵) → 𝑦 = 𝐵)
848adantr 481 . . . . . . . . . . . . . . 15 ((𝑥𝐶𝑦 = 𝐵) → 𝑥𝐴)
8583, 63syl 17 . . . . . . . . . . . . . . 15 ((𝑥𝐶𝑦 = 𝐵) → 𝐵 ∈ V)
8625elrnmpt1 5374 . . . . . . . . . . . . . . 15 ((𝑥𝐴𝐵 ∈ V) → 𝐵 ∈ ran 𝐹)
8784, 85, 86syl2anc 693 . . . . . . . . . . . . . 14 ((𝑥𝐶𝑦 = 𝐵) → 𝐵 ∈ ran 𝐹)
8883, 87eqeltrd 2701 . . . . . . . . . . . . 13 ((𝑥𝐶𝑦 = 𝐵) → 𝑦 ∈ ran 𝐹)
89883adant1 1079 . . . . . . . . . . . 12 ((𝜑𝑥𝐶𝑦 = 𝐵) → 𝑦 ∈ ran 𝐹)
9016adantr 481 . . . . . . . . . . . . . . 15 ((𝑥𝐶𝑦 = 𝐵) → 𝐵 ≠ ∅)
9183, 90eqnetrd 2861 . . . . . . . . . . . . . 14 ((𝑥𝐶𝑦 = 𝐵) → 𝑦 ≠ ∅)
92 nelsn 4212 . . . . . . . . . . . . . 14 (𝑦 ≠ ∅ → ¬ 𝑦 ∈ {∅})
9391, 92syl 17 . . . . . . . . . . . . 13 ((𝑥𝐶𝑦 = 𝐵) → ¬ 𝑦 ∈ {∅})
94933adant1 1079 . . . . . . . . . . . 12 ((𝜑𝑥𝐶𝑦 = 𝐵) → ¬ 𝑦 ∈ {∅})
9589, 94eldifd 3585 . . . . . . . . . . 11 ((𝜑𝑥𝐶𝑦 = 𝐵) → 𝑦 ∈ (ran 𝐹 ∖ {∅}))
9695, 33syl6eleqr 2712 . . . . . . . . . 10 ((𝜑𝑥𝐶𝑦 = 𝐵) → 𝑦𝐷)
97963exp 1264 . . . . . . . . 9 (𝜑 → (𝑥𝐶 → (𝑦 = 𝐵𝑦𝐷)))
981, 82, 97rexlimd 3026 . . . . . . . 8 (𝜑 → (∃𝑥𝐶 𝑦 = 𝐵𝑦𝐷))
9998imp 445 . . . . . . 7 ((𝜑 ∧ ∃𝑥𝐶 𝑦 = 𝐵) → 𝑦𝐷)
10076, 81, 99syl2anc 693 . . . . . 6 ((𝜑𝑦 ∈ ran (𝑥𝐶𝐵)) → 𝑦𝐷)
101100ralrimiva 2966 . . . . 5 (𝜑 → ∀𝑦 ∈ ran (𝑥𝐶𝐵)𝑦𝐷)
102 dfss3 3592 . . . . 5 (ran (𝑥𝐶𝐵) ⊆ 𝐷 ↔ ∀𝑦 ∈ ran (𝑥𝐶𝐵)𝑦𝐷)
103101, 102sylibr 224 . . . 4 (𝜑 → ran (𝑥𝐶𝐵) ⊆ 𝐷)
10475, 103eqssd 3620 . . 3 (𝜑𝐷 = ran (𝑥𝐶𝐵))
10529, 30, 104f1oeq123d 6133 . 2 (𝜑 → ((𝐹𝐶):𝐶1-1-onto𝐷 ↔ (𝑥𝐶𝐵):𝐶1-1-onto→ran (𝑥𝐶𝐵)))
10624, 105mpbird 247 1 (𝜑 → (𝐹𝐶):𝐶1-1-onto𝐷)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wa 384  w3a 1037   = wceq 1483  wnf 1708  wcel 1990  wne 2794  wral 2912  wrex 2913  {crab 2916  Vcvv 3200  cdif 3571  wss 3574  c0 3915  {csn 4177  Disj wdisj 4620  cmpt 4729  ran crn 5115  cres 5116  1-1wf1 5885  1-1-ontowf1o 5887
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1722  ax-4 1737  ax-5 1839  ax-6 1888  ax-7 1935  ax-8 1992  ax-9 1999  ax-10 2019  ax-11 2034  ax-12 2047  ax-13 2246  ax-ext 2602  ax-sep 4781  ax-nul 4789  ax-pow 4843  ax-pr 4906
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3an 1039  df-tru 1486  df-ex 1705  df-nf 1710  df-sb 1881  df-eu 2474  df-mo 2475  df-clab 2609  df-cleq 2615  df-clel 2618  df-nfc 2753  df-ne 2795  df-ral 2917  df-rex 2918  df-reu 2919  df-rmo 2920  df-rab 2921  df-v 3202  df-sbc 3436  df-csb 3534  df-dif 3577  df-un 3579  df-in 3581  df-ss 3588  df-nul 3916  df-if 4087  df-sn 4178  df-pr 4180  df-op 4184  df-uni 4437  df-disj 4621  df-br 4654  df-opab 4713  df-mpt 4730  df-id 5024  df-xp 5120  df-rel 5121  df-cnv 5122  df-co 5123  df-dm 5124  df-rn 5125  df-res 5126  df-ima 5127  df-iota 5851  df-fun 5890  df-fn 5891  df-f 5892  df-f1 5893  df-fo 5894  df-f1o 5895  df-fv 5896
This theorem is referenced by:  sge0fodjrnlem  40633
  Copyright terms: Public domain W3C validator