An infinite subset of a countable set is countable
$begingroup$
In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?
Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: mathbb{N} rightarrow T$. And $S subseteq T = { f(n) | n in mathbb{N} }$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) in S$. And because $S$ is infinite, we continue forever. Now consider the function $beta : mathbb{N} rightarrow S$ which sends $k rightarrow f(n_{k})$.
So in order for $S$ to be countable, $beta$ would have to be a bijection. $beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.
Edit: $beta$ also needs to be surjective. So for every $r in S$ there exists a $q in mathbb{N}$ such that $beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) in {n_{1}, n_{2}, ..., n_{k} ... }$, so we can let $f^{-1}(r) = n_{d}$. Thus $beta(d) = f(n_{d}) = r$.
elementary-set-theory cardinals
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
$endgroup$
add a comment |
$begingroup$
In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?
Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: mathbb{N} rightarrow T$. And $S subseteq T = { f(n) | n in mathbb{N} }$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) in S$. And because $S$ is infinite, we continue forever. Now consider the function $beta : mathbb{N} rightarrow S$ which sends $k rightarrow f(n_{k})$.
So in order for $S$ to be countable, $beta$ would have to be a bijection. $beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.
Edit: $beta$ also needs to be surjective. So for every $r in S$ there exists a $q in mathbb{N}$ such that $beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) in {n_{1}, n_{2}, ..., n_{k} ... }$, so we can let $f^{-1}(r) = n_{d}$. Thus $beta(d) = f(n_{d}) = r$.
elementary-set-theory cardinals
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
$endgroup$
2
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
2
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41
add a comment |
$begingroup$
In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?
Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: mathbb{N} rightarrow T$. And $S subseteq T = { f(n) | n in mathbb{N} }$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) in S$. And because $S$ is infinite, we continue forever. Now consider the function $beta : mathbb{N} rightarrow S$ which sends $k rightarrow f(n_{k})$.
So in order for $S$ to be countable, $beta$ would have to be a bijection. $beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.
Edit: $beta$ also needs to be surjective. So for every $r in S$ there exists a $q in mathbb{N}$ such that $beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) in {n_{1}, n_{2}, ..., n_{k} ... }$, so we can let $f^{-1}(r) = n_{d}$. Thus $beta(d) = f(n_{d}) = r$.
elementary-set-theory cardinals
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
$endgroup$
In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?
Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: mathbb{N} rightarrow T$. And $S subseteq T = { f(n) | n in mathbb{N} }$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) in S$. And because $S$ is infinite, we continue forever. Now consider the function $beta : mathbb{N} rightarrow S$ which sends $k rightarrow f(n_{k})$.
So in order for $S$ to be countable, $beta$ would have to be a bijection. $beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.
Edit: $beta$ also needs to be surjective. So for every $r in S$ there exists a $q in mathbb{N}$ such that $beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) in {n_{1}, n_{2}, ..., n_{k} ... }$, so we can let $f^{-1}(r) = n_{d}$. Thus $beta(d) = f(n_{d}) = r$.
elementary-set-theory cardinals
elementary-set-theory cardinals
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
edited Feb 9 '12 at 22:31
Student
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
asked Feb 9 '12 at 21:35
StudentStudent
1,58412550
1,58412550
2
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
2
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41
add a comment |
2
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
2
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41
2
2
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
2
2
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To fix the last statement:
Suppose that $q=f^{-1}(r)$. Then ${ 0,1,2,dots,q}$ is a finite set. Intersect this with $f^{-1}(S) = { n in mathbb{N} ;|; f(n) in S}$ and get a finite set. By your definition of the $n_k$'s this set is ${n_0,n_1,dots,n_ell}$ for some $ell$. Thus $q=n_ell$. Therefore, $beta(ell)=f(n_ell)=f(q)=r$. Patched.
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
$endgroup$
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
add a comment |
$begingroup$
The set $A$ is countable if there is $f:Atomathbb N$ which is injective.
Suppose $Bsubseteq A$ then $f|_B:Btomathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.
Suppose that $f:Atomathbb N$ is a bijection and $Bsubseteq A$ is infinite. Let $N={f(b)mid bin B}$, the image of $B$.
Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $mathbb N$ is countable:
We define inductively a function $g:mathbb Nto N$, $g(0)=min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.
It is obvious that $g$ is a bijection between $mathbb N$ and $N$. Now we have that $g^{-1}circ f|_B:Btomathbb N$ is a bijection, as wanted.
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
|
show 4 more comments
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%2f107617%2fan-infinite-subset-of-a-countable-set-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To fix the last statement:
Suppose that $q=f^{-1}(r)$. Then ${ 0,1,2,dots,q}$ is a finite set. Intersect this with $f^{-1}(S) = { n in mathbb{N} ;|; f(n) in S}$ and get a finite set. By your definition of the $n_k$'s this set is ${n_0,n_1,dots,n_ell}$ for some $ell$. Thus $q=n_ell$. Therefore, $beta(ell)=f(n_ell)=f(q)=r$. Patched.
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
$endgroup$
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
add a comment |
$begingroup$
To fix the last statement:
Suppose that $q=f^{-1}(r)$. Then ${ 0,1,2,dots,q}$ is a finite set. Intersect this with $f^{-1}(S) = { n in mathbb{N} ;|; f(n) in S}$ and get a finite set. By your definition of the $n_k$'s this set is ${n_0,n_1,dots,n_ell}$ for some $ell$. Thus $q=n_ell$. Therefore, $beta(ell)=f(n_ell)=f(q)=r$. Patched.
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
$endgroup$
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
add a comment |
$begingroup$
To fix the last statement:
Suppose that $q=f^{-1}(r)$. Then ${ 0,1,2,dots,q}$ is a finite set. Intersect this with $f^{-1}(S) = { n in mathbb{N} ;|; f(n) in S}$ and get a finite set. By your definition of the $n_k$'s this set is ${n_0,n_1,dots,n_ell}$ for some $ell$. Thus $q=n_ell$. Therefore, $beta(ell)=f(n_ell)=f(q)=r$. Patched.
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
$endgroup$
To fix the last statement:
Suppose that $q=f^{-1}(r)$. Then ${ 0,1,2,dots,q}$ is a finite set. Intersect this with $f^{-1}(S) = { n in mathbb{N} ;|; f(n) in S}$ and get a finite set. By your definition of the $n_k$'s this set is ${n_0,n_1,dots,n_ell}$ for some $ell$. Thus $q=n_ell$. Therefore, $beta(ell)=f(n_ell)=f(q)=r$. Patched.
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
answered Feb 9 '12 at 21:45
Bill CookBill Cook
23k4869
23k4869
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
add a comment |
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
1
1
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
$begingroup$
Can you see if I understand what you mean in my edit?
$endgroup$
– Student
Feb 9 '12 at 22:23
1
1
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
That's seems reasonable.
$endgroup$
– Bill Cook
Feb 9 '12 at 22:35
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
@BillCook how is {0,1,2,...q} is finite ? thanks
$endgroup$
– Taylor Ted
Jul 8 '15 at 5:17
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
$begingroup$
It's finite since ${0,1,2,dots,q}$ has exactly $q+1$ elements (a finite number of elements).
$endgroup$
– Bill Cook
Jul 8 '15 at 11:18
add a comment |
$begingroup$
The set $A$ is countable if there is $f:Atomathbb N$ which is injective.
Suppose $Bsubseteq A$ then $f|_B:Btomathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.
Suppose that $f:Atomathbb N$ is a bijection and $Bsubseteq A$ is infinite. Let $N={f(b)mid bin B}$, the image of $B$.
Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $mathbb N$ is countable:
We define inductively a function $g:mathbb Nto N$, $g(0)=min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.
It is obvious that $g$ is a bijection between $mathbb N$ and $N$. Now we have that $g^{-1}circ f|_B:Btomathbb N$ is a bijection, as wanted.
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
|
show 4 more comments
$begingroup$
The set $A$ is countable if there is $f:Atomathbb N$ which is injective.
Suppose $Bsubseteq A$ then $f|_B:Btomathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.
Suppose that $f:Atomathbb N$ is a bijection and $Bsubseteq A$ is infinite. Let $N={f(b)mid bin B}$, the image of $B$.
Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $mathbb N$ is countable:
We define inductively a function $g:mathbb Nto N$, $g(0)=min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.
It is obvious that $g$ is a bijection between $mathbb N$ and $N$. Now we have that $g^{-1}circ f|_B:Btomathbb N$ is a bijection, as wanted.
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
|
show 4 more comments
$begingroup$
The set $A$ is countable if there is $f:Atomathbb N$ which is injective.
Suppose $Bsubseteq A$ then $f|_B:Btomathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.
Suppose that $f:Atomathbb N$ is a bijection and $Bsubseteq A$ is infinite. Let $N={f(b)mid bin B}$, the image of $B$.
Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $mathbb N$ is countable:
We define inductively a function $g:mathbb Nto N$, $g(0)=min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.
It is obvious that $g$ is a bijection between $mathbb N$ and $N$. Now we have that $g^{-1}circ f|_B:Btomathbb N$ is a bijection, as wanted.
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
The set $A$ is countable if there is $f:Atomathbb N$ which is injective.
Suppose $Bsubseteq A$ then $f|_B:Btomathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.
Suppose that $f:Atomathbb N$ is a bijection and $Bsubseteq A$ is infinite. Let $N={f(b)mid bin B}$, the image of $B$.
Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $mathbb N$ is countable:
We define inductively a function $g:mathbb Nto N$, $g(0)=min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.
It is obvious that $g$ is a bijection between $mathbb N$ and $N$. Now we have that $g^{-1}circ f|_B:Btomathbb N$ is a bijection, as wanted.
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
edited Feb 9 '12 at 21:52
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
answered Feb 9 '12 at 21:43
Asaf Karagila♦Asaf Karagila
302k32429760
302k32429760
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
|
show 4 more comments
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
1
1
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering.
$endgroup$
– user2093
Feb 9 '12 at 21:44
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
With g :ℕ→N, g(0) is undefined.
$endgroup$
– davide
Jul 31 '18 at 13:00
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
@davide: ??? I explicitly defined it.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:04
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ.
$endgroup$
– davide
Jul 31 '18 at 13:09
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
$begingroup$
@davide: Did you read the word "define"? We define the function $g$. And we define it by recursion.
$endgroup$
– Asaf Karagila♦
Jul 31 '18 at 13:13
|
show 4 more comments
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%2f107617%2fan-infinite-subset-of-a-countable-set-is-countable%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
2
$begingroup$
Your last statement doesn't really prove $beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$.
$endgroup$
– Bill Cook
Feb 9 '12 at 21:41
2
$begingroup$
You're on the right track. Perhaps it is easier to show that any infinite subset of $mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $mathbb{N}$.
$endgroup$
– user2093
Feb 9 '12 at 21:41
$begingroup$
@Bill: That $f$ is a bijection is given.
$endgroup$
– Brian M. Scott
Feb 9 '12 at 21:41