Ytukyg

Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → 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),dots, z(n)$ where no two values are equal. Prove that it is plausible to define $z(n + 1)$ where its value is not equal to any previous value.

What confuses me the most with this proof is where it specifies that $z$ is defined inductively. I know what an inductive proof is however if we are only told it is defined inductively how is it possible for us to define $z(1)$ if we do not know $z$'s definition.

if we had something such as $2^n + 1 = 3^n$ then we could define the base case $n = 1$ easily, we can clearly see the definitions of both sides of this equation to determine that $n = 1$ yields both $3$ in the LHS and $3$ in the RHS of the equation.

I feel like once I jump this hurdle I can solve the rest of the proof, an explanation of how to think about this prop would be absolutely amazing as it seems near impossible to continue without guidance.

Thank you for all the support, the people of math.stackexchange have been unbelievably helpful in my journey through discrete mathematics!

Link to similar question: Proof by induction using functions

I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.

We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.

Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.

Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.

Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.

Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.

Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.

Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.

$vdots$

Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?

Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.

By contradiction, we know that the function $z$ is injective. QED