Handout on Shorthand

Math 295. Handout on Shorthand The phrases “for all”, “there exists”, and “such that” are used so frequently in mathematics that we have found it useful to adopt the following shorthand. The symbol ∀ means “for all” or “for any”. The symbol ∃ means “there exists”. Finally we abbreviate the phrases “such that” and “so that” by the symbol 3 or simply “s.t.”. When mathematics is formally written (as in our text), the use of these symbols is often suppressed. In this class, you may use them freely. To illustrate the use of these symbols, we now state properties (P1) - (P9) of chapter one. Let N denote the set of “numbers” (whatever that may mean, I simply need to be consistent with the notation of chapter one in order to avoid confusion). Note that N is not to be confused with N, the set of natural numbers. I remind you that N has yet to be rigorously discussed, we are simply assuming familiarity with it so as to produce general expectations of how life should go. (P1) ∀ a, b, c ∈ N a + (b + c) = (a + b) + c (P2) ∃ 0 ∈ N 3 ∀ a ∈ N a+0=0+a=a (P3) ∀ a ∈ N ∃ − a ∈ N 3 a + (−a) = (−a) + a = 0 (P4) ∀ a, b ∈ N a+b=b+a (P5) ∀ a, b, c ∈ N a · (b · c) = (a · b) · c (P6) ∃ 1 ∈ N 3 1 6= 0 and ∀ a ∈ N (P7) ∀ a ∈ N if a 6= 0, then ∃ a−1 a·1=1·a=a ∈N3 a · a−1 = a−1 · a = 1 (P8) ∀ a, b ∈ N a·b=b·a (P9) ∀ a, b, c ∈ N a · (b + c) = a · b + a · c 2 1. Unions, Intersections and Complements Here are some laws about intersections and unions you should know. For completeness, I included some definitions. You may assume anything you see written here in your homework despite not being explicitly proven in class. It may be beneficial to prove some of the facts for yourself anyway as practice. For all sets A, B and C we make the following definitions and statements. 1.1. Definitions. For any sets A and B we can assume there is a set S such that A, B ⊂ S. A ∪ B := {x ∈ S | x ∈ A or x ∈ B} A ∩ B := {x ∈ A | x ∈ B} The resultant sets A ∪ B and A ∩ B are independent of the choice of a set S, making the two sets well-defined. 1.2. Commutativity. A ∪ B = B ∪ A A∩B =B∩A 1.3. Associativity. (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) 1.4. The Empty Set. A ∪ ∅ = A A∩∅=∅ 1.5. Distributivity. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 1.6. Generalization. For any collection of sets A, we can assume there exists a set S with A ⊂ S for all A ∈ A. [ A := {x ∈ S | x ∈ A for some A ∈ A} A∈A \ A := {x ∈ S | x ∈ A for all A ∈ A} for A 6= ∅ A∈A These operations are called arbitrary union and arbitrary intersection respectively. Note that the arbitrary intersection is not defined for A = ∅. This is because the arbitrary intersection in this case would not be well-defined (dependent on the choice of a set S). If for some integers a, b such that a < b we have A = {Aa , Aa+1 . . . , Ab }, for some sets Aa , Aa+1 , . . . , Ab , the following convention is used. b [ [ Ai := A i=a b \ i=a A∈A Ai := \ A A∈A Further if for some integer a, there are sets Aa , Aa+1 , Aa+2 , . . . where A = {Aa , Aa+1 , Aa+2 , . . .}, this convention is used. 3 ∞ [ i=a ∞ \ Ai := [ A A∈A Ai := i=a \ A A∈A 1.7. Generalized Distributivity. For a collection of sets A we have that [ [ (B ∩ A) A= B∩ A∈A A∈A 1.8. Complement. When we consider a set A to be a subset of a set E we can define the complement of A relative to E to be E \ A := {x ∈ E | x ∈ / A} Sometimes this is instead denoted (E − A). When the set E is clear from context it will sometimes be denoted Ac or simply A0 . 1.9. De Morgan’s Laws. For two sets A and B which are subsets of a set E we have the following (A ∩ B)c = Ac ∪ B c (A ∪ B)c = Ac ∩ B c 2. Logic Statements 2.1. Definitions. Given a statement of the form ”if p then q” (or ”p ⇒ q”) there are a set of associated statements which are useful to know for proofs. For example the following Converse: ”if q then p” (q ⇒ p) Inverse: ”if not p then not q” (¬p ⇒ ¬q) Contrapositive: ”if not q then not p” (¬q ⇒ ¬p) Biconditional: ”p if and only if q” (p ⇔ q) Contradiction: ”There exists p such that not q” (∃p ⇒ ¬q) Note that these are all defined in relation to an original statement ”if p then q”. The statements are interrelated in various ways; for instance, the inverse of the converse is the contrapositive, etc. 2.2. Example. Let P be a polygon. Consider the statement ”if P is a square then P is a rectangle”. We then have the following Converse: ”if P is a rectangle then P is a square” Inverse: ”if P is not a square then P is not a rectangle” Contrapositive: ”if P is not a rectangle then P is not a square” Biconditional: ”P is a square if and only if P is a rectangle” Contradiction: ”There exists a square P such that P is not a rectangle” 4 2.3. Truth. As you can probably tell from the example, not all associated statements are true if the original statement is true. However, we do know the following facts: (1) The contrapositive is true exactly when the statement is true. (2) The statement is true exactly when the contradiction is false. (3) The converse and inverse are independent from the statement (i.e. could be either true or false regardless of the truth of the original statement) (4) The converse is true exactly when the inverse is true. (5) The biconditional is true exactly when both the statement and its converse are true (which is equivalent to the statement and its inverse being true or the contrapositive and the converse being true or the contrapositive and the inverse being true) (6) The biconditional is then false exactly when either the statement or its converse are false (and so on) Further statements about truth can be derived from the above. All the above listed statements can be useful in proofs. In some problems, it may be easier to prove the contrapositive than the original statement, but by 1, proving the contrapositive is sufficient for proving the statement. Statement 2 is equivalent to proof by contradiction. Forgetting statement 3 is a common logical mistake. Statement 5 describes typical ways of attacking an ”if and only if” problem.