# Proof by induction using functions

Prop: If the set $$A$$ is infinite then there exists an injective function $$z:N→A$$. $$z$$ is defined inductively, for the base case, explain how it is plausible to define$$z(1)$$. Now suppose that $$z(1),z(2),…,z(n)$$ where no two values are equal. Prove that it is possible to define $$z(n+1)$$ where its value is not equal to any previous value.

I now understand that this has a never-ending injective function that can be created, however, I do not understand how to actually write out the proof. I have written induction proofs before but not seeing an equation or sigma notation to follow I feel quite lost setting up a base case or inductive step showing $$z(n + 1)$$.

A written proof with explanation would be much appreciated!

Link to similar question: Proofs involving functions and induction

• 'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not? Nov 28 '18 at 14:09
• Its possible my bad Nov 28 '18 at 14:20
• @Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again? Nov 28 '18 at 14:45
• The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely! Nov 28 '18 at 17:37
• @Zdravstvuyte94 You should at least edit both questions to provide a link to the other. Nov 28 '18 at 19:23

The heart of the argument goes something like this.

Suppose that for some particular $$n$$ you have found $$B = \{z_1, \ldots. z_n\} \subset A$$ in $$A$$, where the $$z_i$$ are all different. That's an assertion about the number $$n$$. You want to show the same assertion is true for $$n+1$$. Well, by hypothesis $$A$$ is infinite. Since $$B$$ is finite, it can't be all of $$A$$, so you can find some element $$a \in A$$ that's not one of the $$z_i$$. Then define $$z_{n+1} = a$$.

What about the base case, to get the induction started? Well, since $$A$$ is infinite it's not empty, so you can choose some element $$a \in A$$ for the value $$z_1$$.

I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.

I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that

If the statement $$P(n)$$ is true then the statement $$P(n+1)$$ is true, even though I don't at the moment know any particular value of $$n$$ for which $$P(n)$$ is true.

• Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these. Nov 28 '18 at 18:28
• @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph. Nov 28 '18 at 18:33