0
$\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}$.

Improve this question
$\endgroup$
  • 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$ – Mike Earnest Aug 10 '18 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$ – Dark Malthorp Aug 10 '18 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$ – Dark Malthorp Aug 10 '18 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$ – Dark Malthorp Aug 10 '18 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$ – Dark Malthorp Aug 10 '18 at 16:40
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.

Improve this answer
$\endgroup$
  • $\begingroup$ An explanation for the downvote would be welcome. $\endgroup$ – DRF Aug 10 '18 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$ – Carl Mummert Aug 10 '18 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$ – Carl Mummert Aug 10 '18 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 '18 at 15:48
  • 1
    $\begingroup$ @DRF The term you're looking for for "rescoped" is "shadowed". $\endgroup$ – Derek Elkins left SE Aug 11 '18 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.

Improve this answer
$\endgroup$
  • $\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 '18 at 15:39
  • $\begingroup$ I think so, if you want something that has unambiguous parsing rules that could be programmed. $\endgroup$ – Carl Mummert Aug 10 '18 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 '18 at 15:47
1
$\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.

Improve this answer
$\endgroup$
  • 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$ – Eric Wofsey Aug 10 '18 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 '18 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$ – Mike Earnest Aug 10 '18 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$ – Eric Wofsey Aug 10 '18 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$ – Mike Earnest Aug 10 '18 at 17:02

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.