Gitterpunkte

Aus ProgrammingWiki

Archivierte Version vom 2016-06-22T09:13:42+00:00. Aktuelle Version

Aufzählbarkeit der Menge der Gitterpunkte

Die Menge G der Gitterpunkte (0,0),(0,1), ... eine x-y-Ebene ist aufzählbar.

1. Geben Sie eine Funktion f an, die \NN bijektiv auf G abbildet.

Cantorsche Paarungsfunktion, s. auch Wikipedia

var f = function (z) {
    var w = Math.floor((Math.sqrt(8*z+1)-1)/2);
    var t = w*(w+1)/2;
    var y = z-t;
    var x = w-y;
    return [x,y];
}

Da f eine bijektive und total berechenbare Funktion ist, kann man die Menge G aufzählen:

for (z=0; z<10; z++) {
    console.log(f(z));
}

2. Definieren Sie eine Ordnungsrelation p_< in G.