Validity of a function g such that g(x)={x}
$begingroup$
I've been reading some set theory lately, and I wanted to revisit a question I had in my first-year algebra course. We had to prove that the set of Zermelo ordinals $mathbb{S}={emptyset,{emptyset},{{emptyset}},...}$ was a valid set under the ZFC axioms. I originally did this by using the axiom schema of replacement and defining a function $mathit{f}:mathbb{N}rightarrowmathbb{S}$ such that for every $mathit{n}inmathbb{N}$ there is exactly once $mathit{s}inmathbb{S}$. However, I wanted to try and re-do this using the recursion theorem as I believe this would be a cleaner approach. The obvious way to do this is as follows:
Let $mathit{g}(x)={x}$, then by said theorem there is a unique sequence $mathit{f}$ s.t. $mathit{f}_0=emptyset$ and $mathit{f}_{n+1}=mathit{g}(mathit{f}_n)$. The only problem is, letting $mathbb{U}$ be the class of all sets, we have that $mathit{g}subsetmathbb{U}timesmathbb{U}$ so it is thus not known to be a set, invalidating it's being a function and thus the entire argument. Is there an easy way to fix this or an alternative method to prove that $mathbb{O}$ is a set using the recursion theorem.
The recursion theorem:https://en.wikipedia.org/wiki/Recursion#The_recursion_theorem
set-theory
$endgroup$
|
show 2 more comments
$begingroup$
I've been reading some set theory lately, and I wanted to revisit a question I had in my first-year algebra course. We had to prove that the set of Zermelo ordinals $mathbb{S}={emptyset,{emptyset},{{emptyset}},...}$ was a valid set under the ZFC axioms. I originally did this by using the axiom schema of replacement and defining a function $mathit{f}:mathbb{N}rightarrowmathbb{S}$ such that for every $mathit{n}inmathbb{N}$ there is exactly once $mathit{s}inmathbb{S}$. However, I wanted to try and re-do this using the recursion theorem as I believe this would be a cleaner approach. The obvious way to do this is as follows:
Let $mathit{g}(x)={x}$, then by said theorem there is a unique sequence $mathit{f}$ s.t. $mathit{f}_0=emptyset$ and $mathit{f}_{n+1}=mathit{g}(mathit{f}_n)$. The only problem is, letting $mathbb{U}$ be the class of all sets, we have that $mathit{g}subsetmathbb{U}timesmathbb{U}$ so it is thus not known to be a set, invalidating it's being a function and thus the entire argument. Is there an easy way to fix this or an alternative method to prove that $mathbb{O}$ is a set using the recursion theorem.
The recursion theorem:https://en.wikipedia.org/wiki/Recursion#The_recursion_theorem
set-theory
$endgroup$
1
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
1
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48
|
show 2 more comments
$begingroup$
I've been reading some set theory lately, and I wanted to revisit a question I had in my first-year algebra course. We had to prove that the set of Zermelo ordinals $mathbb{S}={emptyset,{emptyset},{{emptyset}},...}$ was a valid set under the ZFC axioms. I originally did this by using the axiom schema of replacement and defining a function $mathit{f}:mathbb{N}rightarrowmathbb{S}$ such that for every $mathit{n}inmathbb{N}$ there is exactly once $mathit{s}inmathbb{S}$. However, I wanted to try and re-do this using the recursion theorem as I believe this would be a cleaner approach. The obvious way to do this is as follows:
Let $mathit{g}(x)={x}$, then by said theorem there is a unique sequence $mathit{f}$ s.t. $mathit{f}_0=emptyset$ and $mathit{f}_{n+1}=mathit{g}(mathit{f}_n)$. The only problem is, letting $mathbb{U}$ be the class of all sets, we have that $mathit{g}subsetmathbb{U}timesmathbb{U}$ so it is thus not known to be a set, invalidating it's being a function and thus the entire argument. Is there an easy way to fix this or an alternative method to prove that $mathbb{O}$ is a set using the recursion theorem.
The recursion theorem:https://en.wikipedia.org/wiki/Recursion#The_recursion_theorem
set-theory
$endgroup$
I've been reading some set theory lately, and I wanted to revisit a question I had in my first-year algebra course. We had to prove that the set of Zermelo ordinals $mathbb{S}={emptyset,{emptyset},{{emptyset}},...}$ was a valid set under the ZFC axioms. I originally did this by using the axiom schema of replacement and defining a function $mathit{f}:mathbb{N}rightarrowmathbb{S}$ such that for every $mathit{n}inmathbb{N}$ there is exactly once $mathit{s}inmathbb{S}$. However, I wanted to try and re-do this using the recursion theorem as I believe this would be a cleaner approach. The obvious way to do this is as follows:
Let $mathit{g}(x)={x}$, then by said theorem there is a unique sequence $mathit{f}$ s.t. $mathit{f}_0=emptyset$ and $mathit{f}_{n+1}=mathit{g}(mathit{f}_n)$. The only problem is, letting $mathbb{U}$ be the class of all sets, we have that $mathit{g}subsetmathbb{U}timesmathbb{U}$ so it is thus not known to be a set, invalidating it's being a function and thus the entire argument. Is there an easy way to fix this or an alternative method to prove that $mathbb{O}$ is a set using the recursion theorem.
The recursion theorem:https://en.wikipedia.org/wiki/Recursion#The_recursion_theorem
set-theory
set-theory
edited Dec 18 '18 at 0:51
Andrés E. Caicedo
65.8k8160251
65.8k8160251
asked Dec 17 '18 at 21:39
R.JacksonR.Jackson
1688
1688
1
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
1
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48
|
show 2 more comments
1
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
1
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48
1
1
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
1
1
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Because of the axiom of infinity we know that there exists an inductive set $X$. This is, $X$ satisfies the following property: $(emptysetin X)wedgeforall xin X(xcup{x}in X)$.
Power set axiom guarantees that $A=mathscr P(X)$ is a set. Now you can consider $gsubseteq Xtimes A$, and by induction theorem $mathbb Nsubseteq X$.
$endgroup$
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3044477%2fvalidity-of-a-function-g-such-that-gx-x%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Because of the axiom of infinity we know that there exists an inductive set $X$. This is, $X$ satisfies the following property: $(emptysetin X)wedgeforall xin X(xcup{x}in X)$.
Power set axiom guarantees that $A=mathscr P(X)$ is a set. Now you can consider $gsubseteq Xtimes A$, and by induction theorem $mathbb Nsubseteq X$.
$endgroup$
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
add a comment |
$begingroup$
Because of the axiom of infinity we know that there exists an inductive set $X$. This is, $X$ satisfies the following property: $(emptysetin X)wedgeforall xin X(xcup{x}in X)$.
Power set axiom guarantees that $A=mathscr P(X)$ is a set. Now you can consider $gsubseteq Xtimes A$, and by induction theorem $mathbb Nsubseteq X$.
$endgroup$
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
add a comment |
$begingroup$
Because of the axiom of infinity we know that there exists an inductive set $X$. This is, $X$ satisfies the following property: $(emptysetin X)wedgeforall xin X(xcup{x}in X)$.
Power set axiom guarantees that $A=mathscr P(X)$ is a set. Now you can consider $gsubseteq Xtimes A$, and by induction theorem $mathbb Nsubseteq X$.
$endgroup$
Because of the axiom of infinity we know that there exists an inductive set $X$. This is, $X$ satisfies the following property: $(emptysetin X)wedgeforall xin X(xcup{x}in X)$.
Power set axiom guarantees that $A=mathscr P(X)$ is a set. Now you can consider $gsubseteq Xtimes A$, and by induction theorem $mathbb Nsubseteq X$.
answered Dec 18 '18 at 1:25
Jesús Miguel Martínez CamarenaJesús Miguel Martínez Camarena
363
363
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
add a comment |
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
But not every element of $mathbb{S}$ is in A.
$endgroup$
– R.Jackson
Dec 18 '18 at 2:29
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
$begingroup$
You are completely right sir. My answer doesn't help. I will think if I can think of another way :/
$endgroup$
– Jesús Miguel Martínez Camarena
Dec 18 '18 at 3:35
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3044477%2fvalidity-of-a-function-g-such-that-gx-x%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
How do you get the set $S$ if the $f_n$'s are given?
$endgroup$
– Berci
Dec 17 '18 at 21:51
$begingroup$
The recursion theorem guarantees the existence of the function $mathit{f}:/mathbb{N}rightarrow/mathbb{S}$ such that we have, for every natural $n$,$(n,/mathit{f}_n)/in/mathit{f}$ so just take the projection map $(n,/mathit{f}_n)/rightarrow/mathit{f}_n$
$endgroup$
– R.Jackson
Dec 17 '18 at 22:31
1
$begingroup$
In the version of the recursion theorem I was taught (Hrbacek-Jech) a class function was OK as the basis. You just need to show that every $x$ has a unique successor set $g(x) = {x}$.
$endgroup$
– Henno Brandsma
Dec 19 '18 at 22:23
$begingroup$
@HennoBrandsma this is the same book I’m currently reading. I’m assuming this stronger recursion theorem is the one they alluded to in chapter 4? In that case I’ll get there eventually because currently they’ve only done it with a function $g:mathbb{A}bigtimesmathbb{N}rightarrrowmathbb{A}$ for a set $mathbb{A}$
$endgroup$
– R.Jackson
Dec 19 '18 at 23:03
$begingroup$
You can always view $g$ as a function HF to HF (where HF is the set of hereditary finite sets)... But then again the way to construct HF is by iterating the power set $omega$ times (and the power set is a class function) which you could ask this same question about.
$endgroup$
– spaceisdarkgreen
Dec 21 '18 at 18:48