Results 1 to 10 of 10

Math Help - The number and set of divisors functions problems and proofs...

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    26

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

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

    Quote Originally Posted by Brjakewa View Post
    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 \color{blue}d(n)=|S(n)|
    4) Any two natural numbers must have different sets of divisors so S(n)\ne S(m)~.

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

    Had it said finite subsets then it is true.
    Last edited by Plato; December 1st 2011 at 02:21 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    127

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

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

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

    Quote Originally Posted by Annatala View Post
    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? S(n)\ne S(m)\text{ if }n\ne m so the statent is false.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2011
    Posts
    127

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

    Yes, I just misread it...it seemed like you were answering the inverse. :P (Which of course answers both anyway.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2011
    Posts
    26

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

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

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

    Quote Originally Posted by Brjakewa View Post
    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.
    Quote Originally Posted by Brjakewa View Post
    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, \mathbb{E} is a subset of \mathbb{N}.
    If there were a K such that S(K)=\mathbb{E} then every number in S(K) is a divisor of K.
    Is that possible?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2011
    Posts
    127

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

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2011
    Posts
    26

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

    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Aug 2011
    Posts
    127

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

    "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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of Positive Divisors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 6th 2011, 03:35 AM
  2. Number of divisors problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 7th 2010, 06:07 AM
  3. divisors of a number
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 8th 2010, 08:34 AM
  4. Number of odd divisors
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 17th 2008, 07:00 AM
  5. number of divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 15th 2008, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum