Funcția de cuplu

De la Wikipedia, enciclopedia liberă.

Salt la navigare Salt la căutare

În matematică , funcția pereche este definită ca o funcție care asociază un număr natural cu o corespondență unu la unu fiecărei perechi ordonate de numere naturale ; este deci o aplicație bijectivă $\pi$ ${\ displaystyle \ pi}$ $\ pi$ între setul de produse $\mathbb {N} \times \mathbb {N}$ ${\ displaystyle \ mathbb {N} \ times \ mathbb {N}}$ ${\ displaystyle \ mathbb {N} \ times \ mathbb {N}}$ și mulțimea numerelor naturale $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ :

\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .

{\ displaystyle \ pi: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N}.}

{\ displaystyle \ pi: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N}.}

Se utilizează pentru calcularea cardinalităților

Existența unor astfel de funcții demonstrează că cardinalitatea celor două seturi $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ Și $\mathbb {N} \times \mathbb {N}$ ${\ displaystyle \ mathbb {N} \ times \ mathbb {N}}$ ${\ displaystyle \ mathbb {N} \ times \ mathbb {N}}$ e la fel.

Folosind funcții adecvate pentru a compune în funcția de pereche, este posibil să se demonstreze că și cardinalitatea seturilor de numere întregi $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ și numerele raționale $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ $\ mathbb {Q}$ este egal cu cardinalitatea lui $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ .

Mai mult, compunând o funcție de câteva ori, este posibil să se construiască aplicații biunivoce între orice putere a naturilor $\mathbb {N} ^{k}$ ${\ displaystyle \ mathbb {N} ^ {k}}$ ${\ displaystyle \ mathbb {N} ^ {k}}$ Și $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ . Această tehnică este, de asemenea, utilizată pe scară largă în teoria calculabilității .

Funcția de pereche Cantor

Funcția de cuplu Cantor este o funcție de cuplu definită după cum urmează:

\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.

{\ displaystyle \ pi (k_ {1}, k_ {2}): = {\ frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2}.}

{\ displaystyle \ pi (k_ {1}, k_ {2}): = {\ frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2}.}

Imaginea $\pi (k_{1},k_{2})$ ${\ displaystyle \ pi (k_ {1}, k_ {2})}$ ${\ displaystyle \ pi (k_ {1}, k_ {2})}$ a funcției de cuplu este de obicei indicată cu $\langle k_{1},k_{2}\rangle$ ${\ displaystyle \ langle k_ {1}, k_ {2} \ rangle}$ ${\ displaystyle \ langle k_ {1}, k_ {2} \ rangle}$ .

Această definiție poate fi generalizată pentru a obține funcția tuplor Cantor

\pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N}

{\ displaystyle \ pi ^ {(n)}: \ mathbb {N} ^ {n} \ to \ mathbb {N}}

{\ displaystyle \ pi ^ {(n)}: \ mathbb {N} ^ {n} \ to \ mathbb {N}}

asa de:

\pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})

{\ displaystyle \ pi ^ {(n)} (k_ {1}, \ ldots, k_ {n-1}, k_ {n}): = \ pi (\ pi ^ {(n-1)} (k_ { 1}, \ ldots, k_ {n-1}), k_ {n})}

{\ displaystyle \ pi ^ {(n)} (k_ {1}, \ ldots, k_ {n-1}, k_ {n}): = \ pi (\ pi ^ {(n-1)} (k_ { 1}, \ ldots, k_ {n-1}), k_ {n})}

În calculul enumerării unei funcții calculabile (în informatică teoretică ) se folosește o versiune ușor modificată a funcției de pereche Cantor :

\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}+1.

{\ displaystyle \ pi (k_ {1}, k_ {2}): = {\ frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2} +1.}

{\ displaystyle \ pi (k_ {1}, k_ {2}): = {\ frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2} +1.}

obținută prin enumerarea din la locurile din $1$ ${\ displaystyle 1}$ $1$

Inversia funcției de cuplu Cantor

Să presupunem că z este dat așa cum este definit după cum urmează

z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y

{\ displaystyle z = \ langle x, y \ rangle = {\ frac {(x + y) (x + y + 1)} {2}} + y}

{\ displaystyle z = \ langle x, y \ rangle = {\ frac {(x + y) (x + y + 1)} {2}} + y}

și vrem să găsim x și y . Să definim câteva variabile intermediare:

w=x+y

{\ displaystyle w = x + y}

{\ displaystyle w = x + y}

t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}}

{\ displaystyle t = {\ frac {w (w + 1)} {2}} = {\ frac {w ^ {2} + w} {2}}}

{\ displaystyle t = {\ frac {w (w + 1)} {2}} = {\ frac {w ^ {2} + w} {2}}}

z=t+y

{\ displaystyle z = t + y}

{\ displaystyle z = t + y}

unde t este numărul triunghiular al lui w . Dacă rezolvăm ecuația de gradul doi

w^{2}+w-2t=0

{\ displaystyle w ^ {2} + w-2t = 0}

{\ displaystyle w ^ {2} + w-2t = 0}

pentru w în funcție de t , obținem

w={\frac {{\sqrt {8t+1}}-1}{2}}

{\ displaystyle w = {\ frac {{\ sqrt {8t + 1}} - 1} {2}}}

{\ displaystyle w = {\ frac {{\ sqrt {8t + 1}} - 1} {2}}}

care este o funcție strict crescătoare și întotdeauna definită pentru valorile reale non-negative ale t . Din

t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}

{\ displaystyle t \ leq z = t + y <t + (w + 1) = {\ frac {(w + 1) ^ {2} + (w + 1)} {2}}}

{\ displaystyle t \ leq z = t + y <t + (w + 1) = {\ frac {(w + 1) ^ {2} + (w + 1)} {2}}}

obținem asta

w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1

{\ displaystyle w \ leq {\ frac {{\ sqrt {8z + 1}} - 1} {2}} <w + 1}

{\ displaystyle w \ leq {\ frac {{\ sqrt {8z + 1}} - 1} {2}} <w + 1}

prin urmare

w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor

{\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor}

{\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor}

.

unde ⌊ ⌋ este funcția rotundă în jos.

Acum, pentru a calcula x și y de la z :

la)

w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor

{\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor}

{\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor}

b)

t={\frac {w^{2}+w}{2}}={\frac {w(w+1)}{2}}

{\ displaystyle t = {\ frac {w ^ {2} + w} {2}} = {\ frac {w (w + 1)} {2}}}

{\ displaystyle t = {\ frac {w ^ {2} + w} {2}} = {\ frac {w (w + 1)} {2}}}

y=z-t

{\ displaystyle y = zt}

{\ displaystyle y = z-t}

x=w-y

{\ displaystyle x = wy}

{\ displaystyle x = w-y}

.

Exemplu

Pentru a calcula π ( x , y ) = 1432 = z

Calculăm w cu formula a)

8 × 1432 = 11456,

11456 + 1 = 11457,

√11457 = 107.037,

107.037 - 1 = 106.037,

106.037 ÷ 2 = 53.019,

⌊53.019⌋ = 53,

prin urmare w = 53;

Calculăm t cu formula b)

53 × (53 + 1) = 2862,

2862 ÷ 2 = 1431,

prin urmare t = 1431;

Și, în sfârșit

y=z-t

{\ displaystyle y = zt}

{\ displaystyle y = z-t}

= 1432 - 1431 = 1;

x=w-y

{\ displaystyle x = wy}

{\ displaystyle x = w-y}

= 53 - 1 = 52;

Bibliografie

Ausiello, D'Amore, Gambosi, Limbaje de modelare a complexității

linkuri externe

Perechea funcționează pe site-ul Mathworld , la mathworld.wolfram.com .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

Adus de la „ https://it.wikipedia.org/w/index.php?title=Function_couple&oldid=122122625 ”

Teoria mulțimilor