How to "prove" something in math?

[FTM1000]

i began learning a basic math course at an open university that suppose to teach the basics of math like mathematical proofs but i am struggling with understanding it. i understand the logic of the proofs in the examples the teacher shows in the class but i still have problem with understanding how to write a proof in the homework.
i have a question in my homework that said:
"ℕ is the set of natural numbers. A={1/2, 1/2²,1/2³,...} = {1/2ⁿ|n∈ℕ}
prove that A is infinite set"

i remember that the teacher said that a set is infinite if there is a propersubset(i don't know if it is the right defenition for the ⊂ symbol) that is equinumerous with the group. so what should i write in the answer? that there is a set that is B⊂A(the set from the question) and that B and A are equinumerous by giving some group B as an example?.

sorry if i am not using the right terms, i am learning in hebrew and i am not familiar with the english words for what i saw in the class and my book.

 

[jedishrfu]

You can see that the natural numbers have a one-to-one correspondence with the 1/2^n elements of your set meaning they are the same size and type of infinity ie a countable infinity.

@fresh_42 can answer this better than I though.

 

[Mark44]

You can see that the natural numbers have a one-to-one correspondence with the 1/2^n elements of your set meaning they are the same size and type of infinity ie a countable infinity.

This is really all the OP needs to show. Clearly there is a one-to-one pairing between the elements in ##\mathbb N## (the positive integers) and the set of fractions of the form ##\frac 1 {2^n}##.

 

[fresh_42]

What bothers me most is the usage of the word group in this context. A group is a certain mathematical object and the natural numbers are not a group, so the word set would be the better fit. To prove something, it is always best to start with an account balance:

• What do we want to prove?
• What do we know?
• Which kind of proof might be suitable?

So here we go:

• Show that ##A = \{\frac{1}{2^n}\, : \,n\in \mathbb{N}\}## is infinte.

Now the set ##A## is clear, i.e. no questions here. But what is infinite? I'm not sure I understood your teacher's definition correctly. I read it as: A set "A" is infinite, if it contains a proper subset "B" which has as many elements as ##\mathbb{N}## has. This is the next point, which isn't quite clear: Why a proper subset? If "B" contains as a many elements as ##\mathbb{N}## then it will do. Unfortunately some authors don't distinguish ##" \subset "## and ##" \subseteq "##, so the former doesn't have to mean proper. For this reason I like to write ##"\subseteq "## if equality is allowed and ##"\subsetneq"## if not. Anyway, proper isn't needed here; it makes things unnecessarily complicated. Thus we have

• A set is infinite, if it contains at least as many elements as ##\mathbb{N}## does.

So now we know what we want to prove, and which are the meanings of the words we use, which leads us to the question of how to prove it. The most common argumentation is by an indirect proof: What if it were not the case? and deduce a contradiction from this assumption. This is possible, as we cannot deduce a false statement from a true one. "A" is finite would be a statement we don't know whether it's right or wrong at the beginning. However, if it leads to a contradiction, a false statement, then it could have been true, for otherwise we would have gotten only true conclusions. Another way is a direct proof, which might be easier here: Show that the set "A" contains at least as many elements as ##\mathbb{N}## does. But what does "as many elements as" mean? This should have been considered in the previous part, under the headline: What do we know? We'll have to fill this gap now. Two sets have equally many elements, if there is a one-to-one correspondence, a bijection, between them.

• Direct proof: ##f \, : \, \mathbb{N} \longrightarrow \left\{ \frac{1}{2^n}\, : \,n \in \mathbb{N} \right\} ## has to be shown to be a one-to-one correspondence. This means we have to show that no two elements map to the same one, i.e. ##f(n)=f(m) \Longrightarrow n=m## and that every element in ##A## is hit by ##f##. I'll leave this as an exercise to you.
• Indirect proof: Assume ##A = \left\{ \frac{1}{2^n}\, : \,n \in \mathbb{N} \right\}## is finite. Then we can enumerate all elements of ##A##, i.e. ##A=\{a_1,\ldots a_N\}## for some ##N \in \mathbb{N}## and all ##a_i## are powers of an half. Now think about what this means and whether this can be. If you can conclude a false statement from this assumption, then you will have shown. that the assumption "A is finite" must have been wrong, which in return means the opposite is true, i.e. A is infinite. I'll leave it as an exercise as well, to deduce such a contradiction. Hint: If you have solved the direct proof, you can use a similar argumentation here.

Edit: typo corrected.

 

[FTM1000]

so i just need to prove that there is a bijection between A and ℕ?. i saw in my book an example for a bijection where a set D = {x: x is an odd number between 1 and 49}
and E = {y: y is an even number between 2 and 50} and every x in D is paired(don't sure what word to use here) with y by adding 1 to it,
y = x + 1.
so i can do something like that in this question? like matching for every n ∈ ℕ a number in the set A by doing n/2ⁿ?.
sorry if what i saying is sound stupid or unclear, its simply really new to me and i have hard time matching the hebrew terms i read and hear in my class with the english terms like with the term kvutzot in hebrew which means "groups" in hebrew but in mathematics they are sets and i realized it while i wrote my thread(i saw the wiki article about group in mathematics) and forgot to fix it with the ℕ set.

 

[fresh_42]

so i can do something like that in this question? like matching for every n ∈ ℕ a number in the set A by doing n/2n?.

##1/2^n##, and yes, that's the informal description. The formal way is to show

##f \, : \, \mathbb{N} \longrightarrow \left\{ \frac{1}{2^n}\, : \,n \in \mathbb{N} \right\}## has to be shown to be a one-to-one correspondence. This means we have to show that no two elements map to the same one, i.e. ##f(n)=f(m) \Longrightarrow n=m## and that every element in ##A## is hit by ##f##.

 

[FTM1000]

so we simply pair the 1 from the ℕ set to 1/2 from A set and 2 to 1/2² and 3 to 1/2³ and so on? did i understood it right?.
if so how do i do it in the formal way?, that all what i have to do?.

 

[Mark44]

so we simply pair the 1 from the ℕ set to 1/2 from A set and 2 to 1/2² and 3 to 1/2³ and so on? did i understood it right?.
if so how do i do it in the formal way?, that all what i have to do?.

##f(n) = \frac 1 {2^n}, n \in \mathbb N##
Just show that this function is one-to-one, hence is invertible.

 

[mathwonk]

pardon me if i disagree with these answers. in any proof you always start from a definition, and your teacher has given you a definition that you should use. Namely your teacher said a set is infinite if it is equinumerous with a proper subset. hence you must show your set is equinumerous with a proper subset of itself, not with the set of natural numbers. hence an appropriate proof would be to show that the set you are considering is equinumerous with say the subset of all elements after the first one. such a relation can ben obtained by multiplying your set elements by 1/2. I.e. check that multiplying your set by 1/2 is a bijection between the elements of your set and the proper subset of those elements occurring after the first element.

I.e. the answers given here assume that the set of natural numbers is infinite and that any set equinumerous with an infinite set is also infinite, neither of which facts have been given you. You should use only what has been given. that is what a "proof" is, namely it is a logical argument proceeding from given assumptions.

It is of course true that a set equinumerous with the natural numbers is infinite, but to prove that from your teacher's definition requires two additional proofs, namely that the ntrual numberts are infinite and that any set equinumnerous with an infinite set is also infinite.

Moral: in any proof always begin from a definition.

 

[FTM1000]

pardon me if i disagree with these answers. in any proof you always start from a definition, and your teacher has given you a definition that you should use. Namely your teacher said a set is infinite if it is equinumerous with a proper subset. hence you must show your set is equinumerous with a proper subset of itself, not with the set of natural numbers. hence an appropriate proof would be to show that the set you are considering is equinumerous with say the subset of all elements after the first one. such a relation can ben obtained by multiplying your set elements by 1/2. I.e. check that multiplying your set by 1/2 is a bijection between the elements of your set and the proper subset of those elements occurring after the first element.

I.e. the answers given here assume that the set of natural numbers is infinite and that any set equinumerous with an infinite set is also infinite, neither of which facts have been given you. You should use only what has been given. that is what a "proof" is, namely it is a logical argument proceeding from given assumptions.

It is of course true that a set equinumerous with the natural numbers is infinite, but to prove that from your teacher's definition requires two additional proofs, namely that the ntrual numberts are infinite and that any set equinumnerous with an infinite set is also infinite.

Moral: in any proof always begin from a definition.

so i need to give an example of a set that is a subset of A like B = {1/2²,1/2³,1/2⁴...} and write that there is a formula that pair each member of A to one member of B like x ∈ A , y ∈ B y = 1/2x ?.

 

[mathwonk]

yes, that's the ticket.