Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inductive Proof.

  1. Feb 4, 2012 #1
    1. The problem statement, all variables and given/known data
    Let [itex] n_1=min(n\in\mathbb{N}:f(n){\in}A) [/itex]
    As a start to a defintion of g:N→A, set [itex]g(1)=f(n_1) [/itex]
    Show how to inductively continue this process to produce a 1-1 function g from
    N onto A.
    3. The attempt at a solution
    [itex] g(1)=f(n_1) [/itex] so this is our base case for induction.
    so [itex] g(2)=f(n_1+1) [/itex]
    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. jcsd
  3. Feb 4, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Are there some additional assumptions that you haven't listed? It is obviously not going to be possible to construct a bijection between [itex]\mathbb{N}[/itex] and [itex]A[/itex] unless [itex]A[/itex] is countable. Also, there must be some assumption about [itex]f[/itex]. In general, the set [itex]\{n \in \mathbb{N} : f(n) \in A\}[/itex] could be empty, in which case the minimum isn't even defined.
  4. Feb 4, 2012 #3
    ok, ya sorry, It says there exists [itex] f:\mathbb{N} --->B [/itex] which is 1-1 and onto.
    Let [itex] A\subseteq B [/itex] 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook