This problem occurred to me when I was solving problem 112 in A. Shen and N. K. Vereshchagin, Basic Set Theory (AMS 2002)), just as in this post Can this proof of existence of a Hamel basis using transfinite recursion be shortened/simplified? . So I will quote some parts from that post here.

Let $V$ be vector space with some partial order $\leq$ over it that is isomorphic to $\mathbb{R}$ with its standard ordering $\leq$.

Let be $f: V \to \mathscr{P}(V)$ such function that $$ f(x) = \begin{cases} \bigcup_{w < x} f(w) & \text{if } x \in \operatorname{span}\left(\bigcup_{w < x} f(w)\right) \\ \bigcup_{w < x} f(w) \cup \{x\} & \text{if } x \notin \operatorname{span}\left(\bigcup_{w < x} f(w)\right). \end{cases} $$

We could use the theorem from the book to prove that such function does exist if $\leq$ was well-order over $\mathbb{R}$:

Let $A$ be a well-ordered set, and $B$ an arbitrary set. Let a recursive rule be given, that is, a mapping $F$ whose arguments are an element $x \in A$ and a function $g: [0, x) \to B$, and whose value is an element of $B$. Then there exists exactly one function $f: A \to B$ such that $$ f(x) = F\big(x, f|_{[0, x)}\big) $$ for all $x \in A.$

But of course $\leq$ is not well-order over $\mathbb{R}$. So I think such function doesn't exist (in general case or maybe always, I'm not sure), but how to see and prove it?

  • 2
    $\begingroup$ If an order is not a well-order, we cannot use it for transfinite recursion and induction. See also math.stackexchange.com/questions/3874766/… $\endgroup$
    – Asaf Karagila
    Jan 4, 2021 at 20:00
  • $\begingroup$ If $\langle X,\le\rangle$ is a linear order, we can always define $f(x)=(\leftarrow,x]$ for $x\in X$: then $$\bigcup_{w<x}f(w)=(\leftarrow,x)$$ for each $x\in X$, so $$f(x)=(\leftarrow,x)\cup\{x\}=\left(\bigcup_{w<x}f(w)\right)\cup\{x\}$$ satisfies your condition. But this is not a definition by transfinite recursion, which requires a well-order. $\endgroup$ Jan 4, 2021 at 20:11
  • $\begingroup$ I think I used the wrong notation, I meant $x\in span(\bigcup_{w < x} f(w))$, no $x \in \bigcup_{w < x} f(w)$. But I think there is a function that satisfies my condition if the vector space is finite. And it's clear that in general we can't use transfinite recursion and induction if the the order is not well order. But is there any counter-example exact in my case? Such ordered vector space $V$ isomorphic to $\mathbb{R}$ that there's no such function? $\endgroup$
    – Julja Muvv
    Jan 4, 2021 at 20:31


You must log in to answer this question.