You should be able to solve this.

True or false: Are algebraic numbers countable?
You can't use axiom of choice.

wut

Define countable faggot

Countable as in "to be found at a number line"?

They're countable by virtue of the number of algebraic equations over the rationals being countable in number and the fact that each of them has a finite number of algebraic solutions.

Just apply the fact that a countable union of countable sets is countable.

What's an algebraic number?

>>3
X is countable if there is an injective function from X to the set of natural numbers.

>>5
You're using axiom of choice. Without axiom of choice you don't have the "countable union of countable sets is countable" theorem. Also without axiom of choice, suprajective functions doesn't always have inverse.

>>6
an algebraic number is a complex number that is a root of a non-zero polynomial in one variable with rational coefficients.

>>7
Dumbass.  If X is a countable set whose members are all countable sets, theres a clear bijection between NxN and UX.  NxN is countable by a diagonalization argument, does not require AC at all.  Are you suggesting that the rationals cannot be proved countable if you assume the negation of AC?

>>8
NxN is countable (there is an injective function from NxN to N, in fact f(m,n) = 2^m 3^n works). There is a clear injective function from Q to NxN making Q countable. However there is no  bijection between UX and NxN (not even an injective function). You aren't gonna get any further without AC. Try it if you don't believe me.

>>9
A countably infinite set is one with a bijection between it and the natural numbers.
As X is countably infinite, there is a bijection f between N and X.  As f(i) is countably infinite, there is a bijection gi from N to f(i).  Let g(i,j) = gi(j).  This is a bijection from NxN to UX.

>>10 That's not necessary a biyection:
1) It is a biyection iff the elements of X are disjoint.
2) Even with that, you are using AC in your proof. How do you know that the {gi : gi is a biyection between f(i) and N} is a set?

>>11
Hmm, I think see what you're saying there.  There are going to be many such gi and you need AC to choose a particular one.  I shamefully concede.

I'd say you can probably get round the axiom of choice problem because you can define a well ordering on the set of all integer valued polynomials.

I've not put a lot of thought into it, but a nice well-ordering normally solves the problem.


How about explicitly doing it then.


For ease of, well everything, I'm just going to take positive co-efficients, to include negative ones we'd have to inject the integers into the naturals (easily done without AC) to use the method I'm gonna do.


So we're going to assign each algebraic number 3 integers.

To each irreducible polynomial we assosciate it's degree.

Within each degree of polynomial we can inject into the natural numbers as there are only a countable number of each degree (A finite union is still countable without AC), so we assosciate to each polynomial a second number, it's order in this ordering.


Then to each solution of that polynomial we order them by modulus and then argument in the complex plane, and assign it a third number.


Each algebraic number is uniquely defined by these three numbers (Because we used irreducible polynomials), so let's do an injection:


r |-> (p_a^p_b)^p_c

Where a,b,c are the numbers assosciated with r, and p_i is the ith prime.


That's an injective function into the natural numbers, hence they're countable?


I can't see much choice here, I'm defining countable as "can inject into w (that's an omega)", possibly you might need choice to extend to a bijection, although from what I remember the proof of the Cantor–Bernstein–Schroeder theorem doesn't require AC, (Looked up the proof, it didn't).

Hope I win an internets

Jeez set theory and this AoC shit is boring.

>>14
No, you're probably just dumb :-/

>>16
ur a dork

>>12
Well, I don't. Where do you need {gi : gi is a bijection between f(i) and N} in your proof?

>>13 Here


"
Within each degree of polynomial we can inject into the natural numbers as there are only a countable number of each degree (A finite union is still countable without AC), so we assosciate to each polynomial a second number, it's order in this ordering."

Might need choice here, but I can explicity construct an injection so it's fine.

>>18 You need that to construct the function that "represents g(i,j) =gi(j)" (intuitively you took manually an infinite functions while the proofs are required to be writen in a finite number of reasonings)

>>19
>>13

Yes, the Cantor-Berstein Schröder theorem doesn't need AC. I think your solution is right, an internet for you then. Here is another solution:
-----
Let N be the set of natural numbers. U will denote the symbol for union.
Note that if you have a suprayective function from N to some set X, then you have an injective function from X to N (this without AC, you just need to use that N is well ordered). In consecuense you have that X is countable.

Consider f a biyection between the prime numbers (removing the 2 and 3) and N. Let C = U{N^i x (i+1) : i € N}. Let F be a function from C to N defined by F((a1,a2,...,ai,k)) = 2^k 3^i f(1)^a1 f(2)^a2, ... , f(i)^ai. F is an inyective function, thus |C|=|N|.

Consider a lineal order P for the algebraic numbers (lexicographic for example). Let g be a function from C to the algebraic numbers defined by g((a1,a2,...,ai,k)) = the kth root (relative to P) of the polinomial a1 + a2x + ... + aix^i-1. g is a suprayective function, then you have a suprayective function from N to the algebraic numbers. In consecuence the cardinality of algebraic numbers is the same as the cardinality of N.

>>18 Here

>>20
As I tried to construct this function, I realized that you may be right. I'm not quite ready to shamefully concede, but I'm getting there ;)

>>21
You could always just look it up, it's quite a well documented fact that the proof that a countable union of countable sets is countable has to use the Axiom of choice

>>22
But where's the fun in that?

I still don't see why there's any fuss over the axiom of choice compared to any of the others.

Does standard zfc contain aoc? Is there any such thing as 'standard' zrf?

>>25
The C in ZFC stands for axiom of choice.  There is also ZFnC (I think) which assumes the negation of the axiom of choice.

>>24
Most of the others are much more intuitive, and lead to results that are more intuitive.

Things like the banach-tarski paradox, are not really something you'd want as a consequence of one of your axioms, but then again you probably want the hahn-banach theorem, so it's a pay-off.