3
$\begingroup$

I know two common variants of set abstraction notation. An examples of the first variant is $$ \{\,(x, y)\in\mathbf{R}^2\,|\,x^2 + y^2 = 1\,\} $$ (it is reminiscent of the axiom schema of specification of ZF), and an example of the second is $$ \{\,(\cos t,\sin t)\,|\,t\in\mathbf{R}\,\} $$ (it is reminiscent of the axiom schema of replacement of ZF). I think that in common mathematical tradition, these two "set-builder" expressions unambiguously denote the same set.

The first form of the notation can always be used instead of the second, for example: $$ \{\,(\cos t,\sin t)\,|\,t\in\mathbf{R}\,\} = \{\,(x, y)\in\mathbf{R}^2\,|\,(\exists t\in\mathbf{R})(x =\cos t\wedge y =\sin t)\,\}. $$ However, the "translated" expression is noticeably more verbose.

Sometimes the two are combined: $$ \{\,(\cos t,\sin t)\,|\,t\in\mathbf{R}\wedge 0 < t <\pi\,\}, $$ or simply $$ \{\,(\cos t,\sin t)\,|\,0 < t <\pi\,\}. $$

The first form can be translated into the combined form without much "overhead": $$ \{\,(x, y)\in\mathbf{R}^2\,|\,x^2 + y^2 = 1\,\} = \{\,(x, y)\,|\,x^2 + y^2 = 1\wedge (x, y)\in\mathbf{R}^2\,\}. $$ The second form is just a particular case of this combined form.

In practice, the combined form of "set-builder" notation is quite convenient, but it appears to be ambiguous, unless some artificial syntactic conventions are made. For example, what set $S$ is defined in the following sentence?

Let $p = 1$ and $S = \{\,(p + q, p - q)\,|\,pq = 1\wedge p\in\mathbf{R}\wedge q\in\mathbf{R}\wedge 1 < 2\,\}$.

I see two equally legitimate values for $S$ so defined:

  1. $S =\{(2, 0)\}$ or

  2. $S =\{\,(x, y)\in\mathbf{R}^2\,|\,x^2 - y^2 = 4\,\}$.

Once you think of it, there is also a possibility for $S$ to be empty, if both $p$ and $q$ are viewed as parameters and if the value of $q$ happens to be different from $1$.

Does there exist an unambiguous form of the combined variant of "set-builder" notation?

In general, I do not see how to specify in an expression like $$ \{\,\{\,f(\bar a,\bar b,\bar c)\,|\,\Phi(\bar a,\bar b,\bar c)\,\}\,|\,\Psi(\bar a,\bar b,\bar c)\,\} $$ that, for example, $\bar c$ are parameters, and $\bar b$ are parameters in the inner "set-builder" but not in the outer one. (Note that though all the variables are listed in parentheses each time, it does not mean that all of them are "used": $f$, $\Phi$ and $\Psi$ may very well not depend on some of these "formal parameters.")

For reference, here is how some programming languages deal with a similar issue in list comprehension. More precisely, in programming languages there is no issue, because iterating over a collection and testing a predicate are two different operations in programming, while they are indistinguishable in mathematics.

In Haskell,

[ (m, n) | m <- [0..5], 0 <= n, n <= 5, m^2 + n^2 == 25 ]

is the list of all pairs $(m, n)$, where $m$ is an integer from $0$ to $5$, $0\le n\le 5$, and $m^2 + n^2 = 25$. Note that this very sentence in English is ambiguous! The above expression in Haskell is only valid if $n$ is defined. The value of this expression is [(3,4)] if the value of $n$ is 4, but it is [] (the empty list) if the value of $n$ is 2, for example.

A similar definition in Python will be:

[ (m, n) for m in range(0, 6) if 0 <= n and n <= 5 and m**2 + n**2 == 25 ]

However, the analogous "set-builder" notation $$ \{\,(m, n)\,|\,m\in\{0,\dotsc,5\}\wedge 0\le n\le 5 \wedge m^2 + n^2 = 25\,\} $$ is ambiguous (are "$m$" and "$n$" parameters or bound variables of this expression?).

Here is another example of an ambiguous situation: $$ \{\,\{\,x\,|\,x\in\mathbf{Z}\}\,|\,x\in\mathbf{R}\,\}. $$

For my personal needs, I start considering using my own notation $\{\ldots|\ldots|\ldots\}$ with bound variables listed in the middle, with the following formal "translation": $$ S =\{\,f(\bar x, \bar y)\,|\,\bar x\,|\,\Phi(\bar x, \bar y)\,\}\\ \equiv (\forall\xi)(\xi\in S\Leftrightarrow(\exists\bar x)(\xi = f(\bar x, \bar y)\wedge\Phi(\bar x, \bar y))), $$ where the new variable $\xi$ is distinct from all variables in $\bar x$ and $\bar y$. For example: $$ A =\{\,(\cos t,\sin t)\,|\,t\,|\,t\in\mathbf{R}\,\},\\ B =\{\,(x, y)\,|\,x, y\,|\,x^2 + y^2 = 1\wedge (x, y)\in\mathbf{R}^2\,\},\\ C =\{\,(m, n)\,|\,m\,|\,m\in\{0,\dotsc,5\}\wedge 0\le n\le 5 \wedge m^2 + n^2 = 25\,\},\\ D =\{\,\{\,f(\bar a,\bar b,\bar c)\,|\,\bar a\,|\,\Phi(\bar a,\bar b,\bar c)\,\}\,|\,\bar a,\bar b\,|\,\Psi(\bar a,\bar b,\bar c)\,\},\\ E =\{\,\{\,x\,|\,|\,x\in\mathbf{Z}\,\}\,|\,x\,|\,x\in\mathbf{R}\,\}\quad (=\{\,\{x\}\,|\,x\,|\,x\in\mathbf{Z}\,\}\cup\{\{\}\}), $$ or, alternatively, with words instead of symbols: $$ A =\{\,(\cos t,\sin t)\ \text{for}\ t\ \text{such that}\ t\in\mathbf{R}\,\}. $$ Isn't there some kind of a standard alternative?

It seems that the Z notation might be an example of what I am looking for, but at a first glance it looks incompatible with the usual mathematical "set-builder" syntax, and I wonder how standard it is.


Some comments and answers suggest to never use the same variable name for different variables, at least when their scopes are nested, thus avoiding variable shadowing altogether. IMO, such a restriction is unusual (surely uncommon in programming or formal languages), unnecessary, not easy to observe, and it would require explicit introduction of all parameters (consider omitting "Let $p = 1$" in my example above while still using "$p$" as a parameter).

Quoting the HoTT Book (page 23),

Of course, this should all be familiar to any mathematician: it is the same phenomenon as the fact that if $f(x):\equiv\int_1^2\frac{dt}{x - t}$, then $f(t)$ is not $\int_1^2\frac{dt}{t - t}$, but rather $\int_1^2\frac{ds}{t - s}$.

$\endgroup$
26
  • 2
    $\begingroup$ How do you interpret $S$ as anything but $\{(2,0)\}$? Since $p=1$, you can rewrite $S$ as $\{(1+q,1-q)\mid q=1,q\in \mathbb R,1<2\}$ (also, what is the point of the "$1<2$"?), so the only possible value of $q$ is $1$. $\endgroup$ Aug 10, 2018 at 14:04
  • 2
    $\begingroup$ In short if $p = 1$, then you don't need the qualification $p \in \mathbb{R}$, so including that adds ambiguity because it is either redundant or a re-definition of $p$ but it is not totally clear which. $\endgroup$ Aug 10, 2018 at 15:46
  • 2
    $\begingroup$ I treated $p$ as a constant because you defined it as a constant in the same sentence. The point is, you have to be careful with notation otherwise things can become ambiguous because of overloading. If it's not clear whether or not $t$ was already defined previously, you might include a statement after defining $\{(\cos t, \sin t) | t \in \mathbb{R}\}$, saying something like "recall we defined $t$ as..." $\endgroup$ Aug 10, 2018 at 16:14
  • 2
    $\begingroup$ But if $t$ is a constant, for the sake of clarity, you shouldn't put in the unnecessary predicate $t \in \mathbb{R}$. The notation is unambiguous, but may be unclear to the reader because sometimes (though it is bad practice) people use the same letters to mean different things $\endgroup$ Aug 10, 2018 at 16:17
  • 2
    $\begingroup$ I guess what I'm trying to say is, if you write $| p \in \mathbb{R}$ it's unclear if you're being sloppy by refining $p$ without explicitly saying so or if you're being confusing by adding in redundant information. $\endgroup$ Aug 10, 2018 at 16:40

4 Answers 4

4
$\begingroup$

As I tried to point out in the comments there is no other notation in use, because the notations we have aren't really particularly ambiguous. The example you make would be parsed by pretty much everyone as $S=\{(2,0)\}$ unless the rest of the paper makes this untenable.

There is a simple reason for that and that is that it's very bad form to rescope variables in math. By rescope here I mean we don't write $\forall x\exists y\forall x\cdots$. This is actually well defined as I tried to point out by the example of $\forall x(\exists y(\forall x (x\geq y)\wedge (xy=y)))$. This means the same as $\forall x\exists y\forall z (z\geq y)\wedge (xy=y)$ which is something that's true for natural numbers with 0.

It is very hard to read things like that though and very bad form to write them. Which means that in a given theorem, lemma, etc. the scope of variable and constant names is obvious and they are not reused in strange ways. The ambiguity thus doesn't really arise.

$\endgroup$
11
  • $\begingroup$ An explanation for the downvote would be welcome. $\endgroup$
    – DRF
    Aug 10, 2018 at 15:17
  • 4
    $\begingroup$ I think that "don't use the same variable for two things at the same time" is a key point that most mathematicians learn by example, although it is not explicitly discussed very often. When people learn formal logic, they are sometimes surprised to find out that nested quantifiers can use the same variable, for example. $\endgroup$ Aug 10, 2018 at 15:39
  • 1
    $\begingroup$ @Alexey: I would say that is not using the same variable for two things at the same time, just using it for two things at different times. Inside a single proof, it would be somewhat unusual to use $p$ as both a number and a path, even if technically everything is sound. $\endgroup$ Aug 10, 2018 at 15:47
  • 1
    $\begingroup$ @CarlMummert, "that is not using the same variable for two things at the same time, just using it for two things at different times" -- just like it is with nested quantifiers: one time (under the inner quantifier scope) i use the variable for one thing, the other time (outside the inner scope) i use it for other things. $\endgroup$
    – Alexey
    Aug 10, 2018 at 15:48
  • 1
    $\begingroup$ @DRF The term you're looking for for "rescoped" is "shadowed". $\endgroup$ Aug 11, 2018 at 18:49
3
$\begingroup$

An interesting point about set-builder notation is that it is used as part of informal set theory. Formal set theories such as ZFC do not include set-builder notation, and instead use the comprehension scheme which defines a set using a formula of set theory. Set builder notation is, in some sense, just an abbreviation for the comprehension scheme. It's not meant to be a formal language or a programming language, just a way to convey the definition of a set to another mathematician.

This means that set-builder notation is more of a "natural language" than a formal language. Issues such a free vs. bound variables, or variables vs. parameters, are handled by convention, just like many other issues in ordinary mathematics. So, just as in other areas of ordinary mathematics, it is possible to write vague definitions, or definitions that can be read in multiple ways. Mathematicians avoid that hazard in natural language all the time, not only with set builder notation.

$\endgroup$
3
  • $\begingroup$ I understand your answer as "there is not standard unambiguous notation of this kind". Then I am left with having to invent my own one, I am afraid... $\endgroup$
    – Alexey
    Aug 10, 2018 at 15:39
  • $\begingroup$ I think so, if you want something that has unambiguous parsing rules that could be programmed. $\endgroup$ Aug 10, 2018 at 15:45
  • $\begingroup$ I do not intend to program them yet, i just need to be able to read back what i wrote. $\endgroup$
    – Alexey
    Aug 10, 2018 at 15:47
3
$\begingroup$

Here is my summary of the two notations at play here. \begin{array}{} \{x\in S\mid\psi(x,t_1,t_2,\dots,t_n)\} & & \text{The subset of $S$ satisfying property $\psi$}\\ \{f(x,t_1,\dots,t_n)\mid x\in S\} & & \text{The image of $S$ under $f$} \end{array} In both examples, the $t_i$ are variables which could be defined elsewhere, and every definition gives rise to a different set. However, the variable $x$ plays a special role; it is used as a placeholder to specify a generic element of $S$.

The above two notations are unambiguous. The ambiguity comes when we mix the two notations. $$ \{f(x,t_1,\dots,t_n)\mid x\in S,\psi(x,s_1,\dots,s_m)\}\qquad \text{The image of the subset of $S$ satisfying $\psi$ under $f$.} $$ The problem is that the statement $\psi$ might contain a clause like "$t_i\in T$," so it makes $t_i$ look like the "special" placeholder variable, and it is unclear whether $x$ or $t_i$ or both is supposed to fulfill this role. Your example was $$ \{f(p,q)\mid p\in \mathbb R,q\in \mathbb R,pq=1,1<2\} $$ where $f(p,q)=(p+q,p-q)$. Here, it is unclear whether $p$ and $q$ are both supposed to range freely over $\mathbb{R}$, or $p$ is supposed to be a fixed value while $q$ ranges over $\mathbb R$, or vice versa.

There is a simple way to avoid this ambiguity:

Assume that any variable $x$ which appears on both sides of the divider $\mid$, and which appears on the right side in the form of a clause $x\in S$ for some set $S$, is intended only to be interpreted of the context of this notation as a variable freely ranging over $S$.

Under this rule, the set $S$ you asked about would mean the second interpretation. I realize this is the opposite of what I strongly said in my comment, but I think there is enough precedent in math for having "locally" bound variables which do not interfere with other instances. For example, you could write "$i=5$ and $n=\sum_{i=1}^{5} i$", and most people would agree that $n=15$, that is, $i$ is not equal to $5$ at each point in the summation.

$\endgroup$
10
  • 1
    $\begingroup$ This is not the issue. $\{f(p,q)\mid p\in \mathbb R,q\in \mathbb R,pq=1,1<2\}$ is totally unambiguous in isolation, and only becomes ambiguous when written in a context where $p$ has been given an external definition. $\endgroup$ Aug 10, 2018 at 16:12
  • $\begingroup$ @EricWofsey, "becomes ambiguous when written in a context where ..." means ambiguous IMO, because the "complete context" can be usually viewed as unknown. (Think of a lecturer who said at the first lecture that in the course $p$ will mean $42$, and of a student who comes later and sees $\{(p, q)|0\le p + q\le100\}$.) $\endgroup$
    – Alexey
    Aug 10, 2018 at 16:18
  • $\begingroup$ @EricWofsey I would argue $S=\{f(p,q)\mid p\in \mathbb R,q\in \mathbb R\}$ is ambiguous even without an external definition of $p$. Do you mean the image of $f$ applied to all of $\mathbb R^2$, or do you mean the image of $f$ applied to the vertical line $\{(p,q)\mid q\in \mathbb R\}$, where $p$ is some value to be determined later? In the latter case, the contents of $S$ would be a function of $p$. $\endgroup$ Aug 10, 2018 at 16:24
  • 2
    $\begingroup$ So, the confusion in OP's example really comes from the fact that whichever way you interpret it, they must be violating some rule of mathematical writing: either they are using a variable with two different meanings at the same time, or they are including a strangely redundant condition. I agree with your ultimate diagnosis that the first violation is less serious (as in your example with the summation) and so the second interpretation is "correct", but really the correct answer is to just not write such a thing at all. $\endgroup$ Aug 10, 2018 at 16:58
  • 2
    $\begingroup$ @EricWofsey I agree with your points about how ambiguity would not arise if you write well. These are strange corner cases that would only arise if a machine was trying to interpret human written math for some strange reason. $\endgroup$ Aug 10, 2018 at 17:02
1
$\begingroup$

You can avoid the ambiguity in standard set-builder notation by falling back to "single-variable comprehension" whenever the LHS contains variables that are not bound in the set-builder expression. The downside is that the paraphrase in the presence of free variables makes the expression longer and requires some explicit existential quantifiers.

First, note that using a single variable as the term to the left of the bar can express every set comprehension. For example $\{ z \mathop| \exists x \exists y \mathop. z = (x, y) \land (x, y) \in \mathbb{R}^2 \land x^2 + y^2 = 1 \}$ instead of $\{ (x, y) \in \mathbb{R}^2 \mathop| x^2 + y^2 = 1 \}$. You can explicitly say that when you use this notation that variable appearing in $z$'s position is always bound and never free.

This fallback option is not convenient, but it lets you reserve the abbreviated version for cases where all variable symbols in the term to the left of the bar are bound.

For example, in $\{ (p+q, p-q) \mathop| pq=1 \land p \in \mathbb{R} \land q \in \mathbb{R} \}$, both $p$ and $q$ would unambiguously be bound.

To make $p$ free, you would use $\{ z \mathop| \exists q \mathop. z = (p, q) \land p \in \mathbb{R} \land q \in \mathbb{R}\} $.

I think this convention is simple and standard enough that it could be used in writing without explaining it, which would not be true for a variant of the comprehension notation with an explicit way of annotating bound variables.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .