Questions tagged [transfinite-recursion]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
45 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 ...
Sam's user avatar
  • 4,680
1 vote
1 answer
70 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}(...
Alphie's user avatar
  • 4,710
0 votes
0 answers
35 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 ...
Alphie's user avatar
  • 4,710
1 vote
1 answer
97 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 ...
Alphie's user avatar
  • 4,710
1 vote
1 answer
176 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$ $...
Sam's user avatar
  • 4,680
2 votes
1 answer
95 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 $...
Alphie's user avatar
  • 4,710
1 vote
1 answer
102 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 ...
Alphie's user avatar
  • 4,710
4 votes
0 answers
97 views

Why does proof of Zorn's lemma need to use the fact about ordinals being too large to be a set?

I'm not understanding why its necessary to invoke the knowledge about ordinals in order to prove Zorn's lemma. The Hypothesis in Zorn's lemma is Every chain in the set Z has an upper bound in Z Then ...
Pecan Lim's user avatar
7 votes
1 answer
348 views

TREE(3) and the Goodstein sequence

TREE(3) is an extremely large number that requires ordinal arithmetic to prove it is finite. For what value of n would $G(n)>TREE(3)$? The length of the Goodstein sequence $G(n)$ is how many ...
Sheldon L's user avatar
  • 4,524
0 votes
0 answers
47 views

How to define multivariable double recursive function

I have a question for those who are familiar with recursion theory. According to Wikipedia (https://en.wikipedia.org/wiki/Double_recursion), Raphael M. Robinson called functions of two natural number ...
glutaminemusic's user avatar
3 votes
1 answer
91 views

Help with basic ordinal arithmetic: What is the supremum of the sequence $\omega^{2} + \omega$, $\omega^{2}*2 + \omega$, $\omega^{2}*3 + \omega$, ...?

I need some help with some basic ordinal arithmetic. I am trying to determine the supremum of the sequence $\omega^{2}*1 + \omega$, $\omega^{2}*2 + \omega$, $\omega^{2}*3 + \omega$, ... where the ...
Kyle S's user avatar
  • 33
2 votes
1 answer
50 views

Best Recursive Subdivision Tiling Mapping Function

I am trying to create subdivision tilings inspired by the work of Brian Rushton (eg. page 77 of this paper). The challenge is to subdivide tiles according to a certain rule, and then apply this rule ...
Oscar Saharoy's user avatar
0 votes
1 answer
78 views

How to prove this alternative version of transfinite recursion

There are several formulations of transfinite recursion. I am interested in the following one. Let $(V, \in)$ be a model of ZF. Let $g_1$ be a set and $G_2,G_3 : V \to V$ be two definable class ...
user700974's user avatar
1 vote
1 answer
101 views

Why doesn't transfinite recursion imply dependent axiom of choice

The theorem of transfinite recursion states the following (A quick introduction to basic set Theory). Theorem 4.4 (Transfinite recursion). For every ordinal $\kappa$, set $A$, and map $^3 F: \...
wsz_fantasy's user avatar
  • 1,546
0 votes
1 answer
65 views

How to invoke transfinite recursion

Transfinite recursion states that For any $F:\mathbf{V}\to \mathbf{V}$, there exists a unique $G:\mathbf{ON}\to\mathbf{V}$ such that $\forall\alpha[G(\alpha)=F(G\vert_\alpha)]$ where $\mathbf{V}$ ...
Anon's user avatar
  • 475
4 votes
1 answer
155 views

How to calculate multiplication of transfinite nimbers with a Cantor normal form

I failed to calculate nimber multplication in the form of $[\omega^\alpha]*[\omega^\beta]$, according to the "mex" definition. The cases when $\alpha<3,\beta<3$ are easy, while $[\...
CollinG's user avatar
  • 53
1 vote
0 answers
60 views

$\mathbb{R}_{\rm Sorg.}$ is paracompact but $\mathbb{R}_{\rm Sorg.} \times \mathbb{R}_{\rm Sorg.}$ is not

I’m trying to solve this problem: $\def\bbR{\mathbb{R}} \def\RSorg{\bbR_{\rm Sorg.}} \def\calR{\mathcal{R}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \DeclareMathOperator{\range}{range}$ Prove ...
Paul's user avatar
  • 1,314
1 vote
0 answers
54 views

Can I add this assumption for arbitrary family?

Perhaps, my question is straightforward but I want to make sure. let's consider, $\mathcal F=\{f_{\xi}\colon \xi<\mathfrak c\}$ family of functions from $\mathbb R\to\mathbb R$. If want to prove ...
Gob's user avatar
  • 1,107
2 votes
2 answers
124 views

Construct a function that will be disjoint with continuum many lines

The symbol $\mathbb L$ will stand for the family of all lines in the plane that are neither horizontal nor vertical. Also, we put $\mathbb L_0:=\{\ell\in\mathbb L\colon \ell(0)=0\}$ lemma. Let $\...
00GB's user avatar
  • 2,391
1 vote
1 answer
79 views

Transfinite Recursion Theorem - Particular case - Enderton

I have the following theorem for any formula $\gamma(x,y)$: Theorem of Transfinite Recursion: Given a well-ordered set $A$ such that for any $f$ there is a unique $y$ such that $\gamma(f,y)$ holds, ...
Darsen's user avatar
  • 3,539
3 votes
0 answers
212 views

I have some questions about the Ross-Littlewood Paradox

TLDR at the end. Hi, I recently saw this comment given by "completely-ineffable" on the r/badmathematics subreddit. And I just wanted to make sure if I understand it correctly and wanted to ...
Andrés Romero's user avatar
1 vote
1 answer
103 views

Ordinal notations and the Church-Kleene Ordinal

According to Kleene, an $r$-system is a pair $(S, |\cdot|)$ where $S\subseteq\mathbb{N}$ and $|\cdot|$ maps $S$ to countable ordinals, such that There is a partial recursive $K(x)$, such that $K(x) = ...
abc's user avatar
  • 1,430
0 votes
0 answers
17 views

Proving a recursively defined mapping is right-unique and left-total [duplicate]

The question was originally written in German, but from what I understand, the gist is, that I'm supposed to show that the mapping is both left-total and right-unique. Let A be a set, $a \in A$ and $h:...
Duncan Taylor's user avatar
0 votes
1 answer
128 views

How to more rigorously formalise “value of (Weaver's) P-name” in set theory forcing (recursion)?

Background I have been reading some introductory material on forcing, specifically Nik Weaver's Forcing for mathematicians. What Weaver calls a “$P$-name”, I will call “Weaver's $P$-name” because it ...
Linear Christmas's user avatar
0 votes
0 answers
45 views

Can we define the predicate "ordinal" in ZF-Reg. by recursion?

Working in $\sf ZF-Reg.$ can we define the unary predicate "is an ordinal", denoted by "$\operatorname {od}$", meaning is a von Neumann ordinal, in a recursive manner? The usual ...
Zuhair's user avatar
  • 4,525
4 votes
1 answer
78 views

The set is meager if it has a cover of clopen meager sets

Let $X$ be a topological space such that there exists a collection of meager clopen sets $(C_i)_{i \in I}$ such that $X = \bigcup_{i \in I} C_i$. I want to prove that $X$ is then meager itself. As ...
Nik Bren's user avatar
  • 1,859
1 vote
1 answer
88 views

Comparability theorem for well ordered sets using transfinite recursion

Similar questions have already been asked here and here. But I am asking for verification of my proof. Halmos leaves out an "easy" transfinite induction argument, which I have struggled to ...
Atom's user avatar
  • 3,781
0 votes
1 answer
100 views

Is my simplified proof of Tychonof theorem correct?

I have read the proof of Tychonof theorem from here. Let $(E_\lambda)_{\lambda \in \mathfrak a}$ be an arbitrary collection of compact topological spaces. We endow $E := \prod_{\lambda \in \mathfrak ...
Analyst's user avatar
  • 5,617
4 votes
1 answer
182 views

How to define in ZFC transfinite hierarchies of proper classes (with an example usefull for proof theory)

I was studying some Proof Theory in Pohlers' Proof Theory: first step into impredicativity , and I found myself facing a Set Theory's problem. We need to define this transfinite hierarchy of proper ...
Matteo __'s user avatar
4 votes
1 answer
189 views

Does there exist a Bernstein set such that a finite sum still Bernstein?

Recall that $B\subset\Bbb R$ is a Bernstein set if $B\cap P\neq\emptyset \neq P\setminus B$ for every perfect set $P\subset\Bbb R.$ It can be constructed by an easy transfinite induction. Moreover, ...
00GB's user avatar
  • 2,391
0 votes
1 answer
112 views

About Construction a one-to-one function from $(a,b)$ onto $[a,b]$

This question asked to construct one-to-one function from $(a,b)$ onto $[a,b]$. I know there is a function but it seems the question to define this function explicitly. How this can be done? Edit I ...
00GB's user avatar
  • 2,391
7 votes
1 answer
220 views

Is there a generalization of transfinite recursion that allows defining proper classes?

Transfinite recursion lets one define a sequence of sets $S_\alpha$, for $\alpha$ an ordinal. My question is whether it is possible to generalize this recursion to allow $S_\alpha$ to be classes, not ...
Tom's user avatar
  • 1,104
6 votes
1 answer
165 views

Classifying Vector Spaces without AC

Using the axiom of choice we can give a simple classification of all vector spaces over a given field $K$ up to isomorphism: Any $K$-vector-space $V$ is just isomorphic to $\bigoplus_{i\in B}K$ where $...
H.D. Kirchmann's user avatar
3 votes
1 answer
128 views

Recursive Definition of the Closure of a Set in a Family of Functions

For the sake of consistency, I will define some terms below the question, however, if you are familiar with the terms, that section can be skipped. I am attempting to prove this lemma, for my text ...
BENG's user avatar
  • 1,075
0 votes
1 answer
79 views

Meager set union Bernstein set with empty interior

Fix a meager set $M\subset \Bbb R$. of course $\text{int} M=\emptyset$. I want to construct a Bernstein set $B\subset \Bbb R$ such that $$\text{int}(M\cup B)=\emptyset \tag{1}$$ We know it is true ...
00GB's user avatar
  • 2,391
3 votes
0 answers
104 views

Construct an additive group by transfinite induction

I know one way to construct a Bernstein set that is an additive group.Here is the way that I know. $\{P_\xi\colon \xi<\mathfrak c\}$ all nonempty perfect subsets of $\Bbb R.$ Choose, by recursion ...
00GB's user avatar
  • 2,391
1 vote
2 answers
106 views

Complement of the product of Bernstein set and meager set

Assume $M\subset\mathbb R$ be a meager set with cardinality $\mathfrak c.$ I want to construct a Bernstein set $B$ such that $\mathbb R\setminus(B\cdot M)$ has cardinality $\mathfrak c$ , $B\cdot M=\{...
00GB's user avatar
  • 2,391
1 vote
1 answer
126 views

Question about the formulation of Kenneth Kunen's "Primitive Recursion on Ordinals" Theorem

In Kenneth Kunen's The Foundations of Mathematics, the subject of recursion (on ordinals) is introduced and is described using the following "recipe": $f(\xi)=G(f_{|\xi})$, where $G$ and $f$...
S.C.'s user avatar
  • 4,914
1 vote
0 answers
57 views

Why does creating the basis of any vector space using dense order instead of well order fail in general case?

This problem occurred to me when I was solving problem 112 in A. Shen and N. K. Vereshchagin, Basic Set Theory (AMS 2002)), just as in this post Can this proof of existence of a Hamel basis using ...
Julja Muvv's user avatar
0 votes
1 answer
74 views

Continuous function by transfinite induction

Let $A$ and $B$ subsets of $\mathbb R$ such that both have cardinality $\mathfrak c.$ I want to construct a noncontact function $f\colon A\to B$ by transfinite induction such that $f$ is ...
00GB's user avatar
  • 2,391
2 votes
2 answers
243 views

Bernstein set and it proof.

Definition. A set $B\subset\mathbb R$ is called a Bernstein set if both $B$ and $\mathbb R\setminus B$ intersect each perfect set. I know the construct the of Bernstein set but I got confused with ...
00GB's user avatar
  • 2,391
5 votes
1 answer
470 views

Generalising the recursion theorem to well-founded posets

The recursion theorem states the following. Suppose $(A,\preccurlyeq)$ is a chain with order type $\omega$. Let $X$ be any set, let $x\in X$ and let $g\colon X\times A \to X$ be a function. Then ...
Luke Collins's user avatar
  • 8,740
0 votes
1 answer
180 views

Parametric Transfinite Recursion Theorem implies Double Recursion Theorem?

The Parametric Transfinite Recursion Theorem (PTRT) states: For each operation $\mathbf{G}$, there is an operation $\mathbf{F}$ such that $\mathbf{F}(z,\alpha)=\mathbf{G}(z,\mathbf{F}_z\restriction \...
Zuy's user avatar
  • 4,646
4 votes
1 answer
292 views

Set of cardinality continuum contains a perfect set

I want to make sure if my claim is true or false : Every subset of $\mathbb{R}$ of cardinality continuum contains a perfect set A perfect set is a closed set with no isolated point. It might be there ...
00GB's user avatar
  • 2,391
0 votes
2 answers
295 views

Recursion theorem for ordinals proof

I'm trying to understand the proof of the recursion principle of ordinals, the theorem is: The proof of this theorem uses this other theorem: The proof is pretty long (I'm sorry) so I will try to ...
Andrea Burgio's user avatar
1 vote
0 answers
120 views

Partition $\mathfrak c$-dense set to $\mathfrak c$- many dense set.

A subset of $A\subset\mathbb R$ is called $\mathfrak c$-dense if $ |A\cap I|=\mathfrak c$ for any open interval $I\subset\mathbb R.$ Then, there is a partition for $A$ to continuum many dense set. ...
00GB's user avatar
  • 2,391
3 votes
1 answer
427 views

$\mathbb R$ as continuum many of pairwise disjoint of Bernstein sets

The set $B\subset\mathbb R$ is called Bernstein set if neither $B$ nor $\mathbb R\setminus B$ contains any perfect sets. Theorem: $\mathbb R$ can be written as continuum many of pairwise disjoint ...
00GB's user avatar
  • 2,391
0 votes
1 answer
160 views

family of pairwise disjoint sets in the complement of meager. set

Let $M$ be a meager subset of $\mathbb R$. I want to construct the following family in $\mathbb R\setminus M $ $$F:= \{A_{r}^\xi\colon r\in\mathbb R \ \&\ \xi<c\}$$ Such that all elemnets of $F$...
00GB's user avatar
  • 2,391
0 votes
0 answers
31 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 ...
Elad Elmakias's user avatar
3 votes
0 answers
214 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 ...
user784623's user avatar