Prove that $|1,2,3,…,n|=n$ for all natural numbers $n$ by mathematical inductionUse induction on $n$ to prove that $2n+1<2^n$ for all integers $n≥3$.A simple mathematical induction proof.Proving well-ordering property of natural numbers without induction principle?Prove if $x_1,…,x_n$ are natural numbers with $ngeq2$ then $x_1x_2…x_n$ is odd iff $x_i$ is odd for all $i$, $1leq ileq n$Evaluating the statement an “An injective (but not surjective) function must have a left inverse”1-1 correspondenceShow by mathematical induction that $(2n)! > 2^n*n!$ for all $n geq 2$Proving $v(s,p)=2^p-1(2s-1)$ is a bijection of natural numbers and $f(s)=2s-1$ is a bijection between natural numbers and odd numbers.Elementary questions regarding countable setsProving Elementary question regarding non empty finite sets by contradiction
Important Resources for Dark Age Civilizations?
Can I ask the recruiters in my resume to put the reason why I am rejected?
How does one intimidate enemies without having the capacity for violence?
Rock identification in KY
Arrow those variables!
How much of data wrangling is a data scientist's job?
How old can references or sources in a thesis be?
Today is the Center
LWC SFDX source push error TypeError: LWC1009: decl.moveTo is not a function
Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?
Malformed Address '10.10.21.08/24', must be X.X.X.X/NN or
What does it mean to describe someone as a butt steak?
What doth I be?
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
What typically incentivizes a professor to change jobs to a lower ranking university?
Can I make popcorn with any corn?
Can you really stack all of this on an Opportunity Attack?
Why does Kotter return in Welcome Back Kotter?
Horror movie about a virus at the prom; beginning and end are stylized as a cartoon
Unable to deploy metadata from Partner Developer scratch org because of extra fields
How can I prevent hyper evolved versions of regular creatures from wiping out their cousins?
infared filters v nd
What does the "remote control" for a QF-4 look like?
Was any UN Security Council vote triple-vetoed?
Prove that $|1,2,3,…,n|=n$ for all natural numbers $n$ by mathematical induction
Use induction on $n$ to prove that $2n+1<2^n$ for all integers $n≥3$.A simple mathematical induction proof.Proving well-ordering property of natural numbers without induction principle?Prove if $x_1,…,x_n$ are natural numbers with $ngeq2$ then $x_1x_2…x_n$ is odd iff $x_i$ is odd for all $i$, $1leq ileq n$Evaluating the statement an “An injective (but not surjective) function must have a left inverse”1-1 correspondenceShow by mathematical induction that $(2n)! > 2^n*n!$ for all $n geq 2$Proving $v(s,p)=2^p-1(2s-1)$ is a bijection of natural numbers and $f(s)=2s-1$ is a bijection between natural numbers and odd numbers.Elementary questions regarding countable setsProving Elementary question regarding non empty finite sets by contradiction
$begingroup$
The hint given is as follows :
In the inductive step suppose that $|1,2,3,...,n+1|=k lt n+1$. Let
$$f:1,2,3,dots,n+1rightarrow1,2,dots,k$$ be one-to-one and
onto. Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le
n$ such that $f(l)=k$.
Define a one-to-one function
$$g: 1,2,3,dots,nrightarrow 1,2,dots,k-1.$$
I tried:
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
For the inductive step, let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,n+1rightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow 1,2,...,k-1$ that is one-to-one .
[where does the $k-1$ in the codomain come from..are we simply subtracting $1$ from the largest numbers in the domain and codomain of $f$?? Also would $g$ be onto aswell as one-to-one??]
Presumably if $k-1$ is the least natural number that makes $g$ one-to-one then by defintion $|1,2,...,n|=k-1$
and by the induction hypothesis since $|1,2,...,n|=n$ then $n=k-1$ and $k=n+1$. Therefore with $|1,2,...,n+1|=k$ then $|1,2,...,n+1|=n+1$ as required....
I am very confused here...can somebody help please?
Using the answers given, another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since $f$ is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
elementary-set-theory proof-writing induction
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
$endgroup$
add a comment |
$begingroup$
The hint given is as follows :
In the inductive step suppose that $|1,2,3,...,n+1|=k lt n+1$. Let
$$f:1,2,3,dots,n+1rightarrow1,2,dots,k$$ be one-to-one and
onto. Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le
n$ such that $f(l)=k$.
Define a one-to-one function
$$g: 1,2,3,dots,nrightarrow 1,2,dots,k-1.$$
I tried:
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
For the inductive step, let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,n+1rightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow 1,2,...,k-1$ that is one-to-one .
[where does the $k-1$ in the codomain come from..are we simply subtracting $1$ from the largest numbers in the domain and codomain of $f$?? Also would $g$ be onto aswell as one-to-one??]
Presumably if $k-1$ is the least natural number that makes $g$ one-to-one then by defintion $|1,2,...,n|=k-1$
and by the induction hypothesis since $|1,2,...,n|=n$ then $n=k-1$ and $k=n+1$. Therefore with $|1,2,...,n+1|=k$ then $|1,2,...,n+1|=n+1$ as required....
I am very confused here...can somebody help please?
Using the answers given, another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since $f$ is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
elementary-set-theory proof-writing induction
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
$endgroup$
add a comment |
$begingroup$
The hint given is as follows :
In the inductive step suppose that $|1,2,3,...,n+1|=k lt n+1$. Let
$$f:1,2,3,dots,n+1rightarrow1,2,dots,k$$ be one-to-one and
onto. Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le
n$ such that $f(l)=k$.
Define a one-to-one function
$$g: 1,2,3,dots,nrightarrow 1,2,dots,k-1.$$
I tried:
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
For the inductive step, let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,n+1rightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow 1,2,...,k-1$ that is one-to-one .
[where does the $k-1$ in the codomain come from..are we simply subtracting $1$ from the largest numbers in the domain and codomain of $f$?? Also would $g$ be onto aswell as one-to-one??]
Presumably if $k-1$ is the least natural number that makes $g$ one-to-one then by defintion $|1,2,...,n|=k-1$
and by the induction hypothesis since $|1,2,...,n|=n$ then $n=k-1$ and $k=n+1$. Therefore with $|1,2,...,n+1|=k$ then $|1,2,...,n+1|=n+1$ as required....
I am very confused here...can somebody help please?
Using the answers given, another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since $f$ is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
elementary-set-theory proof-writing induction
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
$endgroup$
The hint given is as follows :
In the inductive step suppose that $|1,2,3,...,n+1|=k lt n+1$. Let
$$f:1,2,3,dots,n+1rightarrow1,2,dots,k$$ be one-to-one and
onto. Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le
n$ such that $f(l)=k$.
Define a one-to-one function
$$g: 1,2,3,dots,nrightarrow 1,2,dots,k-1.$$
I tried:
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
For the inductive step, let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,n+1rightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow 1,2,...,k-1$ that is one-to-one .
[where does the $k-1$ in the codomain come from..are we simply subtracting $1$ from the largest numbers in the domain and codomain of $f$?? Also would $g$ be onto aswell as one-to-one??]
Presumably if $k-1$ is the least natural number that makes $g$ one-to-one then by defintion $|1,2,...,n|=k-1$
and by the induction hypothesis since $|1,2,...,n|=n$ then $n=k-1$ and $k=n+1$. Therefore with $|1,2,...,n+1|=k$ then $|1,2,...,n+1|=n+1$ as required....
I am very confused here...can somebody help please?
Using the answers given, another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since $f$ is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
elementary-set-theory proof-writing induction
elementary-set-theory proof-writing induction
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
edited Mar 30 at 14:32
Cameron Buie
86.4k773161
86.4k773161
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
asked Mar 29 at 10:44
HalfAFootHalfAFoot
347
347
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Let me go through your work. You've gotten off to a good start!
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
Added: Here, it looks like cardinality is defined in terms of simply counting the elements, but if that's so, then there's no need for a proof by contradiction. instead, note that $1,2,...,n$ and $n+1$ have no elements in common, so since $|1,2,...,n|=n$ by inductive hypothesis, and since $|n+1|=1,$ then $$bigl|1,2,dots,n,n+1bigr|=bigl|1,2,dots ncupn+1bigr|=bigl|1,2,...,nbigr|+bigl|n+1bigr|=n+1.$$ Given that they are suggesting a much more complicated approach, I suspect that cardinality has been defined differently. Consequently, this base step may not work.
For the inductive step, let $n ge 1$ be any natural number and assume that $1,2,3,...n|=n$.
Added: It would be better, actually, to assume that $n$ is a natural number such that $|1,...,k|=k$ for all natural numbers $k$ with $1le kle n.$ We'll use this a few times.
The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
We certainly don't want to assume that $k=n+1,$ for exactly the reason you state. The book is trying to lead you down the path to a proof by contradiction.
The idea is to suppose that $k<n+1,$ and use that to show that $bigl1,2,3,...,nbigr|=k-1<n$ contradicting our induction hypothesis.
Added: Unfortunately, without knowing how cardinality is defined for you, I can't suggest a way to show that $k>n+1$ is impossible.
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,nrightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
We certainly could define $f$ not one-to-one, but we already stated that $f$ needs to be one-to-one. However, you haven't really justified that it can be. $1$ is finite and non-empty, too, but that doesn't mean we there is a one-to-one and onto function $1to1,2,...,k,$ does it? Rather, it is because we know that $bigl1,2,,...,kbigr|=k$ and that $bigl1,2,3,...,n,n+1bigr|=k$ (by assumption). However, it's perfectly possible that $f(n+1)=k,$ or that $f(n)=k$ (just not both). However, the hint seems to dismiss the possibility that $f(n+1)=k$ by "$1le lle n$ such that $f(l)=k,$" while at the same time allowing it with "$1le jle k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1le lle n+1,$" instead.
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow1,2,...,k-1$ that is one-to-one .
This isn't quite what we're doing.
[where does the k-1 in the codomain come from..are we simply subtracting 1 from the largest numbers in the domain and codomain of f ?? Also would g be onto aswell as one-to-one??]
It seems like you may have the right idea. We're using $f$ to help us define another one-to-one and onto function, on a smaller domain and codomain--namely, we're removing the largest points from our old domain and codomain to get our new ones. In the case that $f(n+1)=k$--that is, $j=k$ and $n+1=l$--we just need to consider $g(m)=f(m)$ for all $min1,2,...,n.$ It's fairly straightforward to prove that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ which I leave to you.
But what if $j<k$ and $l<n+1$? Well, then we need to be a bit more careful. To keep it onto, we need to make sure something goes to $j$ (where $n+1$ was going), and to have the desired codomain, we can't send $l$ to $k.$ Fortunately, these two problems solve each other! We'll just send $l$ to $j,$ instead.
More rigorously, since $f(n+1)=jin1,...,k-1$ and we have $lin1,2,...,n$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=begincasesj & m=l\f(m) & mne l.endcases$$
I leave it to you to show that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ to obtain the desired contradiction. Please let me know if you have any questions about any of this, or if you simply want to bounce your ideas/attempts off of someone.
Added: Your second attempt is quite a bit better! There are still a few issues, though. Let me address them one by one.
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
It's a bit risky to simply say that we can do something without loss of generality. Textbooks do it all the time (to give the reader something to verify), and professional mathematicians do, too (because they are trying to shorten their proofs, and can safely presume that their intended audience can see why the assumption is justified), but I'd recommend against saying it unless you can first prove explicitly why we can do it.
Instead, I'd say something like "First, we consider the possibility that $k<n+1.$"
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Here is the first place the altered induction hypothesis helps us out. Also, it isn't so much that we're defining a set, but that we are drawing a conclusion about it. We can just say: "By the induction hypothesis, we know that $|1,2,dots ,k|=k$."
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Not exactly. Rather, we can conclude that there is a one-to-one and onto function between the two sets, but we can't really say how it is defined.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
Note here that you didn't offer any definition of $f,$ at all! I would instead say something like: "Let $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ be a one-to-one and onto function. Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k,$ then $f(n+1)in1,2,dots ,k,$ meaning that $f(n+1)=j$ for some $1le jle k.$ Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then $f(l)=k$ for some $1le lle n+1.$"
[case : j=k and l=n+1]
This turns out to be redundant. After all, if $j=k,$ this means that $f(n+1)=k$ by definition of $j,$ so that since $f(l)=k$ and $f$ is one-to-one, we have $l=n+1.$ On the other hand, if $l=n+1,$ then $f(n+1)=k$ by definition of $l,$ and so $j=k$ by definition of $j.$
I would actually prove this explicitly at this point. That allows us to consider only two cases: $l=n+1$ (in which case $j=k$) and $l<n+1$ (in which case $j<k$).
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.
This is a bit awkwardly phrased, but clear enough that you have the right idea for the most part. I would change the last sentence to "Define $g:1,2,dots ,n rightarrow 1,2,dots ,k-1$ by $g(m)=f(m)$ for all $min1,2,dots,n.$"
[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
It seems like you mean for your first sentence to say something like "Let $qin1,2,dots,k-1.$ We will show that $q=g(p)$ for some $pin1,2,dots,n.$" After that, I would say something like "Since $qin1,2,dots,k-1,k$ and since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $pin1,2,dots,n,n+1$ such that $q=f(p).$ Since $f(n+1)=k$ and $qin1,2,dots,k-1,$ then $pne n+1.$ Hence, $pin1,2,dots,n$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
True, because $f$ is one-to-one, so this is not possible. However, if you observe (as mentioned above) that $j=k$ if and only if $l=n+1,$ then you needn't even bring this case up.
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
Likewise, we don't need to bring this case up if we prove that $j=k$ if and only if $l=n+1.$
The proof is fine from here, until we get to the following:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
[case: $p=l$ and $q neq l$].
[case: $p neq l$ and $q=l$].
Here, you're getting into unnecessary cases, while omitting a necessary one! (You never allow $p=l$ and $q=l$.) Let me address your third case to show you why we don't need it (or the second one).
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=pin1,2,...,n$ which is impossible!
Instead, we only need to consider two cases: $pne l$ and $p=l.$ If $pne l,$ then we can prove that $qne l$ (I leave this to you), at which point your first case's proof works just fine to show that $p=q.$ If $p=l,$ then $g(p)=j$ by definition of $g,$ so that $g(q)=j,$ too. However, we must then have $q=l$ (so $p=q$), for if not, then $f(q)=g(q)=j$ by definition of $g,$ but then $f(q)=f(n+1)$ by definition of $j,$ and since $f$ is one-to-one, we would then have $n+1=qin1,2,...,n,$ which is absurd.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$
Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $qin1,2,dots,k-1.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $qne j.$ Since $qin1,2,...,k-1,k$ and $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $min1,2,dots,n,n+1$ such that $f(m)=q.$ Since $qne j,$ then $f(m)ne j=f(n+1),$ so $mne n+1.$ Thus, $min1,2,...,n.$ Furthermore, since $f(m)=qin1,2,dots,k-1,$ then $f(m)ne k=f(l),$ so $mne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Here, again, the adjusted induction hypothesis helps us out.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
Unfortunately, as I mentioned above, this approach will only allow us to prove that $|1,2,dots,n|ge n$ for all $n.$ We still need to address the possibility that $k>n+1.$ However, without knowing how cardinality is defined for you, and what properties of cardinality you are allowed to use, I can't help you address that.
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
$endgroup$
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
|
show 1 more comment
$begingroup$
The problem you were given is somewhat ill-stated, and I believe that is where your confusion is coming from. In particular, they've posed the question as asking, "Show that the cardinality of $1,...,n$ is $n$," without stating what it means for a cardinality (which only talks about bijections between sets) to equal a natural number.
There's an easy way around this, of course: define the cardinality $n$ to be the cardinality of the set $1,...,n$ and say that a set $X$ has cardinality $n$ if there's a bijection from $X$ to $1,...,n$ (Actually, this is more often done with the set $0,...,n-1$ but I'll stick with the convention you are using). However, failing to explicitly bring up this idea obfuscates what's going on in the problem: hiding the interesting thing it is actually getting you to prove and making it look as though it is just asking you to prove the thing that we should actually be using as a definition.
The interesting idea behind this problem is this: after identifying particular cardinalities with natural numbers in the definition, do the cardinalities actually act like natural numbers? One part of showing that is this proof that different numbers are different cardinalities. So let's state this problem as it should actually have been:
Prove that for all $n in mathbbN$ if $k<n$ then there is no bijection from $1,...,n$ to $1,...,k$
We'll prove it by induction on the larger number $n$. (This is where your first question is answered. Don't worry about comparing $n$ to $k$ greater than $n$. That will be sorted when the induction process reaches that larger $k$, at which point it'll show that that $k$ isn't in bijection with any set of cardinality less than $k$, including the $n$ you started with.)
The base case is better proved as: there's no bijection from $1$ to the empty set (i.e. $0$) because there are no functions from an inhabited set to the empty set.
We then get to the induction step. We want to assume that there is no bijection from $1,...,n$ to $1,...,k$ with $k<n$ and use it to show that there is no bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$
This will be proved by contrapositive: we instead assume that there is actually a bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$ and use it to construct a bijection from $1,...,n$ to $1,...,k-1$. $k-1<n$, so this contradicts the induction hypothesis.
This is where you're question "If we define the function as above,then wouldn't the following be possible: $f(n+1)=k$ and $f(n)=k$ and render the function not one-to-one??" is answered. We don't take the function like that, because the existence of a one-to-one function from $1,...,n+1$ to $1,...,k$ is the assumption we are using. Therefore we can pick the function $f$ to be injective.
Your job, when completing the induction step is to construct the bijection from $1,...,n$ to $1,...,k-1$ from the one you've assumed exists from $1,...,n+1$ to $1,...,k$. In the process, you should see why we picked $1,...,k-1$ as the target.
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
$endgroup$
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
add a comment |
$begingroup$
Using the answers given above,another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The base case invovles proving that |$1,2,3,...n$|$=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that |$1,2,3,...n$|$=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since f is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
$endgroup$
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%2f3166994%2fprove-that-1-2-3-n-n-for-all-natural-numbers-n-by-mathematical-ind%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let me go through your work. You've gotten off to a good start!
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
Added: Here, it looks like cardinality is defined in terms of simply counting the elements, but if that's so, then there's no need for a proof by contradiction. instead, note that $1,2,...,n$ and $n+1$ have no elements in common, so since $|1,2,...,n|=n$ by inductive hypothesis, and since $|n+1|=1,$ then $$bigl|1,2,dots,n,n+1bigr|=bigl|1,2,dots ncupn+1bigr|=bigl|1,2,...,nbigr|+bigl|n+1bigr|=n+1.$$ Given that they are suggesting a much more complicated approach, I suspect that cardinality has been defined differently. Consequently, this base step may not work.
For the inductive step, let $n ge 1$ be any natural number and assume that $1,2,3,...n|=n$.
Added: It would be better, actually, to assume that $n$ is a natural number such that $|1,...,k|=k$ for all natural numbers $k$ with $1le kle n.$ We'll use this a few times.
The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
We certainly don't want to assume that $k=n+1,$ for exactly the reason you state. The book is trying to lead you down the path to a proof by contradiction.
The idea is to suppose that $k<n+1,$ and use that to show that $bigl1,2,3,...,nbigr|=k-1<n$ contradicting our induction hypothesis.
Added: Unfortunately, without knowing how cardinality is defined for you, I can't suggest a way to show that $k>n+1$ is impossible.
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,nrightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
We certainly could define $f$ not one-to-one, but we already stated that $f$ needs to be one-to-one. However, you haven't really justified that it can be. $1$ is finite and non-empty, too, but that doesn't mean we there is a one-to-one and onto function $1to1,2,...,k,$ does it? Rather, it is because we know that $bigl1,2,,...,kbigr|=k$ and that $bigl1,2,3,...,n,n+1bigr|=k$ (by assumption). However, it's perfectly possible that $f(n+1)=k,$ or that $f(n)=k$ (just not both). However, the hint seems to dismiss the possibility that $f(n+1)=k$ by "$1le lle n$ such that $f(l)=k,$" while at the same time allowing it with "$1le jle k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1le lle n+1,$" instead.
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow1,2,...,k-1$ that is one-to-one .
This isn't quite what we're doing.
[where does the k-1 in the codomain come from..are we simply subtracting 1 from the largest numbers in the domain and codomain of f ?? Also would g be onto aswell as one-to-one??]
It seems like you may have the right idea. We're using $f$ to help us define another one-to-one and onto function, on a smaller domain and codomain--namely, we're removing the largest points from our old domain and codomain to get our new ones. In the case that $f(n+1)=k$--that is, $j=k$ and $n+1=l$--we just need to consider $g(m)=f(m)$ for all $min1,2,...,n.$ It's fairly straightforward to prove that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ which I leave to you.
But what if $j<k$ and $l<n+1$? Well, then we need to be a bit more careful. To keep it onto, we need to make sure something goes to $j$ (where $n+1$ was going), and to have the desired codomain, we can't send $l$ to $k.$ Fortunately, these two problems solve each other! We'll just send $l$ to $j,$ instead.
More rigorously, since $f(n+1)=jin1,...,k-1$ and we have $lin1,2,...,n$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=begincasesj & m=l\f(m) & mne l.endcases$$
I leave it to you to show that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ to obtain the desired contradiction. Please let me know if you have any questions about any of this, or if you simply want to bounce your ideas/attempts off of someone.
Added: Your second attempt is quite a bit better! There are still a few issues, though. Let me address them one by one.
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
It's a bit risky to simply say that we can do something without loss of generality. Textbooks do it all the time (to give the reader something to verify), and professional mathematicians do, too (because they are trying to shorten their proofs, and can safely presume that their intended audience can see why the assumption is justified), but I'd recommend against saying it unless you can first prove explicitly why we can do it.
Instead, I'd say something like "First, we consider the possibility that $k<n+1.$"
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Here is the first place the altered induction hypothesis helps us out. Also, it isn't so much that we're defining a set, but that we are drawing a conclusion about it. We can just say: "By the induction hypothesis, we know that $|1,2,dots ,k|=k$."
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Not exactly. Rather, we can conclude that there is a one-to-one and onto function between the two sets, but we can't really say how it is defined.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
Note here that you didn't offer any definition of $f,$ at all! I would instead say something like: "Let $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ be a one-to-one and onto function. Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k,$ then $f(n+1)in1,2,dots ,k,$ meaning that $f(n+1)=j$ for some $1le jle k.$ Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then $f(l)=k$ for some $1le lle n+1.$"
[case : j=k and l=n+1]
This turns out to be redundant. After all, if $j=k,$ this means that $f(n+1)=k$ by definition of $j,$ so that since $f(l)=k$ and $f$ is one-to-one, we have $l=n+1.$ On the other hand, if $l=n+1,$ then $f(n+1)=k$ by definition of $l,$ and so $j=k$ by definition of $j.$
I would actually prove this explicitly at this point. That allows us to consider only two cases: $l=n+1$ (in which case $j=k$) and $l<n+1$ (in which case $j<k$).
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.
This is a bit awkwardly phrased, but clear enough that you have the right idea for the most part. I would change the last sentence to "Define $g:1,2,dots ,n rightarrow 1,2,dots ,k-1$ by $g(m)=f(m)$ for all $min1,2,dots,n.$"
[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
It seems like you mean for your first sentence to say something like "Let $qin1,2,dots,k-1.$ We will show that $q=g(p)$ for some $pin1,2,dots,n.$" After that, I would say something like "Since $qin1,2,dots,k-1,k$ and since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $pin1,2,dots,n,n+1$ such that $q=f(p).$ Since $f(n+1)=k$ and $qin1,2,dots,k-1,$ then $pne n+1.$ Hence, $pin1,2,dots,n$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
True, because $f$ is one-to-one, so this is not possible. However, if you observe (as mentioned above) that $j=k$ if and only if $l=n+1,$ then you needn't even bring this case up.
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
Likewise, we don't need to bring this case up if we prove that $j=k$ if and only if $l=n+1.$
The proof is fine from here, until we get to the following:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
[case: $p=l$ and $q neq l$].
[case: $p neq l$ and $q=l$].
Here, you're getting into unnecessary cases, while omitting a necessary one! (You never allow $p=l$ and $q=l$.) Let me address your third case to show you why we don't need it (or the second one).
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=pin1,2,...,n$ which is impossible!
Instead, we only need to consider two cases: $pne l$ and $p=l.$ If $pne l,$ then we can prove that $qne l$ (I leave this to you), at which point your first case's proof works just fine to show that $p=q.$ If $p=l,$ then $g(p)=j$ by definition of $g,$ so that $g(q)=j,$ too. However, we must then have $q=l$ (so $p=q$), for if not, then $f(q)=g(q)=j$ by definition of $g,$ but then $f(q)=f(n+1)$ by definition of $j,$ and since $f$ is one-to-one, we would then have $n+1=qin1,2,...,n,$ which is absurd.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$
Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $qin1,2,dots,k-1.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $qne j.$ Since $qin1,2,...,k-1,k$ and $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $min1,2,dots,n,n+1$ such that $f(m)=q.$ Since $qne j,$ then $f(m)ne j=f(n+1),$ so $mne n+1.$ Thus, $min1,2,...,n.$ Furthermore, since $f(m)=qin1,2,dots,k-1,$ then $f(m)ne k=f(l),$ so $mne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Here, again, the adjusted induction hypothesis helps us out.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
Unfortunately, as I mentioned above, this approach will only allow us to prove that $|1,2,dots,n|ge n$ for all $n.$ We still need to address the possibility that $k>n+1.$ However, without knowing how cardinality is defined for you, and what properties of cardinality you are allowed to use, I can't help you address that.
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
$endgroup$
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
|
show 1 more comment
$begingroup$
Let me go through your work. You've gotten off to a good start!
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
Added: Here, it looks like cardinality is defined in terms of simply counting the elements, but if that's so, then there's no need for a proof by contradiction. instead, note that $1,2,...,n$ and $n+1$ have no elements in common, so since $|1,2,...,n|=n$ by inductive hypothesis, and since $|n+1|=1,$ then $$bigl|1,2,dots,n,n+1bigr|=bigl|1,2,dots ncupn+1bigr|=bigl|1,2,...,nbigr|+bigl|n+1bigr|=n+1.$$ Given that they are suggesting a much more complicated approach, I suspect that cardinality has been defined differently. Consequently, this base step may not work.
For the inductive step, let $n ge 1$ be any natural number and assume that $1,2,3,...n|=n$.
Added: It would be better, actually, to assume that $n$ is a natural number such that $|1,...,k|=k$ for all natural numbers $k$ with $1le kle n.$ We'll use this a few times.
The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
We certainly don't want to assume that $k=n+1,$ for exactly the reason you state. The book is trying to lead you down the path to a proof by contradiction.
The idea is to suppose that $k<n+1,$ and use that to show that $bigl1,2,3,...,nbigr|=k-1<n$ contradicting our induction hypothesis.
Added: Unfortunately, without knowing how cardinality is defined for you, I can't suggest a way to show that $k>n+1$ is impossible.
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,nrightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
We certainly could define $f$ not one-to-one, but we already stated that $f$ needs to be one-to-one. However, you haven't really justified that it can be. $1$ is finite and non-empty, too, but that doesn't mean we there is a one-to-one and onto function $1to1,2,...,k,$ does it? Rather, it is because we know that $bigl1,2,,...,kbigr|=k$ and that $bigl1,2,3,...,n,n+1bigr|=k$ (by assumption). However, it's perfectly possible that $f(n+1)=k,$ or that $f(n)=k$ (just not both). However, the hint seems to dismiss the possibility that $f(n+1)=k$ by "$1le lle n$ such that $f(l)=k,$" while at the same time allowing it with "$1le jle k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1le lle n+1,$" instead.
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow1,2,...,k-1$ that is one-to-one .
This isn't quite what we're doing.
[where does the k-1 in the codomain come from..are we simply subtracting 1 from the largest numbers in the domain and codomain of f ?? Also would g be onto aswell as one-to-one??]
It seems like you may have the right idea. We're using $f$ to help us define another one-to-one and onto function, on a smaller domain and codomain--namely, we're removing the largest points from our old domain and codomain to get our new ones. In the case that $f(n+1)=k$--that is, $j=k$ and $n+1=l$--we just need to consider $g(m)=f(m)$ for all $min1,2,...,n.$ It's fairly straightforward to prove that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ which I leave to you.
But what if $j<k$ and $l<n+1$? Well, then we need to be a bit more careful. To keep it onto, we need to make sure something goes to $j$ (where $n+1$ was going), and to have the desired codomain, we can't send $l$ to $k.$ Fortunately, these two problems solve each other! We'll just send $l$ to $j,$ instead.
More rigorously, since $f(n+1)=jin1,...,k-1$ and we have $lin1,2,...,n$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=begincasesj & m=l\f(m) & mne l.endcases$$
I leave it to you to show that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ to obtain the desired contradiction. Please let me know if you have any questions about any of this, or if you simply want to bounce your ideas/attempts off of someone.
Added: Your second attempt is quite a bit better! There are still a few issues, though. Let me address them one by one.
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
It's a bit risky to simply say that we can do something without loss of generality. Textbooks do it all the time (to give the reader something to verify), and professional mathematicians do, too (because they are trying to shorten their proofs, and can safely presume that their intended audience can see why the assumption is justified), but I'd recommend against saying it unless you can first prove explicitly why we can do it.
Instead, I'd say something like "First, we consider the possibility that $k<n+1.$"
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Here is the first place the altered induction hypothesis helps us out. Also, it isn't so much that we're defining a set, but that we are drawing a conclusion about it. We can just say: "By the induction hypothesis, we know that $|1,2,dots ,k|=k$."
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Not exactly. Rather, we can conclude that there is a one-to-one and onto function between the two sets, but we can't really say how it is defined.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
Note here that you didn't offer any definition of $f,$ at all! I would instead say something like: "Let $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ be a one-to-one and onto function. Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k,$ then $f(n+1)in1,2,dots ,k,$ meaning that $f(n+1)=j$ for some $1le jle k.$ Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then $f(l)=k$ for some $1le lle n+1.$"
[case : j=k and l=n+1]
This turns out to be redundant. After all, if $j=k,$ this means that $f(n+1)=k$ by definition of $j,$ so that since $f(l)=k$ and $f$ is one-to-one, we have $l=n+1.$ On the other hand, if $l=n+1,$ then $f(n+1)=k$ by definition of $l,$ and so $j=k$ by definition of $j.$
I would actually prove this explicitly at this point. That allows us to consider only two cases: $l=n+1$ (in which case $j=k$) and $l<n+1$ (in which case $j<k$).
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.
This is a bit awkwardly phrased, but clear enough that you have the right idea for the most part. I would change the last sentence to "Define $g:1,2,dots ,n rightarrow 1,2,dots ,k-1$ by $g(m)=f(m)$ for all $min1,2,dots,n.$"
[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
It seems like you mean for your first sentence to say something like "Let $qin1,2,dots,k-1.$ We will show that $q=g(p)$ for some $pin1,2,dots,n.$" After that, I would say something like "Since $qin1,2,dots,k-1,k$ and since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $pin1,2,dots,n,n+1$ such that $q=f(p).$ Since $f(n+1)=k$ and $qin1,2,dots,k-1,$ then $pne n+1.$ Hence, $pin1,2,dots,n$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
True, because $f$ is one-to-one, so this is not possible. However, if you observe (as mentioned above) that $j=k$ if and only if $l=n+1,$ then you needn't even bring this case up.
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
Likewise, we don't need to bring this case up if we prove that $j=k$ if and only if $l=n+1.$
The proof is fine from here, until we get to the following:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
[case: $p=l$ and $q neq l$].
[case: $p neq l$ and $q=l$].
Here, you're getting into unnecessary cases, while omitting a necessary one! (You never allow $p=l$ and $q=l$.) Let me address your third case to show you why we don't need it (or the second one).
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=pin1,2,...,n$ which is impossible!
Instead, we only need to consider two cases: $pne l$ and $p=l.$ If $pne l,$ then we can prove that $qne l$ (I leave this to you), at which point your first case's proof works just fine to show that $p=q.$ If $p=l,$ then $g(p)=j$ by definition of $g,$ so that $g(q)=j,$ too. However, we must then have $q=l$ (so $p=q$), for if not, then $f(q)=g(q)=j$ by definition of $g,$ but then $f(q)=f(n+1)$ by definition of $j,$ and since $f$ is one-to-one, we would then have $n+1=qin1,2,...,n,$ which is absurd.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$
Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $qin1,2,dots,k-1.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $qne j.$ Since $qin1,2,...,k-1,k$ and $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $min1,2,dots,n,n+1$ such that $f(m)=q.$ Since $qne j,$ then $f(m)ne j=f(n+1),$ so $mne n+1.$ Thus, $min1,2,...,n.$ Furthermore, since $f(m)=qin1,2,dots,k-1,$ then $f(m)ne k=f(l),$ so $mne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Here, again, the adjusted induction hypothesis helps us out.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
Unfortunately, as I mentioned above, this approach will only allow us to prove that $|1,2,dots,n|ge n$ for all $n.$ We still need to address the possibility that $k>n+1.$ However, without knowing how cardinality is defined for you, and what properties of cardinality you are allowed to use, I can't help you address that.
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
$endgroup$
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
|
show 1 more comment
$begingroup$
Let me go through your work. You've gotten off to a good start!
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
Added: Here, it looks like cardinality is defined in terms of simply counting the elements, but if that's so, then there's no need for a proof by contradiction. instead, note that $1,2,...,n$ and $n+1$ have no elements in common, so since $|1,2,...,n|=n$ by inductive hypothesis, and since $|n+1|=1,$ then $$bigl|1,2,dots,n,n+1bigr|=bigl|1,2,dots ncupn+1bigr|=bigl|1,2,...,nbigr|+bigl|n+1bigr|=n+1.$$ Given that they are suggesting a much more complicated approach, I suspect that cardinality has been defined differently. Consequently, this base step may not work.
For the inductive step, let $n ge 1$ be any natural number and assume that $1,2,3,...n|=n$.
Added: It would be better, actually, to assume that $n$ is a natural number such that $|1,...,k|=k$ for all natural numbers $k$ with $1le kle n.$ We'll use this a few times.
The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
We certainly don't want to assume that $k=n+1,$ for exactly the reason you state. The book is trying to lead you down the path to a proof by contradiction.
The idea is to suppose that $k<n+1,$ and use that to show that $bigl1,2,3,...,nbigr|=k-1<n$ contradicting our induction hypothesis.
Added: Unfortunately, without knowing how cardinality is defined for you, I can't suggest a way to show that $k>n+1$ is impossible.
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,nrightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
We certainly could define $f$ not one-to-one, but we already stated that $f$ needs to be one-to-one. However, you haven't really justified that it can be. $1$ is finite and non-empty, too, but that doesn't mean we there is a one-to-one and onto function $1to1,2,...,k,$ does it? Rather, it is because we know that $bigl1,2,,...,kbigr|=k$ and that $bigl1,2,3,...,n,n+1bigr|=k$ (by assumption). However, it's perfectly possible that $f(n+1)=k,$ or that $f(n)=k$ (just not both). However, the hint seems to dismiss the possibility that $f(n+1)=k$ by "$1le lle n$ such that $f(l)=k,$" while at the same time allowing it with "$1le jle k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1le lle n+1,$" instead.
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow1,2,...,k-1$ that is one-to-one .
This isn't quite what we're doing.
[where does the k-1 in the codomain come from..are we simply subtracting 1 from the largest numbers in the domain and codomain of f ?? Also would g be onto aswell as one-to-one??]
It seems like you may have the right idea. We're using $f$ to help us define another one-to-one and onto function, on a smaller domain and codomain--namely, we're removing the largest points from our old domain and codomain to get our new ones. In the case that $f(n+1)=k$--that is, $j=k$ and $n+1=l$--we just need to consider $g(m)=f(m)$ for all $min1,2,...,n.$ It's fairly straightforward to prove that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ which I leave to you.
But what if $j<k$ and $l<n+1$? Well, then we need to be a bit more careful. To keep it onto, we need to make sure something goes to $j$ (where $n+1$ was going), and to have the desired codomain, we can't send $l$ to $k.$ Fortunately, these two problems solve each other! We'll just send $l$ to $j,$ instead.
More rigorously, since $f(n+1)=jin1,...,k-1$ and we have $lin1,2,...,n$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=begincasesj & m=l\f(m) & mne l.endcases$$
I leave it to you to show that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ to obtain the desired contradiction. Please let me know if you have any questions about any of this, or if you simply want to bounce your ideas/attempts off of someone.
Added: Your second attempt is quite a bit better! There are still a few issues, though. Let me address them one by one.
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
It's a bit risky to simply say that we can do something without loss of generality. Textbooks do it all the time (to give the reader something to verify), and professional mathematicians do, too (because they are trying to shorten their proofs, and can safely presume that their intended audience can see why the assumption is justified), but I'd recommend against saying it unless you can first prove explicitly why we can do it.
Instead, I'd say something like "First, we consider the possibility that $k<n+1.$"
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Here is the first place the altered induction hypothesis helps us out. Also, it isn't so much that we're defining a set, but that we are drawing a conclusion about it. We can just say: "By the induction hypothesis, we know that $|1,2,dots ,k|=k$."
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Not exactly. Rather, we can conclude that there is a one-to-one and onto function between the two sets, but we can't really say how it is defined.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
Note here that you didn't offer any definition of $f,$ at all! I would instead say something like: "Let $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ be a one-to-one and onto function. Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k,$ then $f(n+1)in1,2,dots ,k,$ meaning that $f(n+1)=j$ for some $1le jle k.$ Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then $f(l)=k$ for some $1le lle n+1.$"
[case : j=k and l=n+1]
This turns out to be redundant. After all, if $j=k,$ this means that $f(n+1)=k$ by definition of $j,$ so that since $f(l)=k$ and $f$ is one-to-one, we have $l=n+1.$ On the other hand, if $l=n+1,$ then $f(n+1)=k$ by definition of $l,$ and so $j=k$ by definition of $j.$
I would actually prove this explicitly at this point. That allows us to consider only two cases: $l=n+1$ (in which case $j=k$) and $l<n+1$ (in which case $j<k$).
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.
This is a bit awkwardly phrased, but clear enough that you have the right idea for the most part. I would change the last sentence to "Define $g:1,2,dots ,n rightarrow 1,2,dots ,k-1$ by $g(m)=f(m)$ for all $min1,2,dots,n.$"
[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
It seems like you mean for your first sentence to say something like "Let $qin1,2,dots,k-1.$ We will show that $q=g(p)$ for some $pin1,2,dots,n.$" After that, I would say something like "Since $qin1,2,dots,k-1,k$ and since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $pin1,2,dots,n,n+1$ such that $q=f(p).$ Since $f(n+1)=k$ and $qin1,2,dots,k-1,$ then $pne n+1.$ Hence, $pin1,2,dots,n$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
True, because $f$ is one-to-one, so this is not possible. However, if you observe (as mentioned above) that $j=k$ if and only if $l=n+1,$ then you needn't even bring this case up.
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
Likewise, we don't need to bring this case up if we prove that $j=k$ if and only if $l=n+1.$
The proof is fine from here, until we get to the following:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
[case: $p=l$ and $q neq l$].
[case: $p neq l$ and $q=l$].
Here, you're getting into unnecessary cases, while omitting a necessary one! (You never allow $p=l$ and $q=l$.) Let me address your third case to show you why we don't need it (or the second one).
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=pin1,2,...,n$ which is impossible!
Instead, we only need to consider two cases: $pne l$ and $p=l.$ If $pne l,$ then we can prove that $qne l$ (I leave this to you), at which point your first case's proof works just fine to show that $p=q.$ If $p=l,$ then $g(p)=j$ by definition of $g,$ so that $g(q)=j,$ too. However, we must then have $q=l$ (so $p=q$), for if not, then $f(q)=g(q)=j$ by definition of $g,$ but then $f(q)=f(n+1)$ by definition of $j,$ and since $f$ is one-to-one, we would then have $n+1=qin1,2,...,n,$ which is absurd.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$
Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $qin1,2,dots,k-1.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $qne j.$ Since $qin1,2,...,k-1,k$ and $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $min1,2,dots,n,n+1$ such that $f(m)=q.$ Since $qne j,$ then $f(m)ne j=f(n+1),$ so $mne n+1.$ Thus, $min1,2,...,n.$ Furthermore, since $f(m)=qin1,2,dots,k-1,$ then $f(m)ne k=f(l),$ so $mne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Here, again, the adjusted induction hypothesis helps us out.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
Unfortunately, as I mentioned above, this approach will only allow us to prove that $|1,2,dots,n|ge n$ for all $n.$ We still need to address the possibility that $k>n+1.$ However, without knowing how cardinality is defined for you, and what properties of cardinality you are allowed to use, I can't help you address that.
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
$endgroup$
Let me go through your work. You've gotten off to a good start!
The objective is to prove that for all natural numbers
$n ge1$: $$left|1,2,3,dots,nright|=n.$$
The Base step invovles proving that $|1,2,3,...n|=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
Added: Here, it looks like cardinality is defined in terms of simply counting the elements, but if that's so, then there's no need for a proof by contradiction. instead, note that $1,2,...,n$ and $n+1$ have no elements in common, so since $|1,2,...,n|=n$ by inductive hypothesis, and since $|n+1|=1,$ then $$bigl|1,2,dots,n,n+1bigr|=bigl|1,2,dots ncupn+1bigr|=bigl|1,2,...,nbigr|+bigl|n+1bigr|=n+1.$$ Given that they are suggesting a much more complicated approach, I suspect that cardinality has been defined differently. Consequently, this base step may not work.
For the inductive step, let $n ge 1$ be any natural number and assume that $1,2,3,...n|=n$.
Added: It would be better, actually, to assume that $n$ is a natural number such that $|1,...,k|=k$ for all natural numbers $k$ with $1le kle n.$ We'll use this a few times.
The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Using the hint above:
Suppose $|1,2,3,...n+1|=k$
[the hint goes on to state $k lt n+1$..is this because if $k=n+1$ we
would be assuming what is to be proven hence making the proof
fallacious? what about $k gt n+1$?].
We certainly don't want to assume that $k=n+1,$ for exactly the reason you state. The book is trying to lead you down the path to a proof by contradiction.
The idea is to suppose that $k<n+1,$ and use that to show that $bigl1,2,3,...,nbigr|=k-1<n$ contradicting our induction hypothesis.
Added: Unfortunately, without knowing how cardinality is defined for you, I can't suggest a way to show that $k>n+1$ is impossible.
For my purposes i treat it as a printing mistake and simply assume $|1,2,3,...n+1|=k$.Now since $1,2,3,...n+1$ is finite and non-empty then we can define a one-to-one and onto function $f:1,2,3,...,nrightarrow1,2,...,k.$ Let $1 le j le k$ be such that $f(n+1)=j$ and let $1 le l le n$ such that $f(l)=k$
[if we define the function as above,then wouldn't the following be
possible: f(n+1)=k and f(n)=k and render the function not
one-to-one??]
We certainly could define $f$ not one-to-one, but we already stated that $f$ needs to be one-to-one. However, you haven't really justified that it can be. $1$ is finite and non-empty, too, but that doesn't mean we there is a one-to-one and onto function $1to1,2,...,k,$ does it? Rather, it is because we know that $bigl1,2,,...,kbigr|=k$ and that $bigl1,2,3,...,n,n+1bigr|=k$ (by assumption). However, it's perfectly possible that $f(n+1)=k,$ or that $f(n)=k$ (just not both). However, the hint seems to dismiss the possibility that $f(n+1)=k$ by "$1le lle n$ such that $f(l)=k,$" while at the same time allowing it with "$1le jle k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1le lle n+1,$" instead.
Now with the induction hypothesis $|1,2,3,...n|=n$, $1,2,3,...n$ is finite and non-empty hence we can construct a function $g:1,2,3,...,nrightarrow1,2,...,k-1$ that is one-to-one .
This isn't quite what we're doing.
[where does the k-1 in the codomain come from..are we simply subtracting 1 from the largest numbers in the domain and codomain of f ?? Also would g be onto aswell as one-to-one??]
It seems like you may have the right idea. We're using $f$ to help us define another one-to-one and onto function, on a smaller domain and codomain--namely, we're removing the largest points from our old domain and codomain to get our new ones. In the case that $f(n+1)=k$--that is, $j=k$ and $n+1=l$--we just need to consider $g(m)=f(m)$ for all $min1,2,...,n.$ It's fairly straightforward to prove that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ which I leave to you.
But what if $j<k$ and $l<n+1$? Well, then we need to be a bit more careful. To keep it onto, we need to make sure something goes to $j$ (where $n+1$ was going), and to have the desired codomain, we can't send $l$ to $k.$ Fortunately, these two problems solve each other! We'll just send $l$ to $j,$ instead.
More rigorously, since $f(n+1)=jin1,...,k-1$ and we have $lin1,2,...,n$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=begincasesj & m=l\f(m) & mne l.endcases$$
I leave it to you to show that this is a one-to-one and onto function $1,2,...,nto1,...,k-1,$ to obtain the desired contradiction. Please let me know if you have any questions about any of this, or if you simply want to bounce your ideas/attempts off of someone.
Added: Your second attempt is quite a bit better! There are still a few issues, though. Let me address them one by one.
Let $n ge 1$ be any natural number and assume that $|1,2,3,...n|=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
It's a bit risky to simply say that we can do something without loss of generality. Textbooks do it all the time (to give the reader something to verify), and professional mathematicians do, too (because they are trying to shorten their proofs, and can safely presume that their intended audience can see why the assumption is justified), but I'd recommend against saying it unless you can first prove explicitly why we can do it.
Instead, I'd say something like "First, we consider the possibility that $k<n+1.$"
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Here is the first place the altered induction hypothesis helps us out. Also, it isn't so much that we're defining a set, but that we are drawing a conclusion about it. We can just say: "By the induction hypothesis, we know that $|1,2,dots ,k|=k$."
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Not exactly. Rather, we can conclude that there is a one-to-one and onto function between the two sets, but we can't really say how it is defined.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
Note here that you didn't offer any definition of $f,$ at all! I would instead say something like: "Let $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ be a one-to-one and onto function. Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k,$ then $f(n+1)in1,2,dots ,k,$ meaning that $f(n+1)=j$ for some $1le jle k.$ Since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then $f(l)=k$ for some $1le lle n+1.$"
[case : j=k and l=n+1]
This turns out to be redundant. After all, if $j=k,$ this means that $f(n+1)=k$ by definition of $j,$ so that since $f(l)=k$ and $f$ is one-to-one, we have $l=n+1.$ On the other hand, if $l=n+1,$ then $f(n+1)=k$ by definition of $l,$ and so $j=k$ by definition of $j.$
I would actually prove this explicitly at this point. That allows us to consider only two cases: $l=n+1$ (in which case $j=k$) and $l<n+1$ (in which case $j<k$).
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.
This is a bit awkwardly phrased, but clear enough that you have the right idea for the most part. I would change the last sentence to "Define $g:1,2,dots ,n rightarrow 1,2,dots ,k-1$ by $g(m)=f(m)$ for all $min1,2,dots,n.$"
[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
It seems like you mean for your first sentence to say something like "Let $qin1,2,dots,k-1.$ We will show that $q=g(p)$ for some $pin1,2,dots,n.$" After that, I would say something like "Since $qin1,2,dots,k-1,k$ and since $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $pin1,2,dots,n,n+1$ such that $q=f(p).$ Since $f(n+1)=k$ and $qin1,2,dots,k-1,$ then $pne n+1.$ Hence, $pin1,2,dots,n$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
True, because $f$ is one-to-one, so this is not possible. However, if you observe (as mentioned above) that $j=k$ if and only if $l=n+1,$ then you needn't even bring this case up.
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
Likewise, we don't need to bring this case up if we prove that $j=k$ if and only if $l=n+1.$
The proof is fine from here, until we get to the following:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
[case: $p=l$ and $q neq l$].
[case: $p neq l$ and $q=l$].
Here, you're getting into unnecessary cases, while omitting a necessary one! (You never allow $p=l$ and $q=l$.) Let me address your third case to show you why we don't need it (or the second one).
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since $f$ is one-to-one,then $p=q$ as required.
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=pin1,2,...,n$ which is impossible!
Instead, we only need to consider two cases: $pne l$ and $p=l.$ If $pne l,$ then we can prove that $qne l$ (I leave this to you), at which point your first case's proof works just fine to show that $p=q.$ If $p=l,$ then $g(p)=j$ by definition of $g,$ so that $g(q)=j,$ too. However, we must then have $q=l$ (so $p=q$), for if not, then $f(q)=g(q)=j$ by definition of $g,$ but then $f(q)=f(n+1)$ by definition of $j,$ and since $f$ is one-to-one, we would then have $n+1=qin1,2,...,n,$ which is absurd.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$
Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $qin1,2,dots,k-1.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $qne j.$ Since $qin1,2,...,k-1,k$ and $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ is onto, then there is some $min1,2,dots,n,n+1$ such that $f(m)=q.$ Since $qne j,$ then $f(m)ne j=f(n+1),$ so $mne n+1.$ Thus, $min1,2,...,n.$ Furthermore, since $f(m)=qin1,2,dots,k-1,$ then $f(m)ne k=f(l),$ so $mne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Here, again, the adjusted induction hypothesis helps us out.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
Unfortunately, as I mentioned above, this approach will only allow us to prove that $|1,2,dots,n|ge n$ for all $n.$ We still need to address the possibility that $k>n+1.$ However, without knowing how cardinality is defined for you, and what properties of cardinality you are allowed to use, I can't help you address that.
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
edited Mar 30 at 16:11
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
answered Mar 29 at 12:24
Cameron BuieCameron Buie
86.4k773161
86.4k773161
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
|
show 1 more comment
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
Thank you Cameron for such an extensive response...i will have to look at it later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
$begingroup$
I have finally typed up a new response below...is that better? Thank you for your help
$endgroup$
– HalfAFoot
Mar 29 at 22:33
1
1
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
I've taken a look at your second attempt, and added to my answer accordingly. Also, I've adjusted my commentary slightly on your first attempt. Leave a comment to let me know if you have any questions.
$endgroup$
– Cameron Buie
Mar 30 at 16:14
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
$begingroup$
my goodness!Cameron,you should write a math book,it would be better than the ones i have encountered! Regarding the proof of g being one-to-one, i purposefully omitted the case where p=l and q=l since i thought that would amount to "assuming what is to be proven" . Also, you seem to take (i)p=l and (ii)p $neq l$ as cases to be considered from which to establish/prove some result for q as opposed to letting p,q be arbitrary elements in the domain of g and proceeding with the one-to-one proof as per usual.Was my approach of assuming the different cases for p and q (simultaneously) wrong?
$endgroup$
– HalfAFoot
Mar 30 at 17:48
1
1
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
$begingroup$
Not wrong at all! Just unnecessarily broken up, in this case. If you want to use that route, it's fine. You'll just need to do your second and third cases a bit differently, and at least make mention of the fact that in the case $p=l$ and $q=l,$ we trivially have $p=q.$
$endgroup$
– Cameron Buie
Mar 30 at 17:59
|
show 1 more comment
$begingroup$
The problem you were given is somewhat ill-stated, and I believe that is where your confusion is coming from. In particular, they've posed the question as asking, "Show that the cardinality of $1,...,n$ is $n$," without stating what it means for a cardinality (which only talks about bijections between sets) to equal a natural number.
There's an easy way around this, of course: define the cardinality $n$ to be the cardinality of the set $1,...,n$ and say that a set $X$ has cardinality $n$ if there's a bijection from $X$ to $1,...,n$ (Actually, this is more often done with the set $0,...,n-1$ but I'll stick with the convention you are using). However, failing to explicitly bring up this idea obfuscates what's going on in the problem: hiding the interesting thing it is actually getting you to prove and making it look as though it is just asking you to prove the thing that we should actually be using as a definition.
The interesting idea behind this problem is this: after identifying particular cardinalities with natural numbers in the definition, do the cardinalities actually act like natural numbers? One part of showing that is this proof that different numbers are different cardinalities. So let's state this problem as it should actually have been:
Prove that for all $n in mathbbN$ if $k<n$ then there is no bijection from $1,...,n$ to $1,...,k$
We'll prove it by induction on the larger number $n$. (This is where your first question is answered. Don't worry about comparing $n$ to $k$ greater than $n$. That will be sorted when the induction process reaches that larger $k$, at which point it'll show that that $k$ isn't in bijection with any set of cardinality less than $k$, including the $n$ you started with.)
The base case is better proved as: there's no bijection from $1$ to the empty set (i.e. $0$) because there are no functions from an inhabited set to the empty set.
We then get to the induction step. We want to assume that there is no bijection from $1,...,n$ to $1,...,k$ with $k<n$ and use it to show that there is no bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$
This will be proved by contrapositive: we instead assume that there is actually a bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$ and use it to construct a bijection from $1,...,n$ to $1,...,k-1$. $k-1<n$, so this contradicts the induction hypothesis.
This is where you're question "If we define the function as above,then wouldn't the following be possible: $f(n+1)=k$ and $f(n)=k$ and render the function not one-to-one??" is answered. We don't take the function like that, because the existence of a one-to-one function from $1,...,n+1$ to $1,...,k$ is the assumption we are using. Therefore we can pick the function $f$ to be injective.
Your job, when completing the induction step is to construct the bijection from $1,...,n$ to $1,...,k-1$ from the one you've assumed exists from $1,...,n+1$ to $1,...,k$. In the process, you should see why we picked $1,...,k-1$ as the target.
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
$endgroup$
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
add a comment |
$begingroup$
The problem you were given is somewhat ill-stated, and I believe that is where your confusion is coming from. In particular, they've posed the question as asking, "Show that the cardinality of $1,...,n$ is $n$," without stating what it means for a cardinality (which only talks about bijections between sets) to equal a natural number.
There's an easy way around this, of course: define the cardinality $n$ to be the cardinality of the set $1,...,n$ and say that a set $X$ has cardinality $n$ if there's a bijection from $X$ to $1,...,n$ (Actually, this is more often done with the set $0,...,n-1$ but I'll stick with the convention you are using). However, failing to explicitly bring up this idea obfuscates what's going on in the problem: hiding the interesting thing it is actually getting you to prove and making it look as though it is just asking you to prove the thing that we should actually be using as a definition.
The interesting idea behind this problem is this: after identifying particular cardinalities with natural numbers in the definition, do the cardinalities actually act like natural numbers? One part of showing that is this proof that different numbers are different cardinalities. So let's state this problem as it should actually have been:
Prove that for all $n in mathbbN$ if $k<n$ then there is no bijection from $1,...,n$ to $1,...,k$
We'll prove it by induction on the larger number $n$. (This is where your first question is answered. Don't worry about comparing $n$ to $k$ greater than $n$. That will be sorted when the induction process reaches that larger $k$, at which point it'll show that that $k$ isn't in bijection with any set of cardinality less than $k$, including the $n$ you started with.)
The base case is better proved as: there's no bijection from $1$ to the empty set (i.e. $0$) because there are no functions from an inhabited set to the empty set.
We then get to the induction step. We want to assume that there is no bijection from $1,...,n$ to $1,...,k$ with $k<n$ and use it to show that there is no bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$
This will be proved by contrapositive: we instead assume that there is actually a bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$ and use it to construct a bijection from $1,...,n$ to $1,...,k-1$. $k-1<n$, so this contradicts the induction hypothesis.
This is where you're question "If we define the function as above,then wouldn't the following be possible: $f(n+1)=k$ and $f(n)=k$ and render the function not one-to-one??" is answered. We don't take the function like that, because the existence of a one-to-one function from $1,...,n+1$ to $1,...,k$ is the assumption we are using. Therefore we can pick the function $f$ to be injective.
Your job, when completing the induction step is to construct the bijection from $1,...,n$ to $1,...,k-1$ from the one you've assumed exists from $1,...,n+1$ to $1,...,k$. In the process, you should see why we picked $1,...,k-1$ as the target.
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
$endgroup$
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
add a comment |
$begingroup$
The problem you were given is somewhat ill-stated, and I believe that is where your confusion is coming from. In particular, they've posed the question as asking, "Show that the cardinality of $1,...,n$ is $n$," without stating what it means for a cardinality (which only talks about bijections between sets) to equal a natural number.
There's an easy way around this, of course: define the cardinality $n$ to be the cardinality of the set $1,...,n$ and say that a set $X$ has cardinality $n$ if there's a bijection from $X$ to $1,...,n$ (Actually, this is more often done with the set $0,...,n-1$ but I'll stick with the convention you are using). However, failing to explicitly bring up this idea obfuscates what's going on in the problem: hiding the interesting thing it is actually getting you to prove and making it look as though it is just asking you to prove the thing that we should actually be using as a definition.
The interesting idea behind this problem is this: after identifying particular cardinalities with natural numbers in the definition, do the cardinalities actually act like natural numbers? One part of showing that is this proof that different numbers are different cardinalities. So let's state this problem as it should actually have been:
Prove that for all $n in mathbbN$ if $k<n$ then there is no bijection from $1,...,n$ to $1,...,k$
We'll prove it by induction on the larger number $n$. (This is where your first question is answered. Don't worry about comparing $n$ to $k$ greater than $n$. That will be sorted when the induction process reaches that larger $k$, at which point it'll show that that $k$ isn't in bijection with any set of cardinality less than $k$, including the $n$ you started with.)
The base case is better proved as: there's no bijection from $1$ to the empty set (i.e. $0$) because there are no functions from an inhabited set to the empty set.
We then get to the induction step. We want to assume that there is no bijection from $1,...,n$ to $1,...,k$ with $k<n$ and use it to show that there is no bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$
This will be proved by contrapositive: we instead assume that there is actually a bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$ and use it to construct a bijection from $1,...,n$ to $1,...,k-1$. $k-1<n$, so this contradicts the induction hypothesis.
This is where you're question "If we define the function as above,then wouldn't the following be possible: $f(n+1)=k$ and $f(n)=k$ and render the function not one-to-one??" is answered. We don't take the function like that, because the existence of a one-to-one function from $1,...,n+1$ to $1,...,k$ is the assumption we are using. Therefore we can pick the function $f$ to be injective.
Your job, when completing the induction step is to construct the bijection from $1,...,n$ to $1,...,k-1$ from the one you've assumed exists from $1,...,n+1$ to $1,...,k$. In the process, you should see why we picked $1,...,k-1$ as the target.
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
$endgroup$
The problem you were given is somewhat ill-stated, and I believe that is where your confusion is coming from. In particular, they've posed the question as asking, "Show that the cardinality of $1,...,n$ is $n$," without stating what it means for a cardinality (which only talks about bijections between sets) to equal a natural number.
There's an easy way around this, of course: define the cardinality $n$ to be the cardinality of the set $1,...,n$ and say that a set $X$ has cardinality $n$ if there's a bijection from $X$ to $1,...,n$ (Actually, this is more often done with the set $0,...,n-1$ but I'll stick with the convention you are using). However, failing to explicitly bring up this idea obfuscates what's going on in the problem: hiding the interesting thing it is actually getting you to prove and making it look as though it is just asking you to prove the thing that we should actually be using as a definition.
The interesting idea behind this problem is this: after identifying particular cardinalities with natural numbers in the definition, do the cardinalities actually act like natural numbers? One part of showing that is this proof that different numbers are different cardinalities. So let's state this problem as it should actually have been:
Prove that for all $n in mathbbN$ if $k<n$ then there is no bijection from $1,...,n$ to $1,...,k$
We'll prove it by induction on the larger number $n$. (This is where your first question is answered. Don't worry about comparing $n$ to $k$ greater than $n$. That will be sorted when the induction process reaches that larger $k$, at which point it'll show that that $k$ isn't in bijection with any set of cardinality less than $k$, including the $n$ you started with.)
The base case is better proved as: there's no bijection from $1$ to the empty set (i.e. $0$) because there are no functions from an inhabited set to the empty set.
We then get to the induction step. We want to assume that there is no bijection from $1,...,n$ to $1,...,k$ with $k<n$ and use it to show that there is no bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$
This will be proved by contrapositive: we instead assume that there is actually a bijection from $1,...,n+1$ to $1,...,k$ with $k<n+1$ and use it to construct a bijection from $1,...,n$ to $1,...,k-1$. $k-1<n$, so this contradicts the induction hypothesis.
This is where you're question "If we define the function as above,then wouldn't the following be possible: $f(n+1)=k$ and $f(n)=k$ and render the function not one-to-one??" is answered. We don't take the function like that, because the existence of a one-to-one function from $1,...,n+1$ to $1,...,k$ is the assumption we are using. Therefore we can pick the function $f$ to be injective.
Your job, when completing the induction step is to construct the bijection from $1,...,n$ to $1,...,k-1$ from the one you've assumed exists from $1,...,n+1$ to $1,...,k$. In the process, you should see why we picked $1,...,k-1$ as the target.
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
edited Mar 29 at 18:57
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
answered Mar 29 at 12:32
ChessanatorChessanator
2,3111412
2,3111412
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
add a comment |
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
$begingroup$
Thanks Chessanator,i will look at all these answers later!
$endgroup$
– HalfAFoot
Mar 29 at 13:16
add a comment |
$begingroup$
Using the answers given above,another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The base case invovles proving that |$1,2,3,...n$|$=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that |$1,2,3,...n$|$=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since f is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
$endgroup$
add a comment |
$begingroup$
Using the answers given above,another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The base case invovles proving that |$1,2,3,...n$|$=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that |$1,2,3,...n$|$=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since f is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
$endgroup$
add a comment |
$begingroup$
Using the answers given above,another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The base case invovles proving that |$1,2,3,...n$|$=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that |$1,2,3,...n$|$=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since f is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
$endgroup$
Using the answers given above,another attempt :
The objective is to prove that for all natural numbers $n ge1$:
$$left|1,2,3,dots,nright|=n.$$
(a) The Base step
The base case invovles proving that |$1,2,3,...n$|$=n$ for the base case where $n=1$. Since the number of elements in $1$ is $1$, then
$$left|1right|=1$$ as required.
(b) The Inductive step
Let $n ge 1$ be any natural number and assume that |$1,2,3,...n$|$=n$. The objective is to prove that
$$left|1,2,3,dots,n+1right|=n+1.$$
Suppose for a contradiction that $|1,2,3,dots,n+1| neq n+1$ or more precisely that
either (i) $|1,2,3,dots,n+1|=k lt n+1$
or (ii) $|1,2,3,dots,n+1| =k gt n+1$
and derive a contradiction.
Without loss of generality, consider the case of (i) where we assume that $|1,2,3,dots,n+1|=k lt n+1$ holds.
By the induction hypothesis and with $k<n+1$ we can define a set $1,2,dots ,k$ with the property that $|1,2,dots ,k|=k$.
Since $|1,2,dots ,n+1| =k$ by assumption, then we can use the fact of equal cardinalty across these sets to define a one-to-one and onto function.
Define $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ with $1 le j le k$ be such that $f(n+1)=j$ and $1 le l le n+1$ be such that $f(l)=k$.
This is perhaps the most confusing part for me. The idea now,if I understand it correctly, is to use $f$ to derive
another bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ which, with the help of the induction hypothesis, shall provide us with a contradiction to the initial assumption of $k<n+1$.
Continuing with the proof, the derivation of the bijective function $g:1,2,dots, n rightarrow 1,2,3, dots,k-1 $ from $f:1,2,dots ,n+1 rightarrow 1,2,dots ,k$ defined by
$1 le j le k$ for $f(n+1)=j$
$1 le l le n+1$ for $f(l)=k$
proceeds as follows:
[case : j=k and l=n+1]
$f(n+1)=j=k$ hence $n+1$ is mapped to $k$. The rest of the elements
in the domain and codomain of $f$ cover $1,2,dots, n$ and
$1,2,dots, k-1$ respectively,both coinciding with those of the
function $g$ we seek. Let $m in 1,2,dots, n$ and $g(m)=f(m)$.[Regarding $g$ being one-to-one]
For $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$, since
$g(p)=f(p)$ and $g(q)=f(q)$ then $f(p)=f(q)$ and with $f$ being
one-to-one,$p=g$ as required. Therefore $g$ is one-to-one.[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ and let p be the value found in
$1,2,dots, n$ and prove that $q=g(p)$.Letting p be such that
$q=f(p)$,then with $f(m)=g(m)$, $q=g(p)$ as required.Therefore $g$ is
onto.
[case : j=k and l $lt$ n+1]
$f(n+1)=k$ and $f(l)=j=k$. This would imply that different elements
in the domain are being mapped to the same element k in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l=n+1]
$f(l)=f(n+1)=k$ and $f(n+1)=j<k$. This would imply that the same
element in the domain is mapped to different values in the
codomain...so there is no need to consider this case further??
[case : j$lt$k and l$lt$n+1]
$f(l)=k$ and $f(n+1)=j<k$. This implies that some element in the
domain less than $n+1$ is mapped to $k$ and $n+1$ is mapped to some
element in the codomain that is less than $k$.Since (n+1) is not in the domain of $g$ but is mapped to some element
j in the desired codomain,we need some other element to map to it from the domain.Since l is in the domain of $g$ but maps to some element k not in the
desired function's codomain, we have an element that needs some element in the codomain to map to.
The above suggests that $l in 1,2,dots, n$ should be mapped to $j in 1,2,dots, k-1$
Finally, the function $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is defined as follows:
For all $m in 1,2,dots, n$
- if $m=l$, then $g(m)=j$
- if $m neq l$, then $g(m)=f(m)$
To prove that $g$ is one-to-one and onto:
[Regarding $g$ being one-to-one]
Let $p,q in 1,2,dots, n$, assume that $g(p)=g(q)$ and prove that $p=q$ across the following cases:
[case: $p neq l$ and $q neq l$].
$g(p)=f(q)$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$,
then $f(p)=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p=l$ and $q neq l$].
$g(p)=j$ and $g(q)=f(q)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(q)$. Since f is one-to-one,then $p=q$ as required.
[case: $p neq l$ and $q=l$].
$g(q)=j$ and $g(p)=f(p)$ by defintion of $g$. Since $g(p)=g(q)$, then
$j=f(p)$. Since f is one-to-one,then $p=q$ as required.
[Regarding $g$ being onto]
Let $q in 1,2,dots, k-1$ such that $q=j$. Then with $p=l$, by
definition $q=g(p)$Let $q in 1,2,dots, k-1$ such that $q=f(p)$. Then with $p neq
l$, by definition $q=g(p)$
Therefore $g:1,2,dots, n rightarrow 1,2,dots, k-1$ is one-to-one and onto. Since there is a bijective relation between these sets, their cardinalities are equal such that $|1,2,dots, n|=|1,2,dots, k-1|$.Applying the induction hypothesis to both sides of the equation yields $n=k-1$ which contradicts the initial assumption that $k lt n+1$ or equivalently $n gt k-1$.
Therefore for all natural numbers $n ge 1$, |$1,2,3,dots,n|=n$
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
edited Mar 30 at 7:00
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
answered Mar 29 at 22:32
HalfAFootHalfAFoot
347
347
add a comment |
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%2f3166994%2fprove-that-1-2-3-n-n-for-all-natural-numbers-n-by-mathematical-ind%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
