Menge aller Polynome über Z abzählbar?

Question

,

ich habe eine Aufgabe, die ich nicht gelöst bekomme (eigentlich sogar mehrere, aber ich fange erstmal mit dieser hier an):

Für n ∈ ℕ_0, a_i ∈ ℤ, 0 ≤ i ≤ n und a_n ≠ 0 sei die Funktion p_n : ℤ→ℤ definiert duch:

\( p_n (x) = \( \sum \limits_{i=0}^{n} a i x i = a_n x^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0} \)

p_n heißt Polynom n-ten Grades über ℤ, und ℤ[x] = ∪_n≥0 ℤⁿ[x] sei die Menge aller Polynome über ℤ.

Ist ℤⁿ[x] bzählbar? Begründen Sie Ihre Antwort.

Ich habe zuerst überlegt ob man das vielleicht mit Hilfe einer Primzahlenzerlegung machen könnte.

Zum Beispiel:

2x³+x²+3x+5 = 7² * 5 * 3³ * 2⁵

Kann mir hier vielleicht jemand weiterhelfen?

Comments

Die Menge aller Polynome ist eine abzählbare Menge.

Dazu sollte man wissen das die Menge Z eine abzählbare Menge ist. Ich kann also alle Koeffizienten abzählen und damit ist auch die Zusammenstellung zu einem Polynom abzählbar.

---

Ist es wirklich so einfach? :-) Hätte ich jetzt nicht mit gerechnet. Danke für die schnelle Antwort :-).

Kannst du mir auch etwas zu dieser Aufgabe sagen:

Sei p_n(x) ∈ ℤⁿ[x] und z ∈ ℤ mit p_n(z) = 0. Dann heißt z eine (ganzzahlige) Wurzel von p_n(x).

Es sei ℤⁿ⁺ [x] = {p_n(x) ∈ ℤⁿ[x] | p_n(x) besitzt mindestens eine Wurzel}.

Zeigen Sie: ℤⁿ⁺[x] ist rekursiv aufzählbar.

Ich verstehe leider schon nicht einmal was mit der "Wurzel" gemeint ist, deswegen haben ich hier bisher nichteinmal eine Idee. 

---

Ich habe meine Antwort mal zum Kommentar gewandelt. Ich bin momentan auch etwas ratlos.

Lu oder jemand anders kann hier sicher helfen.

---

OK. Danke auf jedenfall für die erste Antwort.
Ich habe eben noch einen zweiten Kommentar geschrieben, der ist aber irgendwie verloren gegangen. Ich wollte noch Fragen, ob du mir auch sagen kannst wie ich das formal aufschreibe, dass die Menge aller Polynome abzählbar ist.

Ich habe das für die Menge ℤ jetzt auch gefunden, das sieht ja so aus:

f(x) = { 0, falls z = 0

            2z, falls z > 0

           -(2z + 1), falls z < 0

Kannst du mir hierbei vielleicht noch helfen?

---

Sei p_n(x) ∈ ℤⁿ[x] und z ∈ ℤ mit p_n(z) = 0. Dann heißt z eine (ganzzahlige) Wurzel von p_n(x).

Es sei ℤⁿ⁺ [x] = {p_n(x) ∈ ℤⁿ[x] | p_n(x) besitzt mindestens eine Wurzel}.

Zeigen Sie: ℤⁿ⁺[x] ist rekursiv aufzählbar.

Ich verstehe leider schon nicht einmal was mit der "Wurzel" gemeint ist, deswegen haben ich hier bisher nichteinmal eine Idee.

Eine Wurzel ist hier eine ganzzahlige Lösung der angegebenen Gleichung, also eine ganzzahlige Nullstelle des Polynoms. Davon gibt es höchstens n, nach der Voraussetzung oben aber mindestens eine.

---

Ah, ok Danke. Vielleicht komme ich damit ja weiter.

Answer 1

für jedes  n ∈ ℕ  bezeichne die Menge aller  n-Tupel  (z₁,...,z_n)  mit  z_i ∈ ℤ  mit  ℤⁿ. Bekanntlich ist  ℤ  abzählbar und damit auch  ℤ² = ℤ × ℤ. Man weist leicht per Induktion nach, dass auch  ℤⁿ  für alle  n ∈ ℕ  abzählbar ist.
Für jedes  n ∈ ℕ  bezeichne die Menge aller Polynome n-ten Grades mit ganzzahligen Koeffizienten mit  P_n. Ein solches Polynom ist durch dessen  n + 1  Koeffizienten eindeutig bestimmt. D.h. es existiert eine Bijektion  P_n → Zⁿ⁺¹. Damit ist  P_n  abzählbar. Die Vereinigung abzählbar vieler abzählbarer Mengen ist bekanntlich abzählbar. Es folgt, dass die Menge aller Polynome über  ℤ  abzählbar ist.