Let $\Gamma$ be a finite set, $\Omega=\Gamma^{\mathbb{N}}=\left\{(x_1,x_2,\ldots):~\forall i\in\mathbb{N} x_i\in\Gamma\right\}$. For $a_1,\ldots,a_N\in\Gamma$ let $$ [a_1,\ldots,a_N]:=\left\{(x_1,x_2,\ldots)\in\Gamma^{\mathbb{N}}: i=1,\ldots,N x_i=a_i\right\} $$ be the $N$-cylinder which is determined by $a_1,\ldots,a_N$. Define $$ \mathfrak{Z}_N:=\left\{[a_1,\ldots,a_N]: a_1,\ldots,a_N\in\Gamma\right\}. $$ Show, that then $$ \mathfrak{S}:=\bigcup_{N=1}^{\infty}\mathfrak{Z}_N\cup\left\{\emptyset\right\} $$ is a semi-ring for $\Omega$.


Three things are to show:

(1) $\emptyset\in\mathfrak{S}$

(2) $A,B\in\mathfrak{S}\implies A\cap B\in\mathfrak{S}$

(3) $A,B\in\mathfrak{S}$ and $A\subset B\implies~\exists A_1,\ldots,A_n\in\mathfrak{S}$ pairwise disjoint, so that $B\setminus A=A_1\cup\cdots\cup A_n$.

Proof. (1) is clear by definition of $\mathfrak{S}$.

(2) $A\in\mathfrak{S}$, i.e. $A=[a_1,\ldots,a_N]$ for a $N\in\mathbb{N}$ and $a_1,\ldots,a_N\in\Gamma$. $B\in\mathfrak{S}$, i.e. $B=[b_1,\ldots,b_M]$ for a $M\in\mathbb{N}$ and $b_1,\ldots,b_M\in\Gamma$. To my opinion then $$ A\cap B=\begin{cases}A, & N\leq M\wedge a_i=b_i, i=1,\ldots,N\\B, & M\leq N\wedge b_i=a_i, i=1,\ldots,M\\\emptyset, & \text{otherwise}\end{cases} $$ and $A,B,\emptyset\in\mathfrak{S}$.

(3) $A,B\in\mathfrak{S}, A\subset B$. If $A\subset B$, this means for $A=[a_1,\ldots a_N]$ and $B=[b_1,\ldots,b_M]$ that $N\leq M$ and $a_i=b_i, i=1,\ldots,N$. I am not sure, but to my opinion then $B\setminus A=\emptyset$. And so $B\setminus A$ can be writte as disjoint union of ONE set, namely the emptyset.

Would be great to know if my proof is ok.



Your last point is not totally right, because if we have $A\subset B$, then $M\leq N$ (where the notation is the same as yours).

However, acording to this definition of semi ring, the third condition doesn't require that $A\subset B$ (I don't see right now if they are equivalent formulations, but I'll work in the more general outset). So, let $A, B \in \mathfrak{S}$ and let $A=[a_1,\ldots a_N]$ and $B=[b_1,\ldots, b_M]$. Assume without loss of generality, that $N\leq M$. If $a_i=b_i$ for every $1\leq i\leq N$, then $B\subset A$ and we have that $B\setminus A=\emptyset$ If $b_i\neq a_i$ for some $1\leq i\leq N$ then all the sequences in $B$ have as its $i$-the entry $b_i$ and all the sequences in $A$ have as its $i$-the entry $a_i$, so $A$ can't share any sequence with $B$ and we would have $B\setminus A=B$.

I don't see a flaw in your other points, so I think they are right.

  • $\begingroup$ The OP definitely works with this definition. $\endgroup$ – drhab Oct 28 '16 at 15:58

On 3:

I preassume that $\Gamma$ has at least $2$ elements.

Then $\left[a_{1},\dots,a_{N}\right]\subseteq\left[b_{1},\dots,b_{M}\right]$ implies that $M\leq N$ and $a_{i}=b_{i}$ for every $i\in\left\{ 1,\dots,M\right\} $.

So actually we have $\left[b_{1},\dots,b_{M}\right]=\left[a_{1},\dots,a_{M}\right]$.

If $\Delta:=\Gamma^{N-M}\setminus\left\{ \left[a_{M+1},\dots,a_{N}\right]\right\} $ then $\Delta$ is a finite set (since $\Gamma$ is) and we can write:


The RHS is a disjoint union of cylinder sets.

Another question brought me to this question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.