Validity of a function g such that g(x)={x}












0












$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










share|cite|improve this question











$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


















0












$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










share|cite|improve this question











$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
















0












0








0





$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










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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
















  • 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












1 Answer
1






active

oldest

votes


















1












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






share|cite|improve this answer









$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











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
});


}
});














draft saved

draft discarded


















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









1












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






share|cite|improve this answer









$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
















1












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






share|cite|improve this answer









$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














1












1








1





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






share|cite|improve this answer









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







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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


















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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Plaza Victoria

Puebla de Zaragoza

Musa