1
$\begingroup$

I apologize in advance for the Python code below. I don't know how to express this question unambiguously in the language of math.

Let $\mathcal{F}$ be a family of sets. It seems to me that

$$S(x) = \{ g(A,x) : x \in A \in \mathcal{F} \}$$

is ambiguous. I see two interpretations:

1.

def S(x):
    s = set()
    for A in F:
        for x in A:
            s.add(g(A,x))
    return s

2.

def S(x):
    s = set()
    for A in F:
        if x in A:
            s.add(g(A,x))
    return s

Is one of these correct? If so, which? If not, how should it be interpreted?

$\endgroup$
1
$\begingroup$

Yes, this notation is ambiguous, but in this case the second (if) interpretation is very likely intended.

The problem is that it is not clear which variables are 'dummies' (local variables in Python etc.): both $\;A\;$ and $\;x\;$, or just $\;A\;$? A notation invented by Dijkstra-Scholten (see also EWD1300 and Gries-Schneider) makes the dummies explicit: the first interpretation then is $$ S(x) = \{A,x : x \in A \in \mathcal F : g(A,x)\} $$ and the second $$ S(x) = \{A : x \in A \in \mathcal F : g(A,x)\} $$ For example, the last set builder expression can be read as "the set which, for all $\;A\;$ such that $\;x \in A \in \mathcal F\;$, contains $\;g(A,x)\;$".

The first interpretation would mean that the 'external parameter' ('outer') $\;x\;$ is ignored, and the set builder dummy $\;x\;$ 'shadows' the outer $\;x\;$. However, both ignoring parameters and 'shadowing' of dummies / local variables is uncommon in mathematical notation.

Therefore the second interpretation seems to be the intended one.

In general, there are also examples where there is real ambiguity, such as $\;\{x^y \mid x < y\}\;$: what are the dummy variables? That is the reason why I prefer the Dijkstra-Scholten-Gries-Schneider notation, and personally always make sure that the dummies are explicit in set builder notation.

The leading principle I learned from Dijkstra is that it is the writer's responsibility to make sure the readers don't all have to do the same disambiguation and reverse engineering work in trying to understand the writer's intentions. (For a case study from a reader's perspective, see Dijkstra's EWD1200.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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