Prove Countability: Algebraic Numbers

In summary, the conversation discusses whether or not induction is necessary to prove that a set is countable, specifically in regards to showing that the set of algebraic numbers is countable. The use of induction is deemed helpful in this case, especially when considering polynomials of different degrees. The main argument is that since algebraic numbers are roots of polynomials with rational coefficients, the set of algebraic numbers can be shown to be a countable union of finite sets and thus, countable. The confusion lies in keeping track of which sets are being used and how they are being combined, but it is expected that these types of proofs will become easier with practice.
  • #1
quasar_4
290
0
So in general, do I always need to use induction to prove that a set is countable?

I'm trying to prove that the set of algebraic numbers is countable, but not sure if I am supposed to do it by induction. I am not sure how else to do it.
 
Physics news on Phys.org
  • #2
You don't "need to" use induction, but in this case an inductive-type argument is very helpful. Algebraic numbers are roots of polynomials - so it might be a good idea to consider polynomials of degree n separately.
 
  • #3
ok, so the induction would be done on the degree of the polynomial...

I was thinking maybe I could map each algebraic number to the polynomial(s) of which it is a root. Then use this definition of the "height" of the polynomial (in our book, it's the sum of the degree of the polynomial with the absolute value of the coefficients of the poly.). I think it is reasonable to say that since each polynomial of degree n has at most n roots, that the set of algebraic numbers corresponding to all the polynomials of height h is at most countable (I hope this is strong enough).

Then if I take the union of the sets of differing heights, I'd be taking the union of at most countable sets, which must also be at most countable...

where does the induction step fit in? I guess I'm not sure what to show.. that the idea holds for the polynomials of degree 1, then show n => n+1?
 
  • #4
Why should there be an inductive step?

A key point that you might have missed is that algebraic numbers are roots of polynomials with rational coefficients. So for each n, the set P_n of polynomials with rational coefficients of degree <= n is countable. Each p in P_n has at most n roots. Let A_n denote the set of roots of all polynomials in P_n; this is a countable union of finite things, and is thus countable. Finally, the set of algebraic numbers is the union of the A_n's, and is thus countable (being also a countable union of countable sets).

This is pretty much your argument, and it's perfectly fine.
 
  • #5
excellent! I think it is just a bit confusing at first to keep track of which sets are which, and what's being put in union with other things. I am hoping that these proofs get easier as the course goes by... :P
 

Related to Prove Countability: Algebraic Numbers

1. What are algebraic numbers?

Algebraic numbers are numbers that can be expressed as the roots of polynomial equations with integer coefficients. In other words, they are solutions to equations of the form anxn + an-1xn-1 + ... + a0 = 0, where an, an-1, ..., a0 are integers and x is the unknown variable.

2. How do you prove that algebraic numbers are countable?

The proof for countability of algebraic numbers involves showing that they can be put into a one-to-one correspondence with the set of positive integers. This can be done by representing each algebraic number as a finite sequence of integers, and then using the Cantor pairing function to map each sequence to a unique positive integer.

3. What is the significance of proving countability of algebraic numbers?

Proving that algebraic numbers are countable is important in the field of number theory because it helps us understand the structure and properties of these numbers. It also allows us to compare the cardinality of algebraic numbers with other sets of numbers, such as the set of real numbers, which is uncountable.

4. Can irrational numbers be algebraic?

No, irrational numbers cannot be algebraic because they cannot be expressed as the roots of polynomial equations with integer coefficients. Irrational numbers, such as π and √2, are considered to be transcendental numbers, which means they are not solutions to any polynomial equation with integer coefficients.

5. Are all algebraic numbers also rational numbers?

No, not all algebraic numbers are rational numbers. While all rational numbers are algebraic, there are algebraic numbers that are not rational. For example, √2 is an algebraic number, but it is not a rational number. This is because it cannot be expressed as a ratio of two integers.

Similar threads

I ##L^2## square integrable function Hilbert space
    • Calculus
Replies
11
Views
406
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
565
I Is an algorithm for a proof required to halt?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
I Help with basic transfinite induction proof
    • Topology and Analysis
Replies
2
Views
266
MHB Proving Countability: Positive Rational Numbers & Union of Countable Sets
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
A Summing over continuum and uncountable numerocities
    • Calculus
Replies
1
Views
1K
MHB Proving that a subset of a countable set is countable
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
Proof that algebraic numbers are countable
    • Calculus
Replies
2
Views
3K
All the possible posts in PF, all the possible human thoughts
    • Precalculus Mathematics Homework Help
Replies
23
Views
879
Set of all rational sequences countable?
    • Calculus
Replies
2
Views
3K

Hot Threads

Recent Insights

Back
Top