Partially and totally ordered set Definition Let _ be a partial ord er on a set P . An element b in P covers an element a in P if a ≺ b and if a _ c _ b , the c = a or c = b . Element b in P covers the element a , if b is greater than a , and if there are no elements of P ”between” a and b . Exampl...
Principle of Mathematical Induction (PMI) Let p (1) , p (2) , ..., p ( k ) , ... be sentences having the following two properties: 1) p (1) is true; 2) ∀ k ∈ N [ p ( k ) is true ⇒ p ( k + 1) is true ] . Then ∀ n ∈ N p ( n ) is true. Example: Let's prove the Bernoulli inequality: ∀ n ∈ N 1 + nx 6 (...
Proof by contradiction To prove p ⇒ q we prove ( p ∧ ∼ q ) ⇒ q instead. That means, that to prove a theorem we assume its negation and we try to derive a contradiction. Example: The classic example is the proof, that √ 2 is irrational ( q ). Assume, that √ 2 is rational, so √ 2 = a b - irreduc...
Proof by modus ponens To prove p ⇒ q we prove [ p ∧ ( p ⇒ q )] ⇒ q instead. Example: We know, that if a right triangle has sides of lengths a, b, c , which c is the largest, then a 2 + b 2 = c 2 ( p ⇒ q ). Therefore, if we prove that any t...
Proof by modus tollens To prove p ⇒ q we prove [( ∼ q ) ∧ ( p ⇒ q )] ⇒ ( ∼ p ) instead. Example: We know, that if a right triangle has sides of lengths a, b, c , which c is the largest, then a 2 + b 2 = c 2 ( p ⇒ q ). Therefore, if we prove that for any triangle with sides of lengths x, y, z ,...
Properties of generalized union and intersection. Property 1: For every ( A t ) t 2 T : 1) ∀ t ∈ T A t ⊂ S t 2 T A t ∧ T t 2 T A t ⊂ A t ; 2) ∀ t ∈ T A t ⊂ A ⇒ S t 2 T A t ⊂ A ; 3) ∀ t ∈ T A ⊂ A t ⇒ A ⊂ T t 2 T A t ; 4) A ∪ ( S t 2 T A t ) = S t 2 T ( A ∪ A t ); A ∩ ( S t 2 T A t ) = S t 2 T ( A ∩ ...
Properties of quantifiers The commutative properties of quantifiers ∀ x ∀ y p ( x, y ) ⇐⇒ ∀ y ∀ x p ( x, y ) ; ∃ x ∃ y p ( x, y ) ⇐⇒ ∃ y ∃ x p ( x, y ) . But the order of universal and existential quantifiers cannot be changed. ∀ x ∃ y p ( x, y ) ⇐ = ∃ y ∀ x p ( x, y ) .
Properties of union intersection and complement. Property 1 (Properties of ∅ and U (universal set)): A ∪ ∅ = A ; A ∪ U = U ; A ∩ U = A ; A ∩ ∅ = ∅ . Property 2 (The idempotent properties): A ∪ A = A ; A ∩ A = A. Property 3 (The commutative properties): A ∪ B = B ∪ A ; A ∩ B = B ∩ A. Property 4 (The...
Quantifiers Quantifiers are symbols used instead of words ”for every” and ” there exists”. ∀ - ”for every”, ”for all”, ”for each” - universal quantifier, big quantifier . Universal quantifier is a generalization of the conjunction: ∀ x p ( x ) means that p ( x 1 ) ∧ p ( x 2 ) ∧ ... ∧ p ( x n ) is t...
Tautologies (5) [ ∼ ( p ⇒ q )] ⇔ [ p ∧ ( ∼ q )] (law of the negation of implication, also used in the form:) (5') ( p ⇒ q ) ⇔ [( ∼ p ) ∨ q ] (6) ( p ⇔ q ) ⇔ [( p ⇒ q ) ∧ ( q ⇒ p )] (connection between equivalence and implication) (7) [( p ⇒ r ) ∧ ( r ⇒ q )] ⇒ ( p ⇒ q ) (law of transitivity of im...
