Prove that if A is countable, then so is $cl_f(A)$.

106 Views Asked by At

Let B be a set and $f:B^m \rightarrow B$. By definition, given a subset $A \subseteq B$, the closure of $A$ under $f$, denoted by $cl_{f}(A)$, is the smallest subset of $B$ which contains $A$ and is closed under $f$.

Prove that if A is countable, then so is $cl_f(A)$.

My question is, how do I define a function such that $cl_f(A) \mapsto A$.

1

There are 1 best solutions below

0
On

You won't be able to find such a function (I presume you want an injective one, since otherwise you don't get anything out of it). To see this, suppose $B=\mathbb{N}, m=1, f(x)=x+1,$ and $A=\{1\}$. Then $cl_f(A)=\mathbb{N}$, while $A$ itself of course is finite.

The argument that $cl_f(A)$ is countable if $A$ is will have to be more abstract. For simplicity, let's assume that $m=1$ - so $f:B\rightarrow B$. The closure $cl_f(A)$ can be broken up as follows:

  • Let $A_0=A$.

  • Having defined $A_n$, let $A_{n+1}=\{f(x): x\in A_n\}$.

We can now show (exercise) that $cl_f(A)=\bigcup_{n\in\mathbb{N}} A_n$.

Now we use the important fact (exercise) that the union of countably many countable sets is countable. Together with the previous point, this tells us that it will be enough to show that each $A_n$ is countable.

So now the question is, how do we do that? The answer is induction: we want to prove, by induction on $n$, that $A_n$ is countable. For $n=0$ it's true by assumption (remember $A_0=A$).

Now suppose $A_n$ is countable; how do we know that $A_{n+1}$ is also countable? This is going to follow from the following more general fact (exercise): that if $X\subseteq B$ is countable, then $\{f(x): x\in X\}$ is countable. This is sort of the "one-step" version of the thing you're actually trying to prove; note that in general $\{f(x): x\in X\}$ is much smaller than $cl_f(X)$.

So that's how the proof will go:

  • Show how we can decompose $cl_f(A)$ into countably many pieces.

  • Prove that the "one-step closure" of a countable set is countable.

  • Use that to show by induction that each piece of $cl_f(A)$ is countable, if $A$ itself is.

  • Finish using the fact that a countable union of countable sets is countable.


Note that the exercises above are really of two distinct flavors. The second and third are directly about the manipulation of countable sets, while the first is really about finite sets (or rather, finite sequences).

Note also that the first and third exercises become more complicated when we go from $m=1$ to the general case. In particular, the general version of the third exercise is an application of a stronger version of the second exercise: that if I take the finite Cartesian product of countable sets, the result is still countable. (It's a good exercise to show that the word "finite" is necessary there: show that the Cartesian product of $\mathbb{N}$-many copies of $\{1, 2\}$ is uncountable.)