MHB A question on Transfinite Recursion Theorem schema....

[Mathelogician]

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

 

[Evgeny.Makarov]

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.

 

[Mathelogician]

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?

 

[Evgeny.Makarov]

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.

 

[Mathelogician]

By definition. We define a binary relation on sets. Let P(x) denote [FONT=MathJax_Math]x[FONT=MathJax_Main]∈[FONT=MathJax_Main]<[FONT=MathJax_Math]A[FONT=MathJax_Math]B. If [FONT=MathJax_Main]¬[FONT=MathJax_Math]P[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main]) for some x, we posit that the relation holds for x and [FONT=MathJax_Main]∅ 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=MathJax_Main]∈V and [FONT=MathJax_Math]γ[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main],[FONT=MathJax_Math]y[FONT=MathJax_Main]) } 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=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main],[FONT=MathJax_Math]y[FONT=MathJax_Main]).

And then we can conclude the others.
===================================
And i got all other your claims with no dark part.

 

[Evgeny.Makarov]

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$.

 

[Mathelogician]

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.

 

[Evgeny.Makarov]

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)$.

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)$.

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.

 

[Mathelogician]

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]γ and proving [FONT=MathJax_Main]∀[FONT=MathJax_Math]x[FONT=MathJax_Main]∃[FONT=MathJax_Main]![FONT=MathJax_Math]y[FONT=MathJax_Math]γ[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main],[FONT=MathJax_Math]y[FONT=MathJax_Main]).

My problem was proving the blue(and "it' refers to that).
I asked you

If [FONT=MathJax_Main]¬[FONT=MathJax_Math]P[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main]), 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=MathJax_Main]∈[FONT=MathJax_Main]<[FONT=MathJax_Math]A[FONT=MathJax_Math]B. If [FONT=MathJax_Main]¬[FONT=MathJax_Math]P[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main]) for some x, we posit that the relation holds for x and [FONT=MathJax_Main]∅ 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=MathJax_Math]A[FONT=MathJax_Math]B.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.

 

[Evgeny.Makarov]

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.

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.

 

[Mathelogician]

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]γ and a proof of [FONT=MathJax_Main]∀[FONT=MathJax_Math]x[FONT=MathJax_Main]∃[FONT=MathJax_Main]![FONT=MathJax_Math]y[FONT=MathJax_Math]γ[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main],[FONT=MathJax_Math]y[FONT=MathJax_Main]). I wrote [FONT=MathJax_Math]γ explicitly in post #4, and proving [FONT=MathJax_Main]∀[FONT=MathJax_Math]x[FONT=MathJax_Main]∃[FONT=MathJax_Main]![FONT=MathJax_Math]y[FONT=MathJax_Math]γ[FONT=MathJax_Main]([FONT=MathJax_Math]x[FONT=MathJax_Main],[FONT=MathJax_Math]y[FONT=MathJax_Main]) 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.

 

[Evgeny.Makarov]

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!]

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$.

Besides < being a well-ordering on A, I see two assumptions: having a formula $\gamma$ and proving $\forall x\exists! y\;\gamma(x,y)$.

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.

...