• Support PF! Buy your school textbooks, materials and every day products Here!

[Discrete] Prove that |nZ| = |Z| for any postive integer n

  • #1
79
0
I have been studying discrete mathematics for fun and I am kind of stuck on this bijection problem.

1. Homework Statement


I wanted to apologize in advance if i put this homework question in the wrong part of the forums. Discrete Math and much logic math is a computer science type math of logic and boolean. Still its a college level math, so I was hoping that this was the right place. I also thought about posting in the math forums, but because I am trying to teach myself discrete mathematics, I figure it might be technically self-defined ""homework""

Let nℤ denote the set {x ∈ ℤ |∃k ∈ ℤ, x = kn } (ie. 2Z contains multiples of 2, 3Z contains multiples of 3, etc.). Prove that |nℤ| = |ℤ| for any positive integer n. (Hint: You should have a bijection should include n)

Homework Equations

and concepts[/B]
  1. It must involve the Theory or Concept of Bijection and either showing the bijection or proving the bijection
  2. Actually I wanted advice, because I am not sure about the steps of writing a discrete math proof. I get stuck on all the new math symbols which are confusing >-<; To me they seem to be special (bijection case, limit theorem case, iteration case, orthogonality case)
  3. X = kn ∈ ℤ
  4. nℤ

The Attempt at a Solution

(see link)[/B]
I am not really good with proofs or how to write a proofs. I feel like unlike physics problems and derivations which have a very specific series of steps... logic seems to lack steps...
I know bijection involves having tables of values can showing that their is one dependant value for every indepent value... so I made a table then expanded it for the infinite case of K and K+1:
VVVVVV
https://docs.google.com/spreadsheets/d/1S63E5dVCCHca3uLjWURXyiNz2KhJ0GVK0UHELjNDTHI/
^^^^^^^
However, I am not sure if my attempted solution is the right way to go about it or how to turn the answer into a proper proof for discrete mathematics.

Let me know what you guys think.
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
What is the most natural map (aka function) you can think of from ##\mathbb Z## to ##2\mathbb Z##?

Is it one-to-one?
Is its range all of ##2\mathbb Z##?
If you can show that the answer to both those questions is Yes then you have shown that your map is a bijection, which means that ##\mathbb Z## is bijective to ##2\mathbb Z##, which means that ##|\mathbb Z|=|2\mathbb Z|##.

Having done that, try proving it again replacing 2 by a general positive integer ##n##.
 

Related Threads on [Discrete] Prove that |nZ| = |Z| for any postive integer n

Replies
4
Views
9K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
875
  • Last Post
Replies
9
Views
2K
Replies
1
Views
9K
Replies
11
Views
8K
  • Last Post
Replies
4
Views
850
Replies
1
Views
2K
Replies
6
Views
445
  • Last Post
Replies
5
Views
12K
Top