×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Shlomo Oved

101

9

5

# Week 1 Notes MA-UY 2314

Shlomo Oved
NYU

Enter your email below and we will instantly email you these Notes for Discrete Mathematics

(Limited time offer)

Unlock FREE Class Notes

Everyone needs better class notes. Enter your email and we will send you notes for this class for free.

Covers Sets and Functions
COURSE
Discrete Mathematics
PROF.
Dr Nasir Memon
TYPE
Class Notes
PAGES
5
WORDS
KARMA
Free

## Popular in Mathematics

This 5 page Class Notes was uploaded by Shlomo Oved on Thursday September 8, 2016. The Class Notes belongs to MA-UY 2314 at New York University taught by Dr Nasir Memon in Fall 2016. Since its upload, it has received 101 views. For similar materials see Discrete Mathematics in Mathematics at New York University.

×

## Reviews for Week 1 Notes

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/08/16
Shlomi  Oved   Discrete  Mathematics     09/07/16   Professor  Nasir  Memon   2  Metrotech  10-­‐095  10  Floor   Email:  memon@nyu.edu   Office  Hours:  Monday  2-­‐4pm   Doodle.com/memon   Recitation  Instructor:  Joe  Vaisman     Structure  of  Lecture/Recitation   Wednesday-­‐  Quiz,  Lecture,  HW   Monday-­‐  Lecture,  Graded  Quiz  Returned   Wednesday-­‐  Quiz  (Based  on  HW),  Lecture,  HW  (Based  on  last  2  Lectures)   Tuesday  Recitation-­‐  Solved  HW  (3  points)  and  get  half  credit  on  corrected  Quiz   questions     HW/Recitation-­‐  30%   Quiz-­‐  30%   Midterm-­‐  20%   Final-­‐  20%     Chapter  2  Sets  and  Functions   Sets   • Definition-­‐  A  set  is  an  unordered  collection  of  objects/members/elements   • A  capital  letter  is  used  to  denote  a  set.  Ex:  “Set  A”   • A  lowercase  letter  is  used  to  denote  a  member  of  a  set.  Ex:  “a”   • The  notation  ???? ∈ ????  denotes  that  a  is  an  element  of  the  set  A.   • Ways to represent a set of elements:   • ????,????,????  ,????,????                   1,2,3,4               1,2,3  ,…100   • ???? = ???? ????  ????????  ????????  ????????????  ???????????????????? < 1,000,000  (the  |  means  “such  that”)     Common  Sets   • N  =  natural  numbers  =  {0,1,2,3....}   • Z  =  integers  =  {...,-­‐3,-­‐2,-­‐1,0,1,2,3,...}     • Z  =  positive  integers  =  {1,2,3,.....}     • R    set  of  real  numbers     • R =  set  of  positive  real  numbers     • C  =  set  of  complex  numbers     • Q  =  set  of  rational  numbers       Set  Equality   • Definition-­‐  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   •  ∀???? ???? ∈ ????   ↔ ???? ∈ ????  (∀  ????????????????????  "????????????  ????????????")   Shlomi  Oved   Discrete  Mathematics       Universal  Set  and  Empty  Set   • The  universal  set  U  is  the  set  containing  everything  currently  under   consideration.   o Sometimes  implicit   o Sometimes  explicitly  stated   o Contents  depend  on  the  context   • The  empty  set  is  a  set  with  no  elements.  It  is  represented  by  ∅  or  with  {}.   • The  empty  set  is  different  from  a  set  containing  an  empty  set.  Ex:  ∅ ≠ {∅}     Subsets   • Definition-­‐  The  set  A  is  a  subset  of  B,  if  and  only  if  every  element  of  A  is  also   an  element  of  B.   • ???? ⊆ ????  ????????  ????????????????  ????????  ????????????????????????????????  ????ℎ????????  ????  ????????  ????  ????????????????????????  ????????  ????   • An  empty  set  is  a  subset  of  any  set   • Any  set  is  a  subset  of  itself   • ???? ⊆ ????  holds  if  and  only  if  ∀???? ???? ∈ ???? → ???? ∈ ????  is  true.     Proper  Subset   • Definition-­‐  If  ???? ⊆ ????,  but  ???? ≠ ????,  then  we  say  that  A  is  a  proper  subset  of  B.   • To  show  A  is  a  proper  subset  of  B  we  write:  ???? ⊂ ????   • If  ???? ⊂ ????,  then  ∀???? ???? ∈ ???? → ???? ∈ ???? ∧ ∃???? ???? ∈ ???? ∧ ???? ∉ ????     • (  ∃  ????????????????????  there  exists, ∧  ????????????????????  "????????????,"   ∨  ????????????????????  "????????"  )         Set  Cardinality   • Definition-­‐  The  cardinality  of  a  finite  set  A,  denoted  by   ???? ,  is  the  number  of   elements  of  A.   • Examples:     • |ø|=0       • |{1,2,3}|  =  3       • |{ø}|  =  1         Power  Sets   • Definition-­‐  The  set  of  all  subsets  of  a  set  A,  denoted  by   ???? ???? ,????????  ????????????????????????  ????ℎ????  ????????????????????  ????????????  ????????  ????   • If  ???? = ????,????  ????ℎ????????   • ???? ???? = {∅, ???? , ???? , ????,???? }   • ????????  ????  ????????????  ℎ????????  ????  ????????????????????????????????,????ℎ????????  ????ℎ????  ????????????????????????????????????????????  ????????  ????ℎ????  ????????????????????  ????????????  ????????  2   ▯   Set  Operations   Union   • Definition-­‐  If  A  and  B  are  sets,  the  union  of  the  sets,  denoted  by  ???? ∪ ????  is  the   set:   • {????|???? ∈ ???? ∨ ???? ∈ ????}   Shlomi  Oved   Discrete  Mathematics     • Ex:   1,2,3 ∪ 3,4,5 = 1,2,3,4,5   Intersection   • Definition-­‐  The  intersection  of  sets  A  and  B,  denoted  by  ???? ∩ ????  is     • {????|???? ∈ ???? ∧ ???? ∈ ????}   • Ex:   1,2,3 ∩ 3,4,5 = {3}     Complement   • Definition-­‐  If  A  is  a  set,  then  the  compliment  of  A  (with  respect  to  U),  denoted   by  ????,  is    U-­‐A   • ???? = {???? ∈ ????|???? ∉ ????}   • Ex:  If  U  is  the  positive  integers  less  than  100,  what  is  the  compliment  of   {????|???? > 70}   • Answer:   ???? ???? ≤ 70}     Difference   • Definition-­‐  The  difference  of  A  and  B,  denoted  by  A-­‐B,  is  the  set  containing   the  elements  of  A  that  are  not  in  B.  The  difference  of  A  and  B  can  also  be   called  the  complement  of  B  with  respect  to  A.   • ???? − ???? = ???? ???? ∈ ???? ∧ ???? ∉ ???? = ???? ∩ ????     Set  Identities   Identity  Laws   • ???? ∪ ∅ = ????   • ???? ∩ ???? = ????   Domination  Laws   • ???? ∪ ???? = ????   • ???? ∩ ∅ = ∅   Idempotent  Laws   • ???? ∪ ???? = ????   • ???? ∩ ???? = ????   Complementation  Law   • (????) = ????   Commutative  Laws   • ???? ∪ ???? = ???? ∪ ????   • ???? ∩ ???? = ???? ∩ ????   Associative  Laws   • ???? ∪ ???? ∪ ???? = ???? ∪ ???? ∪ ????   • ???? ∩ ???? ∩ ???? = ???? ∩ ???? ∩ ????   Distributive  Laws   • ???? ∩ ???? ∪ ???? = ???? ∩ ???? ∪ ???? ∩ ????   • ???? ∪ ???? ∩ ???? = ???? ∪ ???? ∩ ???? ∪ ????   De  Morgan’s  Laws   • ???? ∪ ???? = ???? ∩ ????   • ???? ∩ ???? = ???? ∪ ????   Shlomi  Oved   Discrete  Mathematics       Membership  Table   • We  construct  the  table  to  proof  certain  statements  such  as  below:   • ???? ∪ ???? ∩ ???? = (???? ∪ ????) ∩ (???? ∪ ????)   A   B   C   ???? ∩ ????   ???? ∪ ???? ∩ ????   ???? ∪ ????   ???? ∪ ????   (???? ∪ ????) ∩ (???? ∪ ????)   1   1   1   1   1   1   1   1   1   1   0   0   1   1   1   1   1   0   0   0   1   1   1   1   1   0   0   0   1   1   1   1   0   1   1   1   1   1   1   1   0   1   0   0   0   1   0   0   0   0   1   0   0   0   1   0   0   0   0   0   0   0   0   0     Generalized  Unions  and  Intersections   • Let  A1,  A2  ,...,  An  be  an  indexed  collection  of  sets.  We  define:             Functions   • Definition-­‐  A  function  f  from  A  to  B  ,denoted  f:  A→B  is  an  assignment  of  each   element  of  A  to  exactly  one  element  of  B.  We  write  f(a)  =  b  if  b  is  the  unique   element  of  B  assigned  by  the  function  f  to  the  element  a  of  A.     • Given  a  function  f:  A→B:   o We  say  f  maps  A  to  B  or  f  is  a  mapping  from  A  to  B.     o A  is  called  the  domain  of  f   o B  is  called  the  codomain  of  f   o If  f(a)  =  b,   § then  b  is  called  the  image  of  a  under  f.     § a  is  called  the  preimage  of  b.   o The  range  of  f  is  the  set  of  all  images  of  points  in  A  under  f.  We    denote   it  by  f(A).       o Two  functions  are  equal  when  they  have  the  same  domain,  the  same   codomain  and  map  each  element  of  the  domain  to  the  same  element   of  the  codomain.       Injections   • Definition-­‐  A  function  is  one  to  one  or  injective  if  an  only  if  f(a)=  f(b)  implies   that  a  =  b  for  all  and  b  in  the  domain  of  f.   Surjections   Shlomi  Oved   Discrete  Mathematics     • Definition-­‐  A  function  f  from  A  to  B  is  called  onto  or  surjective,  if  and  only  if   for  every  element  ???? ∈ ????  there  is  an  element  ???? ∈ ????  with  f(a)  =  b.   Bijections   • Definition-­‐  A  function  f  is  a  one  to  one  correspondence/bijection  if  it  is  both   onto  and  one  to  one.   Inverse  Functions   • Definition-­‐  Let  f  be  a  bijection  from  A  to  B.  Then  the  inverse  of  f,  denoted  as   ▯▯ ????  ????????  ????ℎ????  ????????????????????????????????  ????????????????  ????  ????????  ????.  No  inverse  exists  unless  f  is  a  bijection

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com