1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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