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

learn more… | top users | synonyms (1)

6
votes
1answer
84 views

Is there continuous $f: [0, 1] \rightarrow [0, \infty)$ such that for all $x$ there is $y$ with $f(y) < f(x)$?

I think there isn't. Here's a sketch of a proof. I'm just not sure whether it really works because I'm not confident with the transfinite versions of the standard theorems about limits and convergent ...
11
votes
10answers
704 views

What are the most prominent uses of transfinite induction outside of set theory?

What are the most prominent uses of transfinite induction in fields of mathematics other than set theory? (Was it used in Cantor's investigations of trigonometric series?)
-1
votes
1answer
21 views

Is it possible to extend the set-inclusion order of a power set to a well-ordering?

The original aim is to define recursively a function on the power set of a set such that the functional value of a subset is determined by those of its proper subsets. Thank you.
0
votes
1answer
37 views

uncountable repetitions

I have a question (or two) about recursive naming conventions. Consider the following recursive naming sequence: Base step: Let S be any nonempty set. Let x be any arbitrary element of S. Let S* be ...
1
vote
1answer
70 views

The Definition of Definition by Recursion

The following is presented as the Transfinite Recursion on well-founded relations in Kenneth Kunen's book. Assume that $R$ is set like and well founded on $A$ and ...
3
votes
2answers
84 views

Can this proof of existence of a Hamel basis using transfinite recursion be shortened/simplified?

This is (I hope) a solution to Problem 112 in A. Shen and N. K. Vereshchagin, Basic Set Theory (AMS 2002). It is - I thought! - a semi-routine exercise, part of whose purpose is to enlighten the ...
0
votes
1answer
29 views

Transfinite fixed points of a function

Let the function $F\colon On \rightarrow On$ be defined by the following recursion: $F(0) = \aleph_0$ $F(\alpha+1) = 2^{F(\alpha)}$ (cardinal exponentiation) $F(\lambda) = \sup\{F(\alpha): \alpha ...
1
vote
1answer
74 views

Computing the rank funciton of the Well founded universe of sets

Definitions: $(1)$ We define the $V_\alpha$ function by transfinite recursion as: $V_0=\varnothing$; $V_{\alpha+1}=P(V_\alpha)$; Lim$(\lambda)\rightarrow ...
0
votes
1answer
36 views

Proof of the Principle of Transfinite Induction for On

Principle of Transfinite Induction for On: If $C\neq\varnothing, C\subseteq$ On then $\exists\alpha\in C\forall\beta\in C[\alpha\in\beta\vee\alpha=\beta]$ Proof: (1) As $C\neq\varnothing$, let ...
5
votes
1answer
73 views

Proving $V=V_{\sf On}$ in $\sf Z+Reg$

Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$ Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of ...
2
votes
2answers
101 views

Is it possible to iterate a function transfinite times?

Let $f:A\rightarrow A$ be a function. We can simply define $f\circ f$, $f\circ f\circ f$, etc., for each given natural number inductively. $f^{(0)}=id_A$ $\forall n\in\omega \qquad f^{(n+1)}=f\circ ...
3
votes
1answer
38 views

Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
0
votes
1answer
56 views

Translation invariance of sets implies translation invariance of their generated sigma algebra?

If we have a collection of translation invariant sets (i.e. if $A$ is in the collection, then $A+x$ is in it too) - assume we have some notion of addition (e.g in a vector space). Is the generated ...
2
votes
1answer
102 views

Initial Segment Order Isomorphic to the Ordinal Numbers

Prove that every well-ordered proper class has an initial segment order isomorphic to the ordinal numbers, ON. I have a plan to prove this but it uses a recursive definition and induction which I do ...
3
votes
1answer
248 views

Transfinite recursion and Replacement

I have a question about the use of Replacement when proving the transfinite recursion theorem. It seems that the crucial use of Replacement is made in the step involving the set of all partial ...
1
vote
2answers
65 views

Principle of Proof by Induction on a Well-ordering

Let $(X,\leq)$ be a woset (well ordered set). Let $E$ be a subset of $X$ such that: (i) the smallest element of $X$ is a member of $E$ (ii) for any $x\in X$, if $y<x\rightarrow y\in E$, then ...
0
votes
1answer
29 views

Transfinite induction under an ordinal $\delta$

Can anyone gove me a hint or a direction to the proof of this statement? Let $F:V \rightarrow V$ be an operation, and $ \delta $ an ordinal. Prove, that there exists a unique function $g$ with domain ...
4
votes
1answer
146 views

Definition by Recursion

I just started studying logic, not as a course at a university, but as pastime. Since I do not study logic at an institution I use many different textbooks, including Enderton's $A$ $Mathematical$ ...
4
votes
2answers
203 views

Good resource to learn transfinite induction and/or recursion?

I'm currently reading John H. Conway's On Numbers and Games, but without a good understanding of transfinite induction and/or recursion, progress is very slow. What's a good resource for learning ...
4
votes
3answers
150 views

Which ordinals embed in $2^\omega$ ordered by inclusion?

Which ordinals can be embedded in the power set of $\omega$ ordered by inclusion? I see that $\omega\cdot\omega$ can (and therefore anything less than that): we can partition $\omega$ into $\omega$ ...
9
votes
2answers
223 views

Is transfinite induction needed to remove all the elements from an uncountable set?

Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set? It seems like this can be thought of as an ...
2
votes
1answer
40 views

Well-founded part of a graph

Let (A,R) be a graph. Define by transfinite recursion: $ W_{0}=\emptyset \\ W_{\alpha+1}=\{a \in A : ext_{R}(a) \subseteq W_{\alpha +1}\} \\ W_{\alpha}=\cup_{\beta < \alpha} W_{\beta} \text{if ...
5
votes
2answers
267 views

Application of Transfinite Induction

Our teacher gave us for practice to prove some properties of $V(\alpha)$ defined as $$V(0) = \emptyset,\; V(S(\alpha)) = \mathcal{P}(V(\alpha)),\; Lim(\alpha): V(\alpha) = \bigcup\{V(\beta)\; |\; ...
0
votes
1answer
106 views

Theorem unique bijection between two well-ordered sets satisfying certain conditions

I have some problems understanding the proof of the following theorem. Given two well-ordered sets $(X, \le _X), \ (Y, \le _Y)$ there exists exactly one partial function $f(X, Y)$ such that: 1)$f: \ ...
5
votes
2answers
251 views

Showing there is only one isomorphism between well ordered sets using transfinite induction

I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,<_{1}\right)$ and $\left(B,<_{2}\right)$ there is only one isomorphism between them. To do ...
4
votes
1answer
86 views

Constructing a Bernstein set in a Polish space

I just read the proof of how to construct two Bernstein sets in a Polish space $X$ using the facts that there are at most $2^{\aleph_0}$ many closed subsets if $X$ is Polish and that every closed ...
3
votes
1answer
164 views

Question on the use of a parametric version of Transfinite Recursion Theorem in Introduction to Set Theory 3rd ed. by Hrbacek and Jech

My question concerns a proof given on page 118 in the text Introduction to Set Theory 3rd ed. by Hrbacek and Jech. The authors on page 117 prove a version of the transfinite recursion theorem ...
0
votes
1answer
131 views

Equivalent statement of transfinite/ordinal recursion

I am trying to prove that the "standard" statement of transfinite/ordinal recursion: "Suppose $G$ is a definite operation on partial functions on ordinals. Then there is a unique definite operation ...
0
votes
1answer
269 views

Transfinite induction vs transfinite recursion

Let $\mathfrak{A}$ is a well-ordered set. Let $f$ is a function which maps a start segment $\{ i\in\mathfrak{A} \,|\, i<c \}$ of a transfinite sequence of elements of atomic posets into an element ...
3
votes
3answers
433 views

What does $\upharpoonright$ in $G(F\upharpoonright\alpha)$ mean?

More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function $G\colon V\to V$, there exists a unique transfinite sequence $F\colon\mathrm{Ord}\to V$ (where ...
-1
votes
5answers
514 views

When to use transfinite induction?

How do we know when we are allowed to use transfinite induction in a proof ? Edit : considering the replies i should say the following Consider an infinite sum of fractions. By induction we can ...
7
votes
1answer
329 views

Epsilon induction

I recently came upon this technique called epsilon induction, and was searching for some proof using the same. But I saw no such proof. Does someone know of any proof using this technique?
2
votes
1answer
173 views

Well ordering and maximal principle

I have to prove that given any poset $(P,\preceq)$ there exists a chain $S$ such that it is maximal (meaning that if $S\subseteq S'$ then $S=S'$). The book contains a proof using the axiom of ...
3
votes
1answer
161 views

Showing the existence of the $\omega_\omega$-th power set of $\omega$

Can you tell me if my answer is correct: Show that the set $P^{\omega_\omega}(\omega)$ exists. My answer: Let $P^0 (\omega) = \omega$, $P^{\alpha + 1}(\omega) = P(P^\alpha (\omega))$ and for a ...
2
votes
2answers
405 views

Injection from the set of countable ordinals $\Omega$ into $\mathbb{R}$

I'm reading through this and I'd like to define an injective function from the set of countable ordinals $\Omega$ into $\mathbb{R}$ using transfinite induction (or maybe transfinite recursion?). ...
12
votes
4answers
3k views

Need help with Recursion Theorem (Set Theory)

The recursion theorem In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem ...
8
votes
1answer
236 views

How to prove an extension of ZFC is conservative

Working in ZFC. I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...
5
votes
2answers
627 views

Recursive Mapping

I was wondering about what is the general definition of a recursive mapping between any two sets. Is there a condition for a mapping to be able to be written in recursive form? Is the following claim ...