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

learn more… | top users | synonyms (1)

0
votes
1answer
35 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
57 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
67 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
20 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
68 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
32 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 ...
4
votes
1answer
67 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
97 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 ...
2
votes
1answer
31 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
42 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
94 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
208 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
59 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
28 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
141 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
186 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
141 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$ ...
7
votes
2answers
204 views

Does this require transfinite induction?

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
32 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
256 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
102 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
220 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
81 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 ...
2
votes
1answer
150 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
126 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
246 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
410 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
489 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
307 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
171 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
155 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
386 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?). ...
11
votes
4answers
2k 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
233 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
576 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 ...