Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

quarkine

While studying the countability of sets, i came across the following problem (In Methods of Real Analysis, Goldberg) : Show that Pn=set of polynomials of degree n (with all coefficients being integers and n fixed positive integer) is countable..

  • 5 months ago
  • 5 months ago

  • This Question is Closed
  1. quarkine
    Best Response
    You've already chosen the best response.
    Medals 0

    my try was

    • 5 months ago
    1 Attachment
  2. Alchemista
    Best Response
    You've already chosen the best response.
    Medals 2

    All you need is that \(\mathbb{Z}^n\) is countable because from there you can simply setup a bijection between \(\mathbb{Z}^n\) and \(P_n\) with integer coefficients .

    • 5 months ago
  3. Alchemista
    Best Response
    You've already chosen the best response.
    Medals 2

    This is indeed by induction because \(Z \times Z\) is countable via cantor's pairing function. The same technique used to show that \(\mathbb{Q}\) is countable. Then do the same thing inductively \(\mathbb{Z}^2 \times Z\), etc.

    • 5 months ago
  4. Alchemista
    Best Response
    You've already chosen the best response.
    Medals 2

    Sorry I meant \(\mathbb{Z}^{n + 1}\)

    • 5 months ago
  5. quarkine
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmm i guess that's true but i just needed to know if the method i mentioned above will work.I found it wont :(

    • 5 months ago
  6. quarkine
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks for the answer anyway..

    • 5 months ago
  7. kbomeisl
    Best Response
    You've already chosen the best response.
    Medals 1

    Alchemista is largely correct in that setting up a function between the two given sets is the most parsimonious way to go about such a proof. However, you don't really need a bijection, in fact, a surjection with the natural numbers as the image or an injection with the natural numbers as the preimage would be sufficient. I'm having some trouble interpreting your proof, from what I see, you are mapping a n-tuple of integer coefficients to one natural number. But I can't quite understand what method you are using to map. Honestly, this method will only work for finite term polynomials (which i know is the objective of the assignment) but a mathematician must always work for maximum generalizability. If you start working with arbitrarily number term polynomials, this proof method will fail as Cantor's diagonal method can be used to prove that indeed the cardinality of such polynomials is uncountable. When finding a surjection between a given set and the natural numbers, the function f(x,y,z..) = 2^x(3^y)(5^z)... with each base a prime and each power a member of the set. The fundamental theorem of arithmetic will guarentee that this is a bijection (think unique prime factoring) or course if one is using a general countable set that is not the natural numbers a unique prime factorization is not guarenteed so stick with the natural numbers.

    • 5 months ago
  8. quarkine
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks. What i wanted to do was to assign a unique no. with each polynomial.Your method seems great for that.Never occurred to me to use the fundamental theorem of arithmetic to generate unique number!

    • 4 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.