Lesson 1

We have encountered statements containing the words “there exists” or “for every” multiple times. In mathematics, they are called quantifiers and are denoted by the symbols \(\exists\) and \(\forall\). In a sense, they quantify how often the given predicate \(P(x)\) is true: \((\exists x\colon P(x))\) states that \(P(x)\) is true at least sometimes (at least for some \(x\)), while \((\forall x\colon P(x))\) states that it is always true (for all \(x\)).

Above, we used quantifiers without explaining from which set \(x\) is taken. This is done when it is clear from the context which set is being referred to. Formally, the set should be specified directly in the statement. For example, the statement

\(\forall x \in \{0,1,\dotsc,39\}\colon x^{2}+x+41\) is a prime number

\(\forall x \in \mathbb{Z}_{\ge 0}\colon x^{2}+x+41\) is a prime number

If the set over which the quantifier is taken is finite, then the statement can also be rewritten without the quantifier: \[\begin{align*}(\forall x \in \{1, 2, 3\}\colon P(x))&\equiv (P(1) \land P(2) \land P(3)) \ ,\\ (\exists x \in \{1, 2, 3\}\colon P(x))&\equiv (P(1) \lor P(2) \lor P(3)) \ .\end{align*}\]

In Python, the functions \(\texttt{all}\) and \(\texttt{any}\) evaluate quantifiers over arbitrary iterables. For a finite iterable, they expand the quantifiers as shown above; for an infinite iterable, they may never terminate.

def is_divisible_by_3(x):
    return x % 3 == 0


lst = [5, 17, 6, 10]

print(any([is_divisible_by_3(x) for x in lst]))
print(all([is_divisible_by_3(x) for x in lst]))

True
False