1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 5, 2016 #1
    I have been studying discrete mathematics for fun and I am kind of stuck on this bijection problem.

    1. The problem statement, all variables and given/known data

    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)

    2. Relevant equations and concepts
    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ℤ
    3. The attempt at a solution (see link)
    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:
    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.
  2. jcsd
  3. Jun 6, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted