ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  ctiunct GIF version

Theorem ctiunct 12169
Description: A sequence of enumerations gives an enumeration of the union. We refer to "sequence of enumerations" rather than "countably many countable sets" because the hypothesis provides more than countability for each 𝐵(𝑥): it refers to 𝐵(𝑥) together with the 𝐺(𝑥) which enumerates it. Theorem 8.1.19 of [AczelRathjen], p. 74.

For "countably many countable sets" the key hypothesis would be (𝜑𝑥𝐴) → ∃𝑔𝑔:ω–onto→(𝐵 ⊔ 1o). This is almost omiunct 12173 (which uses countable choice) although that is for a countably infinite collection not any countable collection.

Compare with the case of two sets instead of countably many, as seen at unct 12171, which says that the union of two countable sets is countable .

The proof proceeds by mapping a natural number to a pair of natural numbers (by xpomen 12124) and using the first number to map to an element 𝑥 of 𝐴 and the second number to map to an element of B(x) . In this way we are able to map to every element of 𝑥𝐴𝐵. Although it would be possible to work directly with countability expressed as 𝐹:ω–onto→(𝐴 ⊔ 1o), we instead use functions from subsets of the natural numbers via ctssdccl 7055 and ctssdc 7057.

(Contributed by Jim Kingdon, 31-Oct-2023.)

Hypotheses
Ref Expression
ctiunct.a (𝜑𝐹:ω–onto→(𝐴 ⊔ 1o))
ctiunct.b ((𝜑𝑥𝐴) → 𝐺:ω–onto→(𝐵 ⊔ 1o))
Assertion
Ref Expression
ctiunct (𝜑 → ∃ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
Distinct variable groups:   𝐴,,𝑥   𝐵,   𝑥,𝐹   𝜑,𝑥
Allowed substitution hints:   𝜑()   𝐵(𝑥)   𝐹()   𝐺(𝑥,)

Proof of Theorem ctiunct
Dummy variables 𝑗 𝑘 𝑛 𝑢 𝑧 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 xpomen 12124 . . . . 5 (ω × ω) ≈ ω
21ensymi 6727 . . . 4 ω ≈ (ω × ω)
3 bren 6692 . . . 4 (ω ≈ (ω × ω) ↔ ∃𝑗 𝑗:ω–1-1-onto→(ω × ω))
42, 3mpbi 144 . . 3 𝑗 𝑗:ω–1-1-onto→(ω × ω)
54a1i 9 . 2 (𝜑 → ∃𝑗 𝑗:ω–1-1-onto→(ω × ω))
6 ctiunct.a . . . . . . . 8 (𝜑𝐹:ω–onto→(𝐴 ⊔ 1o))
7 eqid 2157 . . . . . . . 8 {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} = {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}
8 eqid 2157 . . . . . . . 8 (inl ∘ 𝐹) = (inl ∘ 𝐹)
96, 7, 8ctssdccl 7055 . . . . . . 7 (𝜑 → ({𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ⊆ ω ∧ (inl ∘ 𝐹):{𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}–onto𝐴 ∧ ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}))
109simp1d 994 . . . . . 6 (𝜑 → {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ⊆ ω)
1110adantr 274 . . . . 5 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ⊆ ω)
129simp3d 996 . . . . . 6 (𝜑 → ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)})
1312adantr 274 . . . . 5 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)})
149simp2d 995 . . . . . 6 (𝜑 → (inl ∘ 𝐹):{𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}–onto𝐴)
1514adantr 274 . . . . 5 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → (inl ∘ 𝐹):{𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}–onto𝐴)
16 ctiunct.b . . . . . . . 8 ((𝜑𝑥𝐴) → 𝐺:ω–onto→(𝐵 ⊔ 1o))
17 eqid 2157 . . . . . . . 8 {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)} = {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}
18 eqid 2157 . . . . . . . 8 (inl ∘ 𝐺) = (inl ∘ 𝐺)
1916, 17, 18ctssdccl 7055 . . . . . . 7 ((𝜑𝑥𝐴) → ({𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)} ⊆ ω ∧ (inl ∘ 𝐺):{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}–onto𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}))
2019simp1d 994 . . . . . 6 ((𝜑𝑥𝐴) → {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)} ⊆ ω)
2120adantlr 469 . . . . 5 (((𝜑𝑗:ω–1-1-onto→(ω × ω)) ∧ 𝑥𝐴) → {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)} ⊆ ω)
2219simp3d 996 . . . . . 6 ((𝜑𝑥𝐴) → ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})
2322adantlr 469 . . . . 5 (((𝜑𝑗:ω–1-1-onto→(ω × ω)) ∧ 𝑥𝐴) → ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})
2419simp2d 995 . . . . . 6 ((𝜑𝑥𝐴) → (inl ∘ 𝐺):{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}–onto𝐵)
2524adantlr 469 . . . . 5 (((𝜑𝑗:ω–1-1-onto→(ω × ω)) ∧ 𝑥𝐴) → (inl ∘ 𝐺):{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}–onto𝐵)
26 simpr 109 . . . . 5 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → 𝑗:ω–1-1-onto→(ω × ω))
27 eqid 2157 . . . . 5 {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}
2811, 13, 15, 21, 23, 25, 26, 27ctiunctlemuom 12165 . . . 4 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ⊆ ω)
29 eqid 2157 . . . . . 6 (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))) = (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛))))
30 nfv 1508 . . . . . . . . 9 𝑥(1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)}
31 nfcsb1v 3064 . . . . . . . . . 10 𝑥((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}
3231nfel2 2312 . . . . . . . . 9 𝑥(2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)}
3330, 32nfan 1545 . . . . . . . 8 𝑥((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})
34 nfcv 2299 . . . . . . . 8 𝑥ω
3533, 34nfrabxy 2637 . . . . . . 7 𝑥{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}
36 nfcsb1v 3064 . . . . . . . 8 𝑥((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)
37 nfcv 2299 . . . . . . . 8 𝑥(2nd ‘(𝑗𝑛))
3836, 37nffv 5478 . . . . . . 7 𝑥(((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))
3935, 38nfmpt 4056 . . . . . 6 𝑥(𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛))))
4011, 13, 15, 21, 23, 25, 26, 27, 29, 39, 35ctiunctlemfo 12168 . . . . 5 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))):{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵)
41 omex 4552 . . . . . . . 8 ω ∈ V
4241rabex 4108 . . . . . . 7 {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ∈ V
4342mptex 5693 . . . . . 6 (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))) ∈ V
44 foeq1 5388 . . . . . 6 (𝑘 = (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))) → (𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵 ↔ (𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))):{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵))
4543, 44spcev 2807 . . . . 5 ((𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ↦ (((inl ∘ 𝐹)‘(1st ‘(𝑗𝑛))) / 𝑥(inl ∘ 𝐺)‘(2nd ‘(𝑗𝑛)))):{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵 → ∃𝑘 𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵)
4640, 45syl 14 . . . 4 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → ∃𝑘 𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵)
4711, 13, 15, 21, 23, 25, 26, 27ctiunctlemudc 12166 . . . 4 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})})
48 sseq1 3151 . . . . . 6 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (𝑢 ⊆ ω ↔ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ⊆ ω))
49 foeq2 5389 . . . . . . 7 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (𝑘:𝑢onto 𝑥𝐴 𝐵𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵))
5049exbidv 1805 . . . . . 6 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ↔ ∃𝑘 𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵))
51 eleq2 2221 . . . . . . . 8 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (𝑛𝑢𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}))
5251dcbid 824 . . . . . . 7 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (DECID 𝑛𝑢DECID 𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}))
5352ralbidv 2457 . . . . . 6 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → (∀𝑛 ∈ ω DECID 𝑛𝑢 ↔ ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}))
5448, 50, 533anbi123d 1294 . . . . 5 (𝑢 = {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} → ((𝑢 ⊆ ω ∧ ∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛𝑢) ↔ ({𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ⊆ ω ∧ ∃𝑘 𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})})))
5542, 54spcev 2807 . . . 4 (({𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})} ⊆ ω ∧ ∃𝑘 𝑘:{𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}–onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛 ∈ {𝑧 ∈ ω ∣ ((1st ‘(𝑗𝑧)) ∈ {𝑤 ∈ ω ∣ (𝐹𝑤) ∈ (inl “ 𝐴)} ∧ (2nd ‘(𝑗𝑧)) ∈ ((inl ∘ 𝐹)‘(1st ‘(𝑗𝑧))) / 𝑥{𝑤 ∈ ω ∣ (𝐺𝑤) ∈ (inl “ 𝐵)})}) → ∃𝑢(𝑢 ⊆ ω ∧ ∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛𝑢))
5628, 46, 47, 55syl3anc 1220 . . 3 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → ∃𝑢(𝑢 ⊆ ω ∧ ∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛𝑢))
57 ctssdc 7057 . . . 4 (∃𝑢(𝑢 ⊆ ω ∧ ∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛𝑢) ↔ ∃𝑘 𝑘:ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
58 foeq1 5388 . . . . 5 (𝑘 = → (𝑘:ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o) ↔ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o)))
5958cbvexv 1898 . . . 4 (∃𝑘 𝑘:ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o) ↔ ∃ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
6057, 59bitri 183 . . 3 (∃𝑢(𝑢 ⊆ ω ∧ ∃𝑘 𝑘:𝑢onto 𝑥𝐴 𝐵 ∧ ∀𝑛 ∈ ω DECID 𝑛𝑢) ↔ ∃ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
6156, 60sylib 121 . 2 ((𝜑𝑗:ω–1-1-onto→(ω × ω)) → ∃ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
625, 61exlimddv 1878 1 (𝜑 → ∃ :ω–onto→( 𝑥𝐴 𝐵 ⊔ 1o))
Colors of variables: wff set class
Syntax hints:  wi 4  wa 103  DECID wdc 820  w3a 963   = wceq 1335  wex 1472  wcel 2128  wral 2435  {crab 2439  csb 3031  wss 3102   ciun 3849   class class class wbr 3965  cmpt 4025  ωcom 4549   × cxp 4584  ccnv 4585  cima 4589  ccom 4590  ontowfo 5168  1-1-ontowf1o 5169  cfv 5170  1st c1st 6086  2nd c2nd 6087  1oc1o 6356  cen 6683  cdju 6981  inlcinl 6989
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1427  ax-7 1428  ax-gen 1429  ax-ie1 1473  ax-ie2 1474  ax-8 1484  ax-10 1485  ax-11 1486  ax-i12 1487  ax-bndl 1489  ax-4 1490  ax-17 1506  ax-i9 1510  ax-ial 1514  ax-i5r 1515  ax-13 2130  ax-14 2131  ax-ext 2139  ax-coll 4079  ax-sep 4082  ax-nul 4090  ax-pow 4135  ax-pr 4169  ax-un 4393  ax-setind 4496  ax-iinf 4547  ax-cnex 7823  ax-resscn 7824  ax-1cn 7825  ax-1re 7826  ax-icn 7827  ax-addcl 7828  ax-addrcl 7829  ax-mulcl 7830  ax-mulrcl 7831  ax-addcom 7832  ax-mulcom 7833  ax-addass 7834  ax-mulass 7835  ax-distr 7836  ax-i2m1 7837  ax-0lt1 7838  ax-1rid 7839  ax-0id 7840  ax-rnegex 7841  ax-precex 7842  ax-cnre 7843  ax-pre-ltirr 7844  ax-pre-ltwlin 7845  ax-pre-lttrn 7846  ax-pre-apti 7847  ax-pre-ltadd 7848  ax-pre-mulgt0 7849  ax-pre-mulext 7850  ax-arch 7851
This theorem depends on definitions:  df-bi 116  df-dc 821  df-3or 964  df-3an 965  df-tru 1338  df-fal 1341  df-xor 1358  df-nf 1441  df-sb 1743  df-eu 2009  df-mo 2010  df-clab 2144  df-cleq 2150  df-clel 2153  df-nfc 2288  df-ne 2328  df-nel 2423  df-ral 2440  df-rex 2441  df-reu 2442  df-rmo 2443  df-rab 2444  df-v 2714  df-sbc 2938  df-csb 3032  df-dif 3104  df-un 3106  df-in 3108  df-ss 3115  df-nul 3395  df-if 3506  df-pw 3545  df-sn 3566  df-pr 3567  df-op 3569  df-uni 3773  df-int 3808  df-iun 3851  df-br 3966  df-opab 4026  df-mpt 4027  df-tr 4063  df-id 4253  df-po 4256  df-iso 4257  df-iord 4326  df-on 4328  df-ilim 4329  df-suc 4331  df-iom 4550  df-xp 4592  df-rel 4593  df-cnv 4594  df-co 4595  df-dm 4596  df-rn 4597  df-res 4598  df-ima 4599  df-iota 5135  df-fun 5172  df-fn 5173  df-f 5174  df-f1 5175  df-fo 5176  df-f1o 5177  df-fv 5178  df-riota 5780  df-ov 5827  df-oprab 5828  df-mpo 5829  df-1st 6088  df-2nd 6089  df-recs 6252  df-frec 6338  df-1o 6363  df-er 6480  df-en 6686  df-dju 6982  df-inl 6991  df-inr 6992  df-case 7028  df-pnf 7914  df-mnf 7915  df-xr 7916  df-ltxr 7917  df-le 7918  df-sub 8048  df-neg 8049  df-reap 8450  df-ap 8457  df-div 8546  df-inn 8834  df-2 8892  df-n0 9091  df-z 9168  df-uz 9440  df-q 9529  df-rp 9561  df-fz 9913  df-fl 10169  df-mod 10222  df-seqfrec 10345  df-exp 10419  df-dvds 11684
This theorem is referenced by:  ctiunctal  12170  unct  12171
  Copyright terms: Public domain W3C validator