Sei ´(p_i)_(i in N)´ eine Folge, die alle Primzahlen injektiv aufzählt. Du kannst nun für jedes ´k in NN´ jedes beliebige Tupel ´bar(a) = (a_1, …, a_k) in NN^k´ wie folgt auf eine natürliche Zahl abbilden:

´bar(a) |-> p_1^(a_1) * p_2^(a_2) * … * p_(k-1)^(a_(k-1)) * p_k^(a_(k+1))´

Diese Abbildung von ´NN^(**) := uu_(k in N) NN^k´ nach ´NN^+´ soll ´f´ heißen. Außerdem werde das leere Tupel ´epsilon in NN^0´ auf ´1´ abgebildet. Zeige dass für ´f : NN^(**) -> NN^+´

  • ´f´ injektiv ist
  • ´f´ surjektiv ist
Hint 1
Um die Aufgabe besser zu verstehen, legen Sie sich ´p_1´ bis ´p_5´ fest und bilden Sie 0 bis 5-Tupel mittels ´f´ auf natürliche Zahlen ab. So erkennen Sie, warum der letzte Exponent als einziger ´a_k + 1´ heißt.

Solution

  • Teil 1

    Zu zeigen: ´f(a) = f(b) => a = b´

    Sei ´f(a), f(b), k in NN´ ´f(a) = f(b)´ ´EE bar(a) = (a_1, …, a_k), bar(b) = (b_1, …, b_k) in NN^k :´ ´p_1^(a_1) * p_2^(a_2) * … * p_(k-1)^(a_(k-1)) * p_k^(a_(k+1)) =´ ´p_1^(b_1) * p_2^(b_2) * … * p_(k-1)^(b_(k-1)) * p_k^(b_(k+1))´ (Definition der Funktion) ´=> bar(a) = bar(b)´

    Teil 2

    Zu zeigen: ´f(A) = NN´ ´NN sube f(A)´ Sei ´b, k in NN´ ´=> EE bar(a) in NN^k : f(bar(a)) = b´ (Definition: Für jede Zahl existiert eine Primfaktorzerlegung)

    ´f(A) sube NN´ folgt aus der Funktion ´=> f´ ist surjektiv ´q.e.d´

  • URL:
  • Language:
  • Subjects: math
  • Type: Proof
  • Duration: 45min
  • Credits: 4
  • Difficulty: 0.7
  • Tags: primes
  • Note:
    HPI, Mathematik I - Diskrete Strukturen und Logik, Wintersemester 2012/2013
  • Created By: adius
  • Created At:
    2013-04-12 16:49:14 UTC
  • Last Modified:
    2014-07-20 21:34:38 UTC