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+1\}\rightarrow\{1,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,n\}\rightarrow \{1,2,\dots,k-1\}.$$
I tried:
The objective is to prove that for all natural numbers $n \ge1$: $$\left|\{1,2,3,\dots,n\}\right|=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|\{1\}\right|=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+1\}\right|=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+1\}\rightarrow\{1,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,...,n\}\rightarrow \{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,n\}\right|=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|\{1\}\right|=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+1\}\right|=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$
Let me go through your work. You've gotten off to a good start!
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+1\}\bigr|=\bigl|\{1,2,\dots n\}\cup\{n+1\}\bigr|=\bigl|\{1,2,...,n\}\bigr|+\bigl|\{n+1\}\bigr|=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.
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 $1\le k\le n.$ We'll use this a few times.
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 $\bigl\{1,2,3,...,n\}\bigr|=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.
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 $\{1\}\to\{1,2,...,k\},$ does it? Rather, it is because we know that $\bigl\{1,2,,...,k\}\bigr|=k$ and that $\bigl\{1,2,3,...,n,n+1\}\bigr|=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 "$1\le l\le n$ such that $f(l)=k,$" while at the same time allowing it with "$1\le j\le k$ be such that $f(n+1)=j$"! That's bad form. The hint should say "$1\le l\le n+1,$" instead.
This isn't quite what we're doing.
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 $m\in\{1,2,...,n\}.$ It's fairly straightforward to prove that this is a one-to-one and onto function $\{1,2,...,n\}\to\{1,...,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)=j\in\{1,...,k-1\}$ and we have $l\in\{1,2,...,n\}$ with $f(l)=k,$ we can define $g$ as follows: $$g(m)=\begin{cases}j & m=l\\f(m) & m\ne l.\end{cases}$$
I leave it to you to show that this is a one-to-one and onto function $\{1,2,...,n\}\to\{1,...,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.
As I added above, I would alter this induction hypothesis. We end up using the altered form later, in a couple of ways.
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.$"
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$."
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.
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)\in\{1,2,\dots ,k\},$ meaning that $f(n+1)=j$ for some $1\le j\le k.$ Since $f:\{1,2,\dots ,n+1\} \rightarrow \{1,2,\dots ,k\}$ is onto, then $f(l)=k$ for some $1\le l\le 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$).
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 $m\in\{1,2,\dots,n\}.$"
Nicely done, except for a typo: we should say "$p=q$" instead of "$p=g$."
It seems like you mean for your first sentence to say something like "Let $q\in\{1,2,\dots,k-1\}.$ We will show that $q=g(p)$ for some $p\in\{1,2,\dots,n\}.$" After that, I would say something like "Since $q\in\{1,2,\dots,k-1,k\}$ and since $f:\{1,2,\dots ,n+1\} \rightarrow \{1,2,\dots ,k\}$ is onto, then there is some $p\in\{1,2,\dots,n,n+1\}$ such that $q=f(p).$ Since $f(n+1)=k$ and $q\in\{1,2,\dots,k-1\},$ then $p\ne n+1.$ Hence, $p\in\{1,2,\dots,n\}$ so $g(p)=f(p)=q,$ as required. Therefore, $g$ is onto."
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.
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:
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).
That last sentence isn't quite right. Since $f$ is one to one and $f(p)=j=f(n+1),$ then $n+1=p\in\{1,2,...,n\}$ which is impossible!
Instead, we only need to consider two cases: $p\ne l$ and $p=l.$ If $p\ne l,$ then we can prove that $q\ne 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=q\in\{1,2,...,n\},$ which is absurd.
You seem to have the right idea, but aren't executing it very well. I would instead say something like this: "Let $q\in\{1,2,\dots,k-1\}.$ If $q=j,$ then $g(l)=j=q$ by definition of $g.$ Suppose $q\ne j.$ Since $q\in\{1,2,...,k-1,k\}$ and $f:\{1,2,\dots ,n+1\} \rightarrow \{1,2,\dots ,k\}$ is onto, then there is some $m\in\{1,2,\dots,n,n+1\}$ such that $f(m)=q.$ Since $q\ne j,$ then $f(m)\ne j=f(n+1),$ so $m\ne n+1.$ Thus, $m\in\{1,2,...,n\}.$ Furthermore, since $f(m)=q\in\{1,2,\dots,k-1\},$ then $f(m)\ne k=f(l),$ so $m\ne l.$ Thus, by definition of $g,$ we have $g(m)=f(m)=q,$ as desired."
Here, again, the adjusted induction hypothesis helps us out.
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.