1. Not finding help here? Sign up for a free 30min 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!

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

    jbunniii

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Inductive Proof.
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...