Stack Exchange Network

Stack Exchange network consists of 175 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
2answers
25 views

Proof by Induction: Recursively Defined Sequential Set

We recursively define a sequence of subsets of $\mathbb Z$ as follows: Let $S_0=\{0\}$, and let $S_{n+1}=\{2m: m \in S_n\} \cup \{2m+1: m \in S_n\}$ for all $n \geq 0$. (So $S_1=\{0,1\}$, $...
0
votes
0answers
33 views

Vector space of real valued function with size continuum

I know how I can construct a function such that $f^{-1} (y)$ has size less than continuum actually countable. Here is the proof, Define a relationship as following $$x\sim y \ \text{iff} \ x-y\...
0
votes
2answers
63 views

How should we parse this proof that every infinite set has a subset which is eqivalent to the set of natural numbers?

This is again from the chapter Construction of the System of Real Numbers in The Fundamentals of Mathematics, Volume 1. It may be the case that the original wording in the German language would be ...
0
votes
1answer
64 views

Ultratasks in the ITTM Model

[Note: I have not previously seen a definition that relates Beth numbers to Supertasks, however my intuition is that one may exist] A supertask is a countably infinite sequence of operations that ...
1
vote
1answer
156 views

Pardon my ignorance, but isn't TREE(3) a finite number?

Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?). However, I have seen ...
1
vote
1answer
34 views

Difference between Kleene's O and the system $S_1$

On pages 207-208, Rogers (Theory of Recursive Functions and Effective Computability) introduces two system of notations for ordinals: the first is what he calls $S_1$ and the second one is Kleene's $\...
-1
votes
1answer
107 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
53 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
79 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
110 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(...
0
votes
2answers
71 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 ...
0
votes
2answers
80 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
42 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
90 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
60 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
44 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
4answers
96 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
34 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
53 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
62 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
147 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
141 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
143 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
20 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
21 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
59 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
150 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
56 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
131 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
28 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
42 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
76 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
48 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
42 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
204 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
178 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(...
3
votes
1answer
120 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 ...
3
votes
1answer
366 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
76 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
129 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
138 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
514 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
67 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
89 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_{...
2
votes
2answers
1k 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
61 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
327 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
244 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 ...