Functions in Discrete Mathematics

Functions play a fundamental role in Discrete Mathematics, defining mappings between sets and capturing relationships between elements. Learn about functions, their properties such as being one-to-one or onto, and how to determine if a given mapping qualifies as a function. Explore concepts like one-to-one mapping, surjective functions, and more in this comprehensive study of Discrete Mathematics.

• Functions
• Discrete Mathematics
• Mappings
• Properties
• Mathematics

taez368 Follow

Uploaded on Feb 16, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/

2. Todays topics Functions One-to-one, onto, bijective Sequences Inverse function Section 2.2 in Jenkyns, Stephenson

3. What is a function? X,Y are sets A function ?:? ? is a mapping from X to Y Every element ? ? is mapped to f(?) ? Equivalently, can be viewed as a set (?,? ? ) ? ? Note: every element x is mapped to exactly one element in Y, i.e f(x)

4. What is a function? Is the following a function from X to Y? A. Yes B. No X Y

5. What is a function? Is the following a function from X to Y? A. Yes B. No X Y

6. What is a function? Is the following a function from X to Y? A. Yes B. No X Y

7. What is a function? Is the following a function from X to Y? A. Yes B. No Y X

8. What is a function? Is the following a function from Y to X? A. Yes B. No Y X

9. Properties of functions Function ?:? ? f is one-to-one (also called injective) if different values in X are mapped to different values in Y ?,? ?,? ? ? ? ? ? Equivalently: ?,? ?,? ? = ? ? ? = ? (recall: ~Q ~? is equivalent to ? ?)

10. Properties of functions Function ?:? ? f is one-to-one (also called injective) if different values in X are mapped to different values in Y ?,? ?,? ? ? ? ? ? Equivalently: ?,? ?,? ? = ? ? ? = ? (recall: ~Q ~? is equivalent to ? ?) f is onto (also called surjective) if every element of y is mapped to by some x (possibly more than one) ? ? ? ?,? ? = ?

11. Properties of functions Function ?:? ? f is one-to-one (also called injective) if different values in X are mapped to different values in Y ?,? ?,? ? ? ? ? ? Equivalently: ?,? ?,? ? = ? ? ? = ? (recall: ~Q ~? is equivalent to ? ?) f is onto (also called surjective) if every element of y is mapped to by some x (possibly more than one) ? ? ? ?,? ? = ? f is bijective if it is both one-to-one and onto

12. One-to-one, onto, bijective Is the following function A. One-to-one B. Onto C. Both (bijective) D. None X Y

13. One-to-one, onto, bijective Is the following function A. One-to-one B. Onto C. Both (bijective) D. None X Y

14. One-to-one, onto, bijective Is the following function A. One-to-one B. Onto C. Both (bijective) D. None X Y

15. One-to-one, onto, bijective Which of the following functions f:N N is not injective A. f(x)=x B. f(x)=x2 C. f(x)=x+1 D. f(x)=2x E. None/other/more than one

16. One-to-one, onto, bijective Which of the following functions f:N N is not surjective A. f(x)=x B. f(x)=x2 C. f(x)=x+1 D. f(x)=2x E. None/other/more than one

17. Sequences A finite sequence is a1,a2, ,an Example: 1,2,3,5,1,2 If elements are in some set X, it can be equivalently described by ?: 1,2, ,? ? An infinite sequence is a1,a2, ,an, Example: 1,2,4,8,16, That is, ??= 2? It can be equivalently described by ?:? ?

18. Inverses Function ?:? ? A function g:? ? is an inverse of f if ? ?,? ? ? = ? ? ?,? ? ? = ? Questions: Does any function have an inverse? If not, which properties of f are required for it to have an inverse? Is the inverse unique?

19. Inverses Does the following function have an inverse: ?:? ?,?(?) = 2? A. Yes B. No

20. Inverses Does the following function have an inverse: ?:? ?,?(?) = 2? A. Yes B. No

21. Inverses Does the following function have an inverse: ?: 1,2 {1,2,3,4},?(?) = 2? A. Yes B. No

22. Inverses Theorem: a function ?:? ? has an inverse if and only if it is bijective (eg both one-to-one and onto) We will see the proof for finite sets X,Y once we learn some proof techniques The proof extends to infinite sets We will use this to define a notion of size for infinite sets (called cardinality ). We will prove that not all infinite sets have the same cardinality, so this definition makes sense.

23. Next class Proof techniques Read section 3.5 in Jenkyns, Stephenson