 • Date:16 Sep 2020
• Views:0
• Pages:10
• Size:204.52 KB

Share Pdf : Basic Concepts Of Set Theory Functions And Relations

Download and Preview : Basic Concepts Of Set Theory Functions And Relations

Report CopyRight/DMCA Form For : Basic Concepts Of Set Theory Functions And Relations

Transcription:

Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 2, The membership criteria for a set must in principle be well defined and not vague. If we have a set and an object it is possible that we do not know whether this object. belongs to the set or not because of our lack of information or knowledge E g The set. of students in this room over the age of 21 a well defined set but we may not know who. is in it But the answer should exist at any rate in principle It could be unknown but it. should not be vague If the answer is vague for some collection we cannot consider that. collection as a set Another thing If we have a set then for any two elements of it x and y. it should not be vague whether x y or they are different If they are identical then they. are not actually two elements of it the issue really arises when we have two descriptions. of elements and we want to know whether those descriptions describe the same element. or two different elements, For example is the letter q the same thing as the letter Q Well it depends on what. set we are considering If we take the set of the 26 letters of the English alphabet then q. and Q are the same element If we take the set of 52 upper case and lower case letters of. the English alphabet then q and Q are two distinct elements Either is possible but we. have to make it clear what set we are talking about so that we know whether or not q Q. Sometimes we simply assume for the sake of examples that a description is not. vague when perhaps for other purposes it would be vague e g the set of all red objects. Sets can be finite or infinite, There is exactly one set the empty set or null set which has no members at all. A set with only one member is called a singleton or a singleton set Singleton of a. Notation A B C for sets a b c or x y z for members. b A if b belongs to A B A if both A and B are sets and B is a member of A. and c A if c doesn t belong to A,is used for the empty set. 1 2 Specification of sets,There are three main ways to specify a set.
1 by listing all its members list notation, 2 by stating a property of its elements predicate notation. 3 by defining a set of rules which generates defines its members recursive rules. List notation The first way is suitable only for finite sets In this case we list names of. elements of a set separate them by commas and enclose them in braces. Examples 1 12 45 George Washington Bill Clinton a b d m. Three dot abbreviation 1 2 100 See xeroxed preliminaries pp xxii xxiii. 1 2 3 4 this is not a real list notation it is not a finite list but it s common practice. as long as the continuation is clear, Note that we do not care about the order of elements of the list and elements can be listed. several times 1 12 45 12 1 45 1 and 45 12 45 1 are different representations of. the same set see below the notion of identity of sets. Set Theory Basics doc, Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 3,Predicate notation Example,x x is a natural number and x 8. Reading the set of all x such that x is a natural number and is less than 8. So the second part of this notation is a property the members of the set share a condition. or a predicate which holds for members of this set. Other examples,x x is a letter of Russian alphabet.
y y is a student of UMass and y is older than 25,General form. x P x where P is some predicate condition property. The language to describe these predicates is not usually fixed in a strict way But it is. known that unrestricted language can result in paradoxes Example x x x Russell s. paradox see the historical notes about it on pp 7 8 The moral not everything that. looks on the surface like a predicate can actually be considered to be a good defining. condition for a set Solutions type theory other solutions we won t go into them If. you re interested see Chapter 8 Sec 2, Recursive rules Always safe Example the set E of even numbers greater than 3. b if x E then x 2 E,c nothing else belongs to E, The first rule is the basis of recursion the second one generates new elements from the. elements defined before and the third rule restricts the defined set to the elements. generated by rules a and b The third rule should always be there sometimes in practice it. is left implicit It s best when you re a beginner to make it explicit. 1 3 Identity and cardinality, Two sets are identical if and only if 2 they have exactly the same members So A B iff for. every x x A x B, For example 0 2 4 x x is an even natural number less than 5.
From the definition of identity follows that there exists only one empty set its identity is. fully determined by its absence of members Note that empty list notation is not usually. used for the empty set we have a special symbol for it. The number of elements in a set A is called the cardinality of A written A The. cardinality of a finite set is a natural number Infinite sets also have cardinalities but they. are not natural numbers We will discuss cardinalities of infinite sets a little later Chapter. Be careful about if and only if its abbreviation is iff See Preliminaries p xxiii. Set Theory Basics doc, Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 4,1 4 Subsets, A set A is a subset of a set B iff every element of A is also an element of B Such a relation. between sets is denoted by A B If A B and A B we call A a proper subset of B and. write A B Caution sometimes is used the way we are using. Both signs can be negated using the slash through the sign. a b d a b e and a b d a b e a b a b but a b a b, Note that the empty set is a subset of every set A for every set A Why. Be careful about the difference between member of and subset of. 1 5 Power sets, The set of all subsets of a set A is called the power set of A and denoted as A or. sometimes as 2A,For example if A a b A a b a b,From the example above a A a A a A.
1 6 Operations on sets union intersection, We define several operations on sets Let A and B be arbitrary sets. The union of A and B written A B is the set whose elements are just the elements of. A or B or of both In the predicate notation the definition is. A B def x x A or x B,Examples Let K a b L c d and M b d then. K L a b c d,K L M K L M a b c d, The intersection of A and B written A B is the set whose elements are just the. elements of both A and B In the predicate notation the definition is. A B def x x A and x B,K L M K L M,Set Theory Basics doc. Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 5,1 7 More operations on sets difference complement.
Another binary operation on arbitrary sets is the difference A minus B written A B. which subtracts from A all elements which are in B Also called relative complement. the complement of B relative to A The predicate notation defines this operation as. A B def x x A and x B,Examples using the previous K L M. A B is also called the relative complement of B relative to A This operation is to. be distinguished from the complement of a set A written A which is the set consisting of. everything not in A In predicate notation,A def x x A. It is natural to ask where do these objects come from which do not belong to A In. this case it is presupposed that there exists a universe of discourse and all other sets are. subsets of this set The universe of discourse is conventionally denoted by the symbol U. Then we have,1 8 Set theoretic equalities, There are a number of general laws about sets which follow from the definitions of set. theoretic operations subsets etc A useful selection of these is shown below They are. grouped under their traditional names These equations below hold for any sets X Y Z. 1 Idempotent Laws,a X X X b X X X,2 Commutative Laws. a X Y Y X b X Y Y X,3 Associative Laws,a X Y Z X Y Z b X Y Z X Y Z.
4 Distributive Laws,a X Y Z X Y X Z b X Y Z X Y X Z. Set Theory Basics doc, Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 6,5 Identity Laws,b X U U d X U X,6 Complement Laws. a X X U c X X,b X X d X Y X Y,7 DeMorgan s Laws,a X Y X Y b X Y X Y. 8 Consistency Principle,a X Y iff X Y Y b X Y iff X Y X.
Chapter 2 Relations and Functions, Much of mathematics can be built up from set theory this was a project which was. carried out by philosophers logicians and mathematicians largely in the first half of the. 20th century Whitehead and Russell were among the pioneers with their great work. Principia Mathematica Defining mathematical notions on the basis of set theory does not. add anything mathematical and is not of particular interest to the working. mathematician but it is of great interest for the foundations of mathematics showing how. little needs to be assumed as primitive, We illustrate some bits of that project here with some basic set theoretic definitions of. ordered pairs relations and functions along with some standard notions concerning. relations and functions,2 1 Ordered pairs and Cartesian products. As we see there is no order imposed on the elements of a set To describe functions. and relations we will need the notion of an ordered pair written a b for example in. which a is considered the first member element and b is the second member element of. the pair So in general a b b a Whereas for a set a b b a. Is there a way to define ordered pairs in terms of sets You might think not since sets. are themselves unordered But there are in fact various ways it can be done Here is one. way to do it usually considered the most conventional. The ordered pair can be defined as follows,Definition a b def a a b. Set Theory Basics doc, Ling 310 adapted from UMass Ling 409 Partee lecture notes.
March 1 2006 p 7, How can we be sure that that definition does the job it s supposed to do What s crucial is that for. every ordered pair there is indeed exactly one corresponding set of the form a a b and two. different ordered pairs always have two different corresponding sets We won t try to prove that. that holds but it does, There would be nothing wrong with taking the notion of ordered pair as another. primitive notion alongside the notion of set But mathematicians like seeing how far they. can reduce the number of primitives and it s an interesting discovery to see that the notion. of order can be defined in terms of set theory, Cartesian product Suppose we have two sets A and B and we form ordered pairs by. taking an element of A as the first member of the pair and an element of B as the second. member The Cartesian product of A and B written A B is the set consisting of all such. pairs The predicate notation defines it as,A B def x y x A and y B. What happens if either A or B is Suppose A a b What is A. Here are some examples of Cartesian products,Let K a b c and L 1 2 then.
K L a 1 a 2 b 1 b 2 c 1 c 2,L K 1 a 2 a 1 b 2 b 1 c 2 c. L L 1 1 1 2 2 1 2 2, An aside on cardinality and why Cartesian products are called products the Cartesian. part comes from the name of Ren Descartes their inventor Look at the cardinalities of. the sets above and see if you can figure out in general what the cardinality of the set A B. will be given the cardinalities of sets A and B, What about ordered triples The definition of ordered pairs can be extended to ordered. triples and in general to ordered n tuples for any natural n For example ordered triples are. usually defined as,a b c def a b c, And for three sets A B and C the Cartesian product can be defined as. A B C def A B C, In the case when A B C a special notation is used A A A2 A A A A3.
etc And we put A1 def A This notation mimics the notation used for multiplication and. exponents It can because the parallels hold quite uniformly. Set Theory Basics doc, Ling 310 adapted from UMass Ling 409 Partee lecture notes. March 1 2006 p 8,2 2 Relations, In natural language relations are a kind of links existing between objects Examples. mother of neighbor of part of is older than is an ancestor of is a subset of etc. These are binary relations Formally we will define relations between elements of sets. We may write Rab or aRb for a bears R to b And when we formalize relations as. sets of ordered pairs of elements we will officially write a b R. If A and B are any sets and R A B we call R a binary relation from A to B or a binary. relation between A and B A relation R A A is called a relation in or on A. The set dom R a a b R for some b is called the domain of the relation R and the. set range R b a b R for some a is called the range of the relation R. We may visually represent a relation R between two sets A and B by arrows in a. diagram displaying the members of both sets In Figure 2 1 in PtMW Partee ter Meulen. and Wall A a b B c d e and the arrows represent a set theoretic relation R. a d a e b c,see Fig 2 1 p 29, Let us consider some operations on relations The complement of a relation. R A B is defined as,R def A B R, Note that what the complement of a relation is depends on what universe we are. considering A given relation may certainly be a subset of more than one Cartesian. product and its complement will differ according to what Cartesian product we are taking. to be the relevant universe, What is the complement of the relation R a d a e b c on the universe a b.
Set Theory Basics doc The membership criteria for a set must in principle be well defined and not vague If we have a set and an object it is possible that we do not know whether this object belongs to the set or not because of our lack of information or knowledge E g The set of students in this room over the age of 21 a well defined set but we may not know who is in it But the