Week 4

This week we learned about mixed quantifiers.

To recap, the two fundamental logical quantifiers are existential and universal (as far as I'm aware there aren't any more). All the existential quantifier claims is that there exists some element that happens to belong to some set of interest. For example:

"There exists some natural number..." In order to be usable in a precise logical statement, it could be broken down to mean that there exists some number that we can give a name, such as X, that happens to belong to the set of all natural numbers.

Universal quantification goes a giant leap further and makes a claim about all of the elements inside of some set. Extending the previous example:

"Every single natural number that exists..." More precisely, this means that a variable X can be assigned in sequence to every single number in the set of natural numbers, and that whatever statement follows will be true for each of these instantiations of X.

Where it gets interesting is when you combine these two quantifiers into a single statement. In particular, order matters.

1) "Some X exists such that for all Y..."

!=

2) "For all X there exists a Y...".

Statement 1 says that there is a single value that X can take on, that when coupled with any value that Y can take on, yields a truthful statement. Statement 2 says that for every single X that you can pick, you can also pick a unique value Y each time X takes on a new value, in order to make the statement true.

To make this distinction more concrete, imagine the following equation that takes in integer values for X and Y:

3) X = Y

Statement 1 in combination with 3 says that when you pick some X, Statement 3 will be true for any Y value, which is clearly false. Statement 2 in combination with 3 on the other hand says that for any value X takes on, you can pick a Y such that Statement 3 is true. Simply set Y to be X each time and the statement is true.

This difference in quantifier ordering can make a profound difference in the meaning and hence interpretation of all logical statements.