abstract algebra – How to show this ring homomorphism is surjective?

So I’ve been given the following

R = Map(ℝ, ℝ) with addition and multiplication defined by $(f +g)(x) = f(x)+g(x)$ and $(f ·g)(x) = f(x)g(x)$. Let S be the ring of sequences $(a_{n})_{n}≥0$ with entries $a_{n} ∈ R$, and define
φ:R→S
$f 􏰀→ (f(n))_{n}$

I need to use the first isomorphism theorem to find the isomorphism with the domain R/I (where I is the kernel of φ) and codomain S. I have already found I, and have been given the hint that I need to show that the homomorphism given is surjective but I’m not sure how to do that.

I know that for the definition of surjectivity is that for every element of S, there is an element of R that maps to it, but I have no idea how to show that there is a function $f$ that maps to a sequence of the form $(f(n))_{n}$

analytic functions – Homomorphism and holomorphic funtions

Let $M leq mathbb{C}$ the aditive subgroup such that, $$M={n+im in mathbb{C}:n,min mathbb{Z} }$$ Let $f$ be a entire funtion such that $f(0)=0$, suppose that $$g(z+M)=f(z)+M, (zinmathbb{C})$$
define a group homomorphism, $g:mathbb{C}/M rightarrowmathbb{C}/M$, where $mathbb{C}/M$ is the quotient group.

$(a)$ Prove that exists some disk $D$ centered in $0$, such that $f(z+w)=f(z)+f(w)$, for all $z,w in D.$

$(b)$ Prove that exists some $binmathbb{C}$, such that $f(z)=az$, for all $z$ in some neighborhood of $0$.

$(c)$ Prove that exists some $bin mathbb{C}$, such that $g(z+M)=az+M$ for all $z in mathbb{C}.$

I don’t se a clear path, because we never use group properties in the complex variable course, however, as $f$ is entire and $f(0)=0$, there exist an holomorphic funtion $h$, such that $f(z)=z^rh(z)$ for some $rgeq1$, and $h(0)neq0$, but how can I use this?

Even so is not clear for me, how to use the quotient, of wich propertie is important in the Gaussian integers in this case.

Ring homomorphism $varphi : mmathbb Z to mathbb Z _{frac{n}{m}}$

This is what I have to prove:

Let $varphi : mmathbb Z to mathbb Z _{frac{n}{m}}$ where $m mid n$ given by $varphi(x) =overline{left(frac{x}{m}right)}$ is a (not necessarily unital) ring homomorphism iff $m=1$ or $m=n$.

The backward direction is clear to me. It is the forward direction which I have been unable to prove.


Here’s my attempt:

Suppose that the given $varphi$ is a ring homomorphism. Then $varphi (m^2)=varphi (m)$, so, $overline m =overline 1$. Hence $frac{n}{m} mid m-1$.

Further assume that $m ne n$. Let $p$ be any prime dividing $frac{n}{m}$.

Then $p$ divides $n$, also, $p$ divides $m-1$. So $p$ cannot divide $m$.


I have not been able to complete. Hints will be appreciated!

Context-Sensitive Grammars are closed under language substitution, and string homomorphism, but are they closed under inverse language substitution?

Wikipedia note on closure properties.

We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $Sigma$ is a map from $Sigma$ into CSL’s, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) the union of all $L(s)$ for $s in f(S)$ is defined to be $L(f(S))$ and $L(f(S))$ is known to be a CSL itself.

That is my interpretation of language substitution for CSL’s. Well languages are also closed under inverse of string homomorphisms, homomorphisms $f$ being a pecial case of language subtitution in which each $a in Sigma$ gets mapped to a singleton language $L_1(a) = {f(a)}$.

So my question is simple, yet probably hard or interesting to prove. That is, are CSL’s closed under inverse of language substitution?

Let $f$ be a language substitution taking $S$ to $f(S)$. Then $f^{-1}(S) := bigcup f^{-1}(s)$ I’m assuming. Is that a CSL?

computer science – Smallest grammar problem formulated in terms of minimizing a monoid homomorphism into $(Bbb{N}, +, leq)$. What is an algorithm for computing one?

Let the naturals $Bbb{N}$ include $0$.

Let $A = {a,b,c, dots}$ be a finite alphabet of symbols.

Definition 1. A grammar of a string $s in A^*$ is a monoid homomorphism $varphi : A^* to A^*$ such that the iterates $varphi^i(X), i geq 0$ stabilize to $s$ for some $X in A$.

Observation 1. The set of all grammars of strings in $A^*$ forms a monoid $M_A$ under pointwise multiplication.

Definition 2. The size function on $M_A$ is the monoid homomorphism $|cdot | : M_A twoheadrightarrow (Bbb{N}, +)$ given by $|varphi| = sum_{a in A} | varphi(a)|$, where $|varphi(a)|$ simply takes the symbol string length.

Remark 1. $(Bbb{N}, +)$ forms an ordered monoid, so we can speak of $leq$.

Definition 3. A smallest grammar of a string $s in A^*$ is a grammar of $s$, such that for all other grammars $psi$ of $s$, $|varphi| leq |psi|$.

Observation 2. Minimizing the size function above is essentially the same thing as the smallest grammar problem (SGP), where the standard size function is the sum over all variable symbols instead:

$$
| varphi | = sum_{X in in text{variables}(varphi)} |varphi(X)|
$$

. This is true since including the terminals simply adds a constant to the standard size function that you’re minimizing when solving the SGP.

Remark 2. If a grammar does not “make use of” a symbol $x$, then it simply gets mapped to the empty string $varepsilon$ which has length $0$ and thus no contribution to the final grammar size.


Question. using the above definitions, what is an algorithm (regardless of its efficiency) for computing a smallest grammar or alternatively the set of all smallest grammars, of a given input string $s$?


Define $text{supp}(varphi) = { a in A: varphi(a) neq varepsilon}$. Notice that if $varphi$ is a smallest grammar of $s$ and $psi$ is a smallest grammar of $t$, and $text{supp}(varphi) cap text{supp}(psi) = varnothing$, then $varphipsi$ is a smallest grammar of $st$. This is because there are no shared substrings, and so the smallest grammars can be computed independently.

Can we use this fact somehow in an algorithm?

In none of the literature on the smallest grammar problem do they present an algorithm for computing exactly the smallest grammar or set of smallest grammars. All literature on the topic focuses on approximating them.

I want to see an algorithm for computing them exactly. So how would one be written?

nonstandard analysis – Legitimacy of the shadow map serving as a field homomorphism for a specific hyperfinite field formed of a union of hyperfine lattices

I’m hoping to get some comment on the legitimacy of my approach to creating a hyperfinite ring formed of a union of modular groups in order to obtain a field homomorphism from this hyperfinite space to the real numbers. As nonstandard analysis isn’t my area I feel I’m at risk of accidentally making mortal error and so I’m looking for constructive advice regarding the legitimacy of my approach.

As I said I’m looking to construct a hyperfinite space that can serve as an approximation for the reals as a field in the sense that the shadow (standard) map serves a field homomorphism between this space and $mathbb{R}$. As motivation for how I’ve tried to go about this consider taking the following set

$$
{ }^{star} mathbb{Z}_{omega}:=left{k in{ }^{star} mathbb{Z} mid-leftlceil frac{omega-1}{2} leq k leqleftlfloorfrac{omega-1}{2}rightrfloorright}right.
$$

where $omega:=omega_{mathrm{uv}} omega_{mathrm{ir}}$ for some positive $omega_{mathrm{uv}}, omega_{mathrm{ir}} in{ }^{star}mathbb{Z}$ We can define a hyperfinite abelian group with 0 as the unit with the group operation

$$
a+_{omega} b:=left{begin{array}{ll}
a+b & text { if }-leftlceilfrac{omega-1}{2}rightrceil leq a+b leqleftlfloorfrac{omega-1}{2}rightrfloor \
a+b-omega & text { if }leftlfloorfrac{omega-1}{2}rightrfloor<a+b \
a+b+omega & text { if } a+b<-leftlceilfrac{omega-1}{2}rightrceil
end{array}right.
$$

We can go further and define a ring via
$$
a cdot_{omega} b:=left{begin{array}{ll}
a cdot b & text { if }-leftlceilfrac{omega-1}{2}rightrceil leq a cdot b leqleftlfloorfrac{omega-1}{2}rightrfloor \
a cdot b-k omega & text { if }leftlfloorfrac{omega-1}{2}rightrfloor+(k-1) omega<a cdot b leqleftlfloorfrac{omega-1}{2}rightrfloor+k omega \
a cdot b+k omega & text { if }-leftlceilfrac{omega-1}{2}rightrceil-k omega leq a cdot b<-leftlceilfrac{omega-1}{2}rightrceil-(k-1) omega
end{array}right.
$$

where the ring $left({ }^{star} mathbb{Z}_{omega},+_{omega}, 0, cdot omega, 1right)$ is a field if $omega$ is prime.

Now consider the ‘scaled’ version of this structure
$$frac{1}{omega_{mathrm{uv}}} star mathbb{Z}_{omega}=left{frac{k}{omega_{mathrm{uv}}} mid k in star mathbb{Z},-left(frac{omega-1}{2}rightrceil leq k leqleftlfloorfrac{omega-1}{2}rightrfloorright}$$

Now we take the shadow of this

$$
operatorname{shd}left(left(frac{1}{omega_{mathrm{uv}}}^{star} mathbb{Z}_{omega}right)_{mathrm{fin}}right)=left{operatorname{shd}left(frac{k}{omega_{mathrm{uv}}}right) mid k in{mathrm{Z}} text { s.t. }-left(frac{omega-1}{2}right) leq k leq mid frac{omega-1}{2}rightrfloor text { and } frac{k}{omega_{mathrm{uv}}} text { is finite }} subseteq mathbb{R}
$$

Finite elements are closed under the additive group structure of shd $left(left(frac{1}{omega_{mathrm{uv}}} star mathbb{Z}_{omega}right)_{mathrm{fin}}right)$ and taking the standard part is linear with respect to said additive group structure: this means that $left(left(frac{1}{omega_{text {uv }}} star mathbb{Z}_{omega}right)_{text {fin }},+_{omega}, 0right)$ is an abelian group.

Importantly for my purposes if I choose $omega_{mathrm{uv}}$ and $omega_{mathrm{ir}}$ to be ‘infinite’ then I believe I get the following

$$text { shd }:left(left(frac{1}{omega_{mathrm{uv}}} star mathbb{Z}_{omega}right)_{text {fin }},+_{omega}, 0right) longrightarrow(mathbb{R},+, 0)$$
as the range of the modulus is now up to an infinite number as is the scaling.

Now this approach will fail for a ring because we will want to write
$$
frac{h}{omega_{mathrm{uv}}} cdot_{omega} frac{k}{omega_{mathrm{uv}}}=frac{h cdot_{omega} k}{omega_{mathrm{uv}}}
$$

but we see that what we have is
$$
frac{h}{omega_{mathrm{uv}}} cdot omega frac{k}{omega_{mathrm{uv}}}=frac{h cdot_{omega} k}{omega_{mathrm{uv}}^{2}}
$$

which isn’t in our space.

My solution is to do the following and it is the legitimacy of this which I would like to get some opinions on.

Consider this union of lattices of the type we just discussed:

$$bigcup_{n in star mathbb{Z}_{kappa}} frac{1}{omega_{mathrm{uv}}^{n}}^{star} Z_{omega omega_{mathrm{uv}}^{n-1}}$$
where $kappa$ is an ‘infinite’ hyperinteger and
$$
left.frac{1}{omega_{mathrm{uv}}^{n}}^{star} mathbb{Z}_{omega}=left{frac{k}{omega_{mathrm{uv}}^{n}}left|k in{star} mathbb{Z},-left(frac{omega omega_{mathrm{uv}}^{n-1}-1}{2}rightrceil leq k leqright| frac{omega omega_{mathrm{uv}}^{n-1}-1}{2}rightrfloorright}$$

Now this union of lattices of greater and lesser fineness means that the multiplication problem described above is dealt with though perhaps at the cost of the curious choice of the following being the case:
$$
acdot_{omega}b = frac{acdot_{omega}b}{omega^{kappa}}
$$

Note how we have division defined here as we can take the usual modular inverse $i n v_{omega_{u v}}(p)$ and for any

$y=frac{q}{omega_{u v}^{n}}$ we will have $tilde{y}=omega_{u v}^{n} cdot_{omega} operatorname{inv}_{omega_{u v}^{n}}(p)$
$$
y tilde{y}=frac{q cdot_{omega} omega_{u v}^{n} cdot_{omega} i n v_{omega_{u v}^{n}}(q)}{omega_{u v}^{n}}=1
$$

Now the meat of my question: Is this a legitimate field homomorphism?
$$
operatorname{shd}:left(left(frac{1}{omega_{mathrm{uv}}} star mathbb{Z}_{omega}right)_{fin},+_{omega}, 0, cdot omega, 1right) longrightarrow(mathbb{R},+, 0, cdot, 1)
$$

where multiplication and addition are defined as specified here.

at.algebraic topology – Properties of filtrations preserved by a DG-algebra homomorphism

Suppose we have a homomorphism $f : A^{bullet} longrightarrow B^{bullet}$ of differential graded algebras over a field $k$, and consider the filtration

begin{align*}
A^{bullet} supseteq F^0A^{bullet} supseteq F^1A^{bullet} supseteq F^2A^{bullet} supseteq cdots hspace{0.5cm} (*)
end{align*}

of $A$. I’m interested in “pushing forward” or “extending” $(*)$ to a filtration on $B^{bullet}$.

Let $F^n(A^{bullet})^e$ be the two-sided ideal of $B^{bullet}$ generated by the image of the ideal $F^n(A^{bullet})$ of $A^{bullet}$ by $f$. Then we get the sequence of ideals
begin{align*}
B^{bullet} supseteq F^0(A^{bullet})^e supseteq F^1(A^{bullet})^e supseteq F^2(A^{bullet})^e supseteq cdots hspace{0.5cm} (**)
end{align*}

of $B$. I’d like to know the following about $(**)$ :

  1. If the filtration $(*)$ is exhaustive (that is, $A^{bullet} = F^0A^{bullet}$), is $(**)$ also exhaustive ?

  2. If the filtration $(*)$ is separated/Hausdorff (that is, $cap_n F^nA = {0}$) , is $(**)$ also separated/Hausdorff ?

  3. If the filtration $(*)$ is complete (that is, the map $A^{bullet} longrightarrow lim_{n rightarrow infty} A^{bullet} / F^nA^{bullet}$ is an isomorphism), is $(**)$ also complete ?

Are there relatively easy checks that one can do to answer any of these questions ? Alternatively, if there are any references that answer any of these questions, I’d like to know about them.

Thanks !

set theory – The extension of the substitution map of the semigroup of variable words to its Stone–Čech compactification is a homomorphism

Reading the proof of the Hales-Jewett theorem the author defines $W_L$ as the set
of finite words over some alphabet $L$, $W_{L_v}$ as the set of variable-words
over $L$, i.e. finite words over $L cup {v}$ where $v notin L$ and $v$ occurs
at least once, $S = W_L cup W_{L_v}$ and the substitution map from $S$ into $W_L$
obtained by replacing every occurrence of $v$ in the word by some $lambda in L$

Consider $(S, ^frown)$ as a discrete topological space with the concatenation
operation and let $left(beta S, ^frown right)$ be the space of ultrafilters
over $S$ (the Stone–Čech compactification of $S$) with the operation given by $$mathcal{U} ^frown mathcal{V} = left{ A subseteq S | left{x in S | left{y in S | x ^frown y in A right} in mathcal{V} right} in mathcal{U} right}$$

Let $S_{L}^{*} = left{mathcal{U} in S^{*}: W_{L} in mathcal{U}right}$ and $S_{L}^{*} = left{mathcal{U} in S^{*}: W_{L v} in mathcal{U}right}$

at the beginning of the proof the author asserts:

Each letter $lambda in L$ determines the substitution map $x mapsto x(lambda)$ from $W_{L v} cup W_{L}$ into $W_{L},$ which is clearly the identity on $W_{L}$ and which extends to a continuous homomorphism $mathcal{U} mapsto mathcal{U}(lambda)$ from $S_{L v}^{*} cup S_{L}^{*}$ into $S_{L}^{*}$, which is the identity on $S_{L}^{*}$

I’m assuming that the extension is given by the universal property of the
Stone–Čech compactification of $S$ since you can suppose that the substitution map
is continuous and has domain in $S$ and codomain in $beta S$. I can easily verify that the extension is a continuous function that maps $S_{L v}^{*} cup S_{L}^{*}$ into $S_{L}^{*}$ and that it is the identity on $S_{L}^{*}$ using the fact that the
extension given by the Stone–Čech compactification is

$$ mathcal{U}(lambda) = left{ B subseteq S | exists A in mathcal{U} left( A(lambda) subseteq B right) right}$$

I’ve been trying to prove that the extension is a homomorphism using the above equality but it gets very cumbersome and it is not clear how to prove it, I know that one inclusion would prove the equality (since they are ultrafilters) but i can’t prove either of the two so I think that is not the way to prove it, a hint would help me a lot