Inductive Proof.

1. Feb 4, 2012

cragar

1. The problem statement, all variables and given/known data
Let $n_1=min(n\in\mathbb{N}:f(n){\in}A)$
As a start to a defintion of g:N→A, set $g(1)=f(n_1)$
Show how to inductively continue this process to produce a 1-1 function g from
N onto A.
3. The attempt at a solution
$g(1)=f(n_1)$ so this is our base case for induction.
so $g(2)=f(n_1+1)$
If I understand this correctly g is a function that has input values of natural numbers and maps these to the set A.
So I guess I need to show that f(n) is in A and f(n+1) is in A
By definition f(n) is in A for all n, so f(n+1) is in A for all n.
Could I maybe do a proof by contradiction and assume that f(n+1) was not in A and show that it was because n+1 is in the Naturals, therefore it works for f(n), and f(n+1)

Last edited: Feb 4, 2012
2. Feb 4, 2012

jbunniii

Are there some additional assumptions that you haven't listed? It is obviously not going to be possible to construct a bijection between $\mathbb{N}$ and $A$ unless $A$ is countable. Also, there must be some assumption about $f$. In general, the set $\{n \in \mathbb{N} : f(n) \in A\}$ could be empty, in which case the minimum isn't even defined.

3. Feb 4, 2012

cragar

ok, ya sorry, It says there exists $f:\mathbb{N} --->B$ which is 1-1 and onto.
Let $A\subseteq B$ be an infinite subset of B.We must show that A is countable. The question was phrased in 2 parts and I thought they were separate.
Thanks for looking at that.