Let $R$ be a semiring. For $a\in R$,we define $t_a(x)=x+a$ for all $x\in R$.
Prove that $R$ is idempotent(with +) and $1$ has an infinite order if and only if for all $a,x,y\in R$, $t_a(x+y)=t_a(x)+t_a(y)$ and $t_a(xy)=t_a(x)t_a(y)$. Give an example of an infinite semiring with this property.
I've tried something with the definition, but as it's a semiring, there's no "$-a$", i.e., the inverse of an element doesn't exist. Can you help me, please?
Note that $t_a(0) = 0 + a = a$. So, $a + a = t_a(0) + t_a(0) = t_a(0 + 0) = t_a(0) = a$. Thus, $R$ is idempotent, whenever the property $t_a(x + y) = t_a(x) + t_a(y)$ is satisfied.
Conversely, if $R$ is idempotent, then $$t_a(x) + t_a(y) = (x + a) + (y + a) = (x + y) + (a + a) = (x + y) + a = t_a(x + y).$$ So, this condition is equivalent to idempotency.
Idempotent semirings are also known as dioids. With respect to the natural partial order, which is given equivalently as $$x ≤ y ⇔ y ≥ x ⇔ ∃z(x + z = y) ⇔ x + y = y,$$ all the semi-ring operations are monotonic; i.e. if $x ≤ x'$ and $y ≤ y'$ then $xy ≤ x'y'$ and $x + y ≤ x' + y'$.
The other condition $t_a(xy) = t_a(x) t_a(y)$ is just $xy + a = (x + a)(y + a) = xy + xa + ay + a^2$. Setting $x = 0 = y$ entails $a = a^2$. Setting just $x = 0$ or $y = 0$ shows, respectively, that $a = ay + a$ and $a = xa + a$, i.e., that $ay ≤ a$ and $xa ≤ a$. In either case, setting $a = 1$, shows that $x ≤ 1$ and $y ≤ 1$, respectively, thus making $1$ the maximal element of the dioid.
Conversely, suppose $1$ is maximal in a dioid. Then $ay ≤ a$ and $xa ≤ a$, since the product is monotonic (thus, also $a^2 ≤ a$). Therefore, $$(x + a)(y + a) = xy + ay + xa + a^2 ≤ xy + a + a + a = xy + a,$$ since the sum is monotonic and idempotent.
Suppose also that the dioid has the property $a ≤ a^2$. Then $$xy + a ≤ xy + a^2 ≤ xy + ay + xa + a^2 = (x + a)(y + a).$$ Then it follows that $xy + a = (x + a)(y + a)$.
So, in dioids, the second condition $t_a(xy) = t_a(x) t_a(y)$ is equivalent to the identities $a = a^2$ (or just $a ≤ a^2$) and $a ≤ 1$; i.e. that the product be idempotent and that $1$ be maximal.
Example: $C_2$
Consider the dioid generated freely from $\{b,d,p,q\}$, subject to the identities, $bd = 1 = pq$, $bq = 0 = pd$, $db + qp = 1$. Call it $C_2$.
Not only is it infinite, but it has no finite-dimensional matrix representations. Why? Because it completely engulfs all of its own matrix (and vector) algebras as subalgebras. For instance, the $2×2$ matrix algebra is contained isomorphically within the algebra via the correspondence $$A ⇔ d A_{00} b + d A_{01} p + q A_{10} b + q A_{11} p.$$ Matrices of sizes $m×n$ are similarly embedded within the dioid, and only as strict subalgebras, unless $m$ and $n$ are both powers of $2$.
This algebra is involutive, with the involution operation $a ↦ a^†$, generated by $b^† = d$, $p^† = q$ and $d^† = b$, $q^† = p$. So, one can talk meaningfully about projections, i.e. elements $x$ for which $x^† = x = x^2$.
The projections of interest, here, are $1$, $db$, $qp$, $ddbb$, $dqpb$, $qdbp$, $qqpp$, etc. In each case, by virtue of $db + qp = 1$, we have $db ≤ 1$ and $qp ≤ 1$. Iterating this yields the other identities, e.g. $dqpb ≤ d(1)b = db ≤ 1$, and so on.
These projections are closed under products and sums, since no two of them have a non-zero product unless they in a $≤$ relation with one another. Therefore, the subdioid of $C_2$ generated by all of these projections yield an example of an infinite dioid with $1$ as a maximal element and idempotent products.
An example of where the full algebra $C_2$, itself, is used: take the free Kleene algebra generated by the set $X = \{u,v\}$. This a is dioid closed under sums of the form: $$x^* = 1 + x + x^2 + x^3 + ⋯,$$ which is referred to as star-completeness, and is distributive with respect to the infinite sum: $$wx^*y = wy + wxy + wx^2y + wx^3y + ⋯$$ which is referred to as star-continuity.
Infinite sums in a dioid are defined as the supremum or least upper bound with respect to the natural partial order.
Such an algebra is called a *-continuous (and *-complete) Kleene algebra, and the free Kleene algebra generated from the set $X$ is none other than the algebra of regular expressions over the "alphabet" $X$.
Attach $C_2$ to this algebra, and impose the extra conditions $xy = yx$ for $x ∈ X$ and $y ∈ \{b,d,p,q\}$. Then, by virtue of these identities and *-continuity, one has the ability to represent all context-free languages over $X$. For instance, $\{1,uv,uuvv,uuuvvv,⋯\}$ is given by the context-free expression $b(up + qv)^*d$, as you can plainly see by applying star-continuity to this expression and simplifying each monomial. The only ones that don't cancel out to $0$ are those with an equal number of $u$'s and $v$'s in them, with all the $u$'s preceding all of the $v$'s. Equivalently, a context-free expression for it can be generated directly from the grammar $$S → u S v, S → $$ as the following: $$<0|<S| (\hat H + \hat X)^* |0>$$ where $$\hat H = |S>(<v|<S|<u| + 1),\\\hat X = |u>u + |v>v,$$ with the "bra-ket" algebra (which is a copy of $C_4$) represented as: $$<0| = bb, <S| = bp, <u| = pb, <v| = pp$$ and $$|0> = dd, |S> = qd, |u> = dq, |v> = qq$$ so that expression, written explicitly in terms of $C_2$ would be: $$bb bp (qd (pp bp pb + 1) + dq u + qq v)^* dd.$$
In that case, the expansion of the powers $<0|<S| (\hat H + \hat X)^n$, for $n = 0, 1, 2, ⋯$ yield all the length $n$ top-down derivation sequences with respect to the indicated grammar. The projection operators indicate the possible left-most contexts of the parser state at the given point.