Questions tagged [transfinite-recursion]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
26 views

Defining a function using transfinite recursion.

For $p,q\in \mathbb{Q} :p<q $ we define $(p,q) :=\{ x\in \mathbb Q : p<x<q \}$ and we want to define an order like this $$(p,q) < (t,l) \iff p<q$$ and I want to prove that there is an ...
2
votes
0answers
51 views

How does Reinhardt's extension of the set-theoretic universe beyond $V_\Omega$ work?

In this answer it is stated that in William Reinhardt's paper 'Remarks on reflection principles, large cardinals, and elementary embeddings' (1974) Reinhardt suggests extending the set-theoretic ...
0
votes
0answers
6 views

Implementing L-Systems for conversion (instead of drawing): Extending the Hilbert space filling curve

I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
1
vote
1answer
42 views

On the cardinality of the closure of a subset of a dense subset

Is the following true? Given a first countable Hausdorff space $X$ and a dense subset $Y\subset X$ which is initially $2^\omega$-initially Lindelöf in $X$. Let $F$ be a subset of $Y$ such that $\vert ...
1
vote
0answers
43 views

Equivalance relation for a mapping

I have an assignment to solve which is related to Equivalence relation of a mapping. The following picture will show you the content of the question. Actually, for the question a, it can be easily ...
1
vote
0answers
31 views

What is the Turing degree of the set of True formula of Arithmetic whose order is an infinite ordinal

This question was originally posted as a part of this other question, but I was suggested to make a new question for this part. In the first question I asked about the Turing degree of the set of ...
0
votes
1answer
44 views

Proving the cardinality of B<A (Terence Tao's Analysis I book Ex 8.5.15)

Let A and B be two non-empty sets such that A does not have lesser or equal cardinality to B. Using the principle of transfinite induction, prove that B has lesser or equal cardinality to A. (Hint: ...
1
vote
2answers
39 views

Construction of an uncountable set using well ordering principle.

I was trying to prove that a metric space in which every uncountable set has a limit point is separable.Now I was trying to show that it is Lindelof.I proceed like this,If not lindelof,then there is ...
0
votes
1answer
56 views

Using transfinite induction to split $R$ to continuum many pairwise disjoint subsets of $R$

I am looking for different ways to partition $R$. I know some like : (1) Define a relation as following $$x\sim y \ \text{iff} \ x-y\in\mathbb Q(x,y\in\mathbb R)$$. The equivalence classes have the ...
1
vote
0answers
63 views

Continuous function with some properties plus everywhere surjective function must be everywhere surjective

Let me starts with some definitions : $f\colon \mathbb R\to \mathbb R $ is everywhere surjective if $f[I]=\mathbb R$ for every nonempty open interval $I.$ $f$ is Darboux function if $f$ satisfies the ...
0
votes
0answers
48 views

How can I write a perfect set as $c$ many pairwise disjoint perfect sets

I have been thinking about this question but I have not get complete answer yet. the question is Let $P$ a nonempty perfect subsets of $\mathbb R$ then $P$ can be written as continuum many pairwise ...
0
votes
2answers
83 views

Infinitary logic and Undecidability

Good day everybody, I would like to ask a question about undecidability. May I ask You, if we have some problem that is undecidable but true, for example if RH would be found out to be undecidable it ...
1
vote
1answer
38 views

Primitive Recursive Functions

I would like to show that the function $f:\mathbb{N} \to \mathbb{N}$ defined by $f(n)=p_n$ where $p_n$ is the $n+1$ prime number is primitive recursive. The fact is that I just manage to show it is $μ$...
0
votes
1answer
79 views

Definition of addition by transfinite recursion.

Transfinite recursion theorem from T.Jech Set Theory: Let G be a function (on V), then (2.6) below defines a unique function F on Ord such that $F (α) = G(F \restriction α)$ for each α. (2....
0
votes
0answers
70 views

Characterize a $\sigma$-algebra generated by a family of sets $\sigma(C)=\mathcal{B}_{\Omega}$

Well, my intention is basically to understand what is done in the answer here, which I will summarize in the following... and discuss a little more (hence I made a new question). Problem: Given a ...
0
votes
1answer
45 views

Computing these ordinal hyperoperations that are left/right associative

It is somewhat counterintuitive to want tetration to be right-associative over ordinals when ordinal arithmetic is left-associative. To merge these two, I simply took the supremum of the left- and ...
8
votes
2answers
177 views

“Transfinite Peano Axioms”

Perhaps, the class of ordinals $\Omega$ can be axiomatised up to isomorphism by claiming it to be well-ordered such that for every subset $X\subseteq \Omega$ there exists a "succesor" ordinal $\sigma$ ...
0
votes
2answers
34 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\}$, $S_2=\{0,1,...
0
votes
0answers
38 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
66 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
125 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
353 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
55 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 $\...
2
votes
1answer
296 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). The ...
0
votes
2answers
98 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, and ...
0
votes
1answer
126 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
93 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
106 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:\operatorname{...
1
vote
2answers
117 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
73 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
83 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\...
1
vote
4answers
358 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
39 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
101 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
82 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
301 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
212 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
207 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
24 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 ...
1
vote
1answer
72 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
53 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
230 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
62 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
138 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
47 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
82 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
62 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
46 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
261 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+\...