1.6 Sets and Quantifiers
1.6.1 Sets
Sets form an important part of the language of mathematics. Informally, a set simply means a collection of elements. These elements can be any type of mathematical object: they can be numbers, vectors, or even other sets.
Sets are denoted by curly brackets \(\{ ... \}\).
For the purpose of this course, the most important sets are the set of natural numbers: \[\mathbb N=\{1,2,3,\dots\}\] and the set of integers \[\mathbb Z=\{\dots,-3, -2,-1,0,1,2,3,\dots\}\] Note some authors may have the convention that the natural numbers start at \(0\), however if we want to include \(0\) then we will write \[\mathbb N_0=\{0,1,2,\dots\}\] The notation \(x\in X\) means that \(x\) is an element of the set \(X\). For example \(n\in\mathbb Z\) means \(n\) is an element of the set of integers or more briefly \(n\) is an integer.
We can build subsets of a given set using set builder notation: \[\{x\in X : P(x)\}\] denotes the set of elements of \(x\) such that the predicate \(P(x)\) is true. For example \[\{n\in\ \mathbb Z: n \text{ is even}\}\] would denote the set of even numbers. We read the colon \(:\) as “such that,” so we have \(x\in X\) such that \(P(x)\) is true, or \(n\in \mathbb Z\) such that \(n\) is even.
Note some authors use the notation \(\{x\in X \mid P(x)\}\) instead of the colon.
If I write down a set \(A=\{1,2\}\) and another set \(B=\{1,2\}\) then, despite the different names, we think of these as the same set. This is encoded in the following rule (axiom) from set theory:
if all \(x\in A\) are also in \(B\) and all \(x\in B\) are also in \(A\) then \(A\) and \(B\) are the same set
This condition can also be expressed as saying that predicates \(x\in A\) and \(x\in B\) should be equivalent.
if \(x\in A \iff x\in B\) then \(A=B\).
If we just have the implication in one direction, for example \(x\in A\implies x\in B\) then this mean that all elements of \(A\) are also in \(B\) but there might be elements of \(B\) that are not in \(A\).
If \(x\in A\implies x\in B\) then we say that \(A\) is a subset of \(B\), written \(A\subseteq B\) (or as \(B\supseteq A\)).
1.6.2 Quantifiers
Frequently we wish to consider statements that are true for all values of some given variable. For example \[ \text{for every integer }n,\; n^2\geq0. \] In symbolic terms we write this as \[ \forall n\in\mathbb Z, n^2\geq0. \] The symbol “\(\forall\)” is pronounced “for all” or “for every” or “for each”, and is called the universal quantifier.
On the other hand, we may wish to consider statements that are only true for some values of some given variable. For example \[ \text{there exists (at least one) integer number }n \text{ such that } n^2=289. \] In symbolic terms we write this as \[ \exists n\in\mathbb Z, n^2=289. \] The symbol “\(\exists\)” is pronounced “there exists” or “for some”, and is called the existential quantifier.
What would be the negation of the statement \[ \forall n\in\mathbb Z, n^2\geq0. \]
The statement says that “the square of every integer is non-negative” or “every integer has a non-negative square”.
So the negation says that “not every integer has a non-negative square”. In other words “there are some (at least one) integer(s) that do not have a non-negative square”. In symbolic form this is \[ \exists n\in\mathbb Z, \lnot(n^2\geq 0). \]
In general, the negation of the universal quantifier \[ \forall x, P(x) \] is the existential quantifier \[ \exists x, \lnot P(x). \]
In the same way the negation of the existential quantifiers \[ \exists x, P(x) \] is the universal quantifier \[ \forall x, \lnot P(x). \]
The negation of \[ \exists n\in\mathbb Z, n^2=289. \] is \[ \forall n\in\mathbb Z, n^2\neq 289. \] This (false) statement asserts that all integers fails to be solutions of this equation.
1.6.3 Implicit quantifiers
Consider the (now familiar) statement
if \(n\) is even then \(n^2\) is even
In symbols we write this as the implication \[n \text{ is even }\implies n^2\text{ is even }\] When we write this we are not referring to some specific \(n\) for which this is true. Rather we are saying that the implication is always true.
Picking a specific value for \(n\) we can ask about the truth values in this statement, for example if \(n=2\) then the statements \(n\) is even and \(n^2\) is even are both true, so the implication evaluates as \(T\implies T\) which is true.
On the other hand picking another integer value for \(n\), say \(n=3\) then we see that the statements \(n\) is even and \(n^2\) is even are both false. The implication becomes \(F\implies F\) which is again true (by definition of \(\implies\)). Indeed this will work for any integer \(n\): we know this because we proved that if \(n\) is even then \(n^2\) is even.
The original statement should perhaps more precisely be stated as
if \(n\) is any even integer then \(n^2\) is even
which makes it clearer that the statement should be interpreted as \[\forall n\in \mathbb Z,\; n\text{ is even } \implies n^2 \text{ is even }\]
A note on brackets: by convention the statement \(\forall n, P(n)\implies Q(n)\) should be read as \(\forall n, (P(n)\implies Q(n))\) rather than \((\forall n, P(n)) \implies Q(n)\).
Note that in our discussion of proofs we have looked at how to prove that a conclusion is always true whenever the premise is true. In other words we have really been proving statements with (implicit) universal quantifiers: \[\forall n, P(n)\implies Q(n).\] We did however also make use of existential quantifiers: every time we use the statement \(n\) is even we expressed this as “there is an integer \(k\) such that \(n=2k\)” or in symbols: \[\exists k\in Z,\; n=2k\] If we want to write the statement “if \(n\) is even then \(n^2\) is even” purely in symbols then we can do so as follows: \[\forall n \in \mathbb Z, (\exists k \in \mathbb Z, n=2k) \implies (\exists l \in \mathbb Z, n^2=2l)\] As per the above convention about brackets, the initial \(\forall n\in \mathbb Z\) applies to the whole of this statement.
This proof that we gave for this statement demonstrates the use and proof of existential quantifiers. To prove an existential statement, which says there is at least one value of the variable with a certain property, we simply need to construct such an example.
In the case of our current statement, to prove \((\exists l \in \mathbb Z, n^2=2l)\) we need only to construct the value of \(l\). This value is \(2k^2\) where \(k\) is the value that we know exists from the premise \((\exists k \in \mathbb Z, n=2k)\).
We repeat here our earlier proof, but using quantifier notation:
\(n\) is even (premise)
\(\exists k \in \mathbb Z, n=2k\) (definition of even)
so \(n^2=(2k)^2\) (substitution)
\(n^2=(2k)^2=4(k^2)=2(2k^2)\) (algebraic manipulation)
let \(l=2k^2\) (define a variable called \(l\))
then \(n^2=2l\) (substitution)
so \(\exists l\in \mathbb Z, n^2=2l\) (by construction)
\(n^2\) is even (definition of even)