# Tagged Questions

Questions dealing with set-theoretic functions defined by transfinite recursion.

10answers
902 views

### What are the most prominent uses of transfinite induction outside of set theory?

What are the most prominent uses of transfinite induction in fields of mathematics other than set theory? (Was it used in Cantor's investigations of trigonometric series?)
3answers
3k views

### Need help with Recursion Theorem (Set Theory)

The recursion theorem In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem ...
1answer
280 views

### Convergence of the quadratic map $\left(x-\left(x-\left(x- \dots \right)^2 \right)^2 \right)^2$?

Edit - I changed the title and much of the body to better reflect my full question. The old one I don't really care about, although I appreciate Fabian's answer of course. Here is the plot for ...
2answers
237 views

### Is transfinite induction needed to remove all the elements from an uncountable set?

Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set? It seems like this can be thought of as an ...
1answer
241 views

### How to prove an extension of ZFC is conservative

Working in ZFC. I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...
1answer
390 views

### Epsilon induction

I recently came upon this technique called epsilon induction, and was searching for some proof using the same. But I saw no such proof. Does someone know of any proof using this technique?
1answer
92 views

### Is there continuous $f: [0, 1] \rightarrow [0, \infty)$ such that for all $x$ there is $y$ with $f(y) < f(x)$?

I think there isn't. Here's a sketch of a proof. I'm just not sure whether it really works because I'm not confident with the transfinite versions of the standard theorems about limits and convergent ...
2answers
342 views

### Showing there is only one isomorphism between well ordered sets using transfinite induction

I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,<_{1}\right)$ and $\left(B,<_{2}\right)$ there is only one isomorphism between them. To do ...
2answers
711 views

### Recursive Mapping

I was wondering about what is the general definition of a recursive mapping between any two sets. Is there a condition for a mapping to be able to be written in recursive form? Is the following claim ...
1answer
152 views

### Definition by Recursion

I just started studying logic, not as a course at a university, but as pastime. Since I do not study logic at an institution I use many different textbooks, including Enderton's $A$ $Mathematical$ ...
1answer
84 views

### Proving $V=V_{\sf On}$ in $\sf Z+Reg$

Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$ Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of ...
2answers
291 views

### Application of Transfinite Induction

Our teacher gave us for practice to prove some properties of $V(\alpha)$ defined as V(0) = \emptyset,\; V(S(\alpha)) = \mathcal{P}(V(\alpha)),\; Lim(\alpha): V(\alpha) = \bigcup\{V(\beta)\; |\; ...
3answers
168 views

### Which ordinals embed in $2^\omega$ ordered by inclusion?

Which ordinals can be embedded in the power set of $\omega$ ordered by inclusion? I see that $\omega\cdot\omega$ can (and therefore anything less than that): we can partition $\omega$ into $\omega$ ...
2answers
230 views

### Good resource to learn transfinite induction and/or recursion?

I'm currently reading John H. Conway's On Numbers and Games, but without a good understanding of transfinite induction and/or recursion, progress is very slow. What's a good resource for learning ...
1answer
99 views

### Constructing a Bernstein set in a Polish space

I just read the proof of how to construct two Bernstein sets in a Polish space $X$ using the facts that there are at most $2^{\aleph_0}$ many closed subsets if $X$ is Polish and that every closed ...
3answers
517 views

### What does $\upharpoonright$ in $G(F\upharpoonright\alpha)$ mean?

More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function $G\colon V\to V$, there exists a unique transfinite sequence $F\colon\mathrm{Ord}\to V$ (where ...
1answer
212 views

### Showing the existence of the $\omega_\omega$-th power set of $\omega$

Can you tell me if my answer is correct: Show that the set $P^{\omega_\omega}(\omega)$ exists. My answer: Let $P^0 (\omega) = \omega$, $P^{\alpha + 1}(\omega) = P(P^\alpha (\omega))$ and for a ...
2answers
100 views

### Can this proof of existence of a Hamel basis using transfinite recursion be shortened/simplified?

This is (I hope) a solution to Problem 112 in A. Shen and N. K. Vereshchagin, Basic Set Theory (AMS 2002). It is - I thought! - a semi-routine exercise, part of whose purpose is to enlighten the ...
1answer
52 views

### Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
1answer
348 views

### Transfinite recursion and Replacement

I have a question about the use of Replacement when proving the transfinite recursion theorem. It seems that the crucial use of Replacement is made in the step involving the set of all partial ...
1answer
187 views

### Question on the use of a parametric version of Transfinite Recursion Theorem in Introduction to Set Theory 3rd ed. by Hrbacek and Jech

My question concerns a proof given on page 118 in the text Introduction to Set Theory 3rd ed. by Hrbacek and Jech. The authors on page 117 prove a version of the transfinite recursion theorem ...
2answers
459 views

### Injection from the set of countable ordinals $\Omega$ into $\mathbb{R}$

I'm reading through this and I'd like to define an injective function from the set of countable ordinals $\Omega$ into $\mathbb{R}$ using transfinite induction (or maybe transfinite recursion?). ...
2answers
108 views

1answer
131 views

### Initial Segment Order Isomorphic to the Ordinal Numbers

Prove that every well-ordered proper class has an initial segment order isomorphic to the ordinal numbers, ON. I have a plan to prove this but it uses a recursive definition and induction which I do ...
2answers
72 views

### Principle of Proof by Induction on a Well-ordering

Let $(X,\leq)$ be a woset (well ordered set). Let $E$ be a subset of $X$ such that: (i) the smallest element of $X$ is a member of $E$ (ii) for any $x\in X$, if $y<x\rightarrow y\in E$, then ...
2answers
42 views

### closed form iterated logarithms

Is there any way that we could bound the following sum by a closed form expression $\sum_{i=1}^{\log^* N} \log^{(i)}N$ where $\log^{(i)}$ is the $\log$ function iterated $i$ time? Thanks
1answer
76 views

### The Definition of Definition by Recursion

The following is presented as the Transfinite Recursion on well-founded relations in Kenneth Kunen's book. Assume that $R$ is set like and well founded on $A$ and ...
1answer
84 views

1answer
30 views

### Transfinite induction under an ordinal $\delta$

Can anyone gove me a hint or a direction to the proof of this statement? Let $F:V \rightarrow V$ be an operation, and $\delta$ an ordinal. Prove, that there exists a unique function $g$ with domain ...
1answer
142 views

### Equivalent statement of transfinite/ordinal recursion

I am trying to prove that the "standard" statement of transfinite/ordinal recursion: "Suppose $G$ is a definite operation on partial functions on ordinals. Then there is a unique definite operation ...
1answer
340 views

### Transfinite induction vs transfinite recursion

Let $\mathfrak{A}$ is a well-ordered set. Let $f$ is a function which maps a start segment $\{ i\in\mathfrak{A} \,|\, i<c \}$ of a transfinite sequence of elements of atomic posets into an element ...
1answer
35 views

0answers
28 views

### How to iterate a function 8 times about a given interval of x in a Discrete Dynamical System

This is Dynamical Systems, specifically a discrete system. We are using L and R as in Left and Right such as: L=[0,0.5] R=(0.5,1] and LL=[0,0.25] LR=(0.25,0.5] and so on like that. We keep ...
1answer
41 views

### uncountable repetitions

I have a question (or two) about recursive naming conventions. Consider the following recursive naming sequence: Base step: Let S be any nonempty set. Let x be any arbitrary element of S. Let S* be ...
1answer
37 views

### Is it possible to extend the set-inclusion order of a power set to a well-ordering?

The original aim is to define recursively a function on the power set of a set such that the functional value of a subset is determined by those of its proper subsets. Thank you.