Expressions "for every x", "there exists x such that" are called quantifiers. They allow us to construct new predicates (new propositional functions) from existing ones.
Let α(x) denote a propositional function of one variable x. Expressions "for every x, α(x)", "for all x, α(x)", "for any x, α(x)" mean a true proposition if, regardless of an arbitrary value 'a' substituted for the variable x in predicate α(x), the obtained proposition α(a/x) is true, i.e. all possible values of the variable x satisfy the propositional function α(x).

It is accepted in logic and in mathematics that  the quantifier "for every x" is denoted by the symbol of reversed letter A, i.e. ( ∀x). This quantifier is named general or universal.

The following expressions are examples of applying the general quantifier:

( ∀x) (x<0), ( ∀x) ((x-3 = 0) ∨ (x+1 < 4)) → (x< 1), (( ∀x)(x> 0) ∨( ∀y) ((y < 4) → (y < 1))).

The expression "there exists x such that" (sometimes used in equivalent form "for some x, ") is called the existential quantifier. In order to denote this quantifier we use the symbol of the reversed letter E, i.e. we write ( ∃x). We assume that a propositional function followed by this quantifier is a true proposition if and only if there exists some object (element) 'a' such that substitution for the variable x in the predicate α(x) leads to the true proposition α(a/x). For example, the expression (x-3 = 0) is a propositional function defined over the set of real numbers. However, (∃x) (x-3 = 0) is a true proposition, which means that there exists such a real number 'a' that the equation a-3=0 is satisfied.

Question 7.3.1 Let Z(x) denote the predicate "student x pass an exam" characterized over the set of PJWSTK's students. Write down the proposition "every student either passes or does not pass the exam" using quantifiers and the predicate Z(x)?

Example 7.3.1

(1) Consider the formula (( ∀x) ((x>0) ∨ (x ≤ 0)) ∧ ( ∃x) (x² ≤0)). The variable x occurring in the expression ((x>0) ∨ (x ≤0)) is bound by the general quantifier ( ∀x) and  the variable x, occurring in the expression (x² ≤0) is bound by the existential quantifier ( ∃x). The range of the universal quantifier is the propositional function ((x>0) ∨ (x ≤ 0)) and the range of the existential quantifier is the propositional function (x² ≤ 0).

(2) Let us consider now the formula ((( ∀x)(x>0) ∨ (x ≤ 0)) ∧ ( ∃x) (x² ≤ 0)), which differs from the previous one only by the arrangement of brackets. The variable x occurring in the expression (x>0) is still bound by the universal quantifier ( ∀x). However, the variable x  occurring in expression (x ≤ 0) is not bound by any quantifier. Therefore, this appearance of the variable x is free. The range of the general quantifier is the propositional function (x>0).

Remark If the only free variable x occurs  in the propositional function α(x),  then the expressions ( ∃x) α(x), ( ∀x) α(x) are propositions.

Up to now our examples of propositional functions with quantifiers were very simple because they included only one free variable. Of course, this fact is not the current rule: there may be many different variables in one propositional function.

Let α(x,x₁,x₂,...x_n) be a propositional function with the free variables x, x₁, x₂,..., x_n. Appending the symbol of quantifier, we bound the chosen variable only. ( ∃x) α(x, x₁, x₂, ...x_n ) as well as ( ∀x) α(x, x₁, x₂,...x_n ) are propositional functions with free variables x₁, x₂, ..., x_n. However, the variable x is bound in these propositional functions.

In the next sections, we will enumerate only these free variables of the propositional functions which are important for our reasoning. For example, if  we want to stress that x is the only one free variable of the propositional function α(x) which is crucial for us, then we write α(x). It may happen that the expression α includes more free variables, but at the moment, they are not important and that is why we do not mention them.

Example 7.3.2

1. Let us consider the propositional function ( ∀x) ( ∃y) (x+y<6 ∨ x*y<0) defined over the set of real numbers. Both variables x and y are bound by the corresponding quantifiers. The range of the existential quantifier ( ∃y) is the propositional function (x+y<6 ∨ x*y<0)  and the range of the universal quantifier ( ∀x) is the propositional function (x+y<6 ∨ x*y<0).
2. In the propositional function ( ∃x) (x+z<6 ∧ ( ∀y) ( x*y>0)) the variable x (occurred two-times) is bound by the existential quantifier ( ∃x). Its range is the propositional function  (x+z<6 ∧ ( ∀y) ( x*y>0)). The variable y, appearing in the second part of this expression, is bound by the universal quantifier ( ∀y). Its range is the propositional function (x*y>0). The variable z is not bound by any of the quantifiers and is the only one free variable in the formula.

Question 7.3.2 How many free variables are there in the first and in the second formula?

1. ( ∃ x) ( ∃ y)((x*y >0) ∧ (y<0))

2. (( ∃ x) (x*y>0) ∧ ( ∃ y) (y<0))

Let α(x) be a propositional function defined in the set X with just one free variable x. We assume the following definitions of satisfiability of the propositional functions:

The following conclusion is a direct consequence of the above-mentioned definition: for any predicate α(x) characterized over the set X,

- ( ∀ x) α(x) is a false proposition in X (i.e. its value is 0) if and only if {x ∈ X: α(x)} ≠ X,

- ( ∃ x) α(x) is a false proposition in X (i.e. its value is 0) if and only if {x ∈ X: α(x)} = ∅.

Example 7.3.3

1. Let us consider the propositional function (x+2)*(x-3)<0 in the set of real numbers. Because number 2 satisfies this function and number 3 does not, then

   ( ∃x) ((x+2)*(x-3)<0) is a valid proposition  in R, and

   ( ∀x) ( (x+2)*(x-3)<0) is a false proposition in R.

2. The propositional function (A ⊆ B → (A ∪ C) ⊆ (B ∪ C)), defined in the set of all subsets of some set X, is satisfied for every A, B, C. Thus,

   &#( ∀ A)( ∀ B) ( ∀C)(A ⊆ B → (A ∪ C) ⊆ (B ∪ C))

   is a true proposition in the power set P(X).

Example 7.3.4

1. Let us consider the propositional function ( ∀x) ( ∃y) (x+y<6 ∨ x*y<0). It represents a valid proposition over the set of real numbers. However, if we switch the function's domain into natural numbers, then it is false (there are natural numbers, e.g. for x=6, for which one cannot find  a value of y  such that  (x+y<6 ∨ x*y<0) is satisfied).
2. The expression ( ∃x) (x+z<6 ∧ ( ∃y) ( x*y>0)), treated as a propositional function over the set of real numbers, is satisfied by  z=6. It is because there exists a real number a (e.g. a=-1) such that a+6 < 6 and there exists a real number b (e.g. b=1) such that a*b < 0.  Moreover, this formula is valid in the set of  real numbers for arbitrarily chosen values of z. If the same expression ( ∃x)(x+z<6 ∧ ( ∃y)( x*y>0)) is treated as a propositional function in the set of natural numbers, then for some values of z   (e.g. z=6) its value is equal to false. Thus, not all natural numbers satisfy this propositional function.

Notice, that the name of the variable in the expression with a quantifier ( ∀x) α(x) or ( ∃x) α(x)  is of no importance: it is all the same if we write ( ∃x) (x-3<0), ( ∃y) (y-3<0) or ( ∃z) (z-3<0). These propositions are all true over an arbitrary set  (i.e. there exists an object a such that a-3<0) or all are false (i.e. there is no such object).

Question 7.3.3 Does the value of a propositional function depend on the values of bound variables?

If A is a finite set of elements a₁, a₂,..., a_n and α(x) is a propositional function defined in the set A, then the following equivalence is true

( ∃x) α(x) ↔ (α(a₁/x) ∨ α(a₂/x) ∨ ... ∨ α(a_n/x)).

Of course, the proposition ( ∃ x) α(x) has the value 1 over the set A  if and only if at least one element of the set A satisfies the propositional function α(x), i.e. if and only if when the alternative ( α(a₁/x) ∨ α(a₂/x) ∨ ... ∨ α(a_n/x)) is satisfied. The existential quantifier is therefore  a generalization of the logical disjunction.

Similar reasoning may be repeated for the general quantifier. If A = {a₁, a₂, ... a_n} and α(x) is propositional function defined in the set A, then the following equivalence is true

( ∀x) α(x) ↔ (α(a₁/x) ∧ α(a₂/x) ∧ ... ∧ α(a_n/x)).

Proposition ( ∀x) α(x) has the value 1 over set A if and only if all elements of the set A satisfy the propositional function α(x), i.e. if and only if the conjunction (α(a₁/x) ∧ α(a₂/x) ∧ ... ∧ α(a_n/x) ) is a true proposition. The universal quantifier may be treated as a generalization of the logical conjunction.

The relation between generalized operations and quantifiers is quite obvious when we recall their definitions (see subsection 1.6). If A={A_i}_{i ∈ I} is an indexed family of subsets of some space X, then

In other words

and

In order to define the generalized operations on sets we used quantifiers. Now we perform the opposite reasoning, i.e. to explain satisfiability of  the propositional functions we use the generalized operations.

This lemma states that the totality of values x which satisfy the propositional function ( ∃y) α(x,y) is the sum of all sets X_b = {x ∈ X: α(x,b/y)} for b ∈ Y. However, the intersection of all sets X_b gives such values of the variable x which satisfy the propositional function ( ∀y) α(x,y).

Example 7.3.5

1. Let us consider the propositional function ((0 < n) ∧ (0 ≤ x*n ≤ 1)) with two-arguments x, n, respectively over the set of real numbers and the set of natural numbers. The set of real numbers which satisfy the propositional function ( ∀n) ((0 < n) ∧ (0 ≤ x*n ≤ 1)) is the intersection of all sets of the form {x ∈R : 0 ≤x ≤ 1/n} for all natural numbers n>0. Thus, it is a one-element set {0}.

   {x ∈ R : ( ∀n ∈ N⁺)((0 < n) ∧ (0 ≤ x*n ≤ 1)) } = ⎧⎫ _{n ∈ N+}{x ∈ R : ((0 < n) ∧ (0 ≤ x*n ≤ 1)) }=

   = ⎧⎫ _{n ∈ N+}{ x ∈ R : 0 ≤ x ≤ 1/n}= {0}.

   The only value satisfying the propositional function ( ∀n) ((0 < n) ∧ (x*n ≤ 1)) is the real number 0.

2. The set of real numbers which satisfy the propositional function ( ∃n) ((0 < n) ∧ (0 ≤ x*n ≤ 1)) is the union of all sets of the form {x ∈ R : 0 ≤ x ≤ 1/n} for natural numbers n>0. Therefore, it is the closed range [0,1].

   {x ∈ R: ( ∃n ∈ N⁺)((0 < n) ∧ (0 ≤ x*n ≤ 1)) } = ⎩⎭ _{n ∈ N+}{x ∈ R: ((0 < n) ∧ (0 ≤ x*n ≤ 1))}=

   ⎩⎭ _{n ∈ N+}{x ∈ R: 0 ≤ x ≤ 1/n}= [0, 1].

   All real numbers from the range [0,1] satisfy the considered propositional function.

Sometimes, when we construct propositional functions, we assume some extra conditions which restrict the values of the formula's variables, especially those quantifiably bound. Let us consider the proposition:

Although the word "every" appears in this sentence, it is the universal quantifier, the voting rights apply only to at least the 18 years-old people. In this case we say that the general quantifier is restricted (limited) by some condition on possible values of the variable "person".

The restricted range general quantifier limited by a propositional function β(x) is usually denoted by

This expression means that we want to consider not all elements of an arbitrary domain but only these which satisfy the condition β(x). The restricted range quantifier ( ∀ β(x)) bounds all occurrences of the free variable x in the expression β(x). In  ( ∀ β(x)) α(x), the formula α(x) is the range of the universal quantifier and x is  the variable bound by this quantifier.

In the same manner, the restricted range existential quantifier limited by a propositional function β(x) is denoted by the symbol

The formula ( ∃ β(x)) α(x) is read  "there exists x satisfying β(x) such that α(x)". It means that in the  considered domain we do not search for an arbitrary value which satisfies the condition α(x), but this one which additionally satisfies the condition β(x). Thus, the range of the existential quantifier in the expression ( ∃ β(x)) α(x) is the  formula α(x) and x is the variable bound by this quantifier.

Restricted range quantifiers are not essential. All properties determined by this type of quantifiers can be also described with usual quantifiers. The following Lemma 7.3.1 explains it. The question "why we use  restricted range quantifiers" finds its answer if we study the example 7.3.6. The property written down with the help of restricted range quantifiers is often more transparent and shorter than unrestricted notation.

Lemma 7.3.1 states that, if the propositional function ( ∀ β(x)) α(x) is true, then the propositional function ( ∀x) ( β(x) → α(x)) is also true  and vice versa. Similarly, the second part of the lemma states that the propositional functions ( ∃ β(x)) α(x) and ( ∃x) ( β(x) ∧ α(x)) have always the same logical value.

Example 7.3.6

1. The Cauchy's condition states that the sequence (a_n) of real numbers is convergent to a number 'a' if and only if for every ε>0 there exists a natural number n₀ such that for every n>n₀, |a_n -a | < ε.

   We  can write this definition with unrestricted range quantifiers and with restricted range quantifiers:

   lim_{n → ∞} a_n = a wttw ( ∀ ε)(ε>0 → ( ∃ n₀)(n₀ ∈ N ∧ ( ∀ n)(n>n₀ → |a_n -a | < ε)))

   lim_{n → ∞} a_n = a wttw ( ∀ ε>0) ( ∃ n₀ ∈ N) ( ∀ n>n₀) |a_n -a | < ε.

The second version is shorter and easier to understand.


2. The principle of mathematical induction (see lecture 8) states, that for any subset A of the natural numbers' set, if the conditions (1) and (2) are satisfied, then all natural numbers belong to A, where (1) the number 0 belongs to A and (2) if some natural number belongs to A, then the next natural number also belongs to A. We may write this principle as a formula using restricted range quantifiers:

   ( ∀ A ⊆ N ) (0 ∈ A ∧ ( ∀ i ∈N) (i ∈ A → i+1 ∈ A)) → ( ∀ n ∈ N)(n ∈ A).

Question 7.3.4 Let C(x) denote that the colour of  x is red, K(x) denotes that x is a hen and Z(x) means that x lays golden eggs. Write down the following propositions using restricted range quantifiers and the defined above elementary predicates

1. All hens, if only they are red, lay golden eggs.
2. There are hens which, despite being red, do not lay golden eggs.

----- Check the answer -----

« previous section

next section »