Thread: The number and set of divisors functions problems and proofs...

Question Details
We introduce the number of divisors function d previously. For this function, d: N->N, where d(n) is the number of natural number divisors of n.

A function that is related to this function is the so-called set of divisors function. This can be defined as a function S that associates with each natural number the set of its distinct natural number factors. For example, S(6)={1,2,3,6}.

1.) Does there exist a natural number n such that the absolute value of S(n) = 1? Explain.

2.) Does there exist a natural number n such that the absolute value of S(n) =2? Explain?

3.) Write the output for the function d in terms of the output for the function S. That is, write d(n) in terms of S(n).

4.) Is the following statement true or false? Justify your conclusion.
For all natural numbers m and n, if m doesn't equal n, then S(m) = S(n). If it's true, the justification should be a proof...

5.) Is the following statement true or false? Justify your conclusion.
For all sets T that are subsets of N, there exists a natural number n such that S(n) = T. Again, if it's true the justification should be a proof...

Any help on this would be appreciated. This is a nongraded homework problem purely for my understanding and I have almost no idea how do do it, but I'll include my work below...


1.) I said that there does exist a natural number such that S(n)=1, it is 1 itself, I think, but I'm not sure what that means? 1 is in a set by itself because it's its only divisor?

2.) Along the same lines as part 1, would this S(n)=2,3,5,7,9,11, etc and all the other prime numbers, or is it just the set 2 by itself?

3.) All I got is d(n)=S(n) but I know there is more to it than that.

4.) and 5.) no idea

Originally Posted by Brjakewa

Question Details
We introduce the number of divisors function d previously. For this function, d: N->N, where d(n) is the number of natural number divisors of n.
A function that is related to this function is the so-called set of divisors function. This can be defined as a function S that associates with each natural number the set of its distinct natural number factors. For example, S(6)={1,2,3,6}.

1.) Does there exist a natural number n such that the absolute value of S(n) = 1? Explain.

2.) Does there exist a natural number n such that the absolute value of S(n) =2? Explain?

3.) Write the output for the function d in terms of the output for the function S. That is, write d(n) in terms of S(n).

4.) Is the following statement true or false? Justify your conclusion.
For all natural numbers m and n, if m doesn't equal n, then S(m) = S(n). If it's true, the justification should be a proof...

5.) Is the following statement true or false? Justify your conclusion.
For all sets T that are subsets of N, there exists a natural number n such that S(n) = T. Again, if it's true the justification should be a proof...

Any help on this would be appreciated. This is a nongraded homework problem purely for my understanding and I have almost no idea how do do it, but I'll include my work below...


1.) I said that there does exist a natural number such that S(n)=1, it is 1 itself, I think, but I'm not sure what that means? 1 is in a set by itself because it's its only divisor? CORRECT

2.) Along the same lines as part 1, would this S(n)=2,3,5,7,9,11, etc and all the other prime numbers, or is it just the set 2 by itself? The primes are correct but 9 is not prime.

3.) All I got is d(n)=S(n) but I know there is more to it than that.
I think you mean

4) Any two natural numbers must have different sets of divisors so

5) It says "For all sets T that are subsets of N".
So the rest is false because there are infinite sunsets of .

Had it said finite subsets then it is true.

1. Eww, no no no. This is probably some of the confusion. |S(n)| means the cardinality (number of elements) in S(n), not the "absolute value". It doesn't make sense to apply abs to sets. Your answer is correct, coincidentally at least.
2. The answer here would be ANY prime number, not all of them. It just wants you to prove at least one exists. So any choice is acceptable, yes, one exists.
4. I disagree with Plato above. The question is "For all natural numbers m and n, if m doesn't equal n, then S(m) = S(n)," and this is false by easy counterexample (pick any two different naturals). Unless you wrote that backwards, that is.

3 and 5, see Plato's discussion.

Originally Posted by Annatala

4. I disagree with Plato above. The question is "For all natural numbers m and n, if m doesn't equal n, then S(m) = S(n)," and this is false by easy counterexample (pick any two different naturals). Unless you wrote that backwards, that is.

Isn't that what I said? so the statent is false.

Yes, I just misread it...it seemed like you were answering the inverse. :P (Which of course answers both anyway.)

Can someone provide a counterexample for part 5 of my question I'm having difficulty with it. or could someone explain what it is asking to me and then provide a counterexample?

Originally Posted by Brjakewa

Question Details
We introduce the number of divisors function d previously. For this function, d: N->N, where d(n) is the number of natural number divisors of n. A function that is related to this function is the so-called set of divisors function. This can be defined as a function S that associates with each natural number the set of its distinct natural number factors.
5.) Is the following statement true or false? Justify your conclusion.
For all sets T that are subsets of N, there exists a natural number n such that S(n) = T.

Originally Posted by Brjakewa

Can someone provide a counterexample for part 5 of my question I'm having difficulty with it. or could someone explain what it is asking to me and then provide a counterexample?

Your latest posting makes one wonder if you understand anything about this question.
For example, the set of even natural numbers, is a subset of .
If there were a such that then every number in is a divisor of .
Is that possible?

It is asking you to explain whether every set of natural numbers is a divisor set or not. @Plato is correct that any infinite set that does not include 0 would be a counterexample (multiplying an infinite number of numbers will not get you a natural number result), but he misses the fact that any set containing 0 or any set not closed under factorization would also be a counterexample.

If T = {1, 2, 3}, this is no S(n) for any n. T can't contain 2 and 3 unless it also contains 6.

That actually does help a lot indeed thank you very much. And I do understand what this question is asking. Another question is assume for #4) If the proposition was instead:

For all natural numbers m and n, if m doesn't equal n, then S(m) doesn't equal S(n).

I know this is true, so I would have to prove this. Would a reasonable proof be to use contradiction, where I assume S(m)=S(n) so that m=n, which contradicts the assumption forcing the hypothesis to be true? Is that a sound way to tackle this situation, or should I go about another method like contrapositive?

"Contrapositive" isn't a proof method as much as it is a relationship between inverse and converse. The proof methods I can think of: example, deductive inference, principle of induction (which is logically deductive not inductive, ironically), reduction to previous solution, and contradiction (which can be combined with any of the others).

Your intuition is correct. To prove your statement, you want a proof by contradiction. Assume not: there exist different numbers m and n with the same successor. Then show this logically produces a contradiction, which means your assumption must be false (if the remainder of your logic is correct).