A question on Transfinite Recursion Theorem schema....

In summary, the conversation discusses Enderton's "Elements of Set Theory" and its discussion of the red and brown forms of the transfinite recursion theorem schema. It also mentions the use of the general form (brown) to show that the first form (red) is a special case. There is confusion about the green and yellow parts, but it is concluded that the green part holds due to the definition of a binary relation and the yellow part can be proved using transfinite induction. Finally, there is a discussion about constructing a formula and proving its uniqueness, as well as the potential use of the axiom of replacement to associate a single y to every x.
  • #1
Mathelogician
35
0
Hi everybody,
In Enderton's "elements of set theory", he first discusses the red and then after some explanations
he discusses the brown as the general form of transfinite recursion theorem schema.
Then in the blue example, he uses the general form(brown) to show that the first form(red)is a
special case of that.

Now i am confusing with the blue part!
Why does the green part hold?
And how can we prove the yellow part?Thanks,
Mathelogician
View attachment 295
 

Attachments

  • q1.png
    q1.png
    49 KB · Views: 105
Physics news on Phys.org
  • #2
Welcome to the forum! I'm glad you found it.

Do I understand right that $\mathop{\mathrm{seg}}t=\{x\in A\mid x<t\}$ and ${}<A=\{\mathop{\mathrm{seg}t}\mid t\in A\}$?

To start, I think the green part is pretty clear. Either $x\in {^{{}<A}B}$ or $x\notin {^{{}<A}B}$. In both cases one and only one y is associated with x.

I (or somebody else) will write about the yellow part later.
 
  • #3
Thanks my friend, emakarov! Indeed Sudharaka made me conscious of that.

In both cases one and only one y is associated with x.
Why in both cases?!
For the first case i am sure, but not so about the 2nd one. May you explain more?
I mean, If x doesn't belong to that set, why should we have a y which is associated with x? What does even that mean?
 
  • #4
Mathelogician said:
If x doesn't belong to that set, why should we have a y which is associated with x?
By definition. We define a binary relation on sets. Let P(x) denote $x\in {^{{}<A}B}$. If $\neg P(x)$ for some x, we posit that the relation holds for x and $\emptyset$ only, by definition. Formally

let $\gamma(x,y)$ be $(P(x)\land y=G(x))\lor (\neg P(x)\land y=\emptyset)$. (1)

Then pure logic (i.e., with no axioms of set theory) proves $\forall x\exists! y.\,\gamma(x,y)$. Here ∃! is the uniqueness quantifier. One way to write the latter formula explicitly is ∀x∃y∀z. γ(x, z) ↔ z = y.

Now about the yellow part. From (1), we have the following:

If P(x) and γ(x, y), then y = G(x). (2)

By the brown version of the transfinite recursion theorem there exists an F such that ∀t ∈ A. γ(F ↾ seg t, F(t)). The yellow part proves ∀t ∈ A. P(F ↾ seg t) and therefore, by (2), ∀t ∈ A. F(t) = G(F ↾ seg t), which is the conclusion of the red version of the theorem. The proof of ∀t ∈ A. P(F ↾ seg t) is by transfinite induction. Assuming I am right about the interpretation of seg t and <A in post #2, if t is the least element of A, then seg t is the empty set and F ↾ seg t is the empty function, so it belongs to $^{{}<A}B$.

To be finished later.
 
  • #5
By definition. We define a binary relation on sets. Let P(x) denote [FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_Main]<[/FONT][FONT=MathJax_Math]A[/FONT][FONT=MathJax_Math]B[/FONT]. If [FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT] for some x, we posit that the relation holds for x and [FONT=MathJax_Main]∅[/FONT] only, by definition.
Sorry I'm acting so thick headed!
But then what would be the domain of that relation?!
I think it must be the class of all sets [which is not then a set].
But i think i found some way.I will use the axiom of replacement; Then my only question would be whether we can define a class H={(x,y): [FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∈V [/FONT]and [FONT=MathJax_Math]γ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Main])[/FONT] } in which V is the class of all sets.
[indeed I'm studying ZFC, so i am not familiar well to Classes and their properties]
If it IS a class, then since H is a class-function [i,e., a class which has the property of being function except of being a set], by the Replacement axioms, at last we will have: H is a set.(Indeed a relation).
Therefore, for every x, we would have [FONT=MathJax_Math]γ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Main])[/FONT].

And then we can conclude the others.
===================================
And i got all other your claims with no dark part.
 
  • #6
The brown theorem does not require us to prove that $\{(x,y)\mid \gamma(x,y)\}$ is a set. It just requires to construct a formula $\gamma$.
 
  • #7
Evgeny.Makarov said:
The brown theorem does not require us to prove that $\{(x,y)\mid \gamma(x,y)\}$ is a set. It just requires to construct a formula $\gamma$.

I just did it as one way to show that the hypothesis of the brown holds. What's wrong with that?
What is the other way to show that the hypothesis holds for brown?
And What about H's being a class? Is it?
Thanks.
 
  • #8
Mathelogician said:
I just did it as one way to show that the hypothesis of the brown holds.
Could you say briefly again what "it" above is, which assumption of the brown theorem it fulfils and how it does so? Besides < being a well-ordering on A, I see two assumptions: having a formula $\gamma$ and proving $\forall x\exists! y\;\gamma(x,y)$.

Mathelogician said:
What is the other way to show that the hypothesis holds for brown?
To construct a formula $\gamma$ and to prove $\forall x\exists! y\;\gamma(x,y)$.

Mathelogician said:
And What about H's being a class? Is it?
Yes because the first components of pairs in H are all sets. However, this is irrelevant for the application of the transfinite recursion theorems.
 
  • #9
Could you say briefly again what "it" above is, which assumption of the brown theorem it fulfills and how it does so? Besides < being a well-ordering on A, I see two assumptions: having a formula [FONT=MathJax_Math]γ[/FONT] and proving [FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∃[/FONT][FONT=MathJax_Main]![/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Math]γ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Main])[/FONT].

My problem was proving the blue(and "it' refers to that).
I asked you
If [FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT], why should we have a y which is associated with x?
And you answered :

By definition. We define a binary relation on sets. Let P(x) denote [FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_Main]<[/FONT][FONT=MathJax_Math]A[/FONT][FONT=MathJax_Math]B[/FONT]. If [FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT] for some x, we posit that the relation holds for x and [FONT=MathJax_Main]∅[/FONT] only, by definition.

and i answered
But then what would be the domain of that relation?!
I think it must be the class of all sets [which is not then a set].

And it's true because we are associating a (single) y to every x (Not only those in [FONT=MathJax_Main]<[/FONT][FONT=MathJax_Math]A[/FONT][FONT=MathJax_Math]B[/FONT].Which means that domain of the relation contains the class of all sets).
===============================
And after all, i suggested a way (Using the axioms of replacement) to have the same result (associating a single y to every x)

[[[[although i doubt it now! because it doesn't have all of assumptions of the Replacement axioms; and even if it does, i am not sure we can get what we want]]]]+++++++++++++++++++++++++++++++++++++

Anyway, my question still holds.
What is the relation you are asserting?! Write it down here please.
 
  • #10
Mathelogician said:
I asked you
If ¬P(x), why should we have a y which is associated with x?
I found this question bizarre. The definition of gamma says that if ~P(x), then the associated y by definition is the empty set and only it. I think everybody understands what it means to create an association between two groups of objects, i.e., to pair each object from the first group with an object from the second group. If you have a problem with this concept, then you should ask questions in the Pre-algebra subforum, which is dedicated to functions, relations and similar notions. I was not sure what exactly your problem was, so in the beginning of post #4 I offered an informal explanation. I used the word "relation" informally. You can skip the beginning and start with the word "Formally."

Now, I think that the best way to clear a misunderstanding is to go formal and be as precise as possible.

Mathelogician said:
Anyway, my question still holds.
What is the relation you are asserting?! Write it down here please.
And my question also still holds: how does defining a relation help satisfy the premises of the transfinite recursion theorem? I don't see the theorem talking about any relation. It requires a formula $\gamma$ and a proof of $\forall x\exists!y\;\gamma(x,y)$. I wrote $\gamma$ explicitly in post #4, and proving $\forall x\exists!y\;\gamma(x,y)$ is trivial by purely logical reasoning.
 
  • #11
First of all, i have to say that i see no reason to get angry in this thread! It's just a discussion; and for the one who asks, must remain no dark part of the subject! [even if that part seem trivially light for the one who answers]===========================

And my question also still holds: how does defining a relation help satisfy the premises of the transfinite recursion theorem? I don't see the theorem talking about any relation. It requires a formula [FONT=MathJax_Math]γ[/FONT] and a proof of [FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∃[/FONT][FONT=MathJax_Main]![/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Math]γ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Main])[/FONT]. I wrote [FONT=MathJax_Math]γ[/FONT] explicitly in post #4, and proving [FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]∃[/FONT][FONT=MathJax_Main]![/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Math]γ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math]y[/FONT][FONT=MathJax_Main])[/FONT] is trivial by purely logical reasoning.

I talked about a relation after you first talked (informally!) about a binary relation which assigns to every x the proper y.
Now that you ask me what is the necessity of using a relation to reach the answer, you yourself must answer it [formally this time!]

I will stay for the pure logical proof of the assertion.
 
  • #12
Mathelogician said:
Now that you ask me what is the necessity of using a relation to reach the answer, you yourself must answer it [formally this time!]
Evgeny.Makarov said:
The brown theorem does not require us to prove that $\{(x,y)\mid \gamma(x,y)\}$ is a set. It just requires to construct a formula $\gamma$.
Evgeny.Makarov said:
Besides < being a well-ordering on A, I see two assumptions: having a formula $\gamma$ and proving $\forall x\exists! y\;\gamma(x,y)$.
Evgeny.Makarov said:
However, this [i.e., considering whether {(x,y): x∈V and γ(x,y) } is a set or a class] is irrelevant for the application of the transfinite recursion theorems.
...
 

FAQ: A question on Transfinite Recursion Theorem schema....

1. What is the Transfinite Recursion Theorem schema?

The Transfinite Recursion Theorem is a mathematical theorem that allows for the construction of a function from a well-ordered set to a set with a given structure. It is often used in set theory and mathematical logic.

2. How does the Transfinite Recursion Theorem work?

The Transfinite Recursion Theorem works by defining a function that maps each element of a well-ordered set to a unique element in a set with a given structure. This function is defined recursively, starting with the first element in the well-ordered set and continuing until all elements have been mapped.

3. What is the significance of the Transfinite Recursion Theorem?

The Transfinite Recursion Theorem is significant because it allows for the construction of functions that would otherwise be impossible to define. It also has applications in various areas of mathematics, including set theory, topology, and analysis.

4. Are there any limitations to the Transfinite Recursion Theorem?

Like any mathematical theorem, the Transfinite Recursion Theorem has its limitations. It can only be applied to well-ordered sets, and the resulting function may not be continuous. Additionally, the theorem does not provide a unique solution, so care must be taken in choosing the initial conditions and the structure of the set being mapped to.

5. What are some real-world applications of the Transfinite Recursion Theorem?

The Transfinite Recursion Theorem has been used to prove various results in mathematics, such as the existence of well-orderings and the Cantor-Bernstein theorem. It also has applications in computer science, particularly in defining recursive data structures and algorithms. In addition, it has been used in the study of infinite games and decision-making processes.

Similar threads

Replies
11
Views
4K
Replies
4
Views
1K
Replies
28
Views
5K
Replies
1
Views
2K
Replies
30
Views
5K
Back
Top