General definitions of set Set is a basic concept that is not defined. Examples of sets: A = {1, 5, a,w,}; B = {x : x = 2 ∨ x = 5}; C = {∅, {1, 2}, 5}; D = {{{∅}}}. Sets: A,B,C. Elements of the set: a, b, c. The membership relation between set and its element: a ∈ A. If a is not element of A...
Generalization of union and intersection Definition: Let X 6 = ∅ be a space. Let R be a family of all subsets of the space X . Let T 6 = ∅ be an arbitrary set. Function f : T → R is called an indexed family of sets , if: ∀ t ∈ T ∃ A t ∈ R f ( t ) = A t . Examples: 1) Let T = { 1 , 2 , 3 , 4 , 5 } ,...
Graph of the relation Definition A directed graph is a set of points, together with a set of directed arcs connecting some of these points. The points of a directed graph are called vertices (singular: ver- tix) or the nodes of the graph. If D is a directed graph, then ν ( D ) is the set of vertice...
INCLUSION A set A is subset of a set B, if every element of A is also element of B. B is superset of A. A ⊂ B ⇔ ∀a(a ∈ A ⇒ a ∈ B). Examples: a) {1, 4, a} ⊂ {0, 1, 3, 4, a, b}; b) N ⊂ Z ⊂ Q ⊂ R - hierarchy of subsets. The empty set is a subset of any set: ∅ ⊂ A. A set is always a subset of it...
Logic connectives The logic connectives are: not ∼ and ∧ or ∨ if...then (implies) = ⇒ if and only if (equivalent) ⇐⇒ Examples of compound statements: ” Today is not Monday.” (truth-value = 1); 2 x = 2 if and only if x = 1 . (truth-value = 1); If x = 2 and y = 3 then x + y = 100 . (truth-value = 0) ...
Logic statement A statement is any sentence in logic sense that has a truth value , that is any sentence that is either true or false. The true - value is denoted by ”1”. The false - value is denoted by ”0”. Usually sentence are denoted by small letters, like p, q, r, s etc. Types of statements: si...
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...
