Logic: For All and There Exists

Discover: the theorem everyone quotes

Ask why neural networks work at all and someone will say that they “can approximate any function”. That slogan comes from a 1989 theorem by George Cybenko. Here is its heart, exactly as the paper prints it:

The first line is a neural network with one hidden layer. It has $N$ hidden units, each applying a sigmoid $\sigma$ to a weighted input, and their outputs are weighted by the $\alpha_j$ and added up. The second line says the network's output is within $\varepsilon$ (epsilon, Chamber 1's tiny number) of a target function $f$ everywhere on the unit cube $I_n$. The words that join them are the important part. The theorem says: “given any $f$ … and $\varepsilon > 0$, there is a sum, $G(x)$, of the above form, for which” the inequality holds “for all $x$”.

Given any. There is. For all. Those little words are logic, and the order they come in is the whole theorem. Get the order wrong and you'll believe something the theorem never said. By the end of this chamber you'll write it as a single line of symbols and know exactly what it promises.

First, a warm-up with the smallest word of all: if. Here is a version of a puzzle the psychologist Peter Wason devised in 1966.

Learn: propositions and connectives

A proposition is a statement that is either true or false. “$2 + 2 = 4$” is a true proposition and “$7$ is even” is a false one. “$x > 3$” is not a proposition yet, because its truth depends on $x$. A statement with a free variable like that is called a predicate, written $P(x)$. It becomes a proposition once you fix $x$ or quantify it, which is the job of the second half of this chamber.

Propositions combine with connectives. Each one is defined by what it does to truth values:

$\neg P$ is “not P”, $P \land Q$ is “P and Q” (true only when both are), and $P \lor Q$ is “P or Q”, true when at least one is. Mathematical “or” is inclusive: “you may have tea or coffee” in mathematics allows both.

These are the set operations of Chamber 2 in another costume. $x \in A \cap B$ means $(x \in A) \land (x \in B)$, union is $\lor$ and complement is $\neg$. So De Morgan's laws hold for logic too:

The symbol $\equiv$, “is logically equivalent to”, says the two sides have identical truth tables.

Learn: if, then

The connective that carries most of mathematics is implication, $P \Rightarrow Q$, read “P implies Q” or “if P, then Q”. Think of it as a promise: if it rains, I'll bring an umbrella. There's only one way to break that promise. It rains and you don't bring the umbrella. On a dry day the promise isn't tested, so it isn't broken, whatever you carry.

The last two rows surprise people. When $P$ is false the implication is vacuously true. That's why Chamber 2 could say $\varnothing \subseteq A$ for every set $A$: “if $x \in \varnothing$ then $x \in A$” can never be broken, because nothing is in $\varnothing$.

English has many ways to say $P \Rightarrow Q$, and papers use all of them:

Three relatives of $P \Rightarrow Q$ are worth naming. The converse is $Q \Rightarrow P$: “if $n$ is even, then $n$ is divisible by 4”, which is false (take $n = 6$). The contrapositive is $\neg Q \Rightarrow \neg P$: “if $n$ is odd, then $n$ is not divisible by 4”, which is true. And the biconditional $P \Leftrightarrow Q$, “P if and only if Q”, claims both directions at once, $P \Rightarrow Q$ and $Q \Rightarrow P$.

The contrapositive always has the same truth value as the original. Here is why, as a derivation in full. First, reading the table above, $P \Rightarrow Q$ is false in exactly one row, where $P$ is true and $Q$ is false. The formula $\neg P \lor Q$ is also false in exactly that row, so

Now apply that rule to the contrapositive, with $\neg Q$ in the role of $P$ and $\neg P$ in the role of $Q$:

Back to Wason's cards. The rule is vowel $\Rightarrow$ even. Its contrapositive is odd $\Rightarrow$ not a vowel, and it's the same rule. That's why the $7$ must be turned: it's the contrapositive's test case. The $4$ only tests the converse, which the rule never claimed.

Now fill in the tables yourself. The lab checks your columns and then shows you the contrapositive and the converse side by side. There's a bonus round on quantifiers underneath, which the next section explains.

Learn: for all and there exists

Most statements in machine learning are about every input, or claim that some parameter setting exists. Two symbols, the quantifiers, turn predicates into propositions:

• $\forall x \in S,\ P(x)$, “for all $x$ in $S$, $P$ of $x$”: every element passes.
• $\exists x \in S,\ P(x)$, “there exists an $x$ in $S$ such that $P$ of $x$”: at least one does.

A few sentences you could meet in a paper:

The first says ReLU never outputs a negative number. The second says the sigmoid's output always lies strictly between 0 and 1. The third says some parameter setting fits the training data perfectly. To prove a $\forall$ you must handle an arbitrary element, as in Chamber 2's element chasing. To prove an $\exists$ one witness is enough.

On a finite set, $\forall$ is a long “and” and $\exists$ a long “or”. With $S = \{1, 2, 3\}$, the statement $\forall x \in S,\ P(x)$ means $P(1) \land P(2) \land P(3)$. That's why Python calls them all and any.

Order matters. Compare two sentences about the real numbers:

The first says every number has a bigger one, which is true: given $x$, take $y = x + 1$. The second says one single $y$ is bigger than every number, including itself, which is false. In the first, $y$ is chosen after $x$ and may depend on it. In the second, $y$ must be chosen first, once and for all. It's the difference between “everyone has someone they trust” and “there's someone everyone trusts”.

Negating a quantified statement follows two rules:

“Not every weight is positive” means “some weight is not positive”, $\exists i,\ w_i \le 0$. It does not mean “every weight is negative”. With several quantifiers, push the $\neg$ inwards one symbol at a time: each quantifier flips, and the condition at the end is negated. The set a quantifier ranges over, like the $\varepsilon > 0$ in $\forall \varepsilon > 0$, stays as it is.

Learn: definitions, lemmas and theorems

Papers label their statements, and the labels tell you how to read them.

Nearly every theorem has the shape “for all objects of some kind, hypotheses $\Rightarrow$ conclusion”. Reading one means finding three things: what it ranges over, what it assumes, and what it concludes. Proofs also use a small vocabulary of shorthand:

Learn: four ways to prove it

You met a direct proof in Chamber 1: assume the hypothesis and walk forwards to the conclusion. Here's another, the first half of a statement we'll need shortly.

Lemma A. If $n$ is an even integer, then $n^2$ is even.

Proof. Let $n$ be even, so $n = 2k$ for some integer $k$. Then $n^2 = 4k^2 = 2(2k^2)$, which is two times an integer, so $n^2$ is even. $\blacksquare$

Going the other way directly is awkward. Knowing $n^2 = 2m$ tells you little about $n$ itself. So use the contrapositive: prove $\neg Q \Rightarrow \neg P$, which you now know is the same statement.

Lemma B. If $n^2$ is even, then $n$ is even.

Proof. We prove the contrapositive: if $n$ is odd, then $n^2$ is odd. But $n^2 = n \cdot n$, and Chamber 1's prove-it exercise showed that the product of two odd integers is odd. So $n^2$ is odd. $\blacksquare$

Together, Lemmas A and B prove a biconditional: $n$ is even if and only if $n^2$ is even. Now the most famous proof by contradiction, where you assume the claim is false and follow the assumption until something impossible happens.

Theorem. $\sqrt{2}$ is irrational.

Proof. Suppose, for contradiction, that $\sqrt{2}$ is rational. Then $\sqrt{2} = p/q$ for some integers $p$ and $q$ with $q \ne 0$. Any fraction can be reduced to lowest terms, so we may assume that $p$ and $q$ have no common factor greater than 1. Squaring both sides gives $2 = p^2/q^2$, so

So $p^2$ is even, and by Lemma B, $p$ is even. Write $p = 2k$. Substituting, $4k^2 = 2q^2$, so $q^2 = 2k^2$. Now $q^2$ is even, and by Lemma B again, $q$ is even. So $p$ and $q$ are both even, and they share the factor 2. That contradicts our choice of $p/q$ in lowest terms. The assumption must be false, so $\sqrt{2}$ is irrational. $\blacksquare$

Look at how the pieces fit. The proof never touches a decimal expansion; it lives entirely on definitions (rational, even, lowest terms). Lemma B does the real work, twice. And the contradiction lands on the one assumption we made for free, lowest terms. That's the architecture of mathematics in miniature: definitions, then lemmas, then a theorem assembled from them.

The fourth technique only ever disproves. To refute a claim of the form $\forall x,\ P(x)$, you need its negation, $\exists x,\ \neg P(x)$, and one example proves that: a counterexample. Euler noticed that $n^2 + n + 41$ is prime for $n = 0, 1, 2, \ldots, 39$. Forty primes in a row look like a law of nature. Then

and the “law” is dead. No number of confirming cases proves a $\forall$ over an infinite set, but a single counterexample always refutes one. Problem 1 hunts for one in a disguised version of this polynomial.

Learn: the universal approximation theorem, as a sentence

Now back to Cybenko's theorem. Here are its hypotheses, straight from the paper. $I_n = [0, 1]^n$ is the unit cube. $C(I_n)$ is the set of continuous functions on it. $\sigma$ is any continuous sigmoidal function, which the paper defines as one with $\sigma(t) \to 1$ as $t \to +\infty$ and $\sigma(t) \to 0$ as $t \to -\infty$. With those fixed, the theorem is one logical sentence:

Read it aloud: “for every continuous function $f$ on the cube, and every positive tolerance $\varepsilon$, there exist a number of units $N$ and weights such that, for every input $x$ in the cube, the network is within $\varepsilon$ of $f$.” Everything this chamber taught is in that line, and each piece tells you something:

1. It's an existence theorem. $\exists$ promises that suitable weights exist. It says nothing about finding them, and in particular nothing about whether gradient descent will.
2. The order is $\forall f\ \forall \varepsilon\ \exists N$. So $N$ is allowed to depend on $f$ and on $\varepsilon$: a wigglier function or a tighter tolerance may need more units, and the theorem gives no bound. Swapping to $\exists N\ \forall f$ would claim something far stronger, that one network size serves every function, and the theorem says no such thing. In Problem 3, halving $\varepsilon$ doubles the $N$ you need.
3. The hypotheses matter. $f$ must be continuous and the inputs must lie in the bounded cube $I_n$. Outside those conditions this theorem is silent.
4. The last quantifier is $\forall x$. The error bound holds at every input simultaneously, not just on average or at the training points.

Finally, what would it take to refute the theorem? Negate it, flipping every quantifier: $\exists f\ \exists \varepsilon > 0\ \forall N, \alpha_j, \theta_j, y_j\ \exists x \in I_n$ with $|G(x) - f(x)| \ge \varepsilon$. In words, you would need one continuous function and one tolerance that every network misses somewhere. Cybenko's proof shows no such pair exists.

Read beyond the course

Logic is the most reusable thing in this course: every later chamber, and every theory paper, leans on it. These are free and worth your time now.

Papers and lectures

Cybenko's paper is twelve pages of functional analysis, but you can read the parts that matter today if you take them in the right order. Start with the abstract and the first page of the Introduction. Equation (1) there is the one-hidden-layer network, and the definition of “sigmoidal” sits right below it. Then skip Section 2. Its proof uses the Hahn–Banach and Riesz representation theorems and measures, which is graduate analysis. Jump to the start of Section 3 for Theorem 2. Its proof is a single line: “Combine Theorem 1 and Lemma 1”. That's the definition–lemma–theorem architecture of this chamber in action. The heavy lifting happens earlier, and the headline result is assembled from parts. The rest of Section 3, on classification and decision regions, can wait until you've met measures.

Watch

Tom Leighton's first lecture covers this chamber from a computer scientist's angle. Watch for his $\forall n \in \mathbb{N}$ claim about $n^2 + n + 41$, then a conjecture of Euler's about fourth powers that stood for more than two centuries before a counterexample turned up, and his truth table for “implies”, including why “if pigs fly, then I'm king” is true.

A short, clear walk through the negation rules, with examples. Pause before each answer and negate the statement yourself first.

Your turn

You've filled in the truth tables. Now translate logic into words and into Python, prove one statement by contrapositive and another by contradiction, and finish with three problems that turn quantifiers into code.

Proofs

The puzzle is a proof by contrapositive. Watch which statement it starts from, because two of the lines on offer start from the wrong place. The proof you write yourself is a proof by contradiction, in the style of the one for $\sqrt{2}$.

Code it up

Each problem is a quantified statement. The first needs a counterexample, the second a negated quantifier over infinitely many pairs, and the third a witness for Cybenko's $\exists N$.