Set theory - Solution without using the Axiom of Choice.
Clash 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!
general-topology proof-verification axiom-of-choice
add a comment |Â
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!
general-topology proof-verification axiom-of-choice
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
add a comment |Â
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!
general-topology proof-verification axiom-of-choice
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!
general-topology proof-verification axiom-of-choice
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
add a comment |Â
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
add a comment |Â
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.)
add a comment |Â
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.)
add a comment |Â
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.)
add a comment |Â
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.)
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.)
answered Aug 7 at 20:37
Eric Wofsey
163k12190301
163k12190301
add a comment |Â
add a comment |Â
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
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
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
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
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
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