Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [transfinite-recursion]

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

0
votes
0answers
44 views

question about transfinite induction [on hold]

First, by $c$ I mean the continuum Define, by induction, a sequence $\{D_\zeta\colon \zeta<c\}$ of subsets of $\\R$ such that $ D_\zeta=\{x_\eta:\eta<c\}.$It is easy to see the following ...
-1
votes
0answers
26 views

$\omega$th iteration of Cayley-Dickson construction

The first nine Cayley-Dickson hypercomplex algebras are real (1D), complex (2D), quaternion (4D), octonion (8D), sedenion (16D), pathion (32D), chingon (64D), routon (128D), and the voudon (256D) -...
0
votes
0answers
27 views

About transfinite recursion

Transfinite recursion: If $F: V \to V$ is a class function, then there is a unique $G : ON \to V$ such that $G(\alpha) = F(G \restriction \alpha)$ for all ordinals $\alpha$. How from this theorem (...
0
votes
2answers
62 views

How do Hrbacek and Jech derive the class function $F$ in Theorem 4.12 from Theorem 4.11? [duplicate]

My question is about a proof of Theorem 4.12 given in the text Introduction to Set Theory by Hrbacek and Jech. Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, ...
0
votes
1answer
80 views

Are these two parametric versions of Transfinite Recursion equivalent?

Although I'm able to prove $S_1\implies S_2$ with not much difficulty, I failed to prove $S_2\implies S_1$ after several attempts. In particular, I can not handle the case in which $F(z,\alpha+1)=G_2(...
1
vote
2answers
38 views

Are these two statements regarding Transfinite Recursion equivalent?

I have two statements regarding Transfinite Recursion quoted below. It's clear that $S_1$ is the usual Transfinite Recursion Theorem. Let $V$ be the class of all sets, $\operatorname{Ord}$ be the ...
1
vote
2answers
49 views

Is this theorem equivalent to Transfinite Recursion Theorem?

Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, and $G:V\to V$ be a class function. Transfinite Recursion Theorem: There exists a class function $F:\...
0
votes
0answers
31 views

4 equivalent statements of Transfinite Recursion

I'm trying to prove that four versions of Transfinite Recursion below are actually equivalent, i.e. $1\implies 2\implies 3\implies 4\implies 1$. While I'm able to prove $1\implies 2$ and $3\implies 4$,...
1
vote
2answers
60 views

How do the authors deduce this weaker version of Transfinite Recursion?

My question is about a proof of Theorem 4.12 given in the text Introduction to Set Theory by Hrbacek and Jech. The authors first prove Theorems 4.9, 4.10, and 4.11. For reference, I quote these ...
1
vote
0answers
49 views

A bootstrap from the traditional version of Transfinite Recursion to the parametric one

I'm self-learning Transfinite Recursion Theorem and its variants from textbook Introduction to Set Theory by Hrbacek and Jech. After the authors have presented proofs of theorems 4.9, 4.10, and 4.11, ...
1
vote
1answer
34 views

The role of Axiom Schema of Replacement in the proof of Transfinite Recursion Theorem

Transfinite Recursion Theorem: Let $G:V\to V$ be a class function. Then there is a unique function $F:\operatorname{Ord}\to V$ such that $$\forall \alpha\in \operatorname{Ord}:F(\alpha)=G(F\...
0
votes
3answers
48 views

A Proof of Transfinite Recursion Theorem

This proof takes me a huge amount of time to formulate, so I hope that someone can help me verify it. There're possibly subtle mistakes that I'm unable to recognize. Thank you for your dedicated help! ...
0
votes
1answer
31 views

Strong induction with recursive definition function

Look at following recursive function definition for function $F :\mathbb{N}​\times\mathbb{N}​ \to \mathbb{N}$​: $$ \begin{split} F(x,0) & = 0\\ F(x,n) & = x + F(x, n-1) \end{split} $$ Prove ...
0
votes
1answer
43 views

Applying transfinite recursion

Let $f\colon\alpha\to\beta$ be a function between ordinals $\alpha,\beta$. I want to define a function $g\colon\alpha\to\gamma$ for some ordinal $\gamma$ so that $(\forall \eta < \alpha)(g(\eta) =...
0
votes
1answer
54 views

What does a hyperreal version of the Cantor Set look like?

I would like to construct a hyperreal version of the Cantor set. Let $X_0$ be the interval $[0,1]$ in the hyperreal line, and for any $n$, let and let $X_{n+1}$ be the set of hyperreal numbers ...
3
votes
3answers
97 views

How to formally use transfinite recursion to construct a sequence for a proof of Zorn's lemma

I'm trying to get my head around how to prove that the axiom of choice implies Zorn's lemma using transfinite recursion: Transfinite recursion I Let $G$ be a class function. Then there is class ...
5
votes
2answers
126 views

Finding a well-ordering of the natural numbers of a given order type

Let $X$ be the set of all well-orderings of the set of natural numbers, and let $O$ be the set of countable ordinals, i.e. the set of ordinals that are order types of the well-orderings in $X$. Then ...
4
votes
1answer
99 views

Contents of Gentzen's consistency proof of PA

It is surprising that there is lack of information on Gentzen's consistency proof - sure, there are some contents on Gentzen's first consistency proof of Peano axioms, but not on what we usually say ...
1
vote
1answer
16 views

The components are the transfinitely iterated stationary quasicomponents

I read that if we have a topological space $(X,\tau)$, $x\in X$, if we define $C$ as the component of $x$ and $Q$ as the quasicomponents of $x$, we have the well known relations $C\subseteq Q$, so I ...
0
votes
0answers
8 views

Invariant probability of a map

I've to found the invariant probability of this map: $$x_{t+1} = x_{t}+\frac{3}{4}, 0 \leq x < \frac{1}{4}$$ $$x_{t+1} = x_{t}+\frac{1}{4}, \frac{1}{4} \leq x_{t} < \frac{1}{2}$$ $$x_{t+1} = ...
1
vote
1answer
52 views

what is the difference between $\aleph_0$ and $ \beth_0$

I have been looking at the difference between $\aleph_0 $ and $\beth_0$ and I cant conclude the difference. Any help will be much appreciated Thanks in advance
2
votes
1answer
52 views

“Recursively” expressing continuous-time trajectories

I am interested in functions of time I call "trajectories" $h$, each in an arbitrary codomain $D$. $D$ is a set. I wish to express that these trajectories are determined by an initial condition $h_0$ ...
1
vote
0answers
116 views

The Veblen Hierarchy named with uncountable ordinals vs ordinal collapsing functions

I recently came across Feferman's original $\theta$ function. I understood the idea behind it. But to get a better idea of the growth I compared it with the Veblen function. When the multi-variable-...
4
votes
1answer
46 views

Does there exist a weakly increasing cofinal function $\kappa \to \kappa$ strictly below the diagonal?

Let $\kappa$ be an infinite cardinal. Does there always exist a function $f: \kappa \to \kappa$ such that $f$ is weakly increasing ($f(\alpha) \leq f(\beta)$ for $\alpha \leq \beta < \kappa$) $f$ ...
1
vote
1answer
128 views

Better bounds on my ordinal hyperoperators

I've defined some ordinal hyperoperators as follows: $$a\{b\}c=\begin{cases}a+1,&b=0{\rm~or}~c=0\\\sup\{(a\{b\}x)\{y\}a:x<c,y<b\},&\text{else}\end{cases}$$ For $a$ and $c$ that satisfy ...
2
votes
0answers
26 views

Fractran program size

On the subject of lower and upper bounds of John H. Conway's Fractran program size, if you tried to evaluate these using the pumping lemma, couldn't you create an infinity of fractions evaluating the ...
0
votes
1answer
40 views

Question about defining sequence via transfinite induction.

I have sequence $A_i$ where $i\in\mathbb{N}$ and every $A_i$ is countable. Let $A=\bigcup_{i\in\mathbb{N}}A_i$. I want to find new sequence of countable subsets of $A$ such that $C_i\subseteq A_i$ ...
1
vote
1answer
71 views

How does my modified ordinal hierarchy relate to other ordinal hierachies?

I was working on my answer for Golf a number bigger than TREE(3) and I realized I couldn't use The Hardy Hierarchy in the way wanted to. So I defined a slightly modified version: $$H'_0(n)=n+1$$ $$H'_\...
3
votes
1answer
44 views

At what steps is Replacement required in definitions by Transfinite Recursion?

I am trying to pin-point where Replacement is required in a specific definition by Transfinite Recurson. In the general proof of the Transfinite Recursion Theorem, it is noted that Replacement is used ...
1
vote
0answers
40 views

How to find the period of this chaotic map for $x_0=\sqrt{M}$?

Pick $x_0 \in \mathbb{R}$ and define the following map: $$x_n=\begin{cases} 1 & x_{n-1}=1, \\ x_{n-1}-1, & x_{n-1} \geq 2 \\ \frac{1}{x_{n-1}-1}, & x_{n-1} < 2 \end{cases}$$ It gives ...
1
vote
1answer
177 views

A slower ordinal collapsing function and the Bachmann-Howard ordinal.

Madore's ordinal collapsing function is often defined by $$\psi(\alpha)=\min\{\lambda:\lambda\notin C(\alpha)\}\\C(\alpha)=\bigcup_{n<\omega}C(\alpha)_n\\C(\alpha)_{n+1}=C(\alpha)_n\cup\{\gamma+\...
3
votes
1answer
146 views

The Ackermann hierarchy vs. the fast growing hierarchy

Suppose we've defined the Ackermann hierarchy as follows: $$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(...
2
votes
1answer
99 views

Is “theory of classes” “constructive” in NBG and ZFC? How to state theorems about “classes” involving $\exists!$?

The underlying philosophy of constructivism in mathematics is that in order to prove that something exists, we need to "find" or "construct" it. In NBG (von Neumann–Bernays–Gödel axiomatic set ...
1
vote
1answer
283 views

Is there a second Church-Kleene ordinal?

Given the Church-Kleene ordinal $\omega^{CK}_1$, the supremum of all recursive ordinals, can we go further and derive $\omega^{CK}_2$, $\omega^{CK}_3$, $\omega^{CK}_\omega$ or $\omega^{CK}_{\omega^{CK}...
0
votes
1answer
57 views

Is Rudy Rucker's Theta (θ) the same as Θ and also the same as the omega-fixed point (the first aleph-fixed point) and the first beth-fixed point?

Apologies for the long title! So I've been reading Rucker's Infinity and the Mind and came across this: $$ \theta = \aleph_{\aleph_{\aleph_{\aleph_{\ddots}}}} $$ Previously, theta was defined by ...
5
votes
2answers
114 views

“Quantifying” over properties and “operations” in ZFC and transfinite recursion: clarifying confusion

In the book "Introduction to Set Theory" by Hrbacek and Jech, there is a concept of an operation defined for a special type of a fomula, or a property. Given a property $P(x,y)$ such that $\forall ...
2
votes
1answer
24 views

What should be the number of functions with this condition.

The condition is very simple $A=\{1,2,3,4\}$ is the domain of a function $f(x)$. We have to find total number of $f(x)$ such that $fof(x)=x$. Obviously, It means that $f$ ought to be inverse of ...
0
votes
1answer
111 views

Defining Formulas with Transfinite Recursion.

I'm currently working through some set theory texts, and I am having some trouble with using the transfinite recursion theorem to create functions in the language of set theory. I am trying to sort ...
4
votes
1answer
436 views

Intuition and “proof” of transfinite recursion

I am trying to understand transfinite recursion. So far I have encountered two different definitions of this theorem (not completely sure whether they describe the same Principle of Transfinite ...
0
votes
0answers
63 views

1 : 1 Mapping of integers to decimals

First question here so please point me in the right direction if I'm doing this wrong. The basic premise of my question is this : if we take any decimal number such as 0.02053 and "reflect" it about ...
4
votes
1answer
84 views

Justification of inductive definitions in formal ZFC

General question: How can one justify inductive definitions in formal ZFC? Usually, if we want to define a notion per recursion, we just write for example $$F_1 = 1; \, F_2=1$$ $$F_{n+2} = F_n + F_{...
1
vote
2answers
845 views

Transfinite Recursion

I'm trying to understand the concept of transfinite recursion. Can someone provide me examples which clearly illustrates transfinite recursion or provide some references which I can go through?
1
vote
2answers
60 views

Section on Rank in Enderton's Text.

I am confused with a statement Enderton made in his text, Elements of Set Theory on page 202, Chapter 7. There were two Lemmas, Lemma 7Q: For any ordinal number $\delta$ there is a function $F_{\...
2
votes
2answers
248 views

Prove equivalence of Axiom of choice and Zorn's lemma

I have the following proof and there are some steps I do not understand. Can anyone explain to me what is going on? Claim: (AC) $\implies$ Zorn's lemma Proof: Assume that $S$ is a partial ordered ...
1
vote
1answer
177 views

Proving that Monotone Convergence implies Least Upper Bound in $\mathbb{R}$.

I tried proving that Every bounded increasing sequence converges in $\mathbb{R}$. implies that $\mathbb{R}$ has the least upper bound. Here, $\mathbb{R}$ is taken as an ordered field which ...
1
vote
0answers
33 views

Nodes equation: can't find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level $N$ where $X$ is located to narrow our ...
0
votes
0answers
37 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 ...
3
votes
2answers
115 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
6
votes
1answer
100 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 ...
-1
votes
1answer
102 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.