Proof of Polynomial Countability

In summary, by using induction, it can be proven that P(n) is countable. Starting with P(0) and P(1), it can be shown that all polynomials with integer coefficients are countable. This is based on the fact that P(n+1) can be written in terms of P(n) and the union of countable sets is also countable. Therefore, all polynomials with integer coefficients form a countable set.
  • #1
Shaikhob
1
0

Homework Statement


Let P(n) be the set of all polynomial of degree n with integer coefficients. Prove that P(n) is countable, then show that all polynomials with integer coefficients is a countable set.

2. The attempt at a solution
For this problem the book gives me a hint that using induction is one way to prove this. So by going off this I say that P(0) is countable since it is the set of all constants. After this I say that P(1) is countable since P(1) = ax + P(0) in which a ε A and A = {z: z ε Z, z ≠ 0}. Now my problem is that I do not know how to make the jump from P(1) to P(n) and then to P(n+1). For the second part of the question I know that all polynomials with integer coefficients are countable since if we were to take a union of all the sets they would be countable since the union of countable sets are countable.
 
Physics news on Phys.org
  • #2
Hi, welcome to PF.

Looks like you already got all the components in place for a proof by induction.
Suppose that you have proven that P(n) is countable... can you write P(n + 1) in terms of P(n)?
 
  • #3
hint: which terms are in P(n+1) that AREN'T in P(n)?

can you think of a way to write p(x) in P(n+1) as:

"something" + q(x), where q(x) is in P(n)?

maybe the "somethings" might be countable...
 

FAQ: Proof of Polynomial Countability

What is "Proof of Polynomial Countability"?

Proof of Polynomial Countability is a mathematical concept used in computer science and theoretical computer science to determine the efficiency of algorithms and data structures.

How is "Proof of Polynomial Countability" used?

This concept is used to analyze the time complexity of algorithms, specifically how the running time of an algorithm increases as the input size increases.

What does "proof of polynomial countability" mean?

This refers to the ability to prove that an algorithm has a polynomial running time, meaning that the running time increases at a rate that is no faster than a polynomial function.

What are some examples of polynomial-time algorithms?

Examples include sorting algorithms such as Bubble Sort, Insertion Sort, and Merge Sort, as well as searching algorithms like Binary Search and Hash Tables.

Why is "Proof of Polynomial Countability" important?

Understanding the efficiency of algorithms is crucial in computer science, as it allows us to determine the optimal solution for a given problem and improve the performance of our systems.

Similar threads

Back
Top