Questions dealing with set-theoretic functions defined by transfinite recursion.
6
votes
2answers
115 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
26 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 ...
4
votes
2answers
85 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
47 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: \ ...
4
votes
2answers
59 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 ...
0
votes
0answers
30 views
Popular name to task where f(x) for x in 1..N is a random mapping of 1..N and getting the time to a repeated answer?
If f(x) is initialized to return a fixed random mapping of the digits 1..N, then if M is the average number of times that f(f(...f(x)...)) can be applied before a repeat in the returmn value of the ...
4
votes
1answer
53 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
89 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
83 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
130 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 ...
1
vote
2answers
129 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
278 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
182 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
121 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
117 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
278 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?).
...
7
votes
4answers
951 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 ...
5
votes
0answers
182 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 ...
4
votes
2answers
353 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 ...
