4

I have come across the following notation on a cryptography lecture slide that supposedly defines the modulo function:

$\forall a, n. \exists q, r. a = q \times n + r \text{ where } 0 \leq r < n$

Whilst I have a general idea of what it's doing, I am struggling to understand a few parts of the notation, which I have highlighted in red below:

$\forall a\color{red}{,} n\color{red}{.} \exists q\color{red}{,} r\color{red}{.} a = q \times n + r \text{ where } 0 \leq r < n$

What is the meaning of the commas and dots in this definition? It seems to me the dots are separating statements, so it reads:

For all $a$ and $n$ there exists a $q$ and $a$ for which $a = q \times n + r$ where $0 \leq r < n$.

Is that accurate?

Mauro ALLEGRANZA
  • 94,169
Connor
  • 647
  • 4
    The last $\leq$ should be $<$. The commas and periods are just sloppy. – B. Goddard Jul 28 '22 at 21:46
  • Why do you say they're sloppy? What are they supposed to mean? – Connor Jul 28 '22 at 21:48
  • 2
    The commas and full stops are being used as normal punctuation, there is nothing special going on – FShrike Jul 28 '22 at 21:48
  • @FShrike Okay, what does "$\forall a, n.$" mean then? – Connor Jul 28 '22 at 21:50
  • 1
    "For all $a$ and $n$." It's a stop which indicates where the scope begins. It could also be rendered as $\forall a,n\bigl( \exists q,r(a=qn+r\text{ where }0\leq r\lt n)\bigr)$. – Arturo Magidin Jul 28 '22 at 21:54
  • @ArturoMagidin Okay thank you, is that standard notation? Or is it more common to write: $\left(\forall (a, n)\right) \left(\exists (q, r)\right)[a = qn + r, \text{ where } 0 \leq r < n]$? – Connor Jul 28 '22 at 21:57
  • 2
    It's sloppy because we don't have domains for any of the variables. They mean "for all integers $n$ and $a$...." You have to infer the "and". And assume the variables represent integers. I don't think it's wrong, because it's easy to see what it means. But you're trying to extract more precision out of it than is there. – B. Goddard Jul 28 '22 at 22:00
  • @B.Goddard You mean trying to extract more precision out of it in my own re-definition above? – Connor Jul 28 '22 at 22:01
  • 2
    You seem to want the periods to mean something, and they don't. They could have been commas just as well, or left off and the meaning wouldn't be changed. It's a lecture slide, so they're just saving space. – B. Goddard Jul 28 '22 at 22:04
  • @B.Goddard What makes you think I want them to mean something? Is it good practice to write "for all $a$ and $n$" as "$\forall a, n$"? (Ignoring the fact we haven't defined their domains). – Connor Jul 28 '22 at 22:07
  • Because you asked what their meaning was. – B. Goddard Jul 28 '22 at 22:10
  • @B.Goddard Okay, so not anything to do with my re-definition of his statement above then? – Connor Jul 28 '22 at 22:14
  • What you are calling "statements" are not "statements." The phrase "For all a and n" is just a quantifier. It doesn't need separating. I wouldn't have put a period there. – B. Goddard Jul 28 '22 at 22:20
  • @B.Goddard Okay, so is it general notation to have something like $\forall a, n$ as a quantifier? Is that considered none sloppy and clear notation? The re-definition I'm referring to is this one: $(∀(,))(∃(,))[ = +, \text{ where } 0≤<]$, does it mean the same thing as what he wrote in his slide? – Connor Jul 28 '22 at 22:38
  • 3
    My two cents' worth: this definition should be written out as a grammatical English sentence with words for the quantification and symbols only for the parts that are about arithmetic. – Ethan Bolker Jul 28 '22 at 22:48
  • @Connor This is very likely just a typo, but in your statement of what it means you wrote "For all $a$ and $n$ there exists a $q$ and $\color{red}{a}$ for which $a = q \times n + r$ where $0 \leq r < n$", but I believe the $\color{red}{a}$ should be $r$ instead. Note this is just basically stating the division theorem. – John Omielan Jul 29 '22 at 06:09

2 Answers2

3

Your reading is the intended one. The commas here are being used to avoid repeating quantifier signs: $\forall a, n \cdots$ is being used as a shorthand for $\forall a\forall n \cdots$. The dot is being used to separate the quantifiers from the predicate part of the quantification. $\exists q, r. a = q\times n + r$ means $\exists q \exists r(a = q \times n + r)$. These abbreviations are fairly standard. The notation involving the dot is perhaps more common in computer science than in mathematical logic, but it is consistent with the standard notation in the $\lambda$-calculus.

The combination of symbolism and natural language using the word "where" should be avoided. If you want to be formal write "$\land$" not "where".

Rob Arthan
  • 48,577
2

You are correct in your parsing of the symbols. And @FShrike's comment that there is sloppiness in the punctuation is accurate. The quoted

"∀,.∃,.=×+ where 0≤<"

would have better been written symbolically (if one insists) as

"$\forall a,n, \exists q,r$ such that $a=q\cdot n+r$, where $0\le r<n$"

(And, as HansLundmark commented, it ought not be $r\cdot a=...$, but something else... let's try again! :) I myself was fooled by the punctuation, and was hasty, ...

That is, in this year, in LaTeX, a \cdot is a good multiplication symbol...

And, again, in words, as you already surmised, "for all $a$ and $n$, there are $q$ and $r$ such that ..."

(So, in words, $r$ is the remainder of $a$ after dividing-with-remainder by $n$, and $q$ is the (integer-) quotient.)

PM 2Ring
  • 4,844
paul garrett
  • 52,465
  • So the final dot is actually a multiplication symbol? If so, why has he used a $\times$ directly afterwards? That would be so insanely sloppy -.- . – Connor Jul 28 '22 at 21:59
  • 2
    It shouldn't be $r \cdot a$, just $a$, right? – Hans Lundmark Jul 28 '22 at 22:02
  • 1
    Oop, thanks @HansLundmark... I'll repair it. :) – paul garrett Jul 28 '22 at 22:11
  • 1
    And, yes, switching back and forth between \times and \cdot can confuse one's audience, in any case. – paul garrett Jul 28 '22 at 22:12
  • 1
    I often see a full stop separating a quantifier from a following expression. It seems to be a common practice. What seems irregular here to me is mixing this notation with the word “where.” A conjunction, $\land$, would be more consistent. But better still to write it all in words. – David K Jul 28 '22 at 23:21
  • @DavidK, hm, in my own experience, I've not seen full stops separating a quantifier from an expression... But, indeed, times change! :) – paul garrett Jul 28 '22 at 23:23