In this introductory chapter some mathematical notions are presented rapidly

1.2.2 Predicates
Let us now introduce a central concept. A predicate is an assertion or property
that depends upon one or more variables belonging to suitable sets,
and which becomes a formula (hence true or false) whenever the variables are
fixed. Let us consider an example. If is an element of the set of natural numbers,
the assertion is an odd number' is a predicate: is true, false

1.2 Elements of mathematical logic 7 bet

et c. If and denote students of the Polytechnic of Turin, the statement

and follow the same lectures' is a predicate.
Observe that the aforementioned logic operations can be applied to predicates
as well, and give rise to new predicates and so on). This
fact, by the way, establishes a precise relation among the essential connectives
and the set-theoretical operations of taking complements, intersection and
union. In fact, recalling the definition of subset of a given
set , the 'characteristic property' of the elements of A is nothing else but
a predicate, which is true precisely for the elements of . The complement is
thus obtained by negating the characteristic property

while the intersection and union of with another subset are
described respectively by the conjuction and the disjunction of the corresponding
characteristic properties:

The properties of the set-theoretical operations recalled in the previous section
translate into similar properties enjoyed by the logic operations, which the reader
can easily write down.
1.2.3 Quantifiers
Given a predicate with the variable x belonging to a certain set , one is
naturally lead to ask whether is true for all elements , or if there exists at
least one element making true. When posing such questions we are actually
considering the formulas

and

If indicating the set to which belongs becomes necessary, one writes
and '. The symbol ('for all') is called universal quantifier,
and the symbol ('there exists at least') is said existential quantifier.
(Sometimes a third quantifier is used, !, which means 'there exists one and only
one element' or 'there exists a unique'.)
We wish to stress that putting a quantifier in front of a predicate transforms
the latter in a formula, whose truth value may be then determined. The predicate
is strictly less than 7' for example, yields the false formula
(since is false, for example), while ' is true (e.g., x = 6 satisfies
the assertion).

1 Basic notions

The effect of negation on a quantified predicate must be handled with attention.

Suppose for instance x indicates the generic student of the Polytechnic, and let
is an Italian citizen'. The formula ('every student of the Polytechnic
has Italian citizenship') is false. Therefore its negation ' ' is true, but
beware: the latter does not state that all students are foreign, rather that 'there
is at least one student who is not Italian'. Thus the negation of , ' is
We can symbohcally write

Similarly, it is not hard to convince oneself of the logic equivalence

If a predicate depends upon two or more arguments, each of them may be
quantified. Yet the order in which the quantifiers are written can be essential.
Namely, two quantifiers of the same type (either universal or existential) can be
swapped without modifying the truth value of the formula; in other terms

On the contrary, exchanging the places of different quantifiers usually leads to

different formulas, so one should be very careful when ordering quantifiers.
As an example, consider the predicate with x, y varying in the
set of natural numbers. The formula ' means 'given any two natural
numbers, each one is greater or equal than the other', clearly a false statement.
The formula meaning 'given any natural number , there is a
natural number y smaller or equal than , is true, just take for instance.
The formula means 'there is a natural number greater or equal
than each natural number', and is false: each natural number admits a successor
which is strictly bigger than . Eventually, ' ('there are at
least two natural numbers such that one is bigger or equal than the other') holds
trivially.