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

Theorem frmdss2 17839
Description: A subset of generators is contained in a submonoid iff the set of words on the generators is in the submonoid. This can be viewed as an elementary way of saying "the monoidal closure of 𝐽 is Word 𝐽". (Contributed by Mario Carneiro, 2-Oct-2015.)
Hypotheses
Ref Expression
frmdmnd.m 𝑀 = (freeMnd‘𝐼)
frmdgsum.u 𝑈 = (varFMnd𝐼)
Assertion
Ref Expression
frmdss2 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → ((𝑈𝐽) ⊆ 𝐴 ↔ Word 𝐽𝐴))

Proof of Theorem frmdss2
Dummy variable 𝑥 is distinct from all other variables.
StepHypRef Expression
1 simpl1 1184 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝐼𝑉)
2 simpl2 1185 . . . . . . . . 9 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝐽𝐼)
3 sswrd 13715 . . . . . . . . 9 (𝐽𝐼 → Word 𝐽 ⊆ Word 𝐼)
42, 3syl 17 . . . . . . . 8 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → Word 𝐽 ⊆ Word 𝐼)
5 simprr 769 . . . . . . . 8 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝑥 ∈ Word 𝐽)
64, 5sseldd 3890 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝑥 ∈ Word 𝐼)
7 frmdmnd.m . . . . . . . 8 𝑀 = (freeMnd‘𝐼)
8 frmdgsum.u . . . . . . . 8 𝑈 = (varFMnd𝐼)
97, 8frmdgsum 17838 . . . . . . 7 ((𝐼𝑉𝑥 ∈ Word 𝐼) → (𝑀 Σg (𝑈𝑥)) = 𝑥)
101, 6, 9syl2anc 584 . . . . . 6 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑀 Σg (𝑈𝑥)) = 𝑥)
11 simpl3 1186 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝐴 ∈ (SubMnd‘𝑀))
12 wrdf 13712 . . . . . . . . . . 11 (𝑥 ∈ Word 𝐽𝑥:(0..^(♯‘𝑥))⟶𝐽)
1312ad2antll 725 . . . . . . . . . 10 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝑥:(0..^(♯‘𝑥))⟶𝐽)
1413frnd 6389 . . . . . . . . 9 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → ran 𝑥𝐽)
15 cores 5977 . . . . . . . . 9 (ran 𝑥𝐽 → ((𝑈𝐽) ∘ 𝑥) = (𝑈𝑥))
1614, 15syl 17 . . . . . . . 8 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → ((𝑈𝐽) ∘ 𝑥) = (𝑈𝑥))
178vrmdf 17834 . . . . . . . . . . . . 13 (𝐼𝑉𝑈:𝐼⟶Word 𝐼)
18173ad2ant1 1126 . . . . . . . . . . . 12 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → 𝑈:𝐼⟶Word 𝐼)
1918ffnd 6383 . . . . . . . . . . 11 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → 𝑈 Fn 𝐼)
20 fnssres 6340 . . . . . . . . . . 11 ((𝑈 Fn 𝐼𝐽𝐼) → (𝑈𝐽) Fn 𝐽)
2119, 2, 20syl2an2r 681 . . . . . . . . . 10 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑈𝐽) Fn 𝐽)
22 df-ima 5456 . . . . . . . . . . 11 (𝑈𝐽) = ran (𝑈𝐽)
23 simprl 767 . . . . . . . . . . 11 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑈𝐽) ⊆ 𝐴)
2422, 23syl5eqssr 3937 . . . . . . . . . 10 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → ran (𝑈𝐽) ⊆ 𝐴)
25 df-f 6229 . . . . . . . . . 10 ((𝑈𝐽):𝐽𝐴 ↔ ((𝑈𝐽) Fn 𝐽 ∧ ran (𝑈𝐽) ⊆ 𝐴))
2621, 24, 25sylanbrc 583 . . . . . . . . 9 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑈𝐽):𝐽𝐴)
27 wrdco 14029 . . . . . . . . 9 ((𝑥 ∈ Word 𝐽 ∧ (𝑈𝐽):𝐽𝐴) → ((𝑈𝐽) ∘ 𝑥) ∈ Word 𝐴)
285, 26, 27syl2anc 584 . . . . . . . 8 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → ((𝑈𝐽) ∘ 𝑥) ∈ Word 𝐴)
2916, 28eqeltrrd 2884 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑈𝑥) ∈ Word 𝐴)
30 gsumwsubmcl 17814 . . . . . . 7 ((𝐴 ∈ (SubMnd‘𝑀) ∧ (𝑈𝑥) ∈ Word 𝐴) → (𝑀 Σg (𝑈𝑥)) ∈ 𝐴)
3111, 29, 30syl2anc 584 . . . . . 6 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → (𝑀 Σg (𝑈𝑥)) ∈ 𝐴)
3210, 31eqeltrrd 2884 . . . . 5 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ ((𝑈𝐽) ⊆ 𝐴𝑥 ∈ Word 𝐽)) → 𝑥𝐴)
3332expr 457 . . . 4 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ (𝑈𝐽) ⊆ 𝐴) → (𝑥 ∈ Word 𝐽𝑥𝐴))
3433ssrdv 3895 . . 3 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ (𝑈𝐽) ⊆ 𝐴) → Word 𝐽𝐴)
3534ex 413 . 2 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → ((𝑈𝐽) ⊆ 𝐴 → Word 𝐽𝐴))
36 simpl1 1184 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → 𝐼𝑉)
37 simp2 1130 . . . . . . . 8 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → 𝐽𝐼)
3837sselda 3889 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → 𝑥𝐼)
398vrmdval 17833 . . . . . . 7 ((𝐼𝑉𝑥𝐼) → (𝑈𝑥) = ⟨“𝑥”⟩)
4036, 38, 39syl2anc 584 . . . . . 6 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → (𝑈𝑥) = ⟨“𝑥”⟩)
41 simpr 485 . . . . . . 7 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → 𝑥𝐽)
4241s1cld 13801 . . . . . 6 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → ⟨“𝑥”⟩ ∈ Word 𝐽)
4340, 42eqeltrd 2883 . . . . 5 (((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) ∧ 𝑥𝐽) → (𝑈𝑥) ∈ Word 𝐽)
4443ralrimiva 3149 . . . 4 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → ∀𝑥𝐽 (𝑈𝑥) ∈ Word 𝐽)
4518ffund 6386 . . . . 5 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → Fun 𝑈)
4618fdmd 6391 . . . . . 6 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → dom 𝑈 = 𝐼)
4737, 46sseqtr4d 3929 . . . . 5 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → 𝐽 ⊆ dom 𝑈)
48 funimass4 6598 . . . . 5 ((Fun 𝑈𝐽 ⊆ dom 𝑈) → ((𝑈𝐽) ⊆ Word 𝐽 ↔ ∀𝑥𝐽 (𝑈𝑥) ∈ Word 𝐽))
4945, 47, 48syl2anc 584 . . . 4 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → ((𝑈𝐽) ⊆ Word 𝐽 ↔ ∀𝑥𝐽 (𝑈𝑥) ∈ Word 𝐽))
5044, 49mpbird 258 . . 3 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → (𝑈𝐽) ⊆ Word 𝐽)
51 sstr2 3896 . . 3 ((𝑈𝐽) ⊆ Word 𝐽 → (Word 𝐽𝐴 → (𝑈𝐽) ⊆ 𝐴))
5250, 51syl 17 . 2 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → (Word 𝐽𝐴 → (𝑈𝐽) ⊆ 𝐴))
5335, 52impbid 213 1 ((𝐼𝑉𝐽𝐼𝐴 ∈ (SubMnd‘𝑀)) → ((𝑈𝐽) ⊆ 𝐴 ↔ Word 𝐽𝐴))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 207  wa 396  w3a 1080   = wceq 1522  wcel 2081  wral 3105  wss 3859  dom cdm 5443  ran crn 5444  cres 5445  cima 5446  ccom 5447  Fun wfun 6219   Fn wfn 6220  wf 6221  cfv 6225  (class class class)co 7016  0cc0 10383  ..^cfzo 12883  chash 13540  Word cword 13707  ⟨“cs1 13793   Σg cgsu 16543  SubMndcsubmnd 17773  freeMndcfrmd 17823  varFMndcvrmd 17824
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1777  ax-4 1791  ax-5 1888  ax-6 1947  ax-7 1992  ax-8 2083  ax-9 2091  ax-10 2112  ax-11 2126  ax-12 2141  ax-13 2344  ax-ext 2769  ax-rep 5081  ax-sep 5094  ax-nul 5101  ax-pow 5157  ax-pr 5221  ax-un 7319  ax-cnex 10439  ax-resscn 10440  ax-1cn 10441  ax-icn 10442  ax-addcl 10443  ax-addrcl 10444  ax-mulcl 10445  ax-mulrcl 10446  ax-mulcom 10447  ax-addass 10448  ax-mulass 10449  ax-distr 10450  ax-i2m1 10451  ax-1ne0 10452  ax-1rid 10453  ax-rnegex 10454  ax-rrecex 10455  ax-cnre 10456  ax-pre-lttri 10457  ax-pre-lttrn 10458  ax-pre-ltadd 10459  ax-pre-mulgt0 10460
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 843  df-3or 1081  df-3an 1082  df-tru 1525  df-ex 1762  df-nf 1766  df-sb 2043  df-mo 2576  df-eu 2612  df-clab 2776  df-cleq 2788  df-clel 2863  df-nfc 2935  df-ne 2985  df-nel 3091  df-ral 3110  df-rex 3111  df-reu 3112  df-rmo 3113  df-rab 3114  df-v 3439  df-sbc 3707  df-csb 3812  df-dif 3862  df-un 3864  df-in 3866  df-ss 3874  df-pss 3876  df-nul 4212  df-if 4382  df-pw 4455  df-sn 4473  df-pr 4475  df-tp 4477  df-op 4479  df-uni 4746  df-int 4783  df-iun 4827  df-br 4963  df-opab 5025  df-mpt 5042  df-tr 5064  df-id 5348  df-eprel 5353  df-po 5362  df-so 5363  df-fr 5402  df-we 5404  df-xp 5449  df-rel 5450  df-cnv 5451  df-co 5452  df-dm 5453  df-rn 5454  df-res 5455  df-ima 5456  df-pred 6023  df-ord 6069  df-on 6070  df-lim 6071  df-suc 6072  df-iota 6189  df-fun 6227  df-fn 6228  df-f 6229  df-f1 6230  df-fo 6231  df-f1o 6232  df-fv 6233  df-riota 6977  df-ov 7019  df-oprab 7020  df-mpo 7021  df-om 7437  df-1st 7545  df-2nd 7546  df-wrecs 7798  df-recs 7860  df-rdg 7898  df-1o 7953  df-oadd 7957  df-er 8139  df-map 8258  df-en 8358  df-dom 8359  df-sdom 8360  df-fin 8361  df-card 9214  df-pnf 10523  df-mnf 10524  df-xr 10525  df-ltxr 10526  df-le 10527  df-sub 10719  df-neg 10720  df-nn 11487  df-2 11548  df-n0 11746  df-xnn0 11816  df-z 11830  df-uz 12094  df-fz 12743  df-fzo 12884  df-seq 13220  df-hash 13541  df-word 13708  df-lsw 13761  df-concat 13769  df-s1 13794  df-substr 13839  df-pfx 13869  df-struct 16314  df-ndx 16315  df-slot 16316  df-base 16318  df-sets 16319  df-ress 16320  df-plusg 16407  df-0g 16544  df-gsum 16545  df-mgm 17681  df-sgrp 17723  df-mnd 17734  df-submnd 17775  df-frmd 17825  df-vrmd 17826
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator