Mathematical Analysis I (2011-2012)

Basic Notions 1 - Logic and sets

Paolo Boieri
Dipartimento di Matematica

3rd October 2011

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

1 / 14

Formulas

Consider a statement, like Today it is raining or 3 4. When we can establish whether a statement is true or false, we say that this statement is a formula. 14 is an odd number in a (False) formula 2 < 2 is a (True) formula Do you like Mozart? is not a formula The negation of a formula P is denoted by the symbol P. The formula P is True when P is False and P is False when P is True.

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

2 / 14

Conjunction and Disjunction

Starting with two (or several) formulas we can build new formulas, using connectives: The conjunction of P and Q (Symbol: P Q, read as P and Q) is True when both the formulas are true, False in the other cases The disjunction of P and Q (P Q, read as P or Q) is False when P and Q are False, and it is True in the other cases. The conjunction P (P) is always False The disjunction P (P) is always True

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

3 / 14

Implication and Logic Equivalence

The implication P = Q (If P then Q) is False if P is True and Q is False; it is True in the other cases
the formula P is called hypothesis or assumption the formula Q is called consequence or conclusion

We can state that P = Q also saying that

P is said to be a sucient condition for Q Q is said to be a necessary condition for P

The logic equivalence P Q (P if and only if Q) is True if P e Q are both True (or both False); it is False in the other cases We can state that P Q also saying that
P is a necessary and sucient condition for Q Q is a necessary and sucient condition for P

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

4 / 14

Rules of inference

We use three dierent methods for the proof of a theorem The direct proof We prove the conclusion using the assumption, the axioms of the theory and the results already proven The proof by contrapositive In order to prove that P = Q we prove the logically equivalent formula Q = P The proof by contradiction In order to prove that P = Q we show that (P (Q)) = P or that (P (Q)) = R R

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

5 / 14

Quantiers

A predicate is a statement that depends upon one or more variables. A predicate is not True or False, until we x the value of the variable(s). As an example, x is a prime number is a predicate containing the variable x; setting x = 19 we get a True formule, setting x = 10 a False formula. For a predicate we use the notation p(x) (we say also the property p(x)) We obtain a formula in a dierent way, using a quantier The universal quantier (symbol , we read it for all): x : p(x) means that the property p(x) is true for all x The existential quantier (read as there exists a) : x : p(x) means that the property p(x) is true for at least one x.

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

6 / 14

The negation of a quantied predicate

The negation of a quantied predicate is obtained by changing the quantier and by negating the property. (x : p(x)) x : (p(x)) (x : p(x)) x : (p(x))

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

7 / 14

Predicates with two or more variables

A predicate with two or more variables is called also a relation. We consider here predicates with two variables: p(x, y ) Using two quantiers we have eight possible cases: x, y : p(x, y ) x, y : p(x, y ) x, y : p(x, y ) x, y : p(x, y ) y , x : p(x, y ) y , x : p(x, y ) y , x : p(x, y ) y , x : p(x, y )

and eight statements with completely dierent meaning. The negation of a multiply quantied predicate is obtained by changing the quantiers and by negating the relation. For instance: (x, y : p(x, y )) x, y : (p(x, y ))

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

8 / 14

Sets

A set is dened writing a list of its members (called elements), all dierent one from another; the elements are said to belong to the set. Examples: A = {1, 2, 3}, B = {a, b, c, d, e}

If x is an element of the set E , we write x E ; If x is not an element of the set E , we write x E /

A set with no elements is called empty set; the notation is .

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

9 / 14

Sets of numbers

The following sets are widely used in Mathematics. N = {0, 1, 2, 3, . . .} is the set of natural numbers Z = {. . . , 3, 2, 1, 0, +1, +2, +3, . . .} is the set of integer numbers Q = {p/q : p Z, q Z, q = 0, p and q relative primes} is the set of rational numbers, R is the set of real numbers; a real number can be a rational number or a non-rational number (some examples of non rational numbers are 2, 5 3, ).

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

10 / 14

Subsets

Denition. Given a set B, the set A is a subset of B (we say also that A is included in B) when all the elements of A belong also to B. We write AB

If there exists at least one element of B that does not belong to A, we say that A is a proper subset of B (the notation is A B). If A B and B A, the we say that the two sets are equal and we write A = B.

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

11 / 14

The power set

Denition. The set of all subsets of A is called the power set of A. The symbol is P(A). Example. If A = {a, b, c} the power set of A is: {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} If A has n elements, then P(A) has 2n elements.

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

12 / 14

Operating with sets

Denition. Given two sets A e B, we dene the following sets: the union set = A B which is the set of all x belonging to A or belonging to B; the intersection set = A B which is the set of all x belonging to A and belonging to B the dierence = A \ B which is the set of all x that belong to A and do not belong to B the symmetric dierence = AB which is the set of the elements x that belong to A and do not belong to B or belong to B and do not belong to A.

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

13 / 14

Operating with sets - 2

Denition. Given a set A M, the complement of A (in M) (we write A oppure CA) is the set M \ A. The De Morgan laws show the relation between complement, union and intersection. C(A B) = CA (CB) C(A B) = CA (CB)

P. Boieri (Dip. Matematica)

Math.Analysis 2011/12

3rd October 2011

14 / 14