Are there dictionaries in math?

Question

Consider the following dictionary in the programming language Python:

D = {'A': 1, 'B': 2, 'C': 3}

It is saying that the value of A is 1, the value of B is 2, and the value of C is 3. It also has the property that D['A'] = 1 etc.

How would I write such thing in math? I was thinking about

$$D = \{A = 1, B = 2, C = 3\}.$$

However, I am not sure if this is the right or best way to do such thing.

I would like to use the structure for taking sums: e.g. 'AAAA' is interpreted as $1+1+1+1$ etc. What kind of notation should I use?

Answer 1

A dictionary is just a function $\mathrm{Dict}\colon \mathrm{Keys} \rightarrow \mathrm{Values}\cup\{\epsilon\}$ where $\epsilon$ is a "null character" with the understanding that $\epsilon\notin\mathrm{Values}$.

For example, let $\mathrm{Keys}=\{A,B,C,...,Z\}$, and $\mathrm{Values}=\mathbb{Z}$. Then, in your case,

$$ \mathrm{Dict}(x)=\begin{cases} 1 & \text{if }x=A\\ 2 & \text{if }x=B\\ 3 & \text{if }x=C\\ \epsilon & \text{otherwise} \end{cases} $$

Answer 2

Adding to @par 's excellent answer to deal with the second part of the question:

I would like to use the structure for taking sums: e.g. 'AAAA' is interpreted as 1+1+1+1 etc. What kind of notation should I use?

In your case the Keys are characters which you want to think of as Strings that happen to have length 1. The Strings have a natural associative operation - concatenation. (In many languages it's even written with a + sign, although it's not commutative.) The integers come equipped with an associative + too. Then what you want is the assertion that Dict respects those operations: Dict(X+Y) should equal Dict(X)+Dict(Y). There is vocabulary in mathematics for that: Dict is a semigroup homomorphism.

That allows you to extend Dict from the set of one character Strings to the semigroup of all finite Strings.

If that is in fact what you plan to do you should not call your function "Dict". Consider something like "Hash" (since it does assign an integer to a string). Bury the dictionary that gives the value of the hash function on single characters privately inside the definition of a Python object Hash. Then compute Hash.value(s) by looping over the characters in s, looking up their values in the dictionary and adding.

Answer 3

While par's answer is essentially the right response there are still a few subtle issues:

A "dictionary type" is an abstract data type. An instance (basically an element) of that type is literally a function like the one par describes. But the "dictionary type" comes with a bunch of operations that you are allowed to do with its members, for example:

• adding a pair $(k, v)$ to the dictionary
• removing a pair $(k,v)$ from the dictionary
• changing the value $v$ that the key $k$ is mapped to
• finding the value $v$ that the key $k$ is mapped to

and possible more or less (depending on your definition). These operations are part of the definition of an abstract data type. Pure mathematics often does not concern itself directly with computability or how fast something can be computed, but (theoretical) computer science does.

Any abstracted data type may be implemented by numerous different data structures, which differ in the algorithms they use to execute these operations, how the data is stored etc. . None of this (directly) matters for abstract mathematical "function".

Another thing to keep in mind is that members of a type in a programming language are commonly mutable, i.e. they can be "changed over time". This is a feature that we don't normally have in pure mathematics, things do not change over time. There are multiple ways to deal with that: One is insisting that the dictionary has to be immutable and that the operations yield new dictionaries. Another way is thinking of a dictionary as a sequence of functions, where the values of that sequence are certain instances of the dictionary through time.

A more sophisticated method uses a different kind of logic (other than predicate logic) for example temporal logic.

One last issue: I completely ignored any other side effects like exceptions that the Python dictionary may throw. I hear this can be modeled by (computer-scientific) monads.

Answer 4

A standard Python dict corresponds to a function $f\colon K\to U$ in mathematics, where $U$ is the set of all possible Python objects or values of built-in types, and $K$ is a finite subset of $U$. I.e., for some finite set $K$ of keys it associates to each key an arbitrary (Python) value. When trying to evaluate a dict on a value that is not in $K$, a KeyError is raised. This corresponds to the fact that in mathematics you can't ask for the value of $f$ on something that is not a member of $K$.

(Note that in Python, None is a first class object/value unlike null in C or Java. Maybe C++ programmers can think of it as an actual immutable object that is actually located at the memory location specified by the pointer NULL=0. So null is the address of None. I just mention this because the accepted answer by par seems to be confused about this point. It doesn't become clear whether $\epsilon$ is supposed to model None or KeyError. Either way something is wrong or at least confusing.)

For the particular example dictionary D, we can define $f\colon \{A,B,C\} \to U$ by stipulating $f(A)=1$, $f(B)=2$ and $f(C)=3$. The notation AAAA doesn't seem very useful to me except as a shortcut in very specific use cases. In mathematics you would write this as $f(A) + f(A) + f(A) + f(A)$. Of course this only makes sense if $f(A)$ is something for which $+$ is defined.

Answer 5

A dictionary is a partial function from the key space $K$ to the value space $V$, where $K$ is the set of all hashable objects, and $V$ is the set of all Python objects.

A partial function from $K$ to $V$ is a subset of $K\times V$ with the condition that for each $k\in K$ it contains at most one pair that has $k$ as first element. The difference to a function is that a function needs to have exactly one pair with $k$ as first element.

$K\times V$ is the set of pairs $(k,v)$ with $k\in K$ and $v\in V$.