Set theory - Solution without using the Axiom of Choice.

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












I have a question and I want to know if my solution is correct. If it's not, I would like to know why. Anyway, I would love to see more solutions to this problem. There is the problem:

Let $A subseteq P(mathbbR)$ Be a set of open Intervals, when there are no empty sets involved ($emptyset notin A$).
. if $C_1,C_2 in A$, $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. We need to prove that $|A|leq aleph_0$.

At the first time I solved it using the Axiom of Choice, using the fact that we can find a rational number in any non-empty open interval (It helps because $|mathbbQ|=aleph_0$).
Now I am required to solve it without using the axiom of choice. There is my solution, Is it correct?

For any real number $r$, let $r_n$ be the smallest integer that is bigger then r. For each $(a,b) in A$, define $d_(a,b)$ as $d_(a,b)=|b-a|$.
Also, let $n_(a,b)$ be the smallest natural number $n$ such that $frac110^n<d_(a,b)$.

let $k_(a,b)$ be the biggest $x in mathbbN$ such that $b_n-x cdot frac110^n_(a,b) geq b$.


Now define a function $f: A rightarrow mathbbQ$ the following way:

$$
f((a,b))=
begincases
fraca+b2,& textif a in mathbbQ,b in mathbbQ \
a+frac110^n_(a,b), & textif a in mathbbQ,b notin mathbbQ\
b-frac110^n_(a,b), & textif a notin mathbbQ,b in mathbbQ\
b_n-(k_(a,b)+1)cdot frac110^n_(a,b) & textif a notin mathbbQ,b notin mathbbQ
endcases
$$


Now, this is not that hard to show that $f((a,b))$ is a rational number $q in (a,b)$. also, we never get the same rational number twice because $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. So this is Injective function which is exactly what we wanted. Is this solution correct? I am not using the axiom of choice, right? Thanks!







share|cite|improve this question

















  • 1




    math.stackexchange.com/questions/98923/…
    – Asaf Karagila♦
    Aug 7 at 20:42






  • 1




    That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
    – Asaf Karagila♦
    Aug 7 at 21:16














up vote
1
down vote

favorite












I have a question and I want to know if my solution is correct. If it's not, I would like to know why. Anyway, I would love to see more solutions to this problem. There is the problem:

Let $A subseteq P(mathbbR)$ Be a set of open Intervals, when there are no empty sets involved ($emptyset notin A$).
. if $C_1,C_2 in A$, $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. We need to prove that $|A|leq aleph_0$.

At the first time I solved it using the Axiom of Choice, using the fact that we can find a rational number in any non-empty open interval (It helps because $|mathbbQ|=aleph_0$).
Now I am required to solve it without using the axiom of choice. There is my solution, Is it correct?

For any real number $r$, let $r_n$ be the smallest integer that is bigger then r. For each $(a,b) in A$, define $d_(a,b)$ as $d_(a,b)=|b-a|$.
Also, let $n_(a,b)$ be the smallest natural number $n$ such that $frac110^n<d_(a,b)$.

let $k_(a,b)$ be the biggest $x in mathbbN$ such that $b_n-x cdot frac110^n_(a,b) geq b$.


Now define a function $f: A rightarrow mathbbQ$ the following way:

$$
f((a,b))=
begincases
fraca+b2,& textif a in mathbbQ,b in mathbbQ \
a+frac110^n_(a,b), & textif a in mathbbQ,b notin mathbbQ\
b-frac110^n_(a,b), & textif a notin mathbbQ,b in mathbbQ\
b_n-(k_(a,b)+1)cdot frac110^n_(a,b) & textif a notin mathbbQ,b notin mathbbQ
endcases
$$


Now, this is not that hard to show that $f((a,b))$ is a rational number $q in (a,b)$. also, we never get the same rational number twice because $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. So this is Injective function which is exactly what we wanted. Is this solution correct? I am not using the axiom of choice, right? Thanks!







share|cite|improve this question

















  • 1




    math.stackexchange.com/questions/98923/…
    – Asaf Karagila♦
    Aug 7 at 20:42






  • 1




    That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
    – Asaf Karagila♦
    Aug 7 at 21:16












up vote
1
down vote

favorite









up vote
1
down vote

favorite











I have a question and I want to know if my solution is correct. If it's not, I would like to know why. Anyway, I would love to see more solutions to this problem. There is the problem:

Let $A subseteq P(mathbbR)$ Be a set of open Intervals, when there are no empty sets involved ($emptyset notin A$).
. if $C_1,C_2 in A$, $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. We need to prove that $|A|leq aleph_0$.

At the first time I solved it using the Axiom of Choice, using the fact that we can find a rational number in any non-empty open interval (It helps because $|mathbbQ|=aleph_0$).
Now I am required to solve it without using the axiom of choice. There is my solution, Is it correct?

For any real number $r$, let $r_n$ be the smallest integer that is bigger then r. For each $(a,b) in A$, define $d_(a,b)$ as $d_(a,b)=|b-a|$.
Also, let $n_(a,b)$ be the smallest natural number $n$ such that $frac110^n<d_(a,b)$.

let $k_(a,b)$ be the biggest $x in mathbbN$ such that $b_n-x cdot frac110^n_(a,b) geq b$.


Now define a function $f: A rightarrow mathbbQ$ the following way:

$$
f((a,b))=
begincases
fraca+b2,& textif a in mathbbQ,b in mathbbQ \
a+frac110^n_(a,b), & textif a in mathbbQ,b notin mathbbQ\
b-frac110^n_(a,b), & textif a notin mathbbQ,b in mathbbQ\
b_n-(k_(a,b)+1)cdot frac110^n_(a,b) & textif a notin mathbbQ,b notin mathbbQ
endcases
$$


Now, this is not that hard to show that $f((a,b))$ is a rational number $q in (a,b)$. also, we never get the same rational number twice because $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. So this is Injective function which is exactly what we wanted. Is this solution correct? I am not using the axiom of choice, right? Thanks!







share|cite|improve this question













I have a question and I want to know if my solution is correct. If it's not, I would like to know why. Anyway, I would love to see more solutions to this problem. There is the problem:

Let $A subseteq P(mathbbR)$ Be a set of open Intervals, when there are no empty sets involved ($emptyset notin A$).
. if $C_1,C_2 in A$, $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. We need to prove that $|A|leq aleph_0$.

At the first time I solved it using the Axiom of Choice, using the fact that we can find a rational number in any non-empty open interval (It helps because $|mathbbQ|=aleph_0$).
Now I am required to solve it without using the axiom of choice. There is my solution, Is it correct?

For any real number $r$, let $r_n$ be the smallest integer that is bigger then r. For each $(a,b) in A$, define $d_(a,b)$ as $d_(a,b)=|b-a|$.
Also, let $n_(a,b)$ be the smallest natural number $n$ such that $frac110^n<d_(a,b)$.

let $k_(a,b)$ be the biggest $x in mathbbN$ such that $b_n-x cdot frac110^n_(a,b) geq b$.


Now define a function $f: A rightarrow mathbbQ$ the following way:

$$
f((a,b))=
begincases
fraca+b2,& textif a in mathbbQ,b in mathbbQ \
a+frac110^n_(a,b), & textif a in mathbbQ,b notin mathbbQ\
b-frac110^n_(a,b), & textif a notin mathbbQ,b in mathbbQ\
b_n-(k_(a,b)+1)cdot frac110^n_(a,b) & textif a notin mathbbQ,b notin mathbbQ
endcases
$$


Now, this is not that hard to show that $f((a,b))$ is a rational number $q in (a,b)$. also, we never get the same rational number twice because $C_1 neq C_2 rightarrow C_1 cap C_2=emptyset$. So this is Injective function which is exactly what we wanted. Is this solution correct? I am not using the axiom of choice, right? Thanks!









share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited Aug 7 at 20:40









Asaf Karagila♦

292k31403733




292k31403733









asked Aug 7 at 20:28









Omer

1445




1445







  • 1




    math.stackexchange.com/questions/98923/…
    – Asaf Karagila♦
    Aug 7 at 20:42






  • 1




    That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
    – Asaf Karagila♦
    Aug 7 at 21:16












  • 1




    math.stackexchange.com/questions/98923/…
    – Asaf Karagila♦
    Aug 7 at 20:42






  • 1




    That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
    – Asaf Karagila♦
    Aug 7 at 21:16







1




1




math.stackexchange.com/questions/98923/…
– Asaf Karagila♦
Aug 7 at 20:42




math.stackexchange.com/questions/98923/…
– Asaf Karagila♦
Aug 7 at 20:42




1




1




That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
– Asaf Karagila♦
Aug 7 at 21:16




That reminds me of the first time I proved this sort of proposition in front of a classroom full of first-semester freshmen. I later honed and refined this to avoid the very explicit and overly complicated algorithm.
– Asaf Karagila♦
Aug 7 at 21:16










1 Answer
1






active

oldest

votes

















up vote
5
down vote













Yes, this is perfectly correct. Note that you can avoid all your complicated casework by fixing once and for all a bijection $g:mathbbNtomathbbQ$ and then define $f((a,b))=g(n)$ for the least $n$ such that $g(n)in (a,b)$. (Of course, defining such a bijection $g$ explicitly would involve some sort of casework similar to what you did, but fixing such a bijection ahead of time makes the argument conceptually a lot simpler.)






share|cite|improve this answer





















    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',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    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%2f2875367%2fset-theory-solution-without-using-the-axiom-of-choice%23new-answer', 'question_page');

    );

    Post as a guest






























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    5
    down vote













    Yes, this is perfectly correct. Note that you can avoid all your complicated casework by fixing once and for all a bijection $g:mathbbNtomathbbQ$ and then define $f((a,b))=g(n)$ for the least $n$ such that $g(n)in (a,b)$. (Of course, defining such a bijection $g$ explicitly would involve some sort of casework similar to what you did, but fixing such a bijection ahead of time makes the argument conceptually a lot simpler.)






    share|cite|improve this answer

























      up vote
      5
      down vote













      Yes, this is perfectly correct. Note that you can avoid all your complicated casework by fixing once and for all a bijection $g:mathbbNtomathbbQ$ and then define $f((a,b))=g(n)$ for the least $n$ such that $g(n)in (a,b)$. (Of course, defining such a bijection $g$ explicitly would involve some sort of casework similar to what you did, but fixing such a bijection ahead of time makes the argument conceptually a lot simpler.)






      share|cite|improve this answer























        up vote
        5
        down vote










        up vote
        5
        down vote









        Yes, this is perfectly correct. Note that you can avoid all your complicated casework by fixing once and for all a bijection $g:mathbbNtomathbbQ$ and then define $f((a,b))=g(n)$ for the least $n$ such that $g(n)in (a,b)$. (Of course, defining such a bijection $g$ explicitly would involve some sort of casework similar to what you did, but fixing such a bijection ahead of time makes the argument conceptually a lot simpler.)






        share|cite|improve this answer













        Yes, this is perfectly correct. Note that you can avoid all your complicated casework by fixing once and for all a bijection $g:mathbbNtomathbbQ$ and then define $f((a,b))=g(n)$ for the least $n$ such that $g(n)in (a,b)$. (Of course, defining such a bijection $g$ explicitly would involve some sort of casework similar to what you did, but fixing such a bijection ahead of time makes the argument conceptually a lot simpler.)







        share|cite|improve this answer













        share|cite|improve this answer



        share|cite|improve this answer











        answered Aug 7 at 20:37









        Eric Wofsey

        163k12190301




        163k12190301






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2875367%2fset-theory-solution-without-using-the-axiom-of-choice%23new-answer', 'question_page');

            );

            Post as a guest













































































            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            Mutual Information Always Non-negative

            Why am i infinitely getting the same tweet with the Twitter Search API?