# Repeating an algorithm uncountably many times

Consider $f \equiv 0$ on $I = [0,1]$. Define the equivalence class of functions, $X$, that are equal to $f$ almost everywhere (this is indeed an equivalence class). In this equivalence class, we have for any $E \subset [0,1]$ such that $m(E) = 0$,

$$\chi_E(x) = \begin{cases}1 & x \in E \\ 0 & x \not \in E \end{cases}$$

and clearly $\chi_E \sim f \implies \chi_E \in X$. Moreover, given $E_1, E_2 \subset I$ both of measure zero, we know that $\chi_{E_1 \cup E_2} \in X$. What if we repeat this process uncountably many times for some well-ordered set $\{E_{a}\}$, verifying at each step that $\chi_{G_{b}} \in X$ (where $G_{b}$ is the aggregate set up through $E_{b}$, so that $G_{b} = E_{a_1} \cup E_{a_2} \dots \cup E_{b}$ obeying the well-ordering of the uncountable set), but so that for

$$G = \cup_a E_a \implies m(G) > 0$$

and we stop when $G_b$ reaches $G$ by this process of including more sets $1$ by $1$ in this uncountable induction. Then the equivalence relation no longer holds.

I have a feeling this isn't so much a measure theory question, but rather a question of countability and uncountability and infinite induction. I think my question boils down to: can algorithms like the above be repeated uncountably many times and still have meaning?

I would appreciate it if someone can fill in the technical details I'm missing about uncountable induction, and how this prevents a contradiction.

• Can you not traverse a well-ordered, uncountable set in a "one by one" manner? You take the smallest element, perform the algorithm, and then repeat for the index set minus that smallest element. – J. Marx-Kuo Sep 13 '16 at 23:45
• How is an uncountable set exhausted? I thought this was the purpose of a well-ordering. If you know of a formal source on this I would be grateful – J. Marx-Kuo Sep 13 '16 at 23:53
• Even if this argument were valid just for countable sets, couldn't you use it to prove that every countable set is finite? – stewbasic Sep 14 '16 at 0:12
• Maybe if we assume that the process terminated, but I'm not sure if equating "exhausting the set of indices" to the "process terminates" (the latter of which can only happen in finite time) is valid – J. Marx-Kuo Sep 14 '16 at 0:17
• What do you mean by $f \equiv 0$ (right at the beginning of your question)? – Rob Arthan Sep 14 '16 at 0:22

So $X$ is the set of functions on $I$ that are $0$ almost everywhere and your "process" takes the characteristic functions of two sets $E_1$, $E_2$ of measure $0$ and returns the characteristic function of their union $E_1 \cup E_2$. It's meaningful to think about iterating this process transfinitely, but you will never reach a fixed point: if $E$ has measure $0$ then you can always find a larger set $E' \supset E$ that also has measure $0$. To get a fixed point, you would need to apply Zorn's lemma, but that is not possible since the union of an arbitrary chain of measure $0$ subsets can have positive measure.
• It means a point where your process can no longer construct anything new, so that the abstract description of the overall process is complete. E.g., think about solving the recursion equations: $f(0) = 1; f(n+1) = nf(n)$ by slowly building up the graph of $f$ by partial approximations. – Rob Arthan Sep 14 '16 at 1:17
• Your process can't have a fixed point: a fixed point would be a set of measure zero that can't be extended to a larger set of measure zero. Such a set cannot exist in a measure space like the usual measure on $[0, 1]$. – Rob Arthan Sep 14 '16 at 19:49