Proving Equivalence of {5n | n = 1,2,...} and ℤ

[Matt B.]

How would I go about showing that the set {5n | n = 1,2,...} is equivalent to ℤ.

I previously attempted to define a function f as f(n) = 5n/2 , when n is even AND (-1)[(5n-1)/(2)] , when n is odd. I then went on to show that the chosen function is 1-1 and onto, but my professor said this was inaccurate.

Any help would be appreciated! Thank you.

 

[Mark44]

How would I go about showing that the set {5n | n = 1,2,...} is equivalent to ℤ.

What are the numbers in your set? It should be almost trivial to set up a 1-1 mapping between the two sets, much simpler than the one you show below.

BTW, homework questions should be posted in the Homework & Coursework sections, not here in the technical math sections.

I previously attempted to define a function f as f(n) = 5n/2 , when n is even AND (-1)[(5n-1)/(2)] , when n is odd. I then went on to show that the chosen function is 1-1 and onto, but my professor said this was inaccurate.

Any help would be appreciated! Thank you.

 

[jbriggs444]

I previously attempted to define a function f as f(n) = 5n/2 , when n is even AND (-1)[(5n-1)/(2)] , when n is odd. I then went on to show that the chosen function is 1-1 and onto, but my professor said this was inaccurate.
.

What is (-1)[(5n-1)/(2)] when n=1 ?

 

[Matt B.]

What is (-1)[(5n-1)/(2)] when n=1 ?

-2??

 

[jbriggs444]

OK. And what did you want it to be?

 

[Matt B.]

OK. And what did you want it to be?

Do I not need my defined function to be equivalent to all values in ℤ or just any values of ℤ?

 

[jbriggs444]

Do I not need my defined function to be equivalent to all values in ℤ or just any values of ℤ?

Mark44 may have been leading you down a better path in post #2.

Your function is supposed to map values from one set to values in another set. It is supposed to be one to one and onto. We have established that your function takes 1 to -2.

Is 1 a member of the set that you are trying to map to ℤ?

 

[Matt B.]

Mark44 may have been leading you down a better path in post #2.

Your function is supposed to map values from one set to values in another set. It is supposed to be one to one and onto. We have established that your function takes 1 to -2.

Is 1 a member of the set that you are trying to map to ℤ?

I'm confused. So am I simply evaluating 5n at different values for n to deduce my original set that I am trying to map to ℤ? Then that would just be {5,10,15,20,25...} so then my function would just be f(n) = 5n ?

 

[WWGD]

Think of a number in your set as a multiple of a number in $\mathbb Z$ and show for very number in $\mathbb Z$ there is one such multiple.

WWGD4444.

I think the advice of :
Mark44
JBriggs444
WWGD4444

Should do it ;).

 

[Mark44]

I'm confused. So am I simply evaluating 5n at different values for n to deduce my original set that I am trying to map to ℤ? Then that would just be {5,10,15,20,25...} so then my function would just be f(n) = 5n ?

Yes, that's the simple one I was hinting at. Clearly this is a one-to-one function, so each number in the set {n} gets mapped to a number in the set {5n}, and vice versa.

Edit: I wasn't thinking very clearly on this reply...

 

[jbriggs444]

Yes, that's the simple one I was hinting at. Clearly this is a one-to-one function, so each number in the set {n} gets mappe to a number in the set {5n}, and vice versa.

That gets a bijection between {5, 10, 15, ... } and {1, 2, 3, ... }. But I understood the original post to be asking for a bijection with ℤ = { ..., -3, -2, -1, 0, 1, 2, 3, ... }

 

[WWGD]

Ultimately, you can find a bijection between {$5, 10, 15,...$} and $\mathbb N$ and then compose with a not-so-hard bijection between $\mathbb N, \mathbb Z$.

 

[Mark44]

That gets a bijection between {5, 10, 15, ... } and {1, 2, 3, ... }. But I understood the original post to be asking for a bijection with ℤ = { ..., -3, -2, -1, 0, 1, 2, 3, ... }

For some reason, I was thinking (without thinking very hard) that it was the positive integers. I was really thinking $\mathbb{N}$ rather than $\mathbb{Z}$.

 

[VKnopp]

What do you mean equivalent? I beg to differ. $\mathbb{Z}$ is much more dense then your set. I think what you mean is the cardinal is the same. You can prove this via 1 to 1 correspondence.

 

[Mark44]

What do you mean equivalent? I beg to differ. $\mathbb{Z}$ is much more dense then your set. I think what you mean is the cardinal is the same. You can prove this via 1 to 1 correspondence.

"Set equivalence" is appropriate here.
See https://proofwiki.org/wiki/Definition:Set_Equivalence

Let S and T be sets.
Then S and T are equivalent if and only if:
there exists a bijection f:S→T between the elements of S and those of T.

The set in the OP should have the same cardinality as the set that is to be found.

 

[Matt B.]

That gets a bijection between {5, 10, 15, ... } and {1, 2, 3, ... }. But I understood the original post to be asking for a bijection with ℤ = { ..., -3, -2, -1, 0, 1, 2, 3, ... }

So is it not possible to find a 1-1, onto function that relates the set {5, 10, 15,...} onto the set of all integers?

 

[Mark44]

So is it not possible to find a 1-1, onto function that relates the set {5, 10, 15,...} onto the set of all integers?

We didn't say that. See if you can find a way to map some of the numbers in {5, 10, 15, ...} to {0, 1, 2, 3, ...} and the rest of the numbers in {5, 10, 15, ...} to {..., -3, -2, -1}. Or you can follow WWGD's advice in post #12.

 

[Matt B.]

We didn't say that. See if you can find a way to map some of the numbers in {5, 10, 15, ...} to {0, 1, 2, 3, ...} and the rest of the numbers in {5, 10, 15, ...} to {..., -3, -2, -1}. Or you can follow WWGD's advice in post #12.

Here was my original attempt at the solution. Since I'm not following the discussion, can somebody point out what I am misinterpreting?

 

[Matt B.]

We didn't say that. See if you can find a way to map some of the numbers in {5, 10, 15, ...} to {0, 1, 2, 3, ...} and the rest of the numbers in {5, 10, 15, ...} to {..., -3, -2, -1}. Or you can follow WWGD's advice in post #12.

Sorry, it's me again. Since I am trying to map {5, 10, 15, 20, ...} onto {...,-3,-2,-1,0,1,2,3} could I use the function f such that f(n) = n/5 when n is even and (-1)(n/5) when n is odd??

 

[Mark44]

Sorry, it's me again. Since I am trying to map {5, 10, 15, 20, ...} onto {...,-3,-2,-1,0,1,2,3} could I use the function f such that f(n) = n/5 when n is even and (-1)(n/5) when n is odd??

Your set, let's call it S, is {5, 10, 15, 20, ...}
Your function maps the members of S as follows:
5 --> -1
10 --> 2
15 --> -3
20 --> 4
and so on.
No member of S gets paired with 0, 1, -2, 3, -4, and so on, so your function is not onto $\mathbb{Z}$, hence not one-to-one, so this doesn't work.

Your function just scales the input value by multiplying it. To pick up all of the missing numbers, the function also has to translate or shift, the input values. Can you think of a way for 5 --> -1, 15 --> -2, 25 --> -3, and so on, and for 10 --> 0, 20 --> 1, 30 --> 2, and so on?

 

[aikismos]

How would I go about showing that the set {5n | n = 1,2,...} is equivalent to ℤ.

I previously attempted to define a function f as f(n) = 5n/2 , when n is even AND (-1)[(5n-1)/(2)] , when n is odd. I then went on to show that the chosen function is 1-1 and onto, but my professor said this was inaccurate.

Any help would be appreciated! Thank you.

@Matt B.

Here are some clues using a different problem:

Let's say $S := \{ 7n : n \in ℕ\}$

In the elements $(e)$ in $(7, 14, 21, 28, 35, 42, ...)$ you were quick to see that by taking the even values and dividing you could reduce the sequence to the naturals...

7 14 21 28 35 42 ... (divide by 7)
1 2 3 4 5 6 ... (take only even values)
2 4 6 ... (take only those which are even)
1 2 3 ... (you've arrived at the naturals!)

So, in this case $14|e \rightarrow \frac{e}{14} = ℕ$. Of course, part of this is shifting from the $ℕ$ to $S$, which is why the divisibility of $e$ by 14 is required (NB $7(2n) \rightarrow 14n$)

Like Mark44 said, you need to find -W and the remainder of $S$. From your original post, it's obvious you are reaching out and finding two important handles on the problem. Yes, the the negation is necessary to reverse the sequence, and it has to do with the odds. But note that the remainder of $S$ is not $-ℕ$ but $-W$. Think about the difference in the codomains of $\{2n + 1\}$ and $\{2n - 1\}$. What do you notice? You had the right idea, but put it together wrong...

7 14 21 28 35 42 ... (divide by 7)
1 2 3 4 5 6 ... (take only odd values)
1 3 5 ... (now what?)
?
0 -1 -2 -3 ... (this is what you want, right?)

Once you're done, you have to rewrite in terms of $e$ and $S$ by combining the set definition with your notation for naturals!
All you have to do is put it together with what you already know. If you really understand it, then you shouldn't have any problems transferring this thinking to your homework problem.