Least fixed point of a function

161 Views Asked by At

Consider the function $f:\mathcal{P}(\{0,1\}^*)\to\mathcal{P}(\{0,1\}^*)$ defined as: $$f(X)=X\cup\{w01:w\in X\}\cup\{\epsilon\}$$ Where $\epsilon$ denotes a word of length 0. Find the least fixed point of $f$ on $\mathcal{P}(\{0,1\}^*)$ ordered by inclusion.
I cannot convince myself that this function even has a fixed point, since feeding any set of words to it would cause it to output twice as many words (the original input, plus every word from the original with 01 appended to the end). Is my reasoning incorrect?

1

There are 1 best solutions below

0
On

Or even more pertinent in this case - think of the Hilbert Hotel.

EDIT: Meant for this to be a comment but I can't delete! So I'll flesh out a little more.

What can you make your set $X$ so that $X$ and $01X$ coincide almost exactly? If you have a $01$ and a $0101$ in $X$, you won't quite be doubling the size, will you?