Questions tagged [transfinite-recursion]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
53 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 ...
0
votes
1answer
40 views

About a perfect set that is disjoint with family in the form $A\cdot\Bbb Q$ where $A$ is a finite set. [closed]

$A\subset\Bbb R$ is perfect if it is a closed set and contains no isolated point. let $A,B$ be non-empty subsets of $\Bbb R$ and by $A\cdot B$, we mean that $A\cdot B=\{a\cdot b\colon \forall a\in A \ ...
3
votes
1answer
153 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, ...
0
votes
1answer
80 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 ...
0
votes
0answers
19 views

Parameters for well-founded recursion

For a set-like, well-founded relation $R$ on a class $X$, one may use well-founded recursion to define set $S_x$, $x \in X$, using sets $\{S_y \mid y\ R\ x\}$ that can be assumed to be already defined....
7
votes
1answer
112 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 ...
6
votes
1answer
106 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 $...
1
vote
1answer
26 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 ...
0
votes
0answers
35 views

Construct a family of functions that avoid a fix perfect nowhere dense set

Assume we have a family $\mathcal F$ of continuum many functions from $\Bbb R$ to $\Bbb R$, a set $D=\{x_\eta:\eta<\mathfrak c\}$ a subset of $\Bbb R$, and $K$ a perfect nowhere dense subset of $\...
0
votes
1answer
33 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 ...
3
votes
0answers
92 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 ...
1
vote
2answers
86 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=\{...
0
votes
1answer
64 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$...
1
vote
0answers
47 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 ...
0
votes
1answer
54 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 ...
0
votes
0answers
35 views

About construct a function with specific property that miss a line

Recall some definitions: Definition. $A$ is algebraically independent if and only if for every $a\in A$ , $a\notin\mathbb Q(A\setminus\{a\}$). $\mathcal M$- the calss of functions $f$ for which the ...
2
votes
2answers
80 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 ...
3
votes
1answer
79 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 ...
0
votes
1answer
64 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 \...
4
votes
1answer
172 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 ...
0
votes
0answers
27 views

Construct function on perfect set such that the function is continuous

Let $A$ and $C$ be perfect sets ( perfect set is closed and has no isolated point) subsets of $\mathbb R$ and $A\cap \mathbb Q=\emptyset.$ Let $Z$ be subset of $\mathbb R$ such that it intersects ...
0
votes
2answers
64 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 ...
1
vote
0answers
90 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. ...
3
votes
1answer
129 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 ...
0
votes
1answer
111 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$...
0
votes
0answers
28 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
79 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 ...
2
votes
1answer
69 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
44 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
42 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
82 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
48 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
64 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
79 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
61 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 ...
-1
votes
2answers
117 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
60 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
108 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
123 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
57 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
217 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
39 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
41 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
68 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
157 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
450 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
62 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 $\...
3
votes
1answer
446 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
101 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
133 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(...