Συστήματα Αρίθμησης

Ας δούμε το συνηθισμένο δεκαδικό σύστημα αναπαράστασης των πραγματικών αριθμών και πως αυτό μπορεί να γενικευτεί. Έστω ότι έχουμε έναν αριθμό $b$ που θα είναι η βάση του συστήματός μας και ένα πεπερασμένο σύνολο $D=\{d_1,\ldots,d_k\}$ που είναι τα ψηφία μας. Υποθέτουμε ότι το $0$ είναι ένα από τα ψηφία. Ένας ακέραιος αριθμός, για όλα τα συστήματα, θα έχει την μορφή

$$\sum_{i=0}^{M} a_i b^i$$ (1.23)

όπου $a_i\in D$ είναι ένα από τα ψηφία. Μη ακέραιος θα έχει την μορφή

$$\sum_{i=-\infty}^{-1}a_i b^i$$ (1.24)

όπου $a_i\in D$ είναι κάποιο από τα ψηφία. Η γενική αναπαράσταση του αριθμού θα έχει την μορφή

$$\sum_{i=-\infty}^{M} a_i b^i$$ (1.25)

Για να συγκλίνουν οι αναπαραστάσεις 1.24 και 1.25 θα πρέπει να μπεί ο περιορισμός $\vert b\vert>1$

Το συνηθισμένο δεκαδικό μας σύστημα έχει

$$b=10 \ \hbox{και} \ D=\{0,1,2,3,4,5,6,7,8,9\}$$

Το δυαδικό συστημά αρίθμησης, που τόσο πολύ χρησιμοποιείται στην επιστήμη των Η/Υ, έχει

$$b=2 \ \hbox{και}\ D=\{0,1\}$$

Σ'' αυτές τις δύο περιπτώσεις ο τύπος 1.25 μπορεί να αναπαραστήσει όλους τους αριθμούς που ανήκουν στο $[0,\infty).$

Και στις δύο περιπτώσεις οι αρνητικοί αριθμοί δεν μπορούν να αναπαρασταθούν, για να λύσουμε το πρόβλημα απλά πολλαπλασιάζουμε τις σχέσεις 1.23, 1.24 και 1.25 με το $(-1)$.

Το δεκαδικό και το δυαδικό σύστημα έχουν την ιδιομορφία ότι μερικοί αριθμοί έχουν δύο διαφορετικές αναπαραστάσεις, για παράδειγμα

$$1=0 \cdot 10^0 + \sum_{i=-\infty}^{-1}9\cdot 10^i =1\cdot 10^0 + \sum_{i=-\infty}^{-1} 0\cdot 10^i .$$

Θα εξετάσουμε το τριαδικό σύστημα αρίθμησης. Στο τριαδικό συστήμα έχουμε

$$b=3 \ \hbox{και} \ D=\{0,1,2\}$$

Για παράδειγμα

$$21=0\cdot 3^0 +1\cdot 3^1 +2\cdot ^2$$

θα γράφουμε ότι $21=(210)_3$ όπου ο δείκτης μας λέει πια είναι η βάση του συστήματος (εννοείται ότι στο δεκαδικό σύστημα το παραλείπουμε) και η θέση του ψηφίου δείχνει σε πια δύναμη θα είναι υψώμενη η βάση την οποία και θα πολλαπλασιάσει. Η θέση το ψηφίου μετριέται θετικά προς τα αριστερά από τo κόμμα και αρνητικά προς τα δεξιά.
Παράδειγμα:

$$\begin{eqnarray*} \frac{7}{9}&=&0,777\ldots=(0,21)_3=2\cdot 3^{-1} + 1\cdot 3^{... ...=1\cdot 3^0 +1\cdot 3^{-1}+0\cdot 3^{-2} +2\cdot 3^{-3} +\cdots \end{eqnarray*}$$

Μερικοί αριθμοί στο τριαδικό σύστημα και ειδικά οι αριθμοί τις μορφής $a/3^k$ έχουν δύο διαφορετικές αναπαραστάσεις, για παράδειγμα

$$\frac{1}{3}=(0,1)_3=(0,222\ldots)_3$$

Figure: Το τριαδικό σύνολο Cantor και τα πρώτα βήματα κατασκευής του

Πρόταση 1.8.1   Έστω $x\in [0,1]$. Τότε το $x\in C(1/\lambda )$ (τριαδικό σύνολο Cantor ) αν και μόνο αν η αναπαράσταση του $x$ στο τριαδικό σύστημα αρίθμησης μπορεί να χρησιμοποιήσει μόνο τα ψηφία $0$ και $2$.

Απόδειξη: Στην πρώτη θέση από δεξία (μετά το κόμμα) στην τριαδική αναπαράσταση είναι $1$ αν και μόνο αν το $x$ είναι ανάμεσα από

$$\frac{1}{3}=(0,1)_3 \ \hbox{και}\ \frac{2}{3}=(0,1222\ldots)_3$$

Τώρα το $C_1(1/\lambda )=[0,1/3]\cup[2/3,1]$ οπότε, αφού $C(1/3)\subset C_1(1/3)$, το πρώτο ψηφίο μετά το κόμμα για τα σημεία που ανήκουν στο σύνολο $C(1/3)$ δεν είναι $1$ ( τα σημεία $1/3$ και $2/3$ έχουν δύο αναπαραστάσεις, $1/3=(0,0222\ldots)_3$ και $2/3=(0,2)_3$). Η δεύτερη θέση σε τριαδική αναπαράσταση του σημείου του συνόλου $C_1(1/3)$ είναι $1$ αν και μόνο αν ανήκει στα διαστήματα $(1/9,2/9)$ ή $(7/9,8/9)$. Τώρα

$$C_2\left(\frac{1}{3}\right)=\left[0,\frac{1}{9}\right]\cup\... ...ac{2}{3}, \frac{7}{9}\right]\cup \left[\frac{8}{9},1\right]$$

οπότε τα σημεία του $C(1/3)$ δεν περιέχουν $1$ ούτε στην δεύτερη θέση μετά το κόμμα. Συνεχίζοτας έτσι δείχνουμε ότι ένα σημείο που ανήκει στο $C(1/3)$ μπορεί να αναπαρασταθεί στην τριαδική μορφή χρησιμοποιώντας μόνο τα ψηφία $0$ $2$ και καθόλου $1$. $\Box$

Πρόταση 1.8.2   Το τριαδικό σύνολο Cantor , $C(1/3)$, είναι υπεραριθμήσιμο.

Απόδειξη: Τα στοιχεία του $[0,1]$ στην δυαδική αναπαράσταση είναι της μορφής $x=0,a_1a_2a_3\ldots a_i\ldots$ όπου $a_i\in\{0,1\}$. Ορίζουμε το σύνολο $A$ να περέχει όλα τα σημεία του $[0,1]$ σε δυαδικη μορφή και σύνολο $B$ όλα τα σημεία του συνόλου Cantor , $C(1/3)$ σε τριαδική μορφή, αλλά χωρίς να χρησιμοποιείται το ψηφίο $1$ (από την προηγούμενη πρόταση μπορούμε να το κάνουμε). Δηλαδή αν $y\in B$ τότε το $y=0,b_1b_2b_3\ldots b_i\ldots$ όπου $b_i\in \{0,2\}$.

Ορίζουμε ένα προς ένα και επί την συνάρτηση από το $A$ στο $B$, που στέλνει το $a_i$ στο $0$ αν $a_i$ είναι $0$ και στο $2$ αν το $a_i$ είναι $1$.

Άρα το σύνολο $B$ έχει το ίδιο πληθικό αριθμό στοιχείων με το $A$, δηλαδή το $[0,1]$. Όμως το $[0,1]$ είναι υπεραριθμήσιμο. Άρα το σύνολο $C(1/3)$ είναι υπεραριθμήσιμο. $\Box$