Questions tagged [transfinite-recursion]
Questions dealing with set-theoretic functions defined by transfinite recursion.
160
questions
3
votes
1
answer
65
views
Is there a function $f :A^{<\mathbb{N}}\to E$ such that $f (s{}^\frown a)=h(f(s),a,|s|)$ for any $s\in A^{<\mathbb{N}}$ and $a\in A$?
Given a set $A$, define $A^{<\mathbb{N}}:=\cup _{n\in\mathbb{N}}A^n$ with $A^0:=\{\emptyset\} $ and $A^n$ being the $n$-fold cartesian product of $A$.
For any $s:=(s_0,\cdots,s_{n-1})\in A^n\...
- 1,209
1
vote
1
answer
81
views
Any subset of a well-ordered set is isomorphic to an initial segment of this well-ordered set.
I wanted to prove the fact for which I have a sketch of proof: Let $(W,\leq )$ be a well-ordered set and $U$ be a subset of $W$. Then considering the restriction of $\leq $ to $U\times U$, we have ...
- 375
3
votes
1
answer
193
views
Every real function is the sum of two bijections
Context. We are in $\mathsf{ZFC}$.
Problem. Given a function $f : \mathbb R \to \mathbb R$ prove that there exist two bijective functions $g$ and $h$ from $\mathbb R \to \mathbb R$ such that $f = g + ...
- 509
4
votes
1
answer
182
views
Colourful class function
Background. We're in $\mathsf{ZFC}$, and I can use the principle of $\epsilon$-induction, but not (directly) the $\epsilon$-recursion.
Problem. Let $F : V \to V$, where $V$ is the class of all the ...
- 509
1
vote
0
answers
103
views
Relativized extensionality $\implies$ existence of a transitive set isomorphic to the first one
Background. Given two sets $A$ and $B$, we say that $A$ is isomorphic to $B$ if there exists a bijection $f : A \to B$ such that $\forall x,y \in A \; y \in x \leftrightarrow f(y) \in f(x)$. We work ...
- 509
4
votes
1
answer
126
views
Is there a smarter way to calculate $F(\omega^{15} + 7)$? (Ordinal arithmetic)
Given the function $F : \text{Ord} \to \text{Ord}$ definite by transfinite recursion as it follows:
$$F(0) = 0 \qquad F(\alpha + 1) = F(\alpha) + \alpha \cdot 2 + 1 \qquad F(\lambda) = \sup_{\gamma &...
- 509
-1
votes
1
answer
25
views
Is a totally ordered set consisting of discrete point sets containing point p a well-ordered set?
I have encountered a fully ordered set and want to determine whether it is well ordered.
Each element B in this totally ordered set A is a set and includes point p, which means that the elements in A ...
- 1
1
vote
2
answers
104
views
Transfinite recursion to construct a function on ordinals
I am asked to use transfinite recursion to show that there is a function $F:ON \to V$ (here $ON$ denote the class of ordinals and $V$ the class of sets) that satisfies:
$F(0) = 0$
$F(\lambda) = \...
- 839
1
vote
0
answers
68
views
How is transifnite recursion applied?
I've been struggling to understand how ordinal addition, multiplication, and exponentiation, along with the Aleph function $\aleph$, are defined using Transfinite Recursion in Jech's Set Theory or ...
- 5,166
1
vote
1
answer
83
views
On the proof that there exists a strictly increasing function $f : \text{cf}(A) \to A$ such that $\text{rng}(f)$ is cofinal in $A$
I am looking at the following theorem in a set of notes:
Theorem 12.48. Suppose that $(A, <)$ is a simple order with no largest element. Then there is a strictly increasing function $f : \text{cf}(...
- 4,827
1
vote
0
answers
64
views
Recursive definition for the sum of a transfinite sequence of ordinals
A transfinite sequence is a function whose domain is an ordinal $\alpha$. Let $C$ denote the class of all transfinite sequences of ordinals, and let $\text{On}$ denote the class of ordinals.
Use the ...
- 4,827
1
vote
1
answer
120
views
Exercise 6.4.2 Introduction to Set Theory by Hrbacek and Jech
This is exercise 6.4.2 from the book Introduction to Set Theory 3rd ed. by Hrbacek and Jech.
Using the Recursion Theorem 4.9 show that there is a binary operation $F$ such that
$(a)$ $F(x,1)=0$ for ...
- 4,827
1
vote
1
answer
195
views
How to define ordinal addition
From Jech's Set Theory:
We shall now define addition, multiplication and exponentiation of ordinal numbers, using Transfinite Recursion.
Definition 2.18 (Addition). For all ordinal numbers $\alpha$
$...
- 5,166
2
votes
1
answer
122
views
On the definition of ordinal addition using transfinite recursion
Am reading the textbook Introduction to Set Theory 3rd ed. by Hrbacek and Jech. In chapter 6 the authors present two versions of the transfinite recursion theorem:
Transfinite Recursion Theorem. Let $...
- 4,827
1
vote
1
answer
124
views
On the proof of the parametric version of the transfinite recursion theorem
In the book Introduction to Set Theory 3rd ed. by Hrbacek and Jech one can find proofs of the following two theorems:
Transfinite Recursion Theorem. Let $G(x)$ be an operation. Then there exists an ...
- 4,827