Users' Mathboxes Mathbox for Thierry Arnoux < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  gsumwrd2dccatlem Structured version   Visualization version   GIF version

Theorem gsumwrd2dccatlem 33738
Description: Lemma for gsumwrd2dccat 33739. Expose a bijection 𝐹 between (ordered) pairs of words and words with a length of a subword. (Contributed by Thierry Arnoux, 5-Oct-2025.)
Hypotheses
Ref Expression
gsumwrd2dccatlem.u 𝑈 = ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤)))
gsumwrd2dccatlem.f 𝐹 = (𝑎 ∈ (Word 𝐴 × Word 𝐴) ↦ ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩)
gsumwrd2dccatlem.g 𝐺 = (𝑏 ∈ 𝑈 ↦ ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩)
gsumwrd2dccatlem.a (𝜑 → 𝐴 ∈ 𝑉)
Assertion
Ref Expression
gsumwrd2dccatlem (𝜑 → (𝐹:(Word 𝐴 × Word 𝐴)⟶1-1onto𝑈 ∧ ◡𝐹 = 𝐺))
Distinct variable groups:   𝐴,𝑎,𝑏,𝑤   𝐹,𝑏   𝑈,𝑎,𝑏   𝜑,𝑎,𝑏,𝑤
Allowed substitution hints:   𝑈(𝑤)   𝐹(𝑤, 𝑎)   𝐺(𝑤, 𝑎, 𝑏)   𝑉(𝑤, 𝑎, 𝑏)

Proof of Theorem gsumwrd2dccatlem
Dummy variables 𝑛 𝑢 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 gsumwrd2dccatlem.f . . . 4 𝐹 = (𝑎 ∈ (Word 𝐴 × Word 𝐴) ↦ ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩)
2 sneq 4593 . . . . . . . . 9 (𝑤 = ((1st ‘𝑎) ++ (2nd ‘𝑎)) → {𝑤} = {((1st ‘𝑎) ++ (2nd ‘𝑎))})
3 fveq2 6915 . . . . . . . . . 10 (𝑤 = ((1st ‘𝑎) ++ (2nd ‘𝑎)) → (♯‘𝑤) = (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))))
43oveq2d 7466 . . . . . . . . 9 (𝑤 = ((1st ‘𝑎) ++ (2nd ‘𝑎)) → (0...(♯‘𝑤)) = (0...(♯‘((1st ‘𝑎) ++ (2nd ‘𝑎)))))
52, 4xpeq12d 5688 . . . . . . . 8 (𝑤 = ((1st ‘𝑎) ++ (2nd ‘𝑎)) → ({𝑤} × (0...(♯‘𝑤))) = ({((1st ‘𝑎) ++ (2nd ‘𝑎))} × (0...(♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))))))
65eleq2d 2853 . . . . . . 7 (𝑤 = ((1st ‘𝑎) ++ (2nd ‘𝑎)) → (⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ ({𝑤} × (0...(♯‘𝑤))) ↔ ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ ({((1st ‘𝑎) ++ (2nd ‘𝑎))} × (0...(♯‘((1st ‘𝑎) ++ (2nd ‘𝑎)))))))
7 xp1st 8066 . . . . . . . . 9 (𝑎 ∈ (Word 𝐴 × Word 𝐴) → (1st ‘𝑎) ∈ Word 𝐴)
87adantl 487 . . . . . . . 8 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (1st ‘𝑎) ∈ Word 𝐴)
9 xp2nd 8067 . . . . . . . . 9 (𝑎 ∈ (Word 𝐴 × Word 𝐴) → (2nd ‘𝑎) ∈ Word 𝐴)
109adantl 487 . . . . . . . 8 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (2nd ‘𝑎) ∈ Word 𝐴)
11 ccatcl 14759 . . . . . . . 8 (((1st ‘𝑎) ∈ Word 𝐴 ∧ (2nd ‘𝑎) ∈ Word 𝐴) → ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ Word 𝐴)
128, 10, 11syl2anc 596 . . . . . . 7 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ Word 𝐴)
13 ovex 7483 . . . . . . . . . 10 ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ V
1413snid 4623 . . . . . . . . 9 ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ {((1st ‘𝑎) ++ (2nd ‘𝑎))}
1514a1i 11 . . . . . . . 8 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ {((1st ‘𝑎) ++ (2nd ‘𝑎))})
16 0zd 12744 . . . . . . . . 9 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → 0 ∈ ℤ)
17 lencl 14718 . . . . . . . . . . 11 (((1st ‘𝑎) ++ (2nd ‘𝑎)) ∈ Word 𝐴 → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) ∈ ℕ0)
1812, 17syl 18 . . . . . . . . . 10 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) ∈ ℕ0)
1918nn0zd 12757 . . . . . . . . 9 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) ∈ ℤ)
20 lencl 14718 . . . . . . . . . . 11 ((1st ‘𝑎) ∈ Word 𝐴 → (♯‘(1st ‘𝑎)) ∈ ℕ0)
218, 20syl 18 . . . . . . . . . 10 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ∈ ℕ0)
2221nn0zd 12757 . . . . . . . . 9 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ∈ ℤ)
2321nn0ge0d 12709 . . . . . . . . 9 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → 0 ≤ (♯‘(1st ‘𝑎)))
24 lencl 14718 . . . . . . . . . . . . 13 ((2nd ‘𝑎) ∈ Word 𝐴 → (♯‘(2nd ‘𝑎)) ∈ ℕ0)
2510, 24syl 18 . . . . . . . . . . . 12 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(2nd ‘𝑎)) ∈ ℕ0)
2625nn0ge0d 12709 . . . . . . . . . . 11 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → 0 ≤ (♯‘(2nd ‘𝑎)))
2721nn0red 12707 . . . . . . . . . . . 12 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ∈ ℝ)
2825nn0red 12707 . . . . . . . . . . . 12 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(2nd ‘𝑎)) ∈ ℝ)
2927, 28addge01d 11943 . . . . . . . . . . 11 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (0 ≤ (♯‘(2nd ‘𝑎)) ↔ (♯‘(1st ‘𝑎)) ≤ ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎)))))
3026, 29mpbid 235 . . . . . . . . . 10 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ≤ ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎))))
31 ccatlen 14760 . . . . . . . . . . 11 (((1st ‘𝑎) ∈ Word 𝐴 ∧ (2nd ‘𝑎) ∈ Word 𝐴) → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) = ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎))))
328, 10, 31syl2anc 596 . . . . . . . . . 10 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) = ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎))))
3330, 32breqtrrd 5138 . . . . . . . . 9 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ≤ (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))))
3416, 19, 22, 23, 33elfzd 13686 . . . . . . . 8 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (♯‘(1st ‘𝑎)) ∈ (0...(♯‘((1st ‘𝑎) ++ (2nd ‘𝑎)))))
3515, 34opelxpd 5696 . . . . . . 7 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ ({((1st ‘𝑎) ++ (2nd ‘𝑎))} × (0...(♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))))))
366, 12, 35rspcedvdw 3582 . . . . . 6 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ∃𝑤 ∈ Word 𝐴⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ ({𝑤} × (0...(♯‘𝑤))))
3736eliund 4962 . . . . 5 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))))
38 gsumwrd2dccatlem.u . . . . 5 𝑈 = ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤)))
3937, 38eleqtrrdi 2878 . . . 4 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ∈ 𝑈)
40 simpr 490 . . . . . . . . . 10 (((𝜑 ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢)))) → 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢))))
41 xp1st 8066 . . . . . . . . . 10 (𝑏 ∈ ({𝑢} × (0...(♯‘𝑢))) → (1st ‘𝑏) ∈ {𝑢})
42 elsni 4600 . . . . . . . . . 10 ((1st ‘𝑏) ∈ {𝑢} → (1st ‘𝑏) = 𝑢)
4340, 41, 423syl 19 . . . . . . . . 9 (((𝜑 ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢)))) → (1st ‘𝑏) = 𝑢)
44 simplr 781 . . . . . . . . 9 (((𝜑 ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢)))) → 𝑢 ∈ Word 𝐴)
4543, 44eqeltrd 2867 . . . . . . . 8 (((𝜑 ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢)))) → (1st ‘𝑏) ∈ Word 𝐴)
4645adantllr 732 . . . . . . 7 ((((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑏 ∈ ({𝑢} × (0...(♯‘𝑢)))) → (1st ‘𝑏) ∈ Word 𝐴)
4738eleq2i 2859 . . . . . . . . . 10 (𝑏 ∈ 𝑈 ↔ 𝑏 ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))))
4847bilani 510 . . . . . . . . 9 ((𝜑 ∧ 𝑏 ∈ 𝑈) → 𝑏 ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))))
49 eliun 4959 . . . . . . . . 9 (𝑏 ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))) ↔ ∃𝑤 ∈ Word 𝐴𝑏 ∈ ({𝑤} × (0...(♯‘𝑤))))
5048, 49sylib 221 . . . . . . . 8 ((𝜑 ∧ 𝑏 ∈ 𝑈) → ∃𝑤 ∈ Word 𝐴𝑏 ∈ ({𝑤} × (0...(♯‘𝑤))))
51 sneq 4593 . . . . . . . . . . 11 (𝑢 = 𝑤 → {𝑢} = {𝑤})
52 fveq2 6915 . . . . . . . . . . . 12 (𝑢 = 𝑤 → (♯‘𝑢) = (♯‘𝑤))
5352oveq2d 7466 . . . . . . . . . . 11 (𝑢 = 𝑤 → (0...(♯‘𝑢)) = (0...(♯‘𝑤)))
5451, 53xpeq12d 5688 . . . . . . . . . 10 (𝑢 = 𝑤 → ({𝑢} × (0...(♯‘𝑢))) = ({𝑤} × (0...(♯‘𝑤))))
5554eleq2d 2853 . . . . . . . . 9 (𝑢 = 𝑤 → (𝑏 ∈ ({𝑢} × (0...(♯‘𝑢))) ↔ 𝑏 ∈ ({𝑤} × (0...(♯‘𝑤)))))
5655cbvrexvw 3245 . . . . . . . 8 (∃𝑢 ∈ Word 𝐴𝑏 ∈ ({𝑢} × (0...(♯‘𝑢))) ↔ ∃𝑤 ∈ Word 𝐴𝑏 ∈ ({𝑤} × (0...(♯‘𝑤))))
5750, 56sylibr 237 . . . . . . 7 ((𝜑 ∧ 𝑏 ∈ 𝑈) → ∃𝑢 ∈ Word 𝐴𝑏 ∈ ({𝑢} × (0...(♯‘𝑢))))
5846, 57r19.29a 3177 . . . . . 6 ((𝜑 ∧ 𝑏 ∈ 𝑈) → (1st ‘𝑏) ∈ Word 𝐴)
59 pfxcl 14868 . . . . . 6 ((1st ‘𝑏) ∈ Word 𝐴 → ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∈ Word 𝐴)
6058, 59syl 18 . . . . 5 ((𝜑 ∧ 𝑏 ∈ 𝑈) → ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∈ Word 𝐴)
61 swrdcl 14834 . . . . . 6 ((1st ‘𝑏) ∈ Word 𝐴 → ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩) ∈ Word 𝐴)
6258, 61syl 18 . . . . 5 ((𝜑 ∧ 𝑏 ∈ 𝑈) → ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩) ∈ Word 𝐴)
6360, 62opelxpd 5696 . . . 4 ((𝜑 ∧ 𝑏 ∈ 𝑈) → ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ∈ (Word 𝐴 × Word 𝐴))
6448adantr 486 . . . . . . . . . 10 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → 𝑏 ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))))
65 eliunxp 5823 . . . . . . . . . 10 (𝑏 ∈ ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))) ↔ ∃𝑤∃𝑛(𝑏 = ⟨𝑤, 𝑛⟩ ∧ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤)))))
6664, 65sylib 221 . . . . . . . . 9 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ∃𝑤∃𝑛(𝑏 = ⟨𝑤, 𝑛⟩ ∧ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤)))))
67 opeq1 4844 . . . . . . . . . . . . 13 (𝑢 = 𝑤 → ⟨𝑢, 𝑛⟩ = ⟨𝑤, 𝑛⟩)
6867eqeq2d 2777 . . . . . . . . . . . 12 (𝑢 = 𝑤 → (𝑏 = ⟨𝑢, 𝑛⟩ ↔ 𝑏 = ⟨𝑤, 𝑛⟩))
69 eleq1w 2850 . . . . . . . . . . . . 13 (𝑢 = 𝑤 → (𝑢 ∈ Word 𝐴 ↔ 𝑤 ∈ Word 𝐴))
7053eleq2d 2853 . . . . . . . . . . . . 13 (𝑢 = 𝑤 → (𝑛 ∈ (0...(♯‘𝑢)) ↔ 𝑛 ∈ (0...(♯‘𝑤))))
7169, 70anbi12d 644 . . . . . . . . . . . 12 (𝑢 = 𝑤 → ((𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢))) ↔ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤)))))
7268, 71anbi12d 644 . . . . . . . . . . 11 (𝑢 = 𝑤 → ((𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) ↔ (𝑏 = ⟨𝑤, 𝑛⟩ ∧ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤))))))
7372exbidv 1958 . . . . . . . . . 10 (𝑢 = 𝑤 → (∃𝑛(𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) ↔ ∃𝑛(𝑏 = ⟨𝑤, 𝑛⟩ ∧ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤))))))
7473cbvexvw 2074 . . . . . . . . 9 (∃𝑢∃𝑛(𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) ↔ ∃𝑤∃𝑛(𝑏 = ⟨𝑤, 𝑛⟩ ∧ (𝑤 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑤)))))
7566, 74sylibr 237 . . . . . . . 8 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ∃𝑢∃𝑛(𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))))
76 simplr 781 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)))
77 simpr 490 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩))
7876, 77oveq12d 7468 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → ((1st ‘𝑎) ++ (2nd ‘𝑎)) = (((1st ‘𝑏) prefix (2nd ‘𝑏)) ++ ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)))
79 vex 3457 . . . . . . . . . . . . . . . . . . . . 21 𝑢 ∈ V
80 vex 3457 . . . . . . . . . . . . . . . . . . . . 21 𝑛 ∈ V
8179, 80op1std 8044 . . . . . . . . . . . . . . . . . . . 20 (𝑏 = ⟨𝑢, 𝑛⟩ → (1st ‘𝑏) = 𝑢)
8281ad5antlr 748 . . . . . . . . . . . . . . . . . . 19 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (1st ‘𝑏) = 𝑢)
83 simp-4r 796 . . . . . . . . . . . . . . . . . . 19 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → 𝑢 ∈ Word 𝐴)
8482, 83eqeltrd 2867 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (1st ‘𝑏) ∈ Word 𝐴)
8579, 80op2ndd 8045 . . . . . . . . . . . . . . . . . . . 20 (𝑏 = ⟨𝑢, 𝑛⟩ → (2nd ‘𝑏) = 𝑛)
8685ad5antlr 748 . . . . . . . . . . . . . . . . . . 19 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (2nd ‘𝑏) = 𝑛)
87 simpllr 788 . . . . . . . . . . . . . . . . . . . 20 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → 𝑛 ∈ (0...(♯‘𝑢)))
8882eqcomd 2772 . . . . . . . . . . . . . . . . . . . . . 22 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → 𝑢 = (1st ‘𝑏))
8988fveq2d 6919 . . . . . . . . . . . . . . . . . . . . 21 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (♯‘𝑢) = (♯‘(1st ‘𝑏)))
9089oveq2d 7466 . . . . . . . . . . . . . . . . . . . 20 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (0...(♯‘𝑢)) = (0...(♯‘(1st ‘𝑏))))
9187, 90eleqtrd 2869 . . . . . . . . . . . . . . . . . . 19 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → 𝑛 ∈ (0...(♯‘(1st ‘𝑏))))
9286, 91eqeltrd 2867 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (2nd ‘𝑏) ∈ (0...(♯‘(1st ‘𝑏))))
93 pfxcctswrd 14900 . . . . . . . . . . . . . . . . . 18 (((1st ‘𝑏) ∈ Word 𝐴 ∧ (2nd ‘𝑏) ∈ (0...(♯‘(1st ‘𝑏)))) → (((1st ‘𝑏) prefix (2nd ‘𝑏)) ++ ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) = (1st ‘𝑏))
9484, 92, 93syl2anc 596 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (((1st ‘𝑏) prefix (2nd ‘𝑏)) ++ ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) = (1st ‘𝑏))
9578, 94eqtr2d 2802 . . . . . . . . . . . . . . . 16 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)))
9676fveq2d 6919 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (♯‘(1st ‘𝑎)) = (♯‘((1st ‘𝑏) prefix (2nd ‘𝑏))))
97 pfxlen 14874 . . . . . . . . . . . . . . . . . 18 (((1st ‘𝑏) ∈ Word 𝐴 ∧ (2nd ‘𝑏) ∈ (0...(♯‘(1st ‘𝑏)))) → (♯‘((1st ‘𝑏) prefix (2nd ‘𝑏))) = (2nd ‘𝑏))
9884, 92, 97syl2anc 596 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (♯‘((1st ‘𝑏) prefix (2nd ‘𝑏))) = (2nd ‘𝑏))
9996, 98eqtr2d 2802 . . . . . . . . . . . . . . . 16 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))
10095, 99jca 521 . . . . . . . . . . . . . . 15 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏))) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) → ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))))
101100anasss 472 . . . . . . . . . . . . . 14 ((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ ((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩))) → ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))))
102 simplr 781 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)))
103 simpr 490 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))
104102, 103oveq12d 7468 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → ((1st ‘𝑏) prefix (2nd ‘𝑏)) = (((1st ‘𝑎) ++ (2nd ‘𝑎)) prefix (♯‘(1st ‘𝑎))))
1058ad5antr 747 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (1st ‘𝑎) ∈ Word 𝐴)
10610ad5antr 747 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (2nd ‘𝑎) ∈ Word 𝐴)
107 pfxccat1 14892 . . . . . . . . . . . . . . . . . 18 (((1st ‘𝑎) ∈ Word 𝐴 ∧ (2nd ‘𝑎) ∈ Word 𝐴) → (((1st ‘𝑎) ++ (2nd ‘𝑎)) prefix (♯‘(1st ‘𝑎))) = (1st ‘𝑎))
108105, 106, 107syl2anc 596 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (((1st ‘𝑎) ++ (2nd ‘𝑎)) prefix (♯‘(1st ‘𝑎))) = (1st ‘𝑎))
109104, 108eqtr2d 2802 . . . . . . . . . . . . . . . 16 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)))
110102fveq2d 6919 . . . . . . . . . . . . . . . . . . . 20 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (♯‘(1st ‘𝑏)) = (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))))
111105, 106, 31syl2anc 596 . . . . . . . . . . . . . . . . . . . 20 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (♯‘((1st ‘𝑎) ++ (2nd ‘𝑎))) = ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎))))
112110, 111eqtrd 2801 . . . . . . . . . . . . . . . . . . 19 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (♯‘(1st ‘𝑏)) = ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎))))
113103, 112opeq12d 4852 . . . . . . . . . . . . . . . . . 18 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩ = ⟨(♯‘(1st ‘𝑎)), ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎)))⟩)
114102, 113oveq12d 7468 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩) = (((1st ‘𝑎) ++ (2nd ‘𝑎)) substr ⟨(♯‘(1st ‘𝑎)), ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎)))⟩))
115 swrdccat2 14860 . . . . . . . . . . . . . . . . . 18 (((1st ‘𝑎) ∈ Word 𝐴 ∧ (2nd ‘𝑎) ∈ Word 𝐴) → (((1st ‘𝑎) ++ (2nd ‘𝑎)) substr ⟨(♯‘(1st ‘𝑎)), ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎)))⟩) = (2nd ‘𝑎))
116105, 106, 115syl2anc 596 . . . . . . . . . . . . . . . . 17 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (((1st ‘𝑎) ++ (2nd ‘𝑎)) substr ⟨(♯‘(1st ‘𝑎)), ((♯‘(1st ‘𝑎)) + (♯‘(2nd ‘𝑎)))⟩) = (2nd ‘𝑎))
117114, 116eqtr2d 2802 . . . . . . . . . . . . . . . 16 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩))
118109, 117jca 521 . . . . . . . . . . . . . . 15 (((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ (1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎))) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))) → ((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)))
119118anasss 472 . . . . . . . . . . . . . 14 ((((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) ∧ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))) → ((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)))
120101, 119impbida 813 . . . . . . . . . . . . 13 (((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ 𝑢 ∈ Word 𝐴) ∧ 𝑛 ∈ (0...(♯‘𝑢))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
121120anasss 472 . . . . . . . . . . . 12 ((((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 = ⟨𝑢, 𝑛⟩) ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
122121expl 463 . . . . . . . . . . 11 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ((𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))))))
123122adantlr 728 . . . . . . . . . 10 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ((𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))))))
124123exlimdv 1970 . . . . . . . . 9 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (∃𝑛(𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢)))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎))))))
125124imp 412 . . . . . . . 8 ((((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ ∃𝑛(𝑏 = ⟨𝑢, 𝑛⟩ ∧ (𝑢 ∈ Word 𝐴 ∧ 𝑛 ∈ (0...(♯‘𝑢))))) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
12675, 125exlimddv 1972 . . . . . . 7 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)) ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
127 eqop 8076 . . . . . . . 8 (𝑎 ∈ (Word 𝐴 × Word 𝐴) → (𝑎 = ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ↔ ((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩))))
128127adantl 487 . . . . . . 7 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (𝑎 = ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ↔ ((1st ‘𝑎) = ((1st ‘𝑏) prefix (2nd ‘𝑏)) ∧ (2nd ‘𝑎) = ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩))))
129 snssi 4747 . . . . . . . . . . . . 13 (𝑤 ∈ Word 𝐴 → {𝑤} ⊆ Word 𝐴)
130129adantl 487 . . . . . . . . . . . 12 (((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑤 ∈ Word 𝐴) → {𝑤} ⊆ Word 𝐴)
131 fz0ssnn0 13795 . . . . . . . . . . . 12 (0...(♯‘𝑤)) ⊆ ℕ0
132 xpss12 5672 . . . . . . . . . . . 12 (({𝑤} ⊆ Word 𝐴 ∧ (0...(♯‘𝑤)) ⊆ ℕ0) → ({𝑤} × (0...(♯‘𝑤))) ⊆ (Word 𝐴 × ℕ0))
133130, 131, 132sylancl 598 . . . . . . . . . . 11 (((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑤 ∈ Word 𝐴) → ({𝑤} × (0...(♯‘𝑤))) ⊆ (Word 𝐴 × ℕ0))
134133iunssd 5013 . . . . . . . . . 10 ((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))) ⊆ (Word 𝐴 × ℕ0))
135134adantlr 728 . . . . . . . . 9 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → ∪ 𝑤 ∈ Word 𝐴({𝑤} × (0...(♯‘𝑤))) ⊆ (Word 𝐴 × ℕ0))
136135, 64sseldd 3913 . . . . . . . 8 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → 𝑏 ∈ (Word 𝐴 × ℕ0))
137 eqop 8076 . . . . . . . 8 (𝑏 ∈ (Word 𝐴 × ℕ0) → (𝑏 = ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
138136, 137syl 18 . . . . . . 7 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (𝑏 = ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩ ↔ ((1st ‘𝑏) = ((1st ‘𝑎) ++ (2nd ‘𝑎)) ∧ (2nd ‘𝑏) = (♯‘(1st ‘𝑎)))))
139126, 128, 1383bitr4d 314 . . . . . 6 (((𝜑 ∧ 𝑏 ∈ 𝑈) ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) → (𝑎 = ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ↔ 𝑏 = ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩))
140139an32s 665 . . . . 5 (((𝜑 ∧ 𝑎 ∈ (Word 𝐴 × Word 𝐴)) ∧ 𝑏 ∈ 𝑈) → (𝑎 = ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ↔ 𝑏 = ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩))
141140anasss 472 . . . 4 ((𝜑 ∧ (𝑎 ∈ (Word 𝐴 × Word 𝐴) ∧ 𝑏 ∈ 𝑈)) → (𝑎 = ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩ ↔ 𝑏 = ⟨((1st ‘𝑎) ++ (2nd ‘𝑎)), (♯‘(1st ‘𝑎))⟩))
1421, 39, 63, 141f1ocnv2d 7705 . . 3 (𝜑 → (𝐹:(Word 𝐴 × Word 𝐴)⟶1-1onto𝑈 ∧ ◡𝐹 = (𝑏 ∈ 𝑈 ↦ ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩)))
143142simpld 500 . 2 (𝜑 → 𝐹:(Word 𝐴 × Word 𝐴)⟶1-1onto𝑈)
144142simprd 501 . . 3 (𝜑 → ◡𝐹 = (𝑏 ∈ 𝑈 ↦ ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩))
145 gsumwrd2dccatlem.g . . 3 𝐺 = (𝑏 ∈ 𝑈 ↦ ⟨((1st ‘𝑏) prefix (2nd ‘𝑏)), ((1st ‘𝑏) substr ⟨(2nd ‘𝑏), (♯‘(1st ‘𝑏))⟩)⟩)
146144, 145eqtr4di 2819 . 2 (𝜑 → ◡𝐹 = 𝐺)
147143, 146jca 521 1 (𝜑 → (𝐹:(Word 𝐴 × Word 𝐴)⟶1-1onto𝑈 ∧ ◡𝐹 = 𝐺))
Colors of variables:    wff setvar class
This proof depends on syntax axioms:   → wi 4   ↔ wb 209   ∧ wa 401   = wceq 1572  ∃wex 1814   ∈ wcel 2150  ∃wrex 3093   ⊆ wss 3899  {csn 4587  ⟨cop 4839  ∪ ciun 4955   class class class wbr 5107   ↦ cmpt 5191   × cxp 5655  ◡ccnv 5656  ⟶1-1ontowf1o 6564  ‘cfv 6565  (class class class)co 7450  1st c1st 8032  2nd c2nd 8033  0cc0 11238   + caddc 11241   ≤ cle 11382  ℕ0cn0 12645  ...cfz 13678  ♯chash 14514  Word cword 14698   ++ cconcat 14755   substr csubstr 14829   prefix cpfx 14861
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1830  ax-4 1844  ax-5 1947  ax-6 2004  ax-7 2045  ax-8 2152  ax-9 2160  ax-10 2183  ax-11 2200  ax-12 2219  ax-ext 2738  ax-rep 5237  ax-sep 5254  ax-nul 5265  ax-pow 5333  ax-pr 5397  ax-un 7782  ax-cnex 11294  ax-resscn 11295  ax-1cn 11296  ax-icn 11297  ax-addcl 11298  ax-addrcl 11299  ax-mulcl 11300  ax-mulrcl 11301  ax-mulcom 11302  ax-addass 11303  ax-mulass 11304  ax-distr 11305  ax-i2m1 11306  ax-1ne0 11307  ax-1rid 11308  ax-rnegex 11309  ax-rrecex 11310  ax-cnre 11311  ax-pre-lttri 11312  ax-pre-lttrn 11313  ax-pre-ltadd 11314  ax-pre-mulgt0 11315
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1105  df-3an 1106  df-tru 1575  df-fal 1585  df-ex 1815  df-nf 1819  df-sb 2104  df-mo 2570  df-eu 2600  df-clab 2745  df-cleq 2758  df-clel 2842  df-nfc 2916  df-ne 2963  df-nel 3069  df-ral 3084  df-rex 3094  df-reu 3369  df-rab 3416  df-v 3455  df-sbc 3742  df-csb 3851  df-ss 3900  df-pss 4016  df-dif 4049  df-in 4093  df-un 4153  df-nul 4281  df-if 4485  df-pw 4561  df-sn 4588  df-pr 4590  df-op 4840  df-uni 4872  df-int 4912  df-iun 4957  df-br 5108  df-opab 5173  df-mpt 5192  df-tr 5218  df-id 5552  df-eprel 5557  df-po 5565  df-so 5566  df-fr 5610  df-we 5612  df-xp 5663  df-rel 5664  df-cnv 5665  df-co 5666  df-dm 5667  df-rn 5668  df-res 5669  df-ima 5670  df-pred 6329  df-ord 6390  df-on 6391  df-lim 6392  df-suc 6393  df-iota 6519  df-fun 6567  df-fn 6568  df-f 6569  df-f1 6570  df-fo 6571  df-f1o 6572  df-fv 6573  df-riota 7407  df-ov 7453  df-oprab 7454  df-mpo 7455  df-om 7911  df-1st 8034  df-2nd 8035  df-frecs 8336  df-wrecs 8367  df-recs 8416  df-rdg 8455  df-1o 8513  df-er 8754  df-en 9011  df-dom 9012  df-sdom 9013  df-fin 9014  df-card 10056  df-pnf 11383  df-mnf 11384  df-xr 11385  df-ltxr 11386  df-le 11387  df-sub 11581  df-neg 11582  df-nn 12375  df-n0 12646  df-z 12733  df-uz 13005  df-fz 13679  df-fzo 13828  df-hash 14515  df-word 14699  df-concat 14756  df-substr 14830  df-pfx 14862
This theorem is used by:  gsumwrd2dccat  33739
  Copyright terms: Public domain W3C validator