Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Sets
DEF: A set is a collection of elements
...
Sets are the basic data structure out of which most mathematical
theories are built
...
Effort failed!
Curly braces “{“ and “}” are used to denote sets
...
Mathematical sets are unordered so different from Java arrays
...
Mathematical sets
don’t require this, however
...
Thus repeating an
element, or changing the ordering of elements in the description of the set,
does not change the set itself:
{ 11, 11, 11, 12, 13 } = { 11, 12, 13 }
{ , , } = { , , }

Set Notations:

Method 1: Roster Method
{ e1, e2, e3,,……en }
Where e1,e2,…en are elements

Method 2: Set Builder Notation

x x  R ( xZ  x 2 > 100)
OR: { x  R | x squared integer >100 }

Standard Numerical Sets
The natural numbers: N = { 0, 1, 2, 3, 4, … }
The integers: Z = { … -3, -2, -1, 0, 1, 2, 3, … }

The positive integers: Z+ = {1, 2, 3, 4, 5, … }
 The real numbers: R- contains any decimal number of arbitrary precision
 The rational numbers: Q -these are decimal numbers whose decimal
expansion repeats
Q: Give examples of numbers in R but not Q
...
When crossed out “” denotes that the object is not an element
...

Q: Which of the following are true:
 3  R
 -3  N
 -3  R
0  Z+
2
 x xR  x =-5


A: 1, 3 and 4
 3  R
...

 -3  N
...

 -3  R
...


0  Z+
...

 x xR  x2=-5
...
, so can’t
be -5
...
This situation is denoted by S  T
A synonym of “subset” is “contained by”
...
The definition above says that:
ST
 x (xS )  (xT )
We already had all the necessary concepts, but the “” notation saves work
...
A subset S
of T is said to be a proper subset if S is not equal to T
...


The Empty Set
The empty set is the set containing no elements
...


Subset Examples
Q: Which of the following are true:
 N  R
 Z  N
 -3  R
{1,2}  Z+

   



A: 1, 4 and 5
 N  R
...

 Z  N
...

 -3  R
...
-3 is not a subset but an element! (This could have
made sense if we viewed -3 as a set –which in principle is the case– in this
case the proposition is false)
...
This actually makes sense
...

  
...

   
...





Cardinality
The cardinality of a set is the number of distinct elements in the set
...

Q: Compute each cardinality
...

A:
|{1, -13, 4, -13, 1}| = |{1, -13, 4}| = 3
|{3, {1,2,3,4}, }| = 3
...
Compute the
cardinality of {3,S, }
|{}| = || = 0
|{ {}, {{}}, {{{}}} }| = |{ , {}, {{}}| = 3
DEF: The set S is said to be finite if its cardinality is a nonnegative integer
...

EG: N, Z, Z+, R, Q are each infinite
...
In fact, R will end
up having a bigger infinity-type than N, but surprisingly, N has same
infinity-type as Z, Z+, and Q
...

Denote the power set by P (S ) or by 2s
...


Lemma: | 2s | = 2|s|
Power Set –Example
To understand the previous fact consider
S = {1,2,3}
Enumerate all the subsets of S :
0-element sets: {}
1
1-element sets: {1}, {2}, {3}
+3
2-element sets: {1,2}, {1,3}, {2,3}
+3
3-element sets: {1,2,3}
+1
s
3
|s|
Therefore: | 2 | = 8 = 2 = 2

Ordered n-tuples
Notationally, n-tuples look like sets except that curly braces are replaced by
parentheses:
( 11, 12 ) – a 2-tuple a
...
a
...

As opposed to sets, repetition and ordering do matter with n-tuples
...

Here ordered pairs (x,y) of elements of R describe the coordinates of each
point
...

DEF: The Cartesian product of two sets A and B –denoted by A B– is the
set of all ordered pairs (a, b) where aA and bB
...

A: R2 = RR
...
e
...


One can generalize the Cartesian product to several sets simultaneously
...

One can also check this directly from the definition of the Cartesian product
...
logical identities may
be rewritten as follows:
disjunction “” becomes union “”
conjunction “” becomes intersection “”
negation “” becomes complementation “–”
false “F” becomes the empty set 
true “T” becomes the universe of reference U


In fact, the logical identities create the set identities by applying the
definitions of the various set operations
...
For example:
LEMMA: (Associativity of Unions)
(AB )C = A(B C )
Proof : (AB )C = {x | x  A B  x  C }
(by def
...
)
= {x | x  A  ( x  B  x  C ) } (logical assoc
...
)
= A(B C )
(by def
...


Set Identities via Venn
It’s often simpler to understand an identity by drawing a Venn Diagram
...
sets:
a){0,3,6,9} b) {-3,-2,-1,0,1,2,3} c) {c,s,t}
2) For each of the ff
...
are true or false:
a)   {} b) {0}   c)   {0}
d) {}  e)   {} f) {}  {}



---