m1-formal-language

To start talking about anything we need a collection of symbols (a formal-alphabet). Any possible combination of symbols of the formal-alphabet is a formula. Generally there are some combinations that are not allowed. In this case, a collection of formation-rules (a formal-grammar) indicate which formulas are allowed (or well-formed) and which are not. The collection of all the well-formed-formulas (wffs) is known as a formal-language (note that it’s completely defined by the formal-alphabet and the formal-grammar).

Example: The symbols $a,b,c$ define the formal-alphabet $\mathcal{A}=\{a,b,c\}$. Any combination of these symbols is a formula, f.e. $b,ac,cbccca,abcabcabc,cc,$ etc. We can then use a formal-grammar to mark which of these formulas are valid (wffs), f.e., $\mathcal{G}=\{$“Valid formulas have 3 symbols”, “After a $b$ can’t be an $a$”, “After a $c$ must be other $c$“$\}$. Using these 3 formation-rules we have that f.e., the formulas $aab$ and $bcc$ are well-formed, and, f.e., $aca,aaaa,cba$ are not. Then, with the formal-alphabet $\mathcal{A}$ setting the possible formulas, and the formal-grammar $\mathcal{G}$ establishing which formulas are well-formed and which are not, we have completely defined the formal-language $\mathcal{L}$. The formal-language $\mathcal{L}$ (defined by ($\mathcal{A},\mathcal{G}$)) consists then explicitly of the wffs $aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc$. We can then either write the implicit definition of $\mathcal{L}$ as $\mathcal{L}=(\mathcal{A},\mathcal{G})$ or explicitly define it as the collection of wffs $\mathcal{L}=\{aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc\}$.

propositions

A proposition is a statement that has a definite truth-value, either True (T) or False (F). Historically we denote propositions in general with lowercase letters starting from $p$, i.e. $p,q,r,s,\dots$, etc.

Examples: The statements “4 is even” ($p$) and “Rome is the capital of Italy” ($q$) are propositions with truth-value True, while “5 is even” ($r$) is a proposition with truth-value False.

logical-connectives

Say we have two propositions $p$ and $q$ (each, as we saw, with two possible truth-values T or F), we can combine them to form a new proposition in 16 different ways. We’ll use a symbol to denote each case, and call them logical-connectives (or just connectives).

Note: The logical-connectives 11, 13, 2, and 4 in the table are called implication, converse-implication, non-implication, and converse-non-implication respectively.

The new propositions created using connectives (like $r=p$XOR$q$ or $s=p$NOR$q$) are called compound-propositions in contrast to the starting ones ($p$ and $q$ in this case) that are called atomic-propositions.

Example: We can combine the propositions of the previous example with f.e. the XNOR connective to obtain a new proposition that is True only when they have the same truth-value. In this case $p\text{XNOR}q$ read as “4 is even XNOR Rome is the capital of Italy” is a True proposition since both atomic-propositions are True (have truth-value True), and $p\text{XNOR}r$ read “4 is even XNOR 5 is even” is a False proposition since $p$ is True and $r$ is False.

Example: We can also combine the propositions of the previous example with f.e. the AND connective to obtain a new proposition that is True only when both atomic-propositions are True. F.e., $pANDq$ (“4 is even AND Rome is the capital of Italy”) is True, while $pANDr$ (“4 is even AND 5 is even”) is False. Similarly for the NAND connective, we have that $p\text{NAND}q$ is False, while $p\text{NAND}r$ and $q\text{NAND}r$ are True, and for the OR connective, we have that $p\text{OR}q$ is True, $p\text{OR}r$ is True, etc.

The 16 logical-connectives of the previous table let us create 16 new compound-propositions from 2 previous atomic-propositions, but a logical-connective can create a new compound-proposition from only one atomic-proposition $p$. The four possible combinations are: let the truth-values of $p$ untouched, which is known as the identity-connective, invert them, which is known as the negation connective ($\neg$), make them always True, known as the tautology connective ($\top$) and make them always False, known as the contradiction connective ($\perp$).

We can also have logical-connectives that create a new proposition given 3, 4, and any number $n$ of previous propositions. To specify this number we call the 4 connectives that act over just one proposition unary-logical-connectives, the 16 that act over two propositions, binary-logical-connectives, and in general, the $2^{2^n}$ that act over $n$ propositions, n-ary-logical-connectives. We call $n$ the arity of the logical-connective.

Notation note: The binary-logical-connectives AND and OR are often represented with the symbols $\wedge$ and $\vee$ respectively. E.g. the proposition $(pORq)ANDs$ is written as $(p\vee q)\wedge s$, the proposition $\neg (pORq)$ written $\neg (p\vee q)$, etc.

equivalent-propositions

A proposition can have the exact same truth-values as another, in that cases we talk about equivalent-propositions and denote them using $⟺$, f.e. any proposition $p$ is has the same truth-values that its double negation, therefore we say that they are equivalent-propositions, or directly write $p⟺\neg (\neg p)$. You can also note that the negation of the proposition $pORq$ has the opposite truth-values (check the table of binary-logical-connectives) than the proposition $pNORq$, so the negation of $pORq$ results equivalent to $pNORq$, i.e. $pNORq⟺\neg (pORq)$. The same thing occurs for $pNANDq⟺\neg (pANDq)$, and that is why these connectives receive those names (the negation of OR (NOR) and the negation of AND (NAND)). It is common sometimes to replace one for the other for the sake of readability, comparison, brevity, etc.

There exist two pairs of equivalent-propositions that, given their importance and widespread use, receive a name (Morgan’s laws) and that are $\neg (pORq)⟺(\neg p)AND(\neg q)$ and $\neg (pANDq)⟺(\neg p)OR(\neg q)$ (the negation of OR is the AND of the negations and vice versa). You can check (again just looking at the table of binary-logical-connectives) that the negation of OR (or NOR directly) is only True when both $p$ and $q$ are False and the AND connective is only True when $p$ and $q$ are both True, so it is also only True when $\neg p$ and $\neg q$ are both False. You can also check looking at the table, the dual case of the negation of AND and the OR of the negations $\neg p$ and $\neg q$.

Another important pair of equivalent-propositions (important enough to receive a name) is $p\to q⟺(\neg q)\to (\neg p)$, known as the contrapositive-law. For this reason, the proposition $(\neg q)\to (\neg p)$ is known as the contrapositive of the implication $p\to q$.

Finally, another equivalence worth highlighting is $pXNORq⟺(p\to q)AND(q\to p)$. For this reason, the logical-connective XNOR is also called “the biconditional”, and represented with the symbol $\leftrightarrow$ (i.e. instead of $pXNORq$ we often write $p\leftrightarrow q$).

functional-completeness

The number of connectives grows extremely fast with the arity (there are $2^{2^2}=2^4=16$ binary-logical-connectives, $2^{2^3}=2^8=256$ 3-ary-logical-connectives, $2^{2^4}=2^{16}=65536$ 4-ary-logical-connectives, $2^{2^5}=2^{32}=4294967296$ 5-ary-logical-connectives, etc.), but luckily, the great majority of these connectives are redundant (they can be constructed, via equivalences, using other connectives) so we can use a much smaller number of them. F.e., we can see in the table of the binary-connectives that the values are mirrored, i.e. the 8 connectives of the left are just the negation of the 8 on the right. Therefore, we can construct the 16 possible binary-connectives with just 8 and the unary-connective of negation ($\neg$). Furthermore, we can note that the negation is equivalent to the NOR connective applied to the same proposition ($\neg p=p$NOR$p$), so we don’t need the negation anymore, we can construct the 16 binary-connectives using just the 8 of the left. The excellent news is that we can continue this search to find that we can construct any connective (of any arity!!) using only just one binary-connective! (namely the NOR or the NAND connectives). This property is known as NAND completeness (or NOR completeness).

We also saw that we can write the NAND as a combination of the negation and AND $(p\text{NAND}q⟺\neg (p\text{AND}q))$, therefore we can construct any connective from these two (or using the negation and OR connectives since they can construct the NOR). Any collection of connectives that allow us to create all of the others from them (like the NAND and NOR connectives, or the collections $\{\neg ,AND\}$ and $\{\neg ,OR\}$ as we just said) is called functional-complete. The functional-complete collections (FCCs) of logical-connectives that do not contain redundant connectives and are called minimal-functional-complete. F.e., the collections $\{\neg ,\text{AND},\text{XNOR}\}$ and $\{\neg ,\text{AND},\text{OR}\}$ are functional-complete but not minimal since we can construct the $\text{XNOR}$ and $\text{OR}$ connectives using the other two. The collections $\{\text{NAND}\},\{\text{NOR}\},\{\neg ,\text{AND}\},\{\neg ,\text{OR}\}$ are all examples of minimal-functional-complete collections of connectives.

Although we saw that all the connectives can be constructed using just one connective (NAND or NOR), for readability in general we use FCCs of more than one connective. E.g. it’s better to read $p$OR$q$ than $(p$NOR$q)$NOR$(p$NOR$q)$, and it is better to read $p$AND$q$ than $(p$NOR$p)$NOR$(q$NOR$q)$, etc.

propositional-formal-language

As we have been doing, in general, to represent atomic-propositions we use lowercase letters $\{p,q,r,s,t,\dots \}$, and from then, with an FCC (e.g. $\{\neg ,\text{AND}\}$) and parentheses to indicate the order of application of the connectives, we can create any proposition, so they form a formal-alphabet where the propositions are formulas (these are known as propositional-formal-alphabets). But not all the formulas of a propositional-formal-alphabet $\mathcal{A}$ (in our example $\mathcal{A}=\{\neg ,\text{AND},(,),p,q,r,s,\dots \}$) are propositions, e.g. $p((\neg$ or $\neg pq(r$ are just nonsensical combinations of symbols of $\mathcal{A}$. With a formal-grammar $\mathcal{G}$ that identifies as well-formed-formulas just the formulas that are indeed valid propositions, we have that all the propositions form a formal-language, known (very creatively) as propositional-formal-language. The formal-grammar $\mathcal{G}$ used to convert a propositional-formal-alphabet into a propositional-formal-language is known as a propositional-formal-grammar, and the most commonly used consist of just two formation-rules:

1. If $p$ is an atomic-proposition (e.g., $p,q,r,\dots$), then $p$ is a wff.
2. If $\varphi$ and $\psi$ are wffs, then $(\neg \varphi )$ and $(\varphi \text{AND}\psi )$ are wffs, and similarly for other connectives in the FCC, with parentheses enclosing each application.

Examples of wffs of the propositional-formal-language with FCC $\{\neg ,OR,AND\}$ are $p$, $\neg q$, $pORq$, $\neg (pORq)$, $(pORq)ANDs$, $(pORq)AND(sAND(qOR(\neg p)))$, etc. And examples of formulas that are not wffs are $pp$, $ORq$, $(pAND)q$, $q($, $(pOR)AND\neg p$, $((p)ORq$, $p((\neg$, $\neg pq(r$, etc.

order-of-precedence

To reduce the use of parentheses, it is common to define an order-of-precedence for the logical-connectives of the FCC. That is, define an order in which they have to be applied if different connectives appear in a proposition without parentheses. F.e., a very common order-of-precedence of connectives, is: negation $(\neg )$, AND $(\wedge )$, OR $(\vee )$, implication $(\to )$, and then biconditional (or XOR) $(\leftrightarrow )$. With this order, the proposition $p\wedge q\to r$ is interpreted as $(p\wedge q)\to r$, because conjunction ($\wedge$) has higher precedence than implication ($\to$). Similarly, $\neg p\vee q$ is interpreted as $(\neg p)\vee q$, since negation ($\neg$) has higher precedence than disjunction ($\vee$). In contrast, $p\to q\wedge r$ is interpreted as $p\to (q\wedge r)$, and $\neg p\leftrightarrow q\to r$ is interpreted as $(\neg p)\leftrightarrow (q\to r)$.

predicates

A predicate is a statement containing variables, which becomes a proposition when all the variables are given a specific value. Historically we denote variables with lowercase letters starting from $x$, i.e. $x,y,z,a,b\dots$, etc. and predicates with uppercase letters starting from $P$. The number of variables in a predicate is called its arity.

Example: The statement ”$x$ is even” is not a proposition, as its truth-value depends on the value of $x$, but it is a predicate (that we can denote $P(x)$) that if the value of $x$ is, f.e., 2 it becomes the proposition $p=P(2)$ (“2 is even”) with truth-value True, and if the value of $x$ is, f.e., 3 it becomes the proposition $q=P(3)$ (“3 is even”) with truth-value False.

Example: Similarly, the binary-predicate (a predicate of two variables) $Q(x,y)=$”$x$ is the capital of $y$” becomes a proposition when both $x$ and $y$ are specified, e.g., $p=Q($Rome,Spain) (“Rome is the capital of Spain”) is False and $q=Q($Paris,France) is True.

If for the binary-predicate of the previous examples we specify the value of just one of the variables we end up not with a proposition, but with a unary-predicate (a predicate of just one variable).

F.e., if for the previous predicate $Q(x,y)$ we specify the value of $y=$“Spain”, then $Q(x$,“Spain”) becomes the unary-predicate $R(x)=$”$x$ is the capital of Spain” that f.e. is a True proposition for $R($Madrid)=$Q$(Madrid,Spain). Similarly, if we specify the value of $y=$“Spain”, then $Q($Lima,$y$) becomes the unary-predicate $S(y)=$“Lima is the capital of $y$” that f.e. is a False proposition for $S($Canada)=$Q$(Lima,Canada) and a True proposition for $S($Peru)=$Q$(Lima,Peru).

In general, if we have a predicate of $m$ variables, and we specify the value of only $n$, it becomes a new predicate of $m-n$ variables, and when we specify all the $m$ variables it becomes a proposition. So a proposition is a predicate of $m-m=0$ variables in this context.

F.e., the predicate $P(x,y,z)=$”$x$ is a city of $z$ AND $y$ is a city of $z$” is a 3-ary predicate that if we specify f.e. $z=$“Italy” becomes the binary-predicate ”$x$ is a city of Italy AND $y$ is a city of Italy”, and if we specify the value of also $x$ and $y$ with f.e. $x=$“Lima” and $y=$“Madrid”, then it becomes the proposition (or 0-ary predicate) “Lima is a city of Italy AND Madrid is a city of Italy” with truth-value False.

Predicates can be combined using logical-connectives, just as propositions are, to form new predicates (called compound-predicates) since when all the variables of the new compound-predicate are specified, the predicates that were combined (called atomic-predicates) have also all their values specified and become propositions. Then the resulting truth-value is determined just applying the logical-connectives to this propositions.

Example: The predicates $P(x)=$”$x$ is even” and $Q(y,z)=$”$y$ is greater than $z$” can be combined using f.e., the logical-connective AND to form the compound-predicate $R(x,y,z)=$”$x$ is even AND $y$ is greater than $z$” that just as any other predicate becomes a proposition when all of its variables are specified. F.e., $R(4,8,3)$ becomes the True proposition “4 is even AND 8 is greater than 3”, and f.e., $R(6,4,9)$ becomes the False proposition “6 is even AND 4 is greater than 9”.

existential-quantifier

There is another way to convert a predicate into a proposition besides specifying the value of all its variables. It is the statement “there exists (at least one) value of $x$ that makes $P(x)$ a True proposition”. To represent this sentence we use the symbols $\exists xP(x)$ where we have added the symbol $\exists$ known as the existential-quantifier.

Examples: For the predicate $P(x)=$”$x$ is even” without the need to specify a singular value for $x$ we know that the proposition $\exists xP(x)$ (read as “there exists (at least one) value of $x$ that makes ”$x$ is even” a True proposition”) is a True proposition since f.e. $P(2)$ is True, and in the same way we also know that for the predicate $Q(y)=$“Rio de Janeiro is the capital of the country $y$” the proposition $\exists yQ(y)$ is a False proposition since there is no value for $y$ that makes $Q(y)$ True.

predicative-formal-language

You can note that since predicates can be combined using logical-connectives (just as propositions are) to form new predicates, and that predicates of 0-arity represent propositions, then the formal-language of predicates (known as predicative-formal-language) is a generalization of the propositional-formal-language that adds to it the power to talk about variables and existence.

A formal-alphabet that lets us write any predicate (known as a predicative-formal-alphabet), is, as you can guess, formed by the symbols used to form predicates (uppercase letter starting from $P$, and lowercase letters starting from $x$ and parenthesis and commas to list the variables), to combine them (an FCC of logical-connectives), and to talk about existence (the existential-quantifier $\exists$). An example of a predicative-formal-alphabet is $\mathcal{A}=\{\neg ,\text{AND},\exists ,(,,,),P,x,Q,y,R,z,S,\dots \}$ (compare with the example of a propositional-formal-alphabet).

Just as we saw in the propositional-formal-language) case, every predicate is a formula of a predicative-formal-alphabet, but not every formula of a predicative-formal-alphabet is a predicate, since a lot of them are nonsensical combinations of symbols of the formal-alphabet. To differentiate them, we need a formal-grammar. The formal-grammar $\mathcal{G}$ used to convert a predicative-formal-alphabet into a predicative-formal-language, is known as a predicative-formal-grammar, and the most commonly used consist of just the next three formation-rules:

1. If $P$ is a predicate symbol of arity $n$, and $x,y,\dots ,w$ are $n$ variable symbols, then $P(x,y,\dots ,w)$ is a wff.
2. If $\varphi$ and $\psi$ are wffs, then $(\neg \varphi )$ and $(\varphi \text{AND}\psi )$ are wffs, and similarly for other connectives in the FCC, with parentheses enclosing each application.
3. If $\varphi$ is a wff and $x$ is a variable symbol, then $\exists x\varphi$ is a wff.

The propositional-formal-language is a very elemental formal-language and it lacks the power to express ideas more complex than true or false statements. As we’ve said, the predicative-formal-language is a generalization that adds to it the power to talk about variables and existence. This seemingly simple addition might not seem to represent a big change, but incredibly, it ends up providing the formal-language with (as we’ll see a little later) the power to express all the mathematics known to the moment!!

additional-quantifiers

For a predicate $P(x)$ that could be f.e. “Milan is the capital of the country $x$”, we saw that $\exists xP(x)$ is a proposition (False in this case). We can apply the negation connective $\neg$ to make it a True proposition, i.e. $\neg (\exists xP(x))$ is a True proposition read as “there exists no value of $x$ that makes $P(x)$ a True proposition”. To represent this more concisely we use the symbol $\nexists$ (known as the non-existential-quantifier) to write $\neg (\exists xP(x))$ directly as $\nexists xP(x)$.

We can also use the existential-quantifier to the negation of the predicate, i.e. $\exists x\neg (P(x))$ read as “there exists (at least one) value of $x$ that makes $\neg (P(x))$ a True proposition” or equivalently, “there exists (at least one) value of $x$ that makes $P(x)$ a False proposition”. Note that if use the non-existential-quantifier to the negation of the predicate, i.e. $\nexists \neg (P(x))$, we are stating that “there exists no value of $x$ that makes $P(x)$ a False proposition”, and this is equivalently to the statement “every value of $x$ makes $P(x)$ a True proposition”. We can represent this last statement with the symbols $\forall xP(x)$ (making use of the new symbol $\forall$, known as the universal-quantifier).

The existential-quantifier in f.e. $\exists xP(x)$ states that “there exists (at least one) value of $x$ that makes $P(x)$ a True proposition”, but sometimes it is useful to clarify that “there exists exactly one value of $x$ that makes $P(x)$ a True proposition”. This latter proposition is represented with the symbol $!\exists$ (known as the existence-and-uniqueness-quantifier) to write $!\exists xP(x)$. This proposition is True if there is one and only one value of the variable $x$ for which $P(x)$ is True, and False otherwise.

Example: For the predicate $P(x)=$”$x$ is the capital of Spain”, the proposition $!\exists xP(x)$ is True because there is exactly one value of $x$, namely $x=$“Madrid”, that makes $P(x)$ True. In contrast, for the predicate $Q(x)=$”$x$ is even”, the proposition $!\exists xQ(x)$ is False because there are multiple values of $x$ (f.e. 2, 4, 6) that make $Q(x)$ True. Similarly, for the predicate $R(x)=$“Rio de Janeiro is the capital of the country $x$”, $!\exists xR(x)$ is False because no value of $x$ makes $R(x)$ True.

redundancy-of-quantifiers

The existence-and-uniqueness-quantifier can be expressed using the existential-quantifier and logical-connectives. Specifically, $!\exists xP(x)$ is equivalent to $\exists x(P(x)\text{AND}\nexists y(P(y)\text{AND}\neg (y\text{XNOR}x)))$, which states that there exists an $x$ for which $P(x)$ is True and there does not exist a different $y$ for which $P(y)$ is True. This shows that $!\exists$, like $\nexists$ and $\forall$, is not strictly necessary for the predicative-formal-language, as all three can be written using $\exists$ and the functional-complete collection (FCC) of logical-connectives. However, including $\nexists$, $\forall$, and $!\exists$ in the predicative-formal-alphabet is convenient because they shorten formulas and make propositions more intuitive. Note that if we include the quantifiers $\nexists$, $\forall$, and $!\exists$ in the predicative-formal-alphabet $\mathcal{A}$ (f.e., $\mathcal{A}=\{\neg ,\text{AND},\exists ,\nexists ,\forall ,!\exists ,(,),,,P,x,Q,y,R,z,S,\dots \}$), we must update the predicative-formal-grammar $\mathcal{G}$ to account for them. The third formation-rule then becomes: 3. If $\varphi$ is a wff and $x$ is a variable symbol, then $\exists x\varphi$, $\nexists x\varphi$, $\forall x\varphi$, and $!\exists x\varphi$ are wffs.

Note that the predicative-formal-language remains fully expressive with only $\exists$ in the alphabet, but adding these quantifiers enhances readability and compactness. This is analogous to defining a propositional-formal-language with an FCC of logical-connectives that is not minimal (i.e. that contains redundant connectives that enhance readability and compactness).

Note that one can have a predicative-formal-language just connecting propositions with NAND and quantifying predicates with $\exists$, i.e. by understanding just the concept of existence ($\exists$) and the concept of “two things not being true simultaneously” (NAND). If we use instead as FCC $\{\neg ,OR\}$ we can have a predicative-formal-language by understanding just the phrase “to exist or to not exist” (that is indeed the question :P).

partial-quantification

When applying quantifiers to multivariate-predicates (predicates of more than one variable), we can quantify some but not all variables. If we apply a quantifier to fewer than all variables, the result is not a proposition but a predicate with fewer variables. F.e., consider the predicate $P(x,y)=$”$x$ is greater than $y$“. Applying the existential-quantifier to $x$, we write $\exists xP(x,y)$, which becomes the unary-predicate $Q(y)=$“there exists an $x$ that is greater than $y$“. This predicate is True f.e. for $y=5$ (since $6>5$) but False for $y=$“the largest number” (if such a concept is defined).

Example: For the binary-predicate $Q(x,y)=$”$x$ is the capital of $y$”, the proposition $\exists xQ(x,y)$ is the unary-predicate $R(y)=$“there exists an $x$ that is the capital of $y$”, which is True f.e. for $y=$“France” (since $Q($Paris, France$)$ is True) but False for $y=$“Antarctica” (since no $x$ makes $Q(x,\text{Antarctica})$ True). Similarly, $\forall yQ(x,y)$ is the unary-predicate $S(x)=$“for all $y$, $x$ is the capital of $y$”, which is False for any $x$ since no single $x$ is the capital of all countries.

multiple-variables-quantifiers

When multiple quantifiers are applied consecutively to different variables of a predicate, we can collapse the notation for brevity. F.e., the proposition $\exists x\exists y\exists zP(x,y,z)$, read as “there exists an $x$, a $y$, and a $z$ such that $P(x,y,z)$ is True”, can be written more concisely as $\exists x,y,zP(x,y,z)$. Similarly, $\forall x\forall yP(x,y)$ can be written as $\forall x,yP(x,y)$. This collapsed notation is a shorthand that assumes the quantifiers apply to each variable in sequence but does not change the meaning of the proposition or predicate.

Example: For the predicate $P(x,y,z)=$”$x$ is a city of $z$ AND $y$ is a city of $z$”, the proposition $\exists x\exists y\exists zP(x,y,z)$ can be written as $\exists x,y,zP(x,y,z)$, meaning “there exist $x$, $y$, and $z$ such that $x$ and $y$ are cities of $z$“. This is True f.e. for $x=$“Rome”, $y=$“Milan”, and $z=$“Italy”. Similarly, $\forall x,yQ(x,y)$ for $Q(x,y)=$”$x$ is greater than $y$” means “for all $x$ and $y$, $x$ is greater than $y$”, which is False since not all $x,y$ satisfy $x>y$.

Note: You may have noticed that the predicative-formal-grammar does not have a rule for the application of e.g. $\exists x,y,z$. The collapsed notation $\exists x,y,zP(x,y,z)$ is a shorthand for $\exists x\exists y\exists zP(x,y,z)$, permitted in the predicative-formal-grammar only as a notational convenience, provided the quantifiers are applied sequentially to distinct variables (i.e., $\exists x,y,z$ is just a notational tool that replaces the formal $\exists x\exists y\exists z$).

order-of-quantification

When we apply multiple quantifiers of different types, the order in which we apply them can change the meaning of the resulting proposition.

Example: For the predicate $P(x,y)=$ ”$x$ is the capital of $y$”, both $\exists x\exists yP(x,y)$ and $\exists y\exists xP(x,y)$ are the same True proposition, namely “There exists a city that is the capital of some country”. However, $\exists x\forall yP(x,y)$ and $\forall y\exists xP(x,y)$ represent two completely different propositions, the False proposition “There exists a city that is the capital of every country”, and the True proposition “Every country has a capital” respectively.

Example: For the predicate $R(x,y)=$ ”$x$ is a book written by $y$”, both $\exists x\exists yR(x,y)$ and $\exists y\exists xR(x,y)$ are the same True proposition, namely “There exists a book that was written by some author”. However, $\exists y\forall xR(x,y)$ represents the False proposition “There exists an author that has written every book”, and $\forall x\exists yR(x,y)$ the True proposition “Every book has an author”.

For this reason, when we apply multiple quantifiers of different types, we must pay special attention to their order of application.