Functions: Definitions and Terminology | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 2.6 Free with a free account

Functions: Definitions and Terminology

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.6 · lesson 14 of 878 min · free with a free account

← Partially Ordered Sets and LatticesNext lesson: Injective Functions: One-to-One Mappings and Their Properties →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Exactly one output for every input - and what happens when a rule falls short.

  • Define a function as a special relation
  • Distinguish domain, codomain, and range
  • Decide whether a rule is well-defined
  • Compose functions, and use the identity function

Transcript

Everything said in the video, section by section (1,214 words). Read along, or search it.

Set Theory and Functions

Functions: Definitions and Terminology

This section defines one of the most important ideas in mathematics and computing, the function. We'll see a function as a special kind of relation, and separate its domain, codomain, and range. We'll ask what it means for a rule to be well-defined. And we'll compose functions, and meet the identity function.

The Opening Problem

A Build Pipeline, Stage by Stage

A software build pipeline turns source files into a running service, in stages. A compile stage converts each source file into a compiled object. A deploy stage turns each compiled object into a running status. Each stage, examined closely, is just a rule assigning exactly one output to each input. That's precisely a function. Chaining the two stages into one pipeline, straight from source file to status, is what mathematicians call composing functions. And a build that isn't reproducible, where compiling the same source twice can produce two different objects, has failed to define a function at all.

Definition 2.6.1

A Function Is a Special Relation

Recall that a relation from A to B is any set of ordered pairs, with the first element from A and the second from B. A function f from A to B is a relation in which every element of A, is paired with exactly one element of B. We write f of a equals b, for that unique b. Exactly one packages two conditions. First, every element of A is paired with at least one element of B. No domain element is left unassigned. Second, every element of A is paired with at most one element of B. No domain element gets two different outputs. Take A to be three source files, auth, parser, and logger. The compile rule pairs each one with its compiled object, exactly once. So it's a function.

2 Failures

When a Relation Isn't a Function

Now two relations that fail. First, suppose a non-deterministic build sometimes produces a different object for the same source file. parser dot p y is paired with parser dot o, and also with parser v two dot o. That violates the second condition. parser dot p y doesn't have a single, unambiguous image. Second, suppose logger dot p y fails to compile at all. It appears in no pair whatsoever. That violates the first condition. logger dot p y is left without any output, so the relation isn't a function from A to B.

Definition 2.6.2

Domain, Codomain, and Range

For a function from A to B, the domain is A, the full set of legal inputs. The codomain is B, the declared target set, fixed as part of stating the function. And the range, or image, is the set of outputs the function actually produces. The range is always a subset of the codomain, but the two need not be equal. For the compile function, the codomain has four objects, including cache dot o. But the range has only three. cache dot o is a legitimate kind of object the build system can produce. No source file here ever compiles to it. The codomain describes every output the function is declared capable of. The range describes only what it actually produces, and finding it means checking every input.

A 2nd Example

A 4-Bit Hash

Here's a second example, a hashing function h, mapping three files to a four-bit digest. Its codomain is all sixteen possible four-bit strings, from zero zero zero zero to one one one one. Suppose report dot p d f hashes to zero one one zero, and notes dot t x t to one zero one one. And image dot p n g hashes to zero one zero one. Then the range is just those three strings, three of the sixteen in the codomain. That's why the codomain of a hash function is normally far larger, than any range a realistic set of files produces.

Notation and Well-Definedness

A Rule Must Give Exactly One Output

The notation f from A to B states the domain and codomain in one expression. And f of a equals b records that input a is assigned output b. A rule is called well-defined only if it assigns exactly one output to every input. That becomes a genuine question whenever the same input can be described in more than one way. Here's a classic failure. Try to define a function from the rationals to the integers by sending a over b to a, using whatever fraction is given. Take one-half. Written as one over two, the rule gives one. But two over four names exactly the same number, and the rule gives two. One input, two outputs, depending on the representation. The rule isn't well-defined, so it isn't a function on the rationals at all.

Back to the Pipeline

Reproducible Builds Are Well-Defined

The same discipline governs the build pipeline. Suppose compiling byte-identical auth dot p y on two different machines, or at two different times, could legitimately produce two different compiled objects. Then the assignment from source file to compiled object would fail to be well-defined, in exactly the same way as the fraction rule. And a content-addressed cache built on top of it could no longer guarantee that identical inputs resolve to a single, reusable result.

Definitions 2.6.3 and 2.6.4

Composition and the Identity

If f goes from A to B, and g goes from B to C, the composition g after f goes from A to C. It's defined by g after f, of a, equals g of f of a. First apply f, then apply g to the result. Extend the pipeline with a deploy function g. auth dot o and parser dot o map to deployed. logger dot o maps to failed. And cache dot o maps to skipped. Notice that g must be defined on the whole of B, including cache dot o, which f never actually produces. That's what makes the composition a function on all of A. The identity function on A, written i d sub A, sends every element to itself.

Figure 2.6.1 and Table 2.6.1

The Pipeline as Arrow Diagrams

This figure shows the pipeline as arrow diagrams. Every source file on the left has exactly one outgoing arrow, into the compiled objects. cache dot o sits in the codomain with no incoming arrow, so the range is a proper subset of B. The deploy function continues from each object to a status. And the dashed arc shows the composition. auth dot p y goes straight to deployed, without passing through auth dot o explicitly. Computed for every source file, auth and parser reach deployed, and logger reaches failed. That's exactly what a pipeline skipping the intermediate stage computes.

The Identity Function

A Do-Nothing Element

The identity function acts as a do-nothing element under composition. For any f from A to B, and any a, f after the identity on A gives f of the identity of a, which is f of a. So f after the identity is just f. On the output side, the identity on B after f gives the identity of f of a, which is also f of a. This argument doesn't depend on which f, A, or B is chosen. It holds for every function, just by unfolding the two definitions.

Table 2.6.2

Declared Up Front, or Discovered?

This table compares the three sets. The domain and codomain are both fixed as part of stating the function. The range can only be discovered, by checking what the function actually does for every input. Here's something to think about. A student claims that a function's codomain and range are basically the same thing. Using cache dot o, explain why that's false. And why might a system designer declare a codomain larger than any range they expect to see?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Functions: Definitions and Terminology

What is a function in discrete math, and how is it a special kind of relation?
A function from A to B is a relation in which every element of A is paired with exactly one element of B. "Exactly one" means two things: no input is left without an output, and no input gets two different outputs. We write f(a)=b for the unique output b paired with a.
What is the difference between the domain, codomain, and range of a function?
The domain is the set A of legal inputs, the codomain is the declared target set B, and the range (or image) is the set of outputs the function actually produces. The range is a subset of the codomain, but the two need not be equal. For example, a function into \{a,b,c,d\} that never outputs d has d in its codomain but not in its range.
How do you tell whether a rule is well-defined?
A rule is well-defined if it assigns exactly one output to every input, no matter how that input is described. Check inputs that have several representations. The rule sending the fraction a/b to a fails: 1/2 gives 1, but 2/4 names the same number and gives 2. One input, two outputs, so it is not a function on the rationals.
How do you compose two functions, and what does the identity function do?
If f:A\to B and g:B\to C, then g\circ f:A\to C is defined by (g\circ f)(a)=g(f(a)), so you apply f first and then g. The identity function \mathrm{id}_A sends every element of A to itself. It changes nothing under composition: f\circ \mathrm{id}_A=f and \mathrm{id}_B\circ f=f.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →