Have I proved it if I say
f: Natural numbers to S f(n) = 2n-1
?
(a) {1,3,5,7..}
(b) {0,1,4,9..}
I know that by definition a set S is countable if there exists an injective function f: S to N..
I also know that if f is also surjective (so bijective) then the set is coutably infinite.
But I don't know how to PROVE IT!
According to your definition, you need a function from to ... But yes, defined by is a bijection for (a). Note that if 0 in considered a natural number (it varies by country ), then you need 2n+1, not 2n-1. You need to show that f is a bijection by proving that it is an injection and a surjection. Then, from a general theorem, you know that the inverse function exists and it is also a bijection. It is also easy to write this inverse function explicitly.f: Natural numbers to S f(n) = 2n-1
The set in (b) seems to be the set of squares of all natural numbers, so this tells you what the bijection is.
Defining a function f does not prove anything. It's the properties of f with respect to S and N that mean something, so they have to be proved.Have I proved it if I say
f: Natural numbers to S f(n) = 2n-1
Yes. Also note, as I said, that proving that f : N -> S is a bijection is not a proof "by definition" that S is countable. Since your definition talks about a function S -> N, you need to make an extra step by saying that a bijection N -> S implies the existence of a bijection S -> N. It may be easier to define a bijection S -> N to begin with.I need to show that it is a bijection right?
Yes, though, as Plato pointed out, you were right in defining f(n) = 2n - 1.To prove 2n+1 is injective:
f(n1) = f(n2) so 2(n1) + 1 = 2(n2) + 1
2(n1) = 2(n2) so n1 = n2
This proves it's an injection?
Yes. It is easier, though, to define g: S -> N by g(y) = (y + 1) / 2 and to prove that it is an injection: this is all you need to prove that S is countable according to your definition. For every y in S, g(y) is indeed a natural number because y is odd, and so y + 1 is even. Also, for every y1, y2 in S, (y1 + 1) / 2 = (y2 + 1) / 2 implies y1 + 1 = y2 + 1 and so y1 = y2, so g is injective.So now showing that it is surjective.
Let n = (y+1)/2
f(2n-1) = 2 [(y+1)/2] -1
Sof(2n-1) = y
Is this correct?