Class of sets is a semiring, but not a ring

Question

Let $E$ be a nonempty finite set and let $\Omega:=E^\mathbb{N}$ be the set of all $E$-valued sequences $(w_n)_{n\in{\mathbb{N}}}$. For any $w_1,...,w_n\in E$, let $[w_1,...,w_n]_:=\{w'\in\Omega\colon w_i'=w_i,\ \forall i=1,..,n\}$ be the set of all sequences whose first $n$ values are $w_1,...,w_n$. Let $\mathcal{A}_0=\{\emptyset\}$ and define

$\mathcal{A}_n:=\{[w_1,...,w_n]\colon w_1,...,w_n\in E\}$

Finally, let $\mathcal{A}:=\bigcup_{n=0}^\infty \mathcal{A}_n$

I tried to show that this is a semiring, but not a ring for $|E|>1$.

Definition: A class of sets $\mathcal{A}\subset 2^{\Omega}$ is called a semiring if

• $\emptyset \in \mathcal{A}$
• for any two sets $A,B\in\mathcal{A}$, the difference set $B\setminus A$ is a finite union of mutually disjoint sets in $\mathcal{A}$
• $\mathcal{A}$ is closed under finite intersections.

First, the closed intersection: I pick two elements of $\mathcal{A}$, being $\mathcal{A}_n$ and $\mathcal{A}_m$ for which i assume that $n<m$. But no elements $\omega_n = [w_1,...,w_n], \omega_m=[w_1,...,w_m]$ are identical. To see this, consider elements of $[w_1,...,w_m]$ which are identical up to index $n$ (for elements not identical up to $n$ the intersection is empty). In $[w_1,...,w_m]$ we still have indices $w_{n+1},...,w_{m}$ which are fixed for all elements in $[w_1,...,w_m]$, but not for the ones in $[w_1,...,w_n]$. Thus, no two $\omega_n, \omega_m$ are identical and $\mathcal{A}_n\cap\mathcal{A}_m=\emptyset\in\mathcal{A}$.

A similar argument holds for the second condition, where we always have that for $\mathcal{A}_n,\mathcal{A}_m\in\mathcal{A}, \ n\le m$ that $\mathcal{A}_n\setminus\mathcal{A}_m=\emptyset$

The first condition is trivial, since it follows from the definition of $\mathcal{A}_0$.

Is my reasoning correct?

Now I want to show that $\mathcal{A}$ is a ring for $|E|>1$. For this it is enough (from what I have shown so far), to disprove the closedness under unions. I will not make a rigorous proof for this, but only say that the union of two $\mathcal{A}_n,\mathcal{A}_m$ will have elements which can not be produced by a another single $\mathcal{A}_l$.

Is this in principle correct?

Answer 1

You are confusing $\bigcup \mathcal A_n$ with $\bigcup \{\mathcal A_n\}$. The elements of $\mathcal A=\bigcup_\Bbb N \mathcal A_n$ (as you defined it) are the sets $x$ such that $x\in\mathcal A_n$ for some $n\in\Bbb N$. In other words, $\mathcal A$ consists of the sets $[w_1,\dots,w_n]$ such that $n\in\Bbb N$ and $w_i\in E$ for each $i$. So we have that $\mathcal A_n\subseteq\mathcal A$, and not that $\mathcal A_n\in\mathcal A$.

We can check the three conditions for being a semiring:

1. We have $\varnothing\in \mathcal A$, since $\varnothing\in\mathcal A_0\subseteq\mathcal A$.

2. Let $n\leq m$, and let $W=[w_1,\dots,w_n]\in\mathcal A_n$ and $V=[v_1,\dots,v_m]\in\mathcal A_m$, then these are elements of $\mathcal A$. We want to show that $W\setminus V$ and $V\setminus W$ are both finite unions of disjoint sets in $\mathcal A$.

   • Let's start with the case where $w_i\neq v_i$ for some $i\leq n$. Then $[w_1,\dots,w_n]\cap[v_1,\dots,v_m]=\varnothing$, and thus $W\setminus V=W=\bigcup\{W\}$ and $V\setminus W=V=\bigcup\{V\}$

   • In the other case $w_i=v_i$ for each $i\leq n$, and thus $V\subseteq W$. This gives us that $V\setminus W=\varnothing=\bigcup\{\varnothing\}$. On the other hand, the set $W\setminus V$ is now the union of the sets $[w_1,\dots,w_n,u_{n+1},\dots,u_m]$ such that $u_{i}\neq v_i$ for some $n<i\leq m$. How many of these sets are there? Well, there are $|E|^{m-n}$ sequences $u_{n+1},\dots,u_m$, and only one of them is equal to $v_{n+1},\dots,v_m$, thus there are $|E|^{m-n}-1$ of such sets. Since $|E|$ is finite, and all $[w_1,\dots,w_n,u_{n+1},\dots,u_m]$ are disjoint from each other, we see that $W\setminus V$ is the union of a finite family of disjoint sets.

3. Again, let $n\leq m$, and let $[w_1,\dots,w_n]\in\mathcal A_n$ and $[v_1,\dots,v_m]\in\mathcal A_m$, then there are two possibilities:

   • $w_i\neq v_i$ for some $i\leq n$. We saw that $[w_1,\dots,w_n]\cap[v_1,\dots,v_m]=\varnothing$, and this is an element of $\mathcal A$.
   • $w_i=v_i$ for every $i\leq n$. In this case you will see that $[v_1,\dots,v_m]\subseteq[w_1,\dots,w_n]$, giving that $[w_1,\dots,w_n]\cap[v_1,\dots,v_m]=[w_1,\dots,w_n]$, which is in $\mathcal A$.