I am very confused about how to interpret the following.
If we write $\{0,1\}^{+}$=$\cup_{n \in \mathbb{N}} \{0,1\}^{n}$
then I am told that elements of $\{0,1\}^{+}$ are called words and subsists of it are called languages,
Then I was asked,
if we consider $$g: P( \{0,1\}^{+}) \to P( \{0,1\}^{+})$$ defined as
$g(X)=X \cup \{w01:w \in X\} \cup \{\tau\}$
where $\tau$ represents the word of zero length, then find the least fixed point of g ordered by inclusion.
I have been trying to make sense of it but cant make progress. I know that a fixed point is an element $X$ such that $g(X)=X$
I know that since we want the least, the fixed point has to be less then any other fixed points ordered by inclusion to.
Can anyone help to make sense of this? Thank you
Think of the function $g$ as a way to expand a language: you feed it a language $L$, and it spits out a bigger language $L'$ (bigger in the sense that $L\subseteq L'$).
For example, consider the function $h$ given by $h(L)=\{\sigma: \sigma\in L\mbox{ or }\sigma=001011101\}.$ This takes a language, and enlarges it by adding the string $001011101$. The least fixed point of $h$ is the language $M=\{001011101\}$; clearly $h(M)=M$ (all $h$ does is add something already in $M$), so $M$ is a fixed point of $h$.
Now, I claim that $M$ is in fact the least fixed point of $h$. Why? Well, suppose $X$ is a fixed point of $h$ - that is, $h(X)=X$. Then $001011101\in X$, since $001011101\in h(X)$ by definition of $h$ and $h(X)=X$. But this means $M\subseteq X$.
Here's another one: $j(L)=L\cup\{\sigma^\smallfrown\tau: \sigma,\tau\in L\}$. This $j$ takes in a language, and spits out the language consisting of everything that's either already in $L$, or can be gotten by putting two things in $L$ together. For instance, if $L=\{0\}$, then $j(L)=\{0, 00\}$ and $j(j(L))=\{0, 00, 000, 0000\}$.
The least fixed point of $j$ is the empty language, $\emptyset$. Why? Well clearly $\emptyset\subseteq X$ for any fixed point $X$ of $j$ (since $\emptyset$ is a subset of everything); and $\emptyset$ is a fixed point of $j$.
Note that each of the examples above can be gotten by starting with the empty language, and applying the "enlarger" in question. In both these cases, we only needed to apply the enlarger once. This isn't true in general: consider the map $k(L)=L\cup\{0\}\cup\{\sigma\smallfrown\tau: \sigma,\tau\in L\}$. Then:
$k(\emptyset)=\{0\}$.
$k(\{0\})=\{0, 00\}$.
$k(\{0, 00\})=\{0, 00, 000, 0000\}$.
It doesn't look like we're going to get a fixed point this way . . .
. . . but we can take the "limit" of these stages! Let $M_0=\emptyset$, $M_{n+1}=k(M_n)$, and $$M=\bigcup_{n\in\mathbb{N}} k(M_n).$$ Can you figure out what $M$ is? (HINT: see if you can figure out what $M_n$ is for each $n$, first . . .) Can you see why $M$ is the least fixed point of $k$?
Hopefully this makes it more clear what the problem is asking. Try to find the least fixed point of your example function analogously to $k$, above!