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?

  • For your own benefit, I will mention that the notation $\{A=1,B=2,C=3\}$ does not have any meaning (unless you assign it one). You could, very well, assign it a meaning (for example, using my definition below). – parsiad Jul 26 '16 at 14:15
  • Thanks, I think your notation is very good. If I had two dictionaries, I could do it like $\mathrm{f}:\mathrm{Keys} \rightarrow \mathrm{Values}, \mathrm{f}(x) = \dots$ and the same for some $g$? And first define e.g. $\mathrm{Keys} = \{A, B, C\}$ and $\mathrm{Values} = \{1, 2, 3\}$ (not forgetting the $\epsilon$)? – user356363 Jul 26 '16 at 14:18
  • Your arrow is pointing backwards, but yes. Also, don't forget $\epsilon$ (a key property of a dictionary is that it does not have to map all of its inputs to outputs, which corresponds to mapping some inputs to $\epsilon$). – parsiad Jul 26 '16 at 14:19
  • 2
    A python dictionary is just exactly a function in math. So you'd write it as $D(A)=1$, $D(B)=2$, $D(C)=3$. Then $D(A)+D(A)+D(A)+D(A)=4D(A)=4$. Etc... – Gregory Grant Jul 26 '16 at 16:18
  • I had a professor in college say that a function is just a table. If x is this, f(x) is this. It's just that some functions are given a closed form to save paper. – Devsman Jul 27 '16 at 15:07
up vote 101 down vote accepted

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} $$

  • 37
    With a computer science background, came here thinking "haha, finally! CS != Math" left here thinking "Math is so cool!" – utahwithak Jul 26 '16 at 15:28
  • 12
    Actually, this answer is correct for dictionary/map implementations in some programming languages (e.g. for HashMap in Java), but not for the standard dict in Python. In Python, when you evaluate a dict for something that is not a key, you don't get None but a KeyError. In Python terms, this answer describes a defaultdict(lambda: None). – Hans Adler Jul 26 '16 at 17:12
  • 11
    @HansAdler If there is "no set of values" in Python then let it be the set of all literals in Python. That's an ordinary set. - A partial function $f : A \to B$ "is" the same thing as a function $f : A \to B + \{\epsilon\}$, where you map everything without value to $\epsilon$ (this statement can be made really precise in category theory). – Stefan Perko Jul 26 '16 at 17:48
  • 4
    @StefanPerko: There are several possible POVs, but in any case the epsilon in this answer has no business being mentioned at all. The set Keys is clearly meant to serve as the domain of the function because otherwise it would make no sense to mention it in the first place. Equivalently, it's meant to represent the Python set keys(D). For every element of keys(D) you get a value. This value may be None, but since None is a first-class value in Python - the singleton of type NoneType - it really needn't be singled out here. – Hans Adler Jul 26 '16 at 18:00
  • 5
    @HansAdler: there is no difference between a KeyError and an $\epsilon$ other than interpretation; seconding StefanPerko's comment. – parsiad Jul 26 '16 at 19:11

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.

  • "... function $f\colon K\to U$ in mathematics, where $U$ is the set ... " My first thought exactly. Nice write up! (+1) – Jeel Shah Jul 28 '16 at 2:42
  • Note that $K$ is more specifically a subset of all hashable Python objects/values. – Arman Jul 28 '16 at 12:32

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.

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.

  • Mathematics certainly is concerned with computability. – Miles Rout Jul 30 '16 at 1:00

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$.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.