UNIT 1 BASIC CONCEPTS Elementary Logic A. Connectives > AND (Conjunction): A ‘logical operator that connects two statements, where both statements must be true for the compound statement to be true. > OR (Disjunction): A logical operator that connects two statements, where at least one of the statements must be true for the compound statement to be true. i oi > NOT (Negation): A logical operator that reverses the truth value of a statement. > IMPLIES (Implication): A logical operator that connects two statements, where if the first statement is true, the second statement must also be true for the compound statement to be true. > IF AND ONLY IF (Biconditional): A logical operator that connects two statements, where both statements have the same truth value for the compound statement to be true. B. Quantifiers > Universal quantifier (¥): Indicates that a statement is true for all elements in a particular set or domain. >» Existential quantifier (3): Indicates that there exists at least one element in a particular set or domain for which a statement is true. C. Basic laws of logic >» Commutative law: States that the order of logical connectives does not affect the truth value of a compound statement (¢.g., P AQ QAP), > Associative law: States that the grouping of logical connectives does not affect the truth value of a compound statement (e.g., (P AQ) A R © PA(QAR))-48_| Real Analysis > > > D. Techniques of proof > > > > > > A. Sets and set operations B. Distributive law: Describes how logical connectives can be distributed over other logical connectives (¢.g., P A (Q-.V R) = (PA QV(PAR)). De Morgan's laws: Provide a method for simplifying complex logical expressions by negating and changing the logical connectives (e.g., AP AQ) &-P Vv -Q). Identity laws: Describe the interaction between a statement and its negation, and between a statement and a tautology or contradiction. Double negation: States that the negation of a negation of a statement is equivalent to the original statement (e.g., ~(-P) = P). * Direct proof: Establishes the truth of a statement by a series of logical deductions from previously known facts or axioms. Proof by contradiction: Proves a statement by assuming its negation is true and deriving a contradiction. Proof by contrapositive: Proves a statement by proving the contrapositive of the statement (i.e., proving -Q > —P when trying to prove P = Q). Proof by exhaustion: Proves a statement by considering all possible cases and showing that the statement holds true for each case. Proof by induction: Proves a statement for an infinite number of cases by proving a base case and an inductive step. Sets and Functions Set notation: A way to describe a collection of distinct objects, elements or members, often using curly brackets (e.g., {1, 2, 3}). Set membership: The relation between an element and the set to which it belongs (e.g., 1 € {1, 2, 3}). Subset, proper subset: A set A is a subset of B (A © B) if every element of A is also an element of B. A is a proper subset of B(A ¢ B) if A is a subset of B and there exists at least one element in B that is not inA. ’ Set equality Two sets A and B are equal (A = B) if and only if they have the same elements, ic, AS B and BE A.UNIT 1° Basic Concept | 19 C. Union, intersection, difference, complement > Union (A U B): The set of elements that are in A or B or both. > Intersection (A M B): The set of elements that are in both A and B. > Difference (A - B): The set of elements that are in A but not in B. > Complement (A'): The set of elements that are not in A, relative to a universal set U. D. Power set, Cartesian product: > Power set (P(A)): The set of all subsets of A, including.the empty set and A itself. > Cartesian product (A x B): The set of all ordered pairs (a, b), where ais an element of A and b is an element of B. E. Venn diagrams A graphical representation of sets using circles or other shapes to show the relationships among the sets, such as their unions, intersections, and complements. Relations and Functions A. Relation definition A relation between two sets A and B is a subset of the Cartesian product AxB. B. Domain, range, codomain: > Domain: The set ofall first elements (input values) of the ordered pairs in a relation or function. » Range: The set of all second elements (output values) of the ordered pairs in a relation or function. > Codomain: The set of all possible output values of a function, which may include values not in the range. C. Types of relations (reflexive, symmetric, transitive, etc.): > Reflexive: A relation R on a set A is reflexive if (a, a) € R for every element ain A. > Symmetric: A relation R on a set A is symmetric if for every pair of elements (a, b) € R, it also holds that (b, a) € R. > Transitive: A relation R on a set A is transitive if for every pair of elements (a, b) € R and (b,c) € R, it also holds that (a, c) € R.20_| Real Analysis {p. Equivalence relations and partitions ‘An equivalence relation is a relation that is reflexive, symmetric, and transitive. A partition ofa set A is a collection of non-empty subsets of A such that every element in A belongs to exactly one subset, and the subsets are pairwise disjoint. Function Definition A function is a relation between two sets A and B such that each element in A is related to exactly one element in B. 1. One-to-one (injective) and onto (surjective) functions _ a) Definitions and examples > Injective (one-to-one): A function is injective if every element in the domain is mapped to a unique element in the codomain. > Surjective (onto): A function is surjective if every element in the codomain has a corresponding element in the domain. b) Properties and conditions: A function is bijective (both injective and surjective) if it is both one-to-one and onto. A bijective function has a unique inverse function. 2. One-to-one correspondence (bijective functions) a) Definition and examples: A function is said to establish a one-to-one correspondence between two sets A and B ifit is a bijective function. In other words, each element of A is paired with exactly one element of B, and each element of B is paired with exactly one element of A. b) Properties and conditions: One-to-one correspondences are important because they indicate that the two sets A and B have the same cardinality (size). If a bijective function exists between two sets, then they are said to be in one-to-one correspondence or equipotent. 3. Images and inverse images > a) Definition and notation: Image: Given a function f: A — B, the image of an element x in A is the element f(x) in B. Inverse image: Given a function f: A + B, the inverse image of an element y in B is the set of all elements x in A such that f(x) = y. b) Properties and examples: The inverse image of a set is not necessarily unique. However, for a bijective function, the inverse image of each element in the codomain will have exactly one corresponding element in the domain.UNIT 1 Basic Concept | 21 4, Composition of functions a) Definition and notation: The composition of two functions f: A > B and g: B > C is a new function, denoted by (g ° f)(x) or g(f{x)), that maps elements from A to C by first applying the function f and then applying the function g. b) Properties and examples: The composition of functions is associative, meaning that the composition of three functions, he (ge f), is the same as the composition of two functions, (h ° g) ° f. However, the composition of functions is not generally commutative, meaning that g ef is not necessarily the same as fog. 5. Inverse functions a) Definition and notation: If a function f: A > B has a one-to-one correspondence, it-has an inverse function, denoted by f“): B > A, such that f(y) = x if and only if f{x) = y. b) Properties and conditions: The inverse function exists if and only if| ‘the original function is bijective. The composition of a function and its inverse results in the identity function on the respective domain or codomain (i.e., f(y) = y and f(f()) = x). c) Finding inverse functions: To find the inverse of a given function, ‘one can solve the equation f(x) = y for x in terms of y, and then interchange the roles of x and y. Koy -wViN Lomeli eC ER Oral Q.1. Define conjunction and disjunction of the statement. And write the converse and contrapositive of each of the statements given below: i) The ring of integers is a Euclidean ring. [2 +2 +3] ii) A function is continuous whenever it is differentiable. ili) A set is open provided that each point of the set is an interior point. {Tu 2071] Solution: Conjunction and disjunction are two fundamental logical connectives used in propositional logic. Conjunction (denoted by A or "and") is a binary connective that combines two statements, forming a compound statement that is true ifand only if both the original statements are true.