1
$\begingroup$

While reading the paper "On Span Programs" by Karchmer and Wigderson (1993) I have come across the following definition: enter image description here

The highlighted part of the definition contains the following elements that I find confusing:

  1. What is the set represented by $[n]$? Is it the set of all of the natural numbers between 1 (or 0) and N?
  2. What does $\epsilon = 0, 1$ mean? Does this mean that $\epsilon$ can be either 0 or 1? If so, shouldn't it be $\epsilon \in \{0,1\}$?
$\endgroup$
3
$\begingroup$

Yes, for both questions. We have $[n] = \mathbb Z \cap [1,n]$. You’re right that $\epsilon \in \{0,1\}$ is probably better way to write this, but maybe the authors thought it looked clumsy since the notation was already inside a set.

$\endgroup$
1
$\begingroup$

In this context, $[n] := \{1,2,\dots,n\}$.

Here, $\epsilon = 0, 1$ indicates $\epsilon \in \{0,1\}$, but it's been abbreviated to avoid extra curly braces.

By analogy, $x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ indicates $x \in \{\frac{-b + \sqrt{b^2-4ac}}{2a},\frac{-b - \sqrt{b^2-4ac}}{2a}\}$, but it's much neater to write it the first way.

$\endgroup$
1
  • $\begingroup$ I think the best notation would be $x \boldsymbol{\in} \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$. This emphasizes the set of two values, a frequent point of confusion for students. Ah well, you can't really disagree with established convention. $\endgroup$
    – 6005
    Feb 11 '18 at 0:09
0
$\begingroup$

There are alternating views as to whether $[n]$ should refer to $\{1,2,3,\dots,n\}$ or whether $[n]$ should refer to $\{0,1,2,\dots,n-1\}$, similarly to how some people prefer that $\Bbb N$ includes zero while others prefer it does not include zero.

In either case, $[n]$ is the prototypical $n$-element set using the first consecutive $n$ natural numbers. In most scenarios it does not even matter which of the two sets are actually being intended since the point is for the set to be a set with $n$ elements and it doesn't actually matter what those $n$ elements really are and there is an obvious bijection between $\{1,2,3,\dots,n\}$ and $\{0,1,2,\dots,n-1\}$.

$\endgroup$
1
  • $\begingroup$ I agree there could be alternating views and there is of course no "objective" answer, but by far the vast majority of texts I have encountered use $[n]=\{1,2,\dots,n\}$ (i.e. not including $0$). Is that different in your experience? $\endgroup$
    – YiFan
    Jan 31 '19 at 9:21

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.