Lecture 1: Basic Structures 1 PDF

Overview Lecture 1: Basic structures 1 Introduction to the course Sets Relations with other courses September 3, 2024 Sets Subsets...

Overview Lecture 1: Basic structures 1 Introduction to the course Sets Relations with other courses September 3, 2024 Sets Subsets Venn diagrams Set operations Cardinality More complex sets Set identities Generalized unions and intersections Brightspace demo 2/90 Mathematical Structures Part I Overview Introduction Introduction to the course Relations with other courses 3/90 Mathematical Structures 4/90 Mathematical Structures Course organization To attend or not Most of the practical information concerning this course, can be It is not obligatory to come to the lectures. found in the Virtual Course Introduction that is available within the However, if you make the wise decision to come, you are supposed section Content – Start here within Brightspace. to be involved in the lecture. If you didn’t look at this presentation yet, please do so (after this lecture), because it contains a quiz that you need to do in order to Being involved in a live lecture means... get access to the slides later on! – Raise your hand whenever you have a question. If you did look at this presentation, do you have questions about it? – Laptops, smartphones or similar devices are not allowed If you have any questions about it later on, please contact me via ▶ unless you use them for making notes... [email protected] or via Discord (which has as a good side effect ▶... and send these notes to me after the lecture. that all students can see the question and my reaction). In order not to lose too much time, I will only address the most important things during this lecture. 1 Note that mail to [email protected] is delivered at the same mail box, so you can also use that one. 5/90 Mathematical Structures 6/90 Mathematical Structures Notes Brightspace These students promised (implicitly) to send their notes to me on You must enroll for this course via Osiris in order to be enrolled in Monday: Brightspace for this course. – If you haven’t done this yet, do this today! Bram ✓ William ✓ Marijn Brightspace is used for: Ryan ✓ Silke ✓ Wasim – E-mail (make sure to read your official RU-email frequently) Abigail ✓ Serhii Martynas – Announcements – Slides A ✓ means that I have received their notes already. – Assignments – Enrollment for groups for exercise hours ▶ If you haven’t done it yet: register for one of the groups today! – Enrollment for sowiso.nl and discord.com. ▶ If you haven’t done it yet: follow the instructions and register today! 7/90 Mathematical Structures 8/90 Mathematical Structures Any questions so far? Overview Introduction to the course Relations with other courses 9/90 Mathematical Structures 10/90 Mathematical Structures Why do we do this course? Relations with other courses Induction Languages and Automata This course introduces several quite different topics. Sets Each topic is important for other courses in the curriculum of Information Modeling and Databases Functions Predicate logic Induction Computing Science. Relations Relations Semantics and Rewriting Therefore this course is pretty important for your career at this Predicate logic Orderings university... Matrix Calculation Sets Predicate logic... hence failing this course could lead to study delay due to all Functions dependencies. Modular arithmetic Orderings Sets Security Mathematical Structures Combinatorics Functions Functions Induction Functions Cardinality Propositional logic Sets Predicate logic Functions Computability Logic and Applications Sets Predicate logic Induction Functions Imperative Programming Sets Semantics and Correctness Functional Programming 11/90 Mathematical Structures Note that this graph is far from complete!  Part II Overview Sets - basic introduction Sets 13/90 Mathematical Structures 14/90 Mathematical Structures Introduction Naive versus axiomatic set theory Sets are one of the basic building blocks for the types of objects There are basically two ways of defining set theory: considered in discrete mathematics. – Naive set theory as defined by Cantor in 1895 – Sets are important for solving counting problems. – Axiomatic set theory – Programming languages have set operations. It turned out that naive set theory leads to logical inconsistencies Set theory is an important branch of mathematics. and paradoxes: – Many different systems of axioms have been used to develop set – Russell’s paradox (1902): Let S be the set that contains a set x theory. if the set x does not belong to itself, hence S = {x | x ̸∈ x}. Is – In this course we are not concerned with a formal set of axioms S a member of itself? for set theory. Instead, we will use what is called naive set – Compare this with: Henry is a barber who shaves all those, and theory. those only, who do not shave themselves. Does Henry shave himself? Although the naive set theory has its problems, we will use it in this course, because for the ‘simple examples’ in this course it is consistent and it is more intuitive to students. 15/90 Mathematical Structures 16/90 Mathematical Structures Definition of sets Describing a set Definition Roster method A set is an unordered collection of objects, called elements or List all the members of the set between curly braces: members of the set. S = {a, b, c, d} A set is said to contain its elements. The order of the members is not important: We write a ∈ A to denote that a is an element of the set A. The notation a ̸∈ A denotes that a is not an element of the set A. S = {a, b, c, d} = {b, c, a, d} Each distinct object is either a member or not; listing objects Example The natural numbers N. more than once does not change the set: The female students in this class. S = {a, b, c, d} = {a, b, c, b, c, d} The chairs in this room. Ellipses (... ) may be used to describe a set without listing all Remark of the members when the pattern is clear: Note that elements of a set can be sets themselves! S = {a, b, c, d,... , z} 17/90 Mathematical Structures 18/90 Mathematical Structures Describing a set (2) Important sets Set builder notation Natural numbers N = {0, 1, 2, 3,...} Specify the properties that all members must satisfy: Positive natural numbers N+ = {1, 2, 3,...} Integers Z = {... , −3, −2, −1, 0, 1, 2, 3,...} S = {x | x is a positive integer less than 100} + n Z = {1, 2, 3,...} o Positive integers O = {x | x is an odd positive integer less than 10} p Rationals Q = | p ∈ Z and q ∈ Z+ q x ∈ Z+ | x is odd and x < 10  = n o   Positive rationals Q+ = qp | p ∈ Z+ and q ∈ Z+ p Q+ = x ∈ R | x = for some positive integers p and q Real numbers R q Positive real numbers R+ = {x ∈ R | x > 0} Complex numbers C = {p + iq | p ∈ R and q ∈ R} (Note that i is a constant such that i 2 = −1.) Remark Note that the definition of Q+ is different from the definition used on the previous slide. However, the sets are the same. 19/90 Mathematical Structures 20/90 Mathematical Structures Important sets (2) Important sets (3) Note that the look of N, Z and so on maybe a bit different from Let a and b be real numbers. Then what you are used to. [a, b] = {x ∈ R | a ≤ x ≤ b} In fact there are many correct possibilities, for instance: [a, b) = {x ∈ R | a ≤ x < b} (a, b] = {x ∈ R | a < x ≤ b} (a, b) = {x ∈ R | a < x < b} [a, ∞) = {x ∈ R | a ≤ x} (−∞, b] = {x ∈ R | x ≤ b} (a, ∞) = {x ∈ R | a < x} (−∞, b) = {x ∈ R | x < b} The only reason these symbols are used is because you cannot really (−∞, ∞) = R use bold characters on a blackboard... The publisher of the book knows that it is publishing a book and not [a, b] is called the closed interval from a to b. a blackboard and is for that reason simply using N, Z et cetera. (a, b) is called the open interval from a to b. 21/90 Mathematical Structures 22/90 Mathematical Structures Part III Equality Definition Sets - subsets and operations Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if for all x, – x ∈ A implies x ∈ B and – x ∈ B implies x ∈ A. We write A = B if the sets A and B are equal. We write A ̸= B if the sets A and B are not equal. Example {1, 3, 5} = {3, 5, 1} = {1, 3, 3, 3, 5, 5, 5, 5} 23/90 Mathematical Structures 24/90 Mathematical Structures Overview Subsets Subsets Definition The set A is a subset of B if and only if every element of A is also an element of B. Venn diagrams We use the notation A ⊆ B to indicate that set A is a subset of the set B. Set operations We use the notation A ̸⊆ B to indicate that set A is not a subset of the set B. Cardinality Remark Note that for all sets S, S ⊆ S trivially holds. Remark We can use this definition of subsets to give an alternative definition of equality. If A and B are sets then A = B if and only if A ⊆ B and B ⊆ A 25/90 Mathematical Structures 26/90 Mathematical Structures Subsets (2) Subsets (3) When we wish to emphasize that a set A is a subset of a set B but How to prove that A is a subset of B? that A ̸= B, we write A ⊂ B and say that A is a proper subset of B. To prove that A ⊆ B, we need to show that if an arbitrary x For A ⊂ B to be true, it must be the case that A ⊆ B and there belongs to A, then x also belongs to B. must exist an element x of B that is not an element of A. How to prove that A is not a subset of B? To prove that A is not a subset of B, A ̸⊆ B, we have to find a specific element x ∈ A with x ̸∈ B. Such an x is a counterexample to the claim that x ∈ A implies x ∈ B or, in other words, A ⊆ B. How to prove that A = B? To prove that the sets A and B are equal, we typically show that A ⊆ B and B ⊆ A. 27/90 Mathematical Structures 28/90 Mathematical Structures Universal, empty and singleton set Universal, empty and singleton set (2) The Universal set U is the set containing everything currently under Question consideration. Are the sets ∅ and {∅} equal? – Sometimes implicitly stated. – Sometimes explicitly stated. Let’s call for a vote... – Contents depend on the context. Answer The empty set is the set with no elements. No! Do not confuse ∅ with {∅}. The first set contains no elements at all; the second set is a singleton set containing exactly one element, namely – Symbolized ∅, but in the literature the notation {} is the empty set ∅. sometimes2 also used. Any set with exactly one element is called a singleton set. Remark Note that for all sets S, ∅ ⊆ S trivially holds. 2 In this course, {} is not considered correct, so don’t use it! 29/90 Mathematical Structures 30/90 Mathematical Structures Overview Venn diagrams Subsets Sets can be represented graphically using Venn diagrams. In Venn diagrams the universal set U, which contains all the objects Venn diagrams under consideration, is represented by a rectangle. Inside this rectangle, circles or other geometrical figures are used to Set operations represent sets. Sometimes points are used to represent the particular elements of Cardinality the set. Venn diagrams are usually used to indicate the relationships between sets. 31/90 Mathematical Structures 32/90 Mathematical Structures Venn diagrams (2) Venn diagrams (3) Example Note that the letter ‘y’ is sometimes considered a vowel and sometimes Let U be the universal set consisting of the 26 lowercase letters of the considered a consonant in English. English alphabet. Inside this rectangle we draw a circle to represent V , For the theory of sets it doesn’t matter what it is. the set of all vowels in the English alphabet. Inside this circle we indicate the elements of V with points. For the theory of Venn diagrams, this dilemma shows us that there is no way to represent an object that is sometimes an element of a set and sometimes not. 33/90 Mathematical Structures 34/90 Mathematical Structures Venn diagrams (4) Overview Example Subsets Let U be some universal set and let A and B be subsets of U. The Venn diagram shows that A is a subset of B. Venn diagrams Set operations Cardinality In this diagram it is not clear whether A is a proper subset of B or not. If A is a proper subset of B, we could visualize this by adding a point in B which is not in A. 35/90 Mathematical Structures 36/90 Mathematical Structures Set operations Set operations (2) Definition Definition Let A and B be sets. Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set that The intersection of the sets A and B, denoted by A ∩ B, is the set contains those elements that are either in A or in B, or in both. that contains those elements in both A and B. Remark Remark An element x belongs to the union of the sets A and B if and only An element x belongs to the intersection of the sets A and B if and if x belongs to A or x belongs to B. only if x belongs to A and x belongs to B. Hence, A ∪ B = {x | x ∈ A or x ∈ B}. Hence, A ∩ B = {x | x ∈ A and x ∈ B}. The shaded part indicates the union of A and B: The shaded part indicates the intersection of A and B: 37/90 Mathematical Structures 38/90 Mathematical Structures Set operations (3) Set operations (4) Definition Definition Two sets are called disjoint if their intersection is the empty set. Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing Question How do you represent that A and B are disjoint in a Venn diagram? those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A. 39/90 Mathematical Structures 40/90 Mathematical Structures Set operations (5) Set operations (6) Remark Definition The difference of sets A and B is sometimes also denoted by A \ B. Let U be the universal set. The complement of the set A, denoted by A, is the complement of An element x belongs to the difference of A and B if and only if A with respect to U. x ∈ A and x ̸∈ B. Therefore, the complement of the set A, denoted A, is U − A. Hence, A − B = {x | x ∈ A and x ̸∈ B}. Remark The shaded part indicates the difference of A and B: An element x belongs to A if and only if x ̸∈ A. Hence, A = {x ∈ U | x ̸∈ A}. The shaded part indicates the complement of A: 41/90 Mathematical Structures 42/90 Mathematical Structures Overview Cardinality Subsets Definition Let S be a set. Venn diagrams If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the Set operations cardinality of S. The cardinality of S is denoted by | S |, but in the literature the Cardinality notation #S is also3 used. Definition A set is said to be infinite if it is not finite. Remark Next week we will extend the notion of cardinality to infinite sets. 3 In this course, #S is not considered correct, so don’t use it! 43/90 Mathematical Structures 44/90 Mathematical Structures  Part IV Cardinality (2) Example Sets - complex sets and identities If S is the set of letters of the English alphabet, then | S | = 26. The set of integers is infinite. | {1, 2, 3} | = 3 |∅| = 0 | {∅} | = 1 45/90 Mathematical Structures 46/90 Mathematical Structures Overview Power set More complex sets Definition Given a set S, the power set of S is the set of all subsets of the set S. Set identities The power set of S is denoted by P (S). Generalized unions and intersections Example If A = {a, b} then P (A) = {∅, {a} , {b} , {a, b}}. If a set S has n elements, then the cardinality of P (S) is 2n. Because for every element we have to choose between being in the set or not. For each set S it holds that ∅ ∈ P (S) and S ∈ P (S). Furthermore ∅ ⊆ P (S), but S ̸⊆ P (S). (Look carefully at the number of curly braces within P (S).) P (∅) = {∅} because ∅ is the only subset of ∅. P ({∅}) = {∅, {∅}} because ∅ and {∅} are the only subsets of {∅}. 47/90 Mathematical Structures 48/90 Mathematical Structures Cartesian products Cartesian products (2) Definition Definition The ordered n-tuple (a1 , a2 ,... , an ) is the ordered collection that Let A and B be sets. has a1 as its first element, a2 as its second element,... , and an as The Cartesian product of A and B, denoted by A × B, is the set of its nth element. all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence, A × B = {(a, b) | a ∈ A and b ∈ B}. Remark Two ordered n-tuples are equal if and only if each corresponding Remark pair of their elements is equal. Note that the Cartesian products A × B and B × A are not equal, In other words, (a1 , a2 ,... , an ) = (b1 , b2 ,... , bn ) if and only if unless ai = bi , for i = 1, 2,... , n. – A = ∅ or B = ∅, so that A × B = ∅, or – A = B. In particular, ordered 2-tuples are called ordered pairs. Example The ordered pairs (a, b) and (c, d) are equal if and only if a = c Let A = {a, b} and B = {1, 2, 3}. and b = d. Then A × B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)} Note that (a, b) and (b, a) are not equal unless a = b. and B × A = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}. 49/90 Mathematical Structures 50/90 Mathematical Structures Cartesian products (3) Cartesian products (4) Definition Example The Cartesian product of the sets A1 , A2 ,... , An , denoted by Let A = {a, b}, B = {1, 2, 3} and C = {∅}. A1 × A2 × · · · × An , is the set of ordered n-tuples (a1 , a2 ,... , an ) Then where ai belongs to Ai for i = 1, 2,... , n. A × B × C = {(a, 1, ∅), (a, 2, ∅), (a, 3, ∅), (b, 1, ∅), (b, 2, ∅), (b, 3, ∅)} In other words, and (A × B) × C = A1 × A2 × · · · × An = {(a1 , a2 ,... , an ) | ai ∈ Ai for i = 1, 2,... , n}. {((a, 1), ∅), ((a, 2), ∅), ((a, 3), ∅), ((b, 1), ∅), ((b, 2), ∅), ((b, 3), ∅)}. Remark Note that when A, B, and C are sets, (A × B) × C is usually not the same as A × B × C. We use the notation A2 to denote A × A, the Cartesian product of the set A with itself. More generally, An = {(a1 , a2 ,... , an ) | ai ∈ A for i = 1, 2,... , n}. 51/90 Mathematical Structures 52/90 Mathematical Structures Overview Set identities Using these set operations we are now able to prove several set More complex sets identities: Set identities Generalized unions and intersections 53/90 Mathematical Structures 54/90 Mathematical Structures Set identities (2) Set identities (3) And the rest of the list: Question How can we prove these identities? Answer By using the definitions! More precisely: By showing that the set on the left hand side is a subset of the one on the right hand side and vice versa. By using membership tables. Remark Note that in general Venn diagrams are not suitable for proofs, because the semantics are not precise enough! 55/90 Mathematical Structures 56/90 Mathematical Structures Set identities (4) Set identities (5) Remark Example Note that for some of these identities we need De Morgan’s laws We try to prove the first absorption law: A ∪ (A ∩ B) = A. for propositional logic, which are explained in Chapter 1 in the book, We start by showing that A ∪ (A ∩ B) ⊆ A. but will only be explained in lecture 3 in this course. So don’t worry if you cannot understand the proof in the book at this stage; try to 1. Assume x ∈ A ∪ (A ∩ B). (We now have to show that x ∈ A.) understand it again in a few weeks. 2. Then x ∈ A or x ∈ A ∩ B by definition of ∪. 3. Hence we have to examine two cases: a. Case x ∈ A. Then we are immediately done! b. Case x ∈ A ∩ B. Then x ∈ A and x ∈ B by definition of ∩. So in particular x ∈ A and we are also done. 4. So in both cases we can show that x ∈ A, hence we may conclude that x ∈ A. 57/90 Mathematical Structures 58/90 Mathematical Structures Set identities (6) Set identities (7) Example (continued) Example Now we try to prove that A ⊆ A ∪ (A ∩ B). We now try to prove the second distributive law A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) by using a membership table. 1. Assume x ∈ A. (We now have to show that x ∈ A ∪ (A ∩ B).) But how do we create a membership table? 2. Then automatically x ∈ A or x ∈ A ∩ B. A membership table starts with a column for each set under 3. Hence x ∈ A ∪ (A ∩ B) by definition of ∪. consideration. In this case we get the columns for the sets A, B and Hence A ∪ (A ∩ B) = A. C. For each element x ∈ U we have to express its memberships with respect to the three sets A, B and C in a row. For instance, such an element x could be a member of A and C but not of B. We represent this by writing a ‘1’ in the columns of A and C and a ‘0’ in the column of B. If you do this carefully, you will notice that there are 2 · 2 · 2 = 8 different possibilities. Note that for each set you have to see whether x is a member of it or not, hence each set gives two possibilities. 59/90 Mathematical Structures 60/90 Mathematical Structures Set identities (8) Set identities (9) Example (continued) Example (continued) Now we add columns for each set operation being used to get to The final table is shown below: the final sets under consideration. In this case B ∪ C , A ∩ (B ∪ C ), A ∩ B, A ∩ C and (A ∩ B) ∪ (A ∩ C ). Now we complete each row by writing a ‘1’ if the element is a member of the set in a given column and a ‘0’ if not. Finally, we compare the columns of the two sets under examination. In this case the columns for A ∩ (B ∪ C ) and (A ∩ B) ∪ (A ∩ C ). If these columns have the exact same content, then the two sets are the same! Let’s try to make such a membership table for A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) on the blackboard... Note that the columns for A ∩ (B ∪ C ) and (A ∩ B) ∪ (A ∩ C ) are indeed equal and hence we have A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ). 61/90 Mathematical Structures 62/90 Mathematical Structures Overview Generalized unions and intersections So far, we have only defined binary unions and intersections. More complex sets However, because unions and intersections of sets satisfy associative laws, the sets A ∪ B ∪ C and A ∩ B ∩ C are well defined: the Set identities meaning of this notation is unambiguous when A, B, and C are sets. Hence, we do not have to use parentheses to indicate which Generalized unions and intersections operation comes first because A ∪ (B ∪ C ) = (A ∪ B) ∪ C and A ∩ (B ∩ C ) = (A ∩ B) ∩ C. Note that A ∪ B ∪ C contains those elements that are in at least one of the sets A, B, and C , and that A ∩ B ∩ C contains those elements that are in all of A, B, and C. 63/90 Mathematical Structures 64/90 Mathematical Structures Generalized unions and intersections (2) Generalized unions and intersections (3) Definition Definition The union of a collection of sets is the set that contains those The intersection of a collection of sets is the set that contains elements that are members of at least one set in the collection. those elements that are members of all the sets in the collection. [n \n Finite case: A1 ∪ A2 ∪ · · · ∪ An = Ai Finite case: A1 ∩ A2 ∩ · · · ∩ An = Ai i=1 i=1 ∞ [ ∞ \ Infinite case: A1 ∪ A2 ∪ · · · = Ai Infinite case: A1 ∩ A2 ∩ · · · = Ai i=1 i=1 [ \ More generally, when I is a set, Ai is used to denote the union More generally, when I is a set, Ai is used to denote the i∈I i∈I of the sets Ai for i ∈ I. intersection of the sets Ai for i ∈ I. Note that we have Note that we have [ \ Ai = {x | there exists an i ∈ I such that x ∈ Ai } Ai = {x | for all i ∈ I holds that x ∈ Ai } i∈I i∈I 65/90 Mathematical Structures 66/90 Mathematical Structures Overview Brightspace demo Brightspace demo Log in Group enroll (see Course Description) View assignment Create solutions using www.overleaf.com Submit solutions See the details in the handout! 67/90 Mathematical Structures 68/90 Mathematical Structures Brightspace demo (2) Brightspace demo (3) Log in at brightspace.ru.nl. Go to Assignments in the Activities menu. 69/90 Mathematical Structures 70/90 Mathematical Structures Brightspace demo (4) Brightspace demo (5) Click on the name of the assignment. Read the instructions and make sure that you know the submission deadline. Download files ms-assignment-01.pdf and ms-template-01.tex. 71/90 Mathematical Structures 72/90 Mathematical Structures Brightspace demo (6) Brightspace demo (7) Go to www.overleaf.com, register if not done yet, and create a Blank Choose a name for the project including your student number like Project. ms-s1234567. (In the pictures I chose a different name, but in the end it turned out that it would have been better to use a different name.) 73/90 Mathematical Structures 74/90 Mathematical Structures Brightspace demo (8) Brightspace demo (9) Upload the file ms-template-01.tex. Rename the file into something logical. 75/90 Mathematical Structures 76/90 Mathematical Structures Brightspace demo (10) Brightspace demo (11) Put your name, student number and tutorial group at the proper place. Recompile 77/90 Mathematical Structures 78/90 Mathematical Structures Brightspace demo (12) Brightspace demo (13) Add your solutions to the questions by modifying the text that is already Recompile and download the result. Apparently, at least on my system, given in the template. Usually, the template provides some examples to the file name of the file being downloaded is based upon the project help you with LATEX. name and not on the name of the.tex file which is being compiled. For this reason I recommend a project name like ms-s1234567. 79/90 Mathematical Structures 80/90 Mathematical Structures Brightspace demo (14) Brightspace demo (15) Go back to Brightspace to the submission folder page. Press on Add a file and add the file that was just downloaded from www.overleaf.com. 81/90 Mathematical Structures 82/90 Mathematical Structures Brightspace demo (16) Brightspace demo (17) If you are really sure that you added the proper file, press the Submit You will get a confirmation page that you submitted something. Because button. we don’t know yet how stable the submission module is in Brightspace, you are advised to keep a.pdf copy of this confirmation page! 83/90 Mathematical Structures 84/90 Mathematical Structures Brightspace demo (18) Reading list You are done and may now continue with the homework for other courses! The slides Remark Section 2.1, except In the case that even after thinking twice you still found out that you – 2.1.7 Using Set Notation with Quantifiers uploaded the wrong version, just upload a better version. Recall that the – 2.1.8 Truth Sets and Quantifiers system only stores the last version, so be careful! Section 2.2, except – Example 11 – Example 12 – 2.2.4 Computer Representation of Sets 85/90 Mathematical Structures 86/90 Mathematical Structures Notations (1) Notations (2) C Complex numbers, $\mathbb{C}$ a ∈ A a is an element of A, $a \in A$ A 2 A × A, $A^2$ A ̸= B A is not equal to B, $A \neq B$ An A × A × · · · × A (n times), $A^n$ a ̸∈ A a is not an element of A, $a \not\in A$ ∞ #S cardinality of S, $\#S$ \ Ai A1 ∩ A2 ∩ · · · , $\displaystyle\bigcap^{\infty}_{i=1} A_i$ | S | cardinality of S, $\abs{S}$ i=1 \ A × B Cartesian product of A and B, $A \times B$ Ai intersection of the sets Ai for i in I , A complement of A with respect to U, $\overline{A}$ i∈I $\displaystyle\bigcap_{i\in I} A_i$ [a, b] closed interval, $[a,b]$ n \ A − B difference of A and B, $A - B$ Ai A1 ∩ A2 ∩ · · · ∩ An , $\displaystyle\bigcap^{n}_{i=1} A_i$ A \ B difference of A and B, $A \setminus B$ i=1 ∅ Empty set, $\emptyset$ A ∩ B intersection of A and B, $A \cap B$ A = B A is equal to B, $A = B$ ∞ infinity, $\infty$ 87/90 Mathematical Structures 88/90 Mathematical Structures Notations (3) Notations (4) ∞ N Natural numbers, $\mathbb{N}$ [ Ai A1 ∪ A2 ∪ · · · , $\displaystyle\bigcup^{\infty}_{i=1} A_i$ (a, b) open interval, $(a,b)$ i=1 n P (S) power set of S, ${\cal P}(S)$ [ Ai A1 ∪ A2 ∪ · · · ∪ An , $\displaystyle\bigcup^{n}_{i=1} A_i$ Q Rationals, $\mathbb{Q}$ i=1 R Real numbers, $\mathbb{R}$ A ∪ B union of A and B, $A \cup B$ A ̸⊆ B A is not a subset of B, $A \not\subseteq B$ Z Integers, $\mathbb{Z}$ A ⊆ B A is a subset of B, $A \subseteq B$ A ⊂ B A is a proper subset of B, $A \subset B$ (a1 , a2 ,... , an ) ordered n-tuple, $(a_1,a_2,\dots,a_n)$ [ Ai union of the sets Ai for i in I , i∈I $\displaystyle\bigcup_{i\in I} A_i$ 89/90 Mathematical Structures 90/90 Mathematical Structures