$XOR$ fonksiyonunun dogal sayilar uzerinde metrik tanimlamasi

Question

Iki dogruluk degeri $x$, $y$ icin  $x \text{ xor } y = 0$ ancak ve ancak $x = y$ ise.

$X,Y  \in \mathbb{N} $ , $x_i , y_i \in \{0,1\} $ icin $X = \sum_{i=0}^{n} x_i 2^i $ , $Y = \sum_{j=0 }^{m} y_j 2^j $ olsun.

$X \text{ xor } Y = \sum_{k=0}^{max(n,m)}(x_k \text{ xor } y_k)2^k$

seklinde tanimlanmis olsun.

$xor : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$

fonksiyonunun bir uzaklik tanimladigini gosterin .

Comments

takıldıgınız yer nedır

---

takildigim bir yer yok aslinda bugun farkettim paylasmak istedim.

Merak ettiklerim, merak sirasiyla;

$(\mathbb{N},\text{xor})$ orneginde oldugu gibi tek bir fonksiyonun hem bir abelyen grup hem de metrik tanimlamasi hosuma gitti, var mi acaba baska ornekleri ?

$[0,1] $ araligindaki rasyonel sayilar icin $\text{xor}$ tanimlanabilir. Bu durumda olusan metrik uzaydaki her cauchy dizisi yakinsar mi ?

Bu uzaya isometrik uzaylar ne? Simetrileri neler? $(\mathbb{N}^n,\text{xor})$ uzayinda dogrular nasil gozukur, yada dogrulardan bahsedebilir miyiz ?

Altinda yatan daha derin cizgesel anlam nedir ? ($[0,n]$ kadar olan sayilari iki tabaninda yazin ikili gruplar halinde birlestirirseniz elinize bir agac gececek.)

---

Ya bu çok tatlı bir soruymuş, ikidir uzun uzun yorum yazıyorum sonra gönderemeden unutuyorum.

---

$x_i\, xor\, y_i=|x_i-y_i|$ (xor için $\LaTeX$ de $\veebar$, $\oplus$ veya$\not\equiv$kullanılıyormuş)

olması işi kolaylaştırıyor.

---

$X=\{f| f: \mathbb{N}\to\{0,1\}\text{hemen hemen her  n için }f(n)=0\}\subset2^{\mathbb{N}}$ olarak düşünelim.

$X$ ile $\mathbb{N}$ arasında şu eşleme var $n\longleftrightarrow f \Leftrightarrow n=\sum_{k=0}^\infty f(k)2^k$

---

Ya da başka bir deyişle grup yapısıyla beraber $$\bigoplus_{i= 1}^\infty \mathbb{Z}/2\mathbb{Z}$$

grubuna izomorf. Ben bu gruptaki toplama işleminin üçgen eşitsizliğini sağladığını bilmiyordum.

---

Yok izomorf değil. Zaten $\mathbb{N}$ grup değil.

($\mathbb{N}$ de toplarken "  elde " oluyor. diğerinde elde yok)

---

(Duzenleme) ben bunu yazana kadar araya yeni seyler eklenmis. Ona gore duzenleme yaptim

Dogan hocam dediginizi anlamadim pek. Daha dogrusu baglantiyi kuramadim. Biraz daha acabilir misiniz ? (esleme yapmaniz)
Ozgur hocam, o kullandiginiz operasyon ne, gruplari nasil topluyoruz? Nedense aklimda vektorleri konkatene etmek gibi bir operasyon geldi, vektor uzaylarini toplayabiliyorduk sanki.

Soyle bir soru geldi aklima bir de $(\mathbb{Z}/2\mathbb{Z},\oplus,\land)$ bir cisim olmali, $(\mathbb{N},\bar{\oplus},\bar{\land})$ ise  $x\bar{\land}y = \sum x_i\land y_i$ seklinde tanimliysa cisim degil.$(\mathbb{N,\bar{\oplus}},\bar{\land})$ i cisim yapan bir $\bar\land$ var mi varsa nasil gorunuyor acaba .

Ben soyle seyler cizdirdim/hesaplattim.

$16$ ya kadar xor tablosu

|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 |
|  1 |  0 |  3 |  2 |  5 |  4 |  7 |  6 |  9 |  8 | 11 | 10 | 13 | 12 | 15 |
|  2 |  3 |  0 |  1 |  6 |  7 |  4 |  5 | 10 | 11 |  8 |  9 | 14 | 15 | 12 |
|  3 |  2 |  1 |  0 |  7 |  6 |  5 |  4 | 11 | 10 |  9 |  8 | 15 | 14 | 13 |
|  4 |  5 |  6 |  7 |  0 |  1 |  2 |  3 | 12 | 13 | 14 | 15 |  8 |  9 | 10 |
|  5 |  4 |  7 |  6 |  1 |  0 |  3 |  2 | 13 | 12 | 15 | 14 |  9 |  8 | 11 |
|  6 |  7 |  4 |  5 |  2 |  3 |  0 |  1 | 14 | 15 | 12 | 13 | 10 | 11 |  8 |
|  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 | 15 | 14 | 13 | 12 | 11 | 10 |  9 |
|  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |
|  9 |  8 | 11 | 10 | 13 | 12 | 15 | 14 |  1 |  0 |  3 |  2 |  5 |  4 |  7 |
| 10 | 11 |  8 |  9 | 14 | 15 | 12 | 13 |  2 |  3 |  0 |  1 |  6 |  7 |  4 |
| 11 | 10 |  9 |  8 | 15 | 14 | 13 | 12 |  3 |  2 |  1 |  0 |  7 |  6 |  5 |
| 12 | 13 | 14 | 15 |  8 |  9 | 10 | 11 |  4 |  5 |  6 |  7 |  0 |  1 |  2 |
| 13 | 12 | 15 | 14 |  9 |  8 | 11 | 10 |  5 |  4 |  7 |  6 |  1 |  0 |  3 |
| 14 | 15 | 12 | 13 | 10 | 11 |  8 |  9 |  6 |  7 |  4 |  5 |  2 |  3 |  0 |

 

Burada $1024$ e kadar olan sayilarin $xor$ tablosu var

Hazir bunu yapmisken aynisini $\bar{\land}$ ve $\bar{\lor}$ icin de yaptim.

once $\land$

Sonra da $\lor$ icin

Bir de animasyonlar yaptim $f(x,y)==r$ ve $f(x,y)<=r$ bagintilarinda $r$ yi degistirrerek (burada $f$ sirasiyla $\bar{\oplus} , \bar{\land} , \bar{\lor}$)

Bunlar disinda sunu farkettim ki bu uzayda cemberler sadece tek bir noktadan ibaret!

$P$ noktasi ile $Q$ noktasi arasindaki uzaklik $d$ ise, $P$ ile baska herhangi bir noktanin arasindaki uzaklik $d$ olamaz. Bunun uzerine $p$ noktasindaki birim cemberleri ve toplari hesaplatmaya karar verdim. Zaten yukarida $n=16$ ya kadar hesaplamistik. Tabloda $k$  satirinin $l$ sutunu bize. $k$ daki $l$ yaricapli cemberi verecek. Dikkat edin tablonun her satiri farkli, sanki her dogal sayi bu metrik altinda dunyayi bambaska goruyor.

Soruyla ugrasirken soyle seyler de farkettim:

$ x \bar\oplus y \leq x \bar\lor y \leq x+y $ (Ucgen esitsizligini bunu kullanarak kanitladim, bu bagintiyi da tumevarimla kanitladim)

$x \bar\land y \leq min(x,y) $

Bunlari henuz kanitlamadim ama sanirim dogrular

$ (x \bar\land y) + (x \bar\lor y) = x+y $

$ 2(x \bar\lor y) - (x \bar\oplus y) = x+y $

Soyle cizgesel bir sey de dusundum. Asagidaki agacta $k$ yapragindan, $n$ yapragina gecmem icin cikmam gereken kat sayisi neredeyse $k \oplus n$

 

 

---

Dogan hocam $(\mathbb{N},\bar\oplus)$ abelyen bir grup degil mi ?

Bu biraz alakasiz olacak galiba ama

$(\mathbb{Z}/2\mathbb{Z},\oplus,\land) $ bir cisim. Cisimler uzerine vektor uzayi kurabiliriz.

$b=\{b_i\}_{i=0}^{\infty} , b_i\in\mathbb{Z}/2\mathbb{Z}$ serilerinin hepsi bir sure sonra $0$ olsun. Bu seriler bir vektor uzayi kuruyor.

acaba bu uzay $\mathbb{N}$ mi ?

oyleyse bu metrik ($\bar\oplus$) sanirim homojen.

bir uzay homojendir eger her skalar $s$ ve her vektor $x,y$ icin  $d(sx,sy)=|s|d(x,y)$ saglaniyorsa.

$s\in[0,1]$ oldugu icin $\bar\oplus$ un bunu sagladigini gormek kolay.

sanirim bu uzay ayni zamanda translasyon invariant. yani

$d(x+s,y+s) = d(x,y)$

tabi burada $+$ vektor uzayinin "+" yani  $\bar\oplus$.

bu durumda $\|\cdot\|=\cdot\bar\oplus 0$ bu vektor uzayinda bir norm tanimlar. Bu norm bir ic carpimdan geliyor olabilir mi ? Bu normlu uzay tam mi ?

(Duzenleme)

Sanirim bir ic carpma tanimladim. (uyuyup yarin devam edecegim galiba :) )

$\langle x,y\rangle = (x\bar\land(\bar\lnot x \bar\oplus y) + (y\bar\land(\bar\lnot x \bar\oplus y) $

---

@DoganDonmez işlem coordinatewise tanımlanmış, elde olmuyor. Doğal sayılar bu işlem altında bir grup veriyor cidden.

@eloi Kullandığım işlem direkt toplam. $(Z/2Z)^\infty$ gibi düşün ama bir yerden sonra bütün koordinatlar sıfır olmak zorunda. Direkt toplam ve direkt çarpım arasındaki fark bu.

Ben doğal sayıları sola doğru sonsuza uzanan 01-dizileri şeklinde yazdım bu soruyla uğraşırken. Senin yorumunda dediğin gibi.

Dolayısıyla 0,1,2,3,4,5... dizisi 0, 1, 10, 11, 100, 101 gibi gidiyor. Sola doğru sonsuz adet sıfır var ama onları yazmıyorum. Bir de yazımı kolay olsun diye işlemi $*$ ile gösterdim. Buradan her n için $n*n = 0$ olduğu kolayca görünüyor mesela. Iki sayıyı çarparken (ya da toplarken? Bu işleme ne diyeyim bilemedim), aynı koordinatlar sıfır veriyor, koordinatlar farklıysa o koordinata 1 geliyor. Üçgen eşitsizliğine bu açıdan bakmak güzel: $a*b \leq a*c + b*c$ çünkü a ile b'nin k'ıncı koordinatları aynıysa zaten katkısı sıfır, a ile b'nin k'ıncı koordinatları farklıysa c'nin k'ıncı koordinatı a'nın ya da b'nin k'ıncı koordinatından farklı olmak zorunda.

Ilgimi çeken başka bir şey altkumeler arası uzaklık. Ama onu sonra yazayım.

---

@Ozgur, elbette "bu işlem" ile grup oluyor, ben normal toplama işlemi ile grup olmadığını kastediyorum, o nedenle izomorfizm demenin uygun olmadığını düşünüyorum.

---

Ah, tamam. Kusura bakmayın.

---

Hiç önemli değil. Senin yorumların herkes için yararlı oluyor.

---

Ben soyle bir sey daha cizdim

Burada $n\in[1,4]$  yaricapli cemberleri goruyoruz, cap uzunluklarina gore renklendirdim.

---

Nimber diye bir konsept ile karsilastim arastirirken. Benziyor galiba biraz. Carpma islemi de tanimlanmis.

Answer 1

Üçgen eşitsizliği dışındakiler aşikâr.
$x,y,z\in\mathbb{N}$ olsun.

$x=\sum_{i=0}^n x_i 2^i,\  y=\sum_{i=0}^n y_i 2^i,\  z=\sum_{i=0}^n z_i 2^i$
($x_i,y_i,z_i\in\{0,1\}$)
 şeklinde yazalım.
 
 Her $i$ için $|x_i-z_i|\leq|x_i-y_i|+|y_i-z_i|$ olduğundan,
 
  $|x_i-z_i|2^i\leq|x_i-y_i|2^i+|y_i-z_i|2^i  $ ve  
  $\begin{align*}\sum_{k=0}^n|x_i-z_i|2^i&\leq \sum_{k=0}^n\left( |x_i-y_i|2^i+|y_i-z_i|2^i\right) \\&=\sum_{k=0}^n |x_i-y_i|2^i+\sum_{k=0}^n|y_i-z_i|2^i\end{align*}$

olur.   Sol taraf $d(x,y)$ ye, sağ taraf da $d(x,y)+d(y,z)$ olduğundan
  $ d(x,y)\leq d(x,y)+d(y,z) $ olduğu gösterilmiş olur.

Comments

Bu tanımdaki $2^i$ nin bir önemi yok, herhangi bir pozitif sayı için de aynı durum olur.

Özel olarak hepsini 1 alınca ($\sum x_i xor y_i$) "Hamming distance" oluyor.