SI342: More Discrete Math - negating quantifier and size of sets

Negating quantifiers

Consider the following two statements:

S1: All midshipmen are not married , S2: Not all midshipmen are married

Do these statements say different things? One good way to answer this question is to model them with first-order logic. For S1 we have $$ F_1 := \forall m[ \text{isMid}(m) \Rightarrow \neg \text{isMarried}(m) ] $$ and for S2 we have $$ F_2 := \neg \forall m[ \text{isMid}(m) \Rightarrow \text{isMarried}(m) ]. $$ Asking whether these are different leads to the following ...

Question: How does negation work with forall and exists?
Answer: $\neg \forall x[ G ] \Longleftrightarrow \exists x[ \neg G ]$, and $\neg \exists x[ G ] \Longleftrightarrow \forall x[ \neg G ]$.

So, let's figure out what $F_2$ is really saying: $$ \begin{array}{rcl} \neg \forall m[ \text{isMid}(m) \Rightarrow \text{isMarried}(m) ] &\Longleftrightarrow& \exists m [ \neg [\text{isMid}(m) \Rightarrow \text{isMarried}(m) ] ]\\ &\Longleftrightarrow& \exists m [ \neg [\neg\text{isMid}(m) \vee \text{isMarried}(m) ] ]\\ &\Longleftrightarrow& \exists m [ \neg \neg\text{isMid}(m) \wedge \neg\text{isMarried}(m) ]\\ &\Longleftrightarrow& \exists m [ \text{isMid}(m) \wedge \neg\text{isMarried}(m) ] \end{array} $$ So we see that S1 is saying "every mid is not married" while S2 is saying "the is a mid who is not married", which do indeed mean different things.

ACTIVITY

Given: $L$ is a language, $M$ is a FA, $w$ is a string such that $w\in L(M)$ and $w \notin L$.
1. "all strings accepted by M are not in L" : T / F / Maybe
2. "not all strings accepted by M are in L" : T / F / Maybe
Consider the following attempted restatements of the definition of grammar $G$ being ambiguous:
1. there is not a string in L(G) that doesn't have a unique parse tree
2. every string in L(G) does not have a unique parse tree
3. there is a string in L(G) that doesn't have a unique parse tree
4. not every string in L(G) has a unqiue parse tree
5. there is not a string in L(G) that has a unique parse tree
6. not every string in L(G) doesn't have a unique parse tree
Model each of these in first order logic. Simplify using the above rules to push the negations inwards, and then assess: is this equivalent to the grammar being ambiguous?
Note: Just assume strings in L(G) are our domain of discourse in order to simplify things. So, for example:

(6) is equivalent to: $\neg \forall s[ \neg \text{uniquePT}(s) ]$, equivalent to $\exists s[ \neg\neg \text{uniquePT}(s) ]$, equivalent to $\exists s[ \text{uniquePT}(s) ]$.
... so (6) is not a correct restatement of the grammar being ambiguous.

One-to-one correspondence and the size of finite sets

We think we know what the "size" of a set is. But maybe we should make sure. The starting point for our idea of "size" is what's called a one-to-one correspondence.

Let $A$ and $B$ be sets. Function $f:A\rightarrow B$ is a one-to-one-correspondence between $A$ and $B$ if

each element of $B$ is the image of some $x$ in $A$, $\left(\text{i.e. }\forall y \in B[\exists x \in A[f(x) = y]]\right)$, and
no two elements $x$ and $x'$ of $A$ map to the same element of $B$, $\left(\text{i.e. }\forall x,x' \in A[x\neq x' \Rightarrow f(x) \neq f'(x)]\right)$.

Note: This just means we are pairing up elements of $A$ with elements of $B$, leaving nothing left over.

Example 1: Let $A$ be the set of cardinal compass directions, i.e. $A = \{N,S,E,W\}$, and let $B$ be the corners of the unit square with lower-left corner at the origin. Here's a one-to-one correspondence: $$ f\text{ maps } N\rightarrow(1,1),N\rightarrow(0,0),N\rightarrow(0,1),N\rightarrow(1,0) $$

Add picture!

With this definition, we can define what "finite" sets are and what their size is.

We say set $B$ is finite of size $k$, where $k\in \mathbb{N}$, if there is a one-to-one correspondence between $\{0,1,\ldots,k-1\}$ and $B$.

Example 2: $A = \{N,S,E,W\}$ can be put in one-to-one correspondence with $\{0,1,2,3\}$ via the function $0\rightarrow N,1\rightarrow N,2\rightarrow N,3\rightarrow N$, so $A$ is finite of size $4$.

Example 3: The set of (normal) academic periods in the USNA week (i.e. $\{M1,M2,\ldots,F6\}$) is finite of size 30 via the mapping $f(i)$ given by Python code: ['M','T','W','R','F'][i//6] + str(i%6 + 1) for $i \in \{0,1,\ldots,29\}$. Think about it!

Infinite sets

There are, of course, sets that are not finite. For example, $\mathbb{N}$ itself! The proof is that our definition of finite requires a concrete natural number $k$ and a function $f$ with domain $\{0,1,\ldots,k-1\}$. Suppose $\mathbb{N}$ is finite. Then there is a $k$ and a function $f$, and $k$ can't be zero since there needs to be elements that $f$ maps to 1 and to 42 and to 2026 and so on. So, let $m$ be the maximum of $f(0),f(1),\ldots,f(k-1)$. Then $m+1$ is an element of $\mathbb{N}$ that is missed by $f$, which is a contradiction!

So, $\mathbb{N}$ itself is infinite. So what "size" do we say it has? We say it has size $\aleph_0$ (read "aleph null"), and any set it can be put into one-to-one correspondence with also has this size, though we often say that such sets are "countably infinite".

Example 4: The odd natural numbers are countably infinite, despite being a strict subset of $\mathbb{N}$! Why? Because $f(i) = 2i+1$ is a one-to-one mapping from $\mathbb{N}$ to the add natural numbers.

Example 5: The integers (aka $\mathbb{Z}$) are countably infinite, despite being a strict superset of $\mathbb{N}$! Here's the mapping: $$ f(i) = \left\{ \begin{array}{cl} 0 & \text{ if } i = 0\\ (i+1)/2 & \text{ if $i$ is odd}\\ -(i/2) & \text{ if $i$ is even} \end{array} \right. $$

The set of all pairs of natural numbers is, somehow, also just countably infinite

Consider $\mathbb{G} := \mathbb{N}\times\mathbb{N}$, the set of all pairs of natural numbers. It's like 2D grid that's infinite both to the left and to the right. Surely it must not be possible to put $\mathbb{G}$ into one-to-one correspondence with $\mathbb{N}$, right? After all each row and each column, individually, are a copy of $\mathbb{N}$ itself!

Well ... actually it is possible. Infinity is weird like that.

The image to the right shows the beginning of a one-to-one mapping. The top-left dot corresponds to $i=0$ and $f(i) = (0,0)$. As you travel the twisting path, with each successive you increment $i$: so at $i=1$ we get $f(i) = (0,1)$ - note that I'm using (col,row) coordinate system here, which (I guess) is the reverse of what we've commonly done for grids. Sorry! The function $f:\mathbb{N}\rightarrow\mathbb{G}$ that I used for the image defined in the python code below.

Of course, we should prove that this function $f$ has the desired properties - i.e. that each element of $\mathbb{G}$ is paired with one and only one element of $\mathbb{N}$ and vice versa. But you'll have to take my word for it ... or put together your own inductive proof.

The real numbers - a bigger infinity!

So, we naturally have the question of whether there are any infinite sets that are "bigger" than $\mathbb{N}$, i.e. somehow too big to be put into one-to-one correspondence with $\mathbb{N}$. As it turns out, the real numbers ($\mathbb{R}$) is such a set. Let's prove it!

The real numbers cannot be put into one-to-one correspondence with the natural numbers.

The proof is a proof by contradiction. Suppose that there is a one-to-one correspondence between $\mathbb{N}$ and $\mathbb{R}$ given by some function $f$. We will rely on the fact that each real number has a representation in decimal, and define $d_{i,j}$ to be the $j$th digit after the decimal point in the representation of the real number $f(i)$. So if $f(42) = 0.518700\cdots$, then $d_{42,3} = 8$. Now we define $$ \overline{d}_{i,j} = \left\{ \begin{array}{cl} 7 & \text{ if $d_{i,j} = 3$}\\ 3 & \text{ otherwise} \end{array} \right. $$ With this we will define real number $\alpha$ that is not equal to $f(i)$ for any natural number $i$ as follows: $$ \alpha = 0. \overline{d}_{1,1} \overline{d}_{2,2} \overline{d}_{3,3} \overline{d}_{4,4} \overline{d}_{5,5} \overline{d}_{6,6} \overline{d}_{7,7} \overline{d}_{8,8} \overline{d}_{9,9} \cdots $$ Hopefully the following helps you see why $\alpha$ is not matched with any natural number by $f$:

$\alpha = 0$	.	$\overline{d}_{1,1}$	$\overline{d}_{2,2}$	$\overline{d}_{3,3}$	$\overline{d}_{4,4}$	$\overline{d}_{5,5}$	$\overline{d}_{6,6}$	$\overline{d}_{7,7}$	$\overline{d}_{8,8}$	$\overline{d}_{9,9}$	$\ldots$
$f(1) = \cdots$	.	$d_{1,1}$	$d_{1,2}$	$d_{1,3}$	$d_{1,4}$	$d_{1,5}$	$d_{1,6}$	$d_{1,7}$	$d_{1,8}$	$d_{1,9}$	$\ldots$
$f(2) = \cdots$	.	$d_{2,1}$	$d_{2,2}$	$d_{2,3}$	$d_{2,4}$	$d_{2,5}$	$d_{2,6}$	$d_{2,7}$	$d_{2,8}$	$d_{2,9}$	$\ldots$
$f(3) = \cdots$	.	$d_{3,1}$	$d_{3,2}$	$d_{3,3}$	$d_{3,4}$	$d_{3,5}$	$d_{3,6}$	$d_{3,7}$	$d_{3,8}$	$d_{3,9}$	$\ldots$
$f(4) = \cdots$	.	$d_{4,1}$	$d_{4,2}$	$d_{4,3}$	$d_{4,4}$	$d_{4,5}$	$d_{4,6}$	$d_{4,7}$	$d_{4,8}$	$d_{4,9}$	$\ldots$
$f(5) = \cdots$	.	$d_{5,1}$	$d_{5,2}$	$d_{5,3}$	$d_{5,4}$	$d_{5,5}$	$d_{5,6}$	$d_{5,7}$	$d_{5,8}$	$d_{5,9}$	$\ldots$
$f(6) = \cdots$	.	$d_{6,1}$	$d_{6,2}$	$d_{6,3}$	$d_{6,4}$	$d_{6,5}$	$d_{6,6}$	$d_{6,7}$	$d_{6,8}$	$d_{6,9}$	$\ldots$
$f(7) = \cdots$	.	$d_{7,1}$	$d_{7,2}$	$d_{7,3}$	$d_{7,4}$	$d_{7,5}$	$d_{7,6}$	$d_{7,7}$	$d_{7,8}$	$d_{7,9}$	$\ldots$
$f(8) = \cdots$	.	$d_{8,1}$	$d_{8,2}$	$d_{8,3}$	$d_{8,4}$	$d_{8,5}$	$d_{8,6}$	$d_{8,7}$	$d_{8,8}$	$d_{8,9}$	$\ldots$
$f(9) = \cdots$	.	$d_{9,1}$	$d_{9,2}$	$d_{9,3}$	$d_{9,4}$	$d_{9,5}$	$d_{9,6}$	$d_{9,7}$	$d_{9,8}$	$d_{9,9}$	$\ldots$
$\vdots$		$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

Note: We really ought to be careful about the fact that some numbers can be written in two ways, e.g. 1/2 can be written as $0.5$ and $0.499999999\cdots$, but it doesn't really change the idea of the argument.