Sunday 20 November 2011

Sets, Bags and Sequences


Elementary or "naive" set theory is used to define basic mathematical structures. A set is an arbitrary collection of elements, which may be real or imaginary, physical or abstract. In mathematics, sets are usually composed of abstract things like numbers and points, but one can also talk about sets of apples, oranges, people, or canaries. In computer science, sets are composed of bits, bytes, pointers, and blocks of storage. In many applications, the elements are never defined, but are left as abstractions that could be represented in many different ways in the human brain, on a piece of paper, or in computer storage.

Curly braces are used to enclose a set specification. For small, finite sets, the specification of a set can be an exhaustive list of all its elements:
{1, 97, 63, 12}.

This specifies a set consisting of the four integers 1, 97, 63, and 12. Since the order of listing the elements is immaterial, the following specification is equivalent to the one above:
{12, 63, 97, 1}.
If the set is very large, like the set of all mammals, a complete listing is impossible. It is hard enough to enumerate all the people in a single city, let alone all the cats, dogs, mice, deer, sheep, and kangaroos in the entire world. For such sets, the specification must state some rule or property that determines which elements are in the set:
{x | vertebrate(x) and warmBlooded(x) and hasHair(x) and lactiferous(x)}
This specification may be read the set of all x such that x is vertebrate, x is warm blooded, x has hair, and x is lactiferous. A given set may be specified in more than one way. The following four specifications all determine the same set:
{1, 2, 3}
{x | x is an integer and 0<x<4}
{x | x is a positive integer, x divides 6, and xnot =6}
{x | x=1 or x=2 or x=3}

A set specification that lists all elements explicitly is called a definition by extension. A specification that states a property that must be true of each element is called a definition by intension. Only finite sets can be defined by extension. Infinite sets must always be defined by intension or by some operations upon other infinite sets that were previously defined by intension.


In any theory using sets, there are two privileged sets: the empty set {}, which contains no elements at all, and the universal set U, which contains every element that is being considered. In mathematical discussions, for example, the universal set may be the set of all integers Z or the set of all real numbers R. In most discussions, the universal set is usually defined at the beginning of the presentation. Thereafter, other sets are built up from U: subsets of U, pairs of elements of U, sets of sets of elements from U, etc.

Of all the operators that deal with sets, the most basic is element of, which states whether a particular element is in a set: the notation xelement ofS means that x is an element of the set S; it may also be read x is a member of the set S or simply x is in S. All other operators on sets can be defined in terms of element of. Let A and B be any two sets. Following are the common operators of set theory; listed for each one is its name, standard symbol, informal English definition, and formal definition in terms of element of:
  • Union. AunionB is the set that contains all the elements in either A or B or both:
    AunionB = {x | xelement ofA or xelement ofB}.
  • Intersection. AintersectionB is the set that contains all the elements that are in both A and B:
    AintersectionB = {x | xelement ofA and xelement ofB}.
  • Complement. -A is the set that contains everything in the universal set that is not in A:
    -A  = {x | xelement ofU and not xelement ofA}.
  • Difference. A-B is the set that contains all the elements that are in A but not in B:
    A-B = {x | xelement ofA and not xelement ofB}.
  • Subset. AsubsetB means that every element of A is also an element of B:
    If xelement ofA, then xelement ofB.
    
    In particular, every set is a subset of itself: AsubsetA.
  • Proper subset. A is a proper subset of B if AsubsetB and there is at least one element of B that is not in A:
    If xelement ofA,
    then xelement ofB and there exists some b
    where belement ofB and not belement ofA.
  • Superset. A is a superset of B if B is a subset of A.
  • Empty set. The empty set has no elements: for every x, it is false that xelement of{}. The empty set is a subset of every set, including itself: for every set A, {}subsetA.
  • Disjoint sets. Two sets A and B are said to be disjoint if they have no common elements; i.e., their intersection is the empty set: AintersectionB={}.
The operators for union, intersection, and complement satisfy several standard identities. Some of the identities listed below are similar to the rules of ordinary arithmetic. Addition and multiplication, for example, obey the rules of commutativity and associativity, and the minus sign obeys the rule of double complementation. Idempotency, absorption, and De Morgan's laws, however, do not hold for ordinary arithmetic. Distributivity holds for multiplication over addition, but addition does not distribute over multiplication.
  • Idempotency. AintersectionA is identical to A, and AunionA is also identical to A.
  • Commutativity. AintersectionB is identical to BintersectionA, and AunionB is identical to BunionA.
  • Associativity. Aintersection(BintersectionC) is identical to (AintersectionB)intersectionC, and Aunion(BunionC) is identical to (AunionB)unionC.
  • Distributivity. Aintersection(BunionC) is identical to (AintersectionB)union(AintersectionC), and Aunion(BintersectionC) is identical to (AunionB)intersection(AunionC).
  • Absorption. Aintersection(AunionB) is identical to A, and Aunion(AintersectionB) is also identical to A.
  • Double complementation. - -A is identical to A.
  • De Morgan's laws. -(AintersectionB) is identical to -Aunion-B. and -(AunionB) is identical to -Aintersection-B.

For complex sets, the rule for determining which elements are in the set may be too complex to state in a single expression. An example is the set of all grammatical sentences in some language, natural or artificial. Such sets are typically specified by a recursive definition:
  • First a finite starting set of elements is given.
  • Then some operations are specified for generating new elements of the set from old elements.
  • Finally, the set is defined to be the smallest set containing the starting elements and all others that can be derived from them by repeated application of the generating operations.
The set resulting from these operations is said to be the closure of the starting set under the given generating operations. As an example of a recursive definition, the set S of all positive integers not divisible by 3 could be specified by intension:
S = {x | x is an integer, x>0, and 3 does not divide x}.
But the property x is an integer depends on some prior definition of the set of all integers. The following recursive definition depends only on the operation of adding 3:
  • Let the set {1, 2} be a subset of S.
  • If x is any element of S, then x+3 is also an element of S.
  • S is the smallest set that has the above two properties; i.e., S is a proper subset of any other set that has those properties.
All elements of S may be enumerated by starting with {1, 2}. The first stage of adding 3 generates the new elements 4 and 5, adding 3 to them gives 7 and 8, then 10 and 11, and so on. The set S is the closure of the set {1, 2} under the operation of adding 3. A recursive definition is a special kind of definition by intension. Formal grammars define languages by a recursive definition in which the generating operations are specified by a set of production rules.

A set has no duplicate elements. Since all duplicates are discarded in computing the union of two sets, the union operator is idempotent: AunionA=A. In some cases, one may want to allow duplicates; therefore, a bag is a collection of things with possible duplicates. Since there may be more than one occurrence of a given element x, the count operator @ is a generalization of the element operator element of. The expression x@A is the number of times the element x occurs in the bag A. Bags are useful for many purposes, such as taking averages: if four men have heights of 178cm, 184cm, 178cm, and 181cm, then the set of those numbers is {178, 181, 184} with the average 181; but the bag of the numbers is {178, 178, 181, 184} with average 180.25.
sequence is an ordered bag. To distinguish ordered sequences from unordered sets and bags, the elements of a sequence are enclosed in angle brackets: left angle bracket178, 184, 178, 181right angle bracket; the empty sequence is written left angle bracketright angle bracket. If a sequence has n elements, the elements are numbered from 1 to n (or alternatively from 0 to n-1). A sequence of two elements is sometimes called an ordered pair; a sequence of three elements, a triple; a sequence of four, aquadruple; a sequence of five, a quintuple; and a sequence of n elements, an n-tuple. Historically, the theory of sets was first defined without considering order. On a piece of paper or in computer storage, however, the elements of a set must be listed in some order. Sequences are therefore easier to represent than bags, and bags are easier to represent than sets: a bag is a sequence with the ordering ignored, and a set is a sequence with both order and duplicates ignored.

New sets may be created by combining elements from the universe U in various ways. The cross product of two sets A and B, written A×B, is the set of all possible ordered pairs with the first element of each pair taken from Aand the second element from B. If A is the set {1,2} and B is the set {x,y,z}, then A×B is the set,
{left angle bracket1,xright angle bracketleft angle bracket1,yright angle bracketleft angle bracke
t1,zright angle bracketleft angle bracket2,xright angle bracketleft angle bracket2,yright angle
bracketleft angle bracket2,zright angle bracket}.

With the notation for defining a set by a property or rule, it is possible to give a general definition for the cross product A×B:

{left angle bracketx,yright angle bracket | xelement ofA and yelement ofB}.

The cross product can also be extended to three or more sets. The product A×B×C is defined as

{left angle bracketx,y,zright angle bracket | xelement ofAyelement ofB, and zelement ofC}.

Since René Descartes introduced pairs of numbers for identifying points on a plane, the cross product is also called the Cartesian product in his honor.


Inside a computer or the human brain, all sets that are explicitly stored must be finite. But mathematical definitions and proofs are generally simpler if there is no upper limit on the size of sets. Therefore, definitions in computer science often permit infinite sets, but with the understanding that any implementation will only choose a finite subset. Most infinite sets discussed in computer science are assumed to be countable: a countably infinite set is one whose elements can be put in a one-to-one correspondence with the integers. The set of all real numbers is uncountable, but such sets are far beyond anything that can be implemented in computer systems.

The terminology for sets is quite standard, although some authors use the word class for set and others make a distinction between classes and sets. Bags are not used as commonly as sets, and the terminology is less standard. Some authors use the word multiset for a bag. Sequences are sometimes called lists or vectors, but some authors draw distinctions between them. Some authors use the symbol ∅ for the empty set, but the notation {} is more consistent with the notation left angle bracketright angle bracket for the empty sequence.

62 comments:

  1. This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free.
    women's designer handbags

    ReplyDelete
  2. Your new valuable key points imply much a person like me and extremely more to my office workers. With thanks from every one of us.

    Best AWS Training in Chennai | Amazon Web Services Training in Chennai

    ReplyDelete
  3. This is most informative and also this post most user friendly and super navigation to all posts... Thank you so much for giving this information to me.. 

    angularjs Training in chennai
    angularjs Training in chennai

    angularjs-Training in tambaram

    angularjs-Training in sholinganallur

    angularjs-Training in velachery

    ReplyDelete
  4. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.
    python training in pune | python training institute in chennai | python training in Bangalore

    ReplyDelete
  5. After reading this web site I am very satisfied simply because this site is providing comprehensive knowledge for you to audience. Thank you to the perform as well as discuss anything incredibly important in my opinion. We loose time waiting for your next article writing in addition to I beg one to get back to pay a visit to our website in
    Java training in Marathahalli | Java training in Btm layout

    Java training in Jaya nagar | Java training in Electronic city

    ReplyDelete
  6. Your very own commitment to getting the message throughout came to be rather powerful and have consistently enabled employees just like me to arrive at their desired goals.
    Data Science course in kalyan nagar | Data Science course in OMR

    Data Science course in chennai | Data science course in velachery

    Data science course in jaya nagar | Data science training in tambaram

    ReplyDelete
  7. Really you have enclosed very good information's. it will educates lot of young students and please furnish more information's in future.
    Java Courses in Sholinganallur
    Java Training in Guindy
    Java Training in Thirumangalam
    Java Training in Bangalore

    ReplyDelete
  8. Thank you for awesome writeup. It if truth be told used to be an amusement account it. Glance complex to more brought agreeable from you! Also Check: YoWhatsApp Apk & WhatsApp Groups.

    ReplyDelete
  9. Informative blog! it was very useful for me.Thanks for sharing. Do share more ideas regularly.

    Java Interview Questions and Answers

    ReplyDelete

  10. This is most informative and also this post most user friendly and super navigation to all posts... Thank you so much for giving this information to me..

    Core Java Online Training


    Advanced Java Online Training

    ReplyDelete
  11. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

    timing tablets price in pakistan
    timing tablets for man
    timing tablets name
    timing medicine in pakistan
    best timing tablets in pakistan

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share. purple amethyst ring

    ReplyDelete
  14. Great job here on _______ I read a lot of blog posts, but I never heard a topic like this. I Love this topic you made about the blogger's bucket list. Very resourceful. unique garnet rings

    ReplyDelete
  15. Aroma Indian Cuisine is the best Indian Restaurant Epping. We have the best Indian food around and an atmosphere to match. Our recipes are authentic and time-tested on http://aromaindian.com.au/

    ReplyDelete
  16. Thanks for posting such an blog it is really very informative. And useful for the freshers Keep posting the
    timing tablets

    ReplyDelete
  17. Best Prices In Pakistan
    Please VISIT MY Website biggest shopping website 50% off sale Contact NUmber +923000023915
    Top Saling Product
    EtsayDaraz Click hare visit Website
    Cash on Delivery all over Pakistan Online etsaydaraz.com biggest shopping website, Call & SmS Whatsapp 03000023915
    Hot Lin call girls Best Pakistan

    ReplyDelete
  18. He is a French actor and businessman. He is known as one of Europe’s most prominent actors and screen sex symbols from the 1960s and 1970s.
    Alain Delon Personal Information

    ReplyDelete
  19. Best collection of shayari ,qoutes and status.
    Sorry Status
    badmashi status
    whatsapp Bio
    Rajput Status
    Gussa Status
    Bhaigiri Status
    army Status
    Best Jaat Status in hindi and jaat shayari for whatsapp and facebook.

    ReplyDelete
  20. Ludo King is Indian Board Game That Played By Anyone Who Want, Here Some Vip features of Ludo King Apk That User Want to Use Then Here Download Link of Ludo King Modified Application

    ReplyDelete
  21. Download Telugu Ringtone Mp3 Telugu Ringtones Download New Mp3 Ringtone Download

    ReplyDelete
  22. Thanks for sharing this Check the uk thunderball lottery result.check set for life

    ReplyDelete
  23. Trade FX At Home On Your PC: roboforex login Is A Forex Trading Company. The Company States That You Can Make On Average 80 – 300 Pips Per Trade. roboforex login States That It Is Simple And Easy To Get Started.

    ReplyDelete

  24. Thanks For this great content. Really Enjoyed.Keep It up.We are a group of content writing services and running a community in the same niche.If anyone want content writing services then hire content writer and increase conversions for your online store. viagra price in pakistan You have done a extraordinary job!


    ReplyDelete
  25. Tradingzy is the best and most reliable Seo company And offers a wide variety of Link Fx Seo , including an affordable monthly subscription service, one-time links, and blog comments. With any of these services, you can be assured that your site will rank higher in the search engine results page and receive an influx of targeted traffic.

    ReplyDelete
  26. Live Seacoin Price from all markets and SEA coin market Capitalization. Stay up to date with the latest SEA price movements and forum discussion. Check out our snapshot charts and see when there is an opportunity to buy or sell.

    ReplyDelete
  27. Our stock alerts provide you with the latest Truff Stock market trends so that you can stay up-to-date on all of the latest Truff Stock market moves.

    ReplyDelete
  28. We understand that standing on the sidelines of the stock market can be frustrating. Our live, real stock market overview will help you stay up to date on Truff Stock . With our simple interface and real time quotes, staying on top of your stocks is now easier than ever!

    ReplyDelete
  29. How To Start A Forex Broker is a comprehensive guide to deciding on the best Forex Brokers, Trading Costs and Fees. Find out which brokers offer the best value for money?

    ReplyDelete
  30. Bfarf stock Real-Time Overview Of A Stock, Including Recent And Historical Price Charts, News, Events, Analyst Rating Changes And Other Key Stock Information.

    ReplyDelete
  31. Track your stocks in all major markets instantly with our unique live stock overview. See Mmatf Stock live prices changes as they occur and view change details, including volume and share changes.

    ReplyDelete
  32. The Mmatf Stock Overview offers real time stock price updates. All you need to do is open the application and you can view Streaming stock prices of your favorite stocks.

    ReplyDelete
  33. If you have been looking for facts about What Is Liquidity In Cryptocurrency and how it works, Then tradingzy is the best and most reliable place. because tradingzy is Digital Marketing agency focusing on Forex Seo.

    ReplyDelete

  34. Fudxcoin deals in selling and purchasing of crypto currency. It deals in blockchain technology.

    Crypto currency is the digital currency or virtual currency with is used as a medium of exchange where individual ownership records are stored in computer.There are many types of Crypto currency like Bitcoin,Ethereum,Ripple Etc

    The rate of crypto current going in market varies day to day.Crypto currency can be purchased from coin base and different sites like Fudxcoin(www.Fudxcoin.com)
    Block Chain Technology is the method of keeping record of sale and purchase of crypto currency.


    contact@fudxcoin.com
    +1 209-921-6581

    ReplyDelete
  35. Read our honest broker review of TD Ameritrade Review , one of the best online trading companies. Find out about the advantages of using a broker like TD Ameritrade Review, and learn more about the stock market and the best ways to invest in it. Read more here.

    ReplyDelete
  36. i'm honest natured you take conveyance of to selfishness in your message. It makes you stand dependancy out from numerous helper essayists that can't uphold over the top climate content remembering you. Fifa 19 Pc Free Download

    ReplyDelete