# infinite prove

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• September 22nd 2012, 01:08 AM
Burcin
infinite prove
I need to prove this question: 2 http://upload.wikimedia.org/math/9/b...cec0743fcd.png the set of all even natural numbers. Prove that 2 http://upload.wikimedia.org/math/9/b...cec0743fcd.png is countably infinite.

I know that I can combine each even number with an http://upload.wikimedia.org/math/9/b...cec0743fcd.png number so that 2=1, 4=2, 6=3,....

I know how to write it down but not how to prove it proper.
And ik know I need to prove its bijective but I dont know how.
• September 22nd 2012, 02:15 AM
girdav
Re: infinite prove
Use the bijection $f\colon \Bbb N \to 2\Bbb N$, $f(n):=2n$.
• September 22nd 2012, 03:16 AM
Burcin
Re: infinite prove
f: N-->2N f(n)=2n

So if I want to prove its bijective I say:

n1,n2 ∈N f(n1)=f(n2) so 2n1=2n2 so n1=n2 so f is injective

n∈N f(n)=2n so n lays in the image of f so f is surjective

I say f is bijective. Is my prove correct?
Can I now say that 2N is countably finite ?
• September 22nd 2012, 03:21 AM
emakarov
Re: infinite prove
Quote:

Originally Posted by Burcin
f: N-->2N f(n)=2n

So if I want to prove its bijective I say:

n1,n2 ∈N f(n1)=f(n2) so 2n1=2n2 so n1=n2 so f is injective

Correct.

Quote:

Originally Posted by Burcin
n∈N f(n)=2n so n lays in the image of f

Why does n lie in the image of f?
• September 22nd 2012, 03:32 AM
Burcin
Re: infinite prove
n∈N and n∈2N so that f(n)=2n so we see that n lie in the image of f?
• September 22nd 2012, 03:37 AM
emakarov
Re: infinite prove
Quote:

Originally Posted by Burcin
n∈N and n∈2N so that f(n)=2n so we see that n lie in the image of f?

I don't understand what you are saying. What exactly are you proving (without using the word "surjective")? What is n? Why n∈2N? Not every n is in 2N.
• September 22nd 2012, 03:49 AM
Burcin
Re: infinite prove
well I tought for every n∈N there exists a 2n∈2N so that f(n)=2n is this correct proven
• September 22nd 2012, 03:52 AM
emakarov
Re: infinite prove
Quote:

Originally Posted by Burcin
well I tought for every n∈N there exists a 2n∈2N so that f(n)=2n

True.

Quote:

Originally Posted by Burcin
is this correct proven

No. I am still not sure what you are proving.
• September 22nd 2012, 04:01 AM
Burcin
Re: infinite prove
I need to prove this question: 2N is the set of all even natural numbers. Prove that 2N is countably infinite. ( N= natural numbers I cant copy the right notation)

In the forum girdav said that I need to use f;N->2N and f=2n
I thought I needed to prove that f is bijective to say that 2N is countably infinite
• September 22nd 2012, 04:11 AM
emakarov
Re: infinite prove
Quote:

Originally Posted by Burcin
I need to prove this question: 2N is the set of all even natural numbers. Prove that 2N is countably infinite. ( N= natural numbers I cant copy the right notation)

In the forum girdav said that I need to use f;N->2N and f=2n
I thought I needed to prove that f is bijective to say that 2N is countably infinite

I understand all this. I agreed that you have proved injectivity of f. We were talking about surjectivity. In post #6 I asked what you are proving without using the word "surjective." It is very important to get the statement right, including the quantifiers ("there exists," "for all"). A proof must match the structure of the claim. For example, there are specific ways to prove claims that start with "For all." Also, a proof must not contain undefined objects like n. All identifiers should be properly introduced.

So, what exactly are you proving at this point?
• September 22nd 2012, 04:25 AM
Burcin
Re: infinite prove
take any n you want 2n∈2N
if n≥0 then n∈N and f(n)=2n
so 2n is the image of f so f is surjective
• September 22nd 2012, 04:35 AM
emakarov
Re: infinite prove
Quote:

Originally Posted by Burcin
take any n you want 2n∈2N
if n≥0 then n∈N and f(n)=2n
so 2n is the image of f so f is surjective

This sort of, somewhat resembles a proof, and if I had evidence that you understand how to write similar proofs, I could possibly accept it. As it is, I doubt this. And I can't help you until you write the exact claim you are proving.
• September 22nd 2012, 05:20 AM
HallsofIvy
Re: infinite prove
Quote:

Originally Posted by Burcin
n∈N and n∈2N so that f(n)=2n so we see that n lie in the image of f?

If you are using n as the argument of f, you cannot require that n be in 2N. And by asserting that n is in N, you are going the wrong way.

Rather, to prove f is "surjective" (one-to-one) you need to prove "If y is in 2N then there exist n in N such that y= f(x)". If y is even then, by definition of "even", there exist n in N such that y= 2n= f(n).
• September 22nd 2012, 05:20 AM
Burcin
Re: infinite prove
I understand the theorie behind it all but I don't know how to use it to prove things, because I just started at the university.
I don't know what you mean do you mean that I cant prove proper that f is surjective?
• September 22nd 2012, 05:25 AM
Burcin
Re: infinite prove
So I don't neet to prove if f is surjective and injective to answer the question if 2|N is countably infinite
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last