- #1

- 612

- 1

- Thread starter JonF
- Start date

- #1

- 612

- 1

- #2

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 4,019

- 228

The proof that the rationals are countable might be a good place to draw inspiration from

- #3

- 612

- 1

P(x) would be a function since it maps to a single set. That set would contain all of the roots.

- #4

- 612

- 1

I think I got it, not very formal, but does this look good?

Claim: Let A_n where n is a natural, be the set of all the roots of a nth degree polynomial. A_n is countable.

Clearly this is true is n = 1 since this set would be the rational numbers.

Suppose the claim holds for naturals less than or equal to n. Consider polynomials of degree n+1. They will be in the form of ax^n+1 + P_n. Where P_n is at most an nth degree polynomial and a is an integer. By the fundamental theorem of algebra each of these ax^n+1 + P_n polynomials have the less than or equal number, or one more root than P_n. Thus A_n+1 has to be less than P_n x {1,0}, which is countable. Thus the claim is true.

The union of all A_n would be the algebraic numbers. Each A_n was just proved to be countable. Since n is a natural this a countable union of countable sets, which is countable.

Claim: Let A_n where n is a natural, be the set of all the roots of a nth degree polynomial. A_n is countable.

Clearly this is true is n = 1 since this set would be the rational numbers.

Suppose the claim holds for naturals less than or equal to n. Consider polynomials of degree n+1. They will be in the form of ax^n+1 + P_n. Where P_n is at most an nth degree polynomial and a is an integer. By the fundamental theorem of algebra each of these ax^n+1 + P_n polynomials have the less than or equal number, or one more root than P_n. Thus A_n+1 has to be less than P_n x {1,0}, which is countable. Thus the claim is true.

The union of all A_n would be the algebraic numbers. Each A_n was just proved to be countable. Since n is a natural this a countable union of countable sets, which is countable.

Last edited:

- #5

- 382

- 4

- #6

- 811

- 6

We know that the polynomials are countable.

We know that an n-degree polynomials have at most n roots.

So we can write out a sequence:

Polynomial #1, Smallest root

Polynomial #1, 2nd Smallest root

...

Polynomial #1, Biggest root

Polynomial #2, Smallest root

Polynomial #2, 2nd Smallest root

...

Polynomial #2, Biggest root

...

Polynomial #n, Some root

...

We have a sequence of all the algebraic numbers. (And it's obviously countable). This sequence contains duplicates, though. If we remove all the duplicate entries, the list is still infinite. And an infinite subset of a countable set is countable.

You can harden that into a formal proof, but that's the idea.

- #7

- 612

- 1

This list doesn’t work, since it relies on the successor to an infinite amount of elements. For example, tell me what number in your list would (2)^1/5 be. There is no way you can do this, since 2^15 would come after all of the rational numbers.

We know that the polynomials are countable.

We know that an n-degree polynomials have at most n roots.

So we can write out a sequence:

Polynomial #1, Smallest root

Polynomial #1, 2nd Smallest root

...

Polynomial #1, Biggest root

Polynomial #2, Smallest root

Polynomial #2, 2nd Smallest root

...

Polynomial #2, Biggest root

...

Polynomial #n, Some root

...

We have a sequence of all the algebraic numbers. (And it's obviously countable). This sequence contains duplicates, though. If we remove all the duplicate entries, the list is still infinite. And an infinite subset of a countable set is countable.

You can harden that into a formal proof, but that's the idea.

Last edited:

- #8

- 811

- 6

It does not rely on any successor function.This list doesn’t work, since it relies on the successor to an infinite amount of elements. For example, tell me what number in your list would (2)^1/5 be. There is no way you can do this, since 2^15 would come after all of the rational numbers.

The only thing it relies on is that the cartesian product of two countable sets is countable.

Let's say, for illustration, the polynomial x^5 - 2 is the n-th polynomial in your favorite enumeration. And let's say k is the sum of the count of roots for polynomials 1, 2, 3, ..., n. (In most enumerations, k is probably going to be a very, very big number). And lastly, let's assume, for simplicity, that x^5 - 2 is the FIRST polynomial in the chosen enumeration with the root of 2^(1/5). Then the algebraic number 2^(1/5) has an index of k+1.

With a minor tweak to the idea above, it works with any root. The index is always finite and is unique. Thus, we have defined a bijection to the integers, and the algebraic numbers are countable.

- Last Post

- Replies
- 3

- Views
- 1K

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 1K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 685

- Last Post

- Replies
- 6

- Views
- 1K

- Replies
- 12

- Views
- 3K

- Replies
- 3

- Views
- 1K

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K