Elementary questions regarding countable setsCan surjective functions map an element from the domain…Proving sets A and B are countableGiving injective formulas for a function f: $mathbbN rightarrow L$ given a set $L = (a,b)mid a,b ∈ mathbb N$Questions regarding Cantors' TheoremIs $g : mathbb R →mathbb R$, $g(x) = |x|$ one-to-one and onto?Show that if there is a function $g:Yto X$ such that $gcirc f$ is the identity function on $X$, then $f$ is one to one.Well-ordered and Inductive SetsIs the statement “all bounded subsets of countable sets are finite” true?Proving f is onto given if $g circ f = h circ f$, then g = hHow to describe an instance where every $y$ in a codomaine $Y$ is mapped to multiple elements $x$ in a domaine $X$
Venezuelan girlfriend wants to travel the USA to be with me. What is the process?
Are there any examples of a variable being normally distributed that is *not* due to the Central Limit Theorem?
Intersection Puzzle
Is it possible to create a QR code using text?
Can I run a new neutral wire to repair a broken circuit?
Can a virus destroy the BIOS of a modern computer?
Is "remove commented out code" correct English?
How seriously should I take size and weight limits of hand luggage?
Unlock My Phone! February 2018
Why is consensus so controversial in Britain?
How do I gain back my faith in my PhD degree?
Is it inappropriate for a student to attend their mentor's dissertation defense?
Which is the best way to check return result?
Method Does Not Exist error message
How would I stat a creature to be immune to everything but the Magic Missile spell? (just for fun)
Assassin's bullet with mercury
Should I tell management that I intend to leave due to bad software development practices?
Why no variance term in Bayesian logistic regression?
Do UK voters know if their MP will be the Speaker of the House?
What method can I use to design a dungeon difficult enough that the PCs can't make it through without killing them?
Do scales need to be in alphabetical order?
What do you call someone who asks many questions?
How to show a landlord what we have in savings?
Arrow those variables!
Elementary questions regarding countable sets
Can surjective functions map an element from the domain…Proving sets A and B are countableGiving injective formulas for a function f: $mathbbN rightarrow L$ given a set $L = (a,b)mid a,b ∈ mathbb N$Questions regarding Cantors' TheoremIs $g : mathbb R →mathbb R$, $g(x) = |x|$ one-to-one and onto?Show that if there is a function $g:Yto X$ such that $gcirc f$ is the identity function on $X$, then $f$ is one to one.Well-ordered and Inductive SetsIs the statement “all bounded subsets of countable sets are finite” true?Proving f is onto given if $g circ f = h circ f$, then g = hHow to describe an instance where every $y$ in a codomaine $Y$ is mapped to multiple elements $x$ in a domaine $X$
$begingroup$
can somebody help me correct my attempts at proving the following result? Much appreciated.
Theorem. Suppose $X$ is a nonempty finite set. Let $n$ be the least natural number such that there is a one-to-one function $f: X rightarrow $ $1,2,3,...,n$. With the number of elements in $X$ being |$X$|$=n$, prove that $f$ must be onto.
My Attempt:
Suppose for contradiction that $f$ is not onto,then there exist some elements in the codomain $1,2,3,...,n$ such that no elements of the domain map to them. Let $1 le i le n$ be the largest element of the codomain such that $i notin ran(f)$.
[case $i=n$]. If $i=n$, then by definition $n notin ran(f)$.Since n is the least natural number that ensures $f$ to be one-to-one, it must be the case that $n in ran(f)$ providing the contradiction sought.
[case $i<n$] the book gives the hint :
if $i<n$,let $a in X$ be such that $f(a)=n$.Define a one-to-one
function $g : Xrightarrow$ $1,2,...,n-1$.
Hence i thought : With $i<n$ and by definition $i notin ran(f)$ but $n in ran(f)$,there is an element $a in X$ such that $f(a)=n$. With $|X|=n$,the number of elements in the domain and codomain are the same,therefore if there is no element in $X$ that maps to $i in $ $1,2,3,...,n-1$ then $f$ cannot be one-to-one...but where is g?
this feels wrong but i do not know what to do!
Any help appreciated.
proof-verification elementary-set-theory proof-writing
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
$endgroup$
add a comment |
$begingroup$
can somebody help me correct my attempts at proving the following result? Much appreciated.
Theorem. Suppose $X$ is a nonempty finite set. Let $n$ be the least natural number such that there is a one-to-one function $f: X rightarrow $ $1,2,3,...,n$. With the number of elements in $X$ being |$X$|$=n$, prove that $f$ must be onto.
My Attempt:
Suppose for contradiction that $f$ is not onto,then there exist some elements in the codomain $1,2,3,...,n$ such that no elements of the domain map to them. Let $1 le i le n$ be the largest element of the codomain such that $i notin ran(f)$.
[case $i=n$]. If $i=n$, then by definition $n notin ran(f)$.Since n is the least natural number that ensures $f$ to be one-to-one, it must be the case that $n in ran(f)$ providing the contradiction sought.
[case $i<n$] the book gives the hint :
if $i<n$,let $a in X$ be such that $f(a)=n$.Define a one-to-one
function $g : Xrightarrow$ $1,2,...,n-1$.
Hence i thought : With $i<n$ and by definition $i notin ran(f)$ but $n in ran(f)$,there is an element $a in X$ such that $f(a)=n$. With $|X|=n$,the number of elements in the domain and codomain are the same,therefore if there is no element in $X$ that maps to $i in $ $1,2,3,...,n-1$ then $f$ cannot be one-to-one...but where is g?
this feels wrong but i do not know what to do!
Any help appreciated.
proof-verification elementary-set-theory proof-writing
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
$endgroup$
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
2
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10
add a comment |
$begingroup$
can somebody help me correct my attempts at proving the following result? Much appreciated.
Theorem. Suppose $X$ is a nonempty finite set. Let $n$ be the least natural number such that there is a one-to-one function $f: X rightarrow $ $1,2,3,...,n$. With the number of elements in $X$ being |$X$|$=n$, prove that $f$ must be onto.
My Attempt:
Suppose for contradiction that $f$ is not onto,then there exist some elements in the codomain $1,2,3,...,n$ such that no elements of the domain map to them. Let $1 le i le n$ be the largest element of the codomain such that $i notin ran(f)$.
[case $i=n$]. If $i=n$, then by definition $n notin ran(f)$.Since n is the least natural number that ensures $f$ to be one-to-one, it must be the case that $n in ran(f)$ providing the contradiction sought.
[case $i<n$] the book gives the hint :
if $i<n$,let $a in X$ be such that $f(a)=n$.Define a one-to-one
function $g : Xrightarrow$ $1,2,...,n-1$.
Hence i thought : With $i<n$ and by definition $i notin ran(f)$ but $n in ran(f)$,there is an element $a in X$ such that $f(a)=n$. With $|X|=n$,the number of elements in the domain and codomain are the same,therefore if there is no element in $X$ that maps to $i in $ $1,2,3,...,n-1$ then $f$ cannot be one-to-one...but where is g?
this feels wrong but i do not know what to do!
Any help appreciated.
proof-verification elementary-set-theory proof-writing
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
$endgroup$
can somebody help me correct my attempts at proving the following result? Much appreciated.
Theorem. Suppose $X$ is a nonempty finite set. Let $n$ be the least natural number such that there is a one-to-one function $f: X rightarrow $ $1,2,3,...,n$. With the number of elements in $X$ being |$X$|$=n$, prove that $f$ must be onto.
My Attempt:
Suppose for contradiction that $f$ is not onto,then there exist some elements in the codomain $1,2,3,...,n$ such that no elements of the domain map to them. Let $1 le i le n$ be the largest element of the codomain such that $i notin ran(f)$.
[case $i=n$]. If $i=n$, then by definition $n notin ran(f)$.Since n is the least natural number that ensures $f$ to be one-to-one, it must be the case that $n in ran(f)$ providing the contradiction sought.
[case $i<n$] the book gives the hint :
if $i<n$,let $a in X$ be such that $f(a)=n$.Define a one-to-one
function $g : Xrightarrow$ $1,2,...,n-1$.
Hence i thought : With $i<n$ and by definition $i notin ran(f)$ but $n in ran(f)$,there is an element $a in X$ such that $f(a)=n$. With $|X|=n$,the number of elements in the domain and codomain are the same,therefore if there is no element in $X$ that maps to $i in $ $1,2,3,...,n-1$ then $f$ cannot be one-to-one...but where is g?
this feels wrong but i do not know what to do!
Any help appreciated.
proof-verification elementary-set-theory proof-writing
proof-verification elementary-set-theory proof-writing
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
asked Mar 28 at 20:03
HalfAFootHalfAFoot
347
347
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
2
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10
add a comment |
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
2
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
2
2
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since the mapping $f:X rightarrow Y$ is one-one, by definition it means that
$ forall a,bin X,;;aneq bRightarrow f(a)neq f(b)$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.
answered Mar 28 at 20:53
dnqxtdnqxt
4725
$endgroup$
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
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%2f3166348%2felementary-questions-regarding-countable-sets%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$
Since the mapping $f:X rightarrow Y$ is one-one, by definition it means that
$ forall a,bin X,;;aneq bRightarrow f(a)neq f(b)$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.
answered Mar 28 at 20:53
dnqxtdnqxt
4725
$endgroup$
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
add a comment |
$begingroup$
Since the mapping $f:X rightarrow Y$ is one-one, by definition it means that
$ forall a,bin X,;;aneq bRightarrow f(a)neq f(b)$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.
answered Mar 28 at 20:53
dnqxtdnqxt
4725
$endgroup$
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
add a comment |
$begingroup$
Since the mapping $f:X rightarrow Y$ is one-one, by definition it means that
$ forall a,bin X,;;aneq bRightarrow f(a)neq f(b)$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.
answered Mar 28 at 20:53
dnqxtdnqxt
4725
$endgroup$
Since the mapping $f:X rightarrow Y$ is one-one, by definition it means that
$ forall a,bin X,;;aneq bRightarrow f(a)neq f(b)$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.
answered Mar 28 at 20:53
dnqxtdnqxt
4725
answered Mar 28 at 20:53
dnqxtdnqxt
4725
answered Mar 28 at 20:53
dnqxtdnqxt
4725
answered Mar 28 at 20:53
dnqxtdnqxt
4725
4725
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
add a comment |
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
This answer misses the point, which is how to define the function $g$. The comment from @amrsa nails it.
$endgroup$
– TonyK
Mar 28 at 21:02
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
Indeed, but this answer still proves the 'theorem'.
$endgroup$
– dnqxt
Mar 28 at 21:03
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
the book requires proof by contradiction...so suppose f is not onto..etc...thanks anyways
$endgroup$
– HalfAFoot
Mar 28 at 21:08
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
$begingroup$
If i understand the problem correctly...if we can find a function g:X->1,..n-1 that is one to one...then n is no longer the least natural number for there to be a one to one function ..but n-1 ... however i still do not understand how we get to g...
$endgroup$
– HalfAFoot
Mar 28 at 21:51
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%2f3166348%2felementary-questions-regarding-countable-sets%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
$begingroup$
I don't even get the theorem statement. Did you miss-type something?
$endgroup$
– famesyasd
Mar 28 at 20:16
$begingroup$
Does it basically say that if X is in a bijection with 0..n and 0..n' for some natural number n,n' then n = n'?
$endgroup$
– famesyasd
Mar 28 at 20:19
2
$begingroup$
define $g(a)=i$ and $g(x)=f(x)$ otherwise
$endgroup$
– amrsa
Mar 28 at 20:19
$begingroup$
That is not what "countable" means! You should say "finite sets" instead.
$endgroup$
– TonyK
Mar 28 at 20:59
$begingroup$
amrsa..so basically g:X->1,2,3,...,n-1 where g(a)=i and g(x)=f(x) otherwise?? i still do not understand....suppose X=b,c,d,a then f:X->1,2,3,n=4 is one-to-one, where b is mapped to 1 ,c mapped to 2,etc...now suppose by contradiction that f i not onto and consider the case where i<n then i<4..let us set i=3...hence 3 is not an element of ran(f)..with g:X->1,2,3=n-1...wouldn't we have 4 elements in X and 3 elements in the codomain?..how can this be one to one?
$endgroup$
– HalfAFoot
Mar 28 at 22:10