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

In summary, the conversation is discussing a homework problem related to discrete mathematics. The problem involves proving that the cardinality of the set of multiples of a positive integer n, denoted by nℤ, is equal to the cardinality of the set of all integers, ℤ. The conversation also touches on the concept of bijection and the steps involved in writing a proof for discrete mathematics. The suggested approach is to find a one-to-one function from ℤ to nℤ and show that its range is all of nℤ, which would prove that |nℤ| = |ℤ|. The conversation concludes with a suggestion to try solving the problem again for a general positive integer n.
  • #1
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:
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.
Physics news on Phys.org
  • #2
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##.

1. What does the notation |nZ| mean in this statement?

The notation |nZ| represents the set of all multiples of the positive integer n. For example, if n = 2, then |nZ| would be the set {0, 2, 4, 6, ...}.

2. What is the significance of proving that |nZ| = |Z|?

This proof shows that for any positive integer n, the set of all multiples of n has the same cardinality (number of elements) as the set of all integers. This means that both sets are infinite and their elements can be paired up, demonstrating that they have the same size.

3. How can we prove that |nZ| = |Z|?

This can be proven using the concept of a bijection, which is a function that maps elements from one set to another in a one-to-one and onto manner. In this case, we can show that there exists a bijection between the set of all multiples of n and the set of all integers, which proves that they have the same cardinality.

4. Can you provide an example of a bijection between |nZ| and |Z|?

Yes, one example is the function f(x) = nx, where x is an element of |Z|. This function maps elements from |Z| to |nZ| in a one-to-one and onto manner, thus demonstrating a bijection between the two sets.

5. Is this statement true for all values of n, including non-positive integers?

No, this statement is only true for positive integers. If n is a non-positive integer (0 or a negative integer), then |nZ| would be the empty set, which does not have the same cardinality as |Z|.

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