DOC PREVIEW
UNL CSCE 235 - Sets Handout Notes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

SetsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 2.1, 2.2 of [email protected] IWe’ve already implicitly dealt with se ts (intege rs, Z; rationals (Q)etc.) but here we will develop more fully the definitions, propertiesand operations of sets.DefinitionA set is an unordered collec tion of (unique) objects.Sets are fundamental discrete structures that form the basis ofmore complex disc rete structures like graphs.Contrast this definition with the one in the book (compare bag,multi-set, tuples, etc).DefinitionIntroduction IIThe objects in a set are called elements or members of a set. A setis said to contain its elements.Recall the notation: for a set A, an element x we writex ∈ Aif A contains x andx 6∈ Aotherwise.Latex notation: \in, \notin.Terminology IDefinitionTwo sets, A and B are equal if they contain the same elements. Inthis case we write A = B.Example{2, 3, 5, 7} = {3, 2, 7, 5} since a set is unordered.Also, {2, 3, 5, 7} = {2, 2, 3, 3, 5, 7} since a set contains uniqueelements.However, {2, 3, 5, 7} 6= {2, 3}.Terminology IIA multi-set is a set where you specify the number of occurrences ofeach element: {m1· a1, m2· a2, . . . , mr· ar} is a set where m1occurs a1times, m2occurs a2times, etc.Note in CS (Databases), we distinguish:Ia set is w/o repetitionIa bag is a set with repetitionTerminology IIIWe’ve already seen set builder notation:O = {x | (x ∈ Z) ∧ (x = 2k for some k ∈ Z)}should be read O is the set that contains all x such that x is aninteger and x is even.A set is defined in intension, when you give its set builder notation.O = {x | (x ∈ Z) ∧ (0 ≤ x ≤ 8) ∧ (x = 2k for some k ∈ Z)}A set is defined in extension, when you enumerate all the elements.O = {0, 2, 4, 6, 8}Venn DiagramExampleA set can also be represented graphically using a Venn diagram.UA BCxyzaFigure: Venn DiagramMore Terminology & Notation IA set that has no elements is referred to as the empty set or nullset and is denoted ∅.A singleton set is a set that has only one element. We usuallywrite {a}. Note the different: brackets indicate that the object is aset while a without brackets is an element.The subtle difference also exists with the empty set: that is∅ 6= {∅}The first is a set, the second is a set containing a set.More Terminology & Notation IIDefinitionA is said to be a subset of B and we writeA ⊆ Bif and only if every element of A is also an element of B.That is, we have an equivalence:A ⊆ B ⇐⇒ ∀x(x ∈ A → x ∈ B)More Terminology & Notation IIITheoremFor any set S,I∅ ⊆ S andIS ⊆ S(Theorem 1, page 115.)The proof is in the book—note that it is an excellent example of avacuous proof!Latex notation: \emptyset, \subset, \subseteq.More Terminology & Notation IVDefinitionA set A that is a subset of B is called a proper subset if A 6= B.That is, there is some element x ∈ B such that x 6∈ A. In this casewe write A ⊂ B or to be even more definite we writeA ( BExampleLet A = {2}. Let B = {x | (x ∈ N) ∧ (x ≤ 100) ∧ (x is prime)}.Then A ( B.Latex notation: \subsetneq.More Terminology & Notation VSets can be eleme nts of other s ets.Example{∅, {a}, {b}, {a, b}}and{{1}, {2}, {3}}are sets with se ts for elements.More Terminology & Notation VIDefinitionIf there are exactly n distinct e lem ents in a set S, with n anonnegative integer, we say that S is a finite se t and thecardinality of S is n. Notationally, we write|S| = nDefinitionA set that is not finite is said to be infinite.More Terminology & Notation VIIExampleRecall the set B = {x | (x ≤ 100) ∧ (x is prime)}, its cardinality is|B| = 25since there are 25 primes less than 100. Note the cardinality of theempty set:|∅| = 0The sets N, Z, Q, R are all infinite.Proving Equivalence IYou may be asked to show that a set is a subset, proper subset orequal to another set. To do this, use the equivalence discussedbefore:A ⊆ B ⇐⇒ ∀x(x ∈ A → x ∈ B)To show that A ⊆ B it is enough to show that for an arbitrary(nonspecific) element x, x ∈ A implies that x is also in B. Anyproof method could be used.To show that A ( B you must show that A is a subset of B justas before. But you must also show that∃x((x ∈ B) ∧ (x 6∈ A))Finally, to show two sets equal, it is enough to show (much like anequivalence) that A ⊆ B and B ⊆ A independently.Proving Equivalence IILogically speaking this is showing the following quantifiedstatements:∀x(x ∈ A → x ∈ B)∧∀x(x ∈ B → x ∈ A)We’ll see an example later.The Power Set IDefinitionThe power set of a se t S, denoted P(S) is the set of all subsets ofS.ExampleLet A = {a, b, c} then the p ower set isP(S) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}Note that the empty set and the set itself are always elements ofthe power set. This follows from Theorem 1 (Rosen, p115).The Power Set IIThe power set is a fundamental combinatorial object useful whenconsidering all possible combinations of elements of a se t.FactLet S be a set such that |S| = n, then|P(S)| = 2nTuples ISometimes we may need to consider ordered collections.DefinitionThe ordered n-tuple (a1, a2, . . . , an) is the ordered c ollection w iththe aibeing the i-th element for i = 1, 2, . . . , n.Two ordered n-tuples are equal if and only if for eachi = 1, 2, . . . , n, ai= bi.For n = 2, we have ordered pairs.Cartesian Products IDefinitionLet A and B be sets. The Cartesian product of A and B denotedA × B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B:A × B = {(a, b) | (a ∈ A) ∧ (b ∈ B)}The Cartesian product is also known as the cross product.DefinitionA subset of a Cartesian product, R ⊆ A × B is called a relation.We will talk more about relations in the next set of slides.Cartesian Products IINote that A × B 6= B × A unless A = ∅ or B = ∅ or A = B. Canyou find a counter example to prove this?Cartesian Products IIICartesian products can be generalized for any n-tuple.DefinitionThe Cartesian product of n sets, A1, A2, . . . , An, denotedA1× A2× · · · × AnisA1×A2×· · ·×An= {(a1, a2, . . . , an) | ai∈ Aifor i = 1, 2, . . . , n}Notation With QuantifiersWhenever we wrote ∃xP(x) or ∀xP (x), we specified the universeof discourse using explicit English language.Now we can simplify things using set notation!Example∀x ∈ R(x2≥ 0)∃x ∈ Z(x2= 1)Or you can mix quantifiers:∀a, b,


View Full Document

UNL CSCE 235 - Sets Handout Notes

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Sets Handout Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sets Handout Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sets Handout Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?