CSCI 381 Goldberg Lecture 6: Mathematical Structures and Functions

Administrative Updates

Course Materials

Notes Distribution

Full lecture notes will be emailed after class
Contains second tab with function examples
Includes partial functions breakdown

Important Schedule Update - HOLIDAY CLOSURE

President’s Day Holiday

February 16 (Monday): College CLOSED - NO CLASS
February 17 (Tuesday): Possibly closed - CHECK CALENDAR
Next lecture: Likely one week from today (check college calendar)

Action Required

Double check your college calendar for exact holiday dates
Do not assume Monday class - it’s likely cancelled
Plan accordingly for the extended break

Attendance

Text word “present” to register attendance
Last call before end of class

Next Steps

Verify college holiday schedule (Feb 16-17)
Check when next lecture is scheduled
Watch for email with lecture notes
Review materials before resuming next week

Lecture Content

Exhaustive Searches

Cost of Exhaustive Searching (Brute-Force method)

Here, the Time Complexity equals the size of search space.

Initially, mathematical structures are stored in un/ordered sets.

Structure #1. Subsets of a Set

How many subsets are there of a given set?

Suppose a Set where elements are indexed from 0 (as in C++/Java).

Let denote the cardinality of .

A method to encode such a set with its subsets is by using a one-dimensional array/vector.

		E0	E1				En-1
Sub/set	Si	1	1	0	0	0	1	{E0, E1, En-1}

Any subset (of a set of size ) can be encoded by boolean values in a bit vector, where 1 indicates membership and 0 indicates non-membership.

For example: is represented as

The binary representations range from to (subscript 2 denotes base 2).

So counting the number of subsets is equivalent to determining how many bitstrings (arrays of only 0/1 values) of size n

As mentioned many times before, this finite string of length n can be encoded by natural numbers ranging 0 (when the vector contains all 0’s) to (2^n) -1 (when the vector contains all 1’s). So a simple for loop enumerating the natural numbers from 0 to (2^n) -1 can then each be decoded into the binary representation of each such natural number, which automatically represents a unique subset of an initial set S of size n.

In summary, there are such subsets. The set of all subsets is denoted or , called the power set.

Structure #2. Relations from a Set to a Set

Conventionally, let and .

S1	S2

A1 B1 A Graph is a “Graph”ical representation of a Relation.

A2 B2 Standard (default) relations have two sets whereas . —> . Standard (default) graphs are from one set to itself. Ai . But, this is only a default convention. Relations can . . be over one set and graphs can be over two sets. Am Bn A graph from set A to a set B is called bipartite.

Note: For diagramming purposes, the two sets appear of the same length (size) but mathematically of course of any size. This indicated by the fact that |S1| = m, |S2| = n, with most probably with m <> n. The Cartesian Product is ONE such relationship/mapping but contains the maximum number of connections FROM/TO.

S1 x S2 = {<A1,B1>,…,<Ai,Bj>,…,<Am,Bn>}

An arbitrary relation from to is a subset of the Cartesian product .

Note that contains all possible connections from to , whereas contains only some of these.

Relation as Subset

Since , all possible relations from to form the power set:

Based on Structure #1:

The relation with the maximum number of connections is the Cartesian product itself. In graph terminology, a graph with all possible edges is called a complete graph, denoted (for two sets) or (for one set).

Structure #3. Directed Graphs over a Set

A directed graph is defined as where:

is the vertex set (nodes)
is the edge set (arcs)
is the number of vertices

Note that (edges are pairs of vertices).

A graph is a graphical representation of a relation. While relations typically involve two sets (), directed graphs typically map a set to itself (). However, these are equivalent when we set .

Therefore, by applying Structure #1 and #2:

where .

Example: Consider a vertex set with nodes. The number of distinct directed graphs over is:

Note: This is arguably larger than the estimated number of atoms in the observable universe.

Homework: How many undirected graphs are there over a set of vertices?

Structure #4. Partial Mapping from a Set to a Set

In a partial mapping, each element Ai has independently n possible Bj elements to choose from to map into, but in addition, each element Ai has the extra right to not go at all (this is what causes the mapping to be “partial” or undefin The partial mapping can only make one of these choices for each element Ai.

By the multiplication principle, each of the elements has independent choices (n targets plus the option to not map). Thus:

Real-world example: A scientific calculator has multiple buttons corresponding to partial functions (e.g., division by zero, square root of negative numbers).

When a computing machine encounters an undefined input:

Computationally, this typically throws an exception or produces an error message.

However, in Turing’s theoretical framework, a partially computable function must enter an infinite loop when given an undefined input. Otherwise, one could solve the halting problem by checking if the function terminates (determining solvability). If the machine crashes instead of looping, you could infer that the code is unsolvable.

Structure #5. Total Mapping (Function) from a Set to a Set

In a total mapping, each element must map to exactly one element (but multiple elements may map to the same target).

Note: “Exactly one” differs from “uniquely one” (covered in Structure #6). In a constant function, all elements map to the same target. For example: for all .

By the multiplication principle, each of the elements has independent choices. Thus:

Structure #6. Injective Mapping (One-to-One Function) from a Set to a Set

Also known as: Permutations

Historical note: Early 19th-century mathematics textbooks explicitly recognized that injective mappings are permutations. Despite modern pedagogy often treating them as distinct concepts, they are mathematically equivalent.

Injective mappings are also total functions. By the pigeonhole principle, if each element of must map to a distinct element of , then .

Important Distinction: “Exactly One” vs. “Uniquely One”

In a total mapping (Structure #5), each element has “exactly one” choice—a quantitative restriction meaning one target is selected. However, multiple elements can choose the same target. For example, a constant function maps all elements to the same value.

In an injective mapping, each element must choose a “uniquely one”—both a quantitative AND qualitative restriction: exactly one choice, and each must choose a different target from all other elements.

Counting Injective Mappings: The Catering Analogy

A helpful analogy: Imagine a waiter circulating at a fancy party with 100 distinctly shaped cakes in a dessert lineup. Each guest selects one cake:

1st guest: 100 choices
2nd guest: 99 choices (one cake taken)
3rd guest: 98 choices
In one-to-one mapping:
has choices
has choices (one already taken)
has choices
has choices

By the multiplication principle:

This formula equals:

Decomposing Injective Mappings into Two Steps

Alternatively, an injective mapping can be decomposed:

(1) Choose elements from : ways (selecting which cakes to use)

(2) Arrange these chosen elements for the elements of : permutations (assigning selected cakes to guests)

Thus:

Summary: An injective mapping is equivalent to first selecting a subset, then permuting it.

Stirling’s Inequality

Theorem: For :

(Proof by induction, discussed in a separate session.)

Structure #7. Surjective Mapping (Onto Function) from a Set to a Set

Every element in is mapped to by at least one element in . This requires .

Surjective mappings are total: each element of maps to exactly one element of , and every element of is “reached” by at least one element from .

There is no simple closed formula for surjective mappings. Instead, we use:

where the non-onto count is calculated using the Inclusion-Exclusion principle.

The complication arises from the Inclusion-Exclusion (I-E) Principle, which corrects for overcounting in union calculations.

Inclusion-Exclusion Principle with an Example

Scenario: A Math club has 50 members, and a Computer Science society has 50 members. They throw a joint end-of-semester party (pizza party!). How many people attend?

Naive approach: [INCORRECT]
Problem: Some students are double majors (both Math and CS)
Correct approach:

The Inclusion-Exclusion principle handles this correction by subtracting the overcounted intersection.

For three sets:

Connection to Pascal’s Triangle: The coefficients in I-E formulas (1, 3, 3, 1 for three sets, etc.) correspond to rows of Pascal’s triangle. This is not coincidental—combinatorics fundamentally connects to Pascal’s triangle.

Applying Inclusion-Exclusion to Count Surjections

To count surjective mappings, we prevent total mappings from missing certain elements of :

By Inclusion-Exclusion:

Therefore:

This formula appears in every discrete mathematics reference text, though the derivation is involved.

Structure #8. Partitions and Their Relationship to Surjective Mappings

A partition of a set into subsets satisfies:

(1) Each is nonempty — no empty boxes

(2) — no extraneous elements

(3) — all original elements included

(4) for — subsets are mutually disjoint

Analogy: Think of packing household items for a move. Each box is nonempty, contains only your items, holds all your belongings collectively, and no item appears in multiple boxes.

Two Naming Conventions

(a) -partition (): The number of subset pieces is fixed ahead of time. (“I will provide exactly boxes; use only these.”)

(b) Partition (): No prior restriction on the number of subsets. (“Use however many boxes you need; I’ll pay for what you use.”)

Connection to Karp’s NP-Complete Problems

Important note: Richard Karp’s landmark 1972 paper “Reducibility Among Combinatorial Problems” includes at least 4 out of 21 NP-complete problems that fundamentally involve partitioning. Understanding partitions is essential for comprehending Karp’s reduction framework.

Key Relationship: Partitions and Surjective Mappings

There is a profound connection between -partitions and surjective mappings. From an onto-mapping perspective, two surjections may look completely different, but from a partition perspective, they are identical.

Example: Consider surjective mappings from to :

Surjection 1:

Surjection 2 (boxes labeled differently):

(swapped with above)
(swapped)
(swapped)
(swapped)

Critical insight: From a function perspective, these are different surjections (outputs differ). From a partition perspective, these are the same partition (the grouping is identical; only box labels changed).

Mathematically:

Two surjections are different if their function values differ
But they represent the same partition if they partition the same elements the same way

Counting Partitions from Surjections

The number of -partitions equals the number of onto mappings divided by :

Explanation: Dividing by removes the effects of reordering the subsets. Since partitions are unordered (the labels don’t matter), different orderings of the same subsets are now treated as identical.

Bell Numbers

The Bell number counts the total number of partitions for a set of size , summed over all possible values of :

Growth rate: Bell numbers grow remarkably quickly. Examples:

(partitions of a 3-element set)
(partitions of a 5-element set)
(partitions of a 10-element set)

Despite dividing onto-mappings by the enormous factorial when computing , the summed Bell numbers exhibit extraordinary combinatorial growth. This explosive growth illustrates why partitioning problems appear so frequently in NP-complete formulations.

Structure #9. Bijections (One-to-One Correspondence)

A bijection (or 1-1 correspondence) is important because it allows for the definition of an inverse. The inverse relation holds true in both directions.

Classic definition: A (total) function that is both 1-1 (injective) and onto (surjective).

Recall the constraints:

Injective:
Surjective:

Therefore: Bijective requires

An alternative (equivalent) definition: An injective function between equal-sized sets .

Recall that the number of injective mappings equals

When :

Why Injectivity Alone Doesn’t Provide an Inverse

Consider with elements and with elements where .

For an injective mapping , one might propose an inverse by “reversing arrows”: if , then .

Problem: Since , some elements are unreached by any element in . These unreached elements have no element to map back to, making the “inverse” a partial function rather than a total function.

For the elements that are involved in the original injective mapping, the inverse property holds perfectly. But the incompleteness makes it unsuitable as a true function inverse.

Key insight: A proper inverse function requires both forward and reverse mappings to be total. This is only possible when —exactly when bijections exist. Only bijections possess well-defined, total function inverses.

Partial Calculator

	Button	Invalid Input	Windows Response	NOTE
a)	1/x	0	Cannot divide by zero
b)	√	-1	Invalid input	square root function on any negative value
c)	log	0	Invalid input	or any negative value; typically natural log base
d)	ln	0	Invalid input	or any negative value; base
e)	/	0	Cannot divide by zero	when the denominator is zero
f)	x^y	x=y=0	1	*technically wrong (see below)
g)	arc sin	2	Invalid input	inverse sin function; not defined for any value
h)	arc cos	2	Invalid input	inverse cos function; not defined for any value
i)	tan	90 or 270	Invalid input	value in degrees
j)	!	-1	Invalid input	or any negative value

Note on :

For the case where , two rules conflict:

0 raised to any power equals 0
Any number raised to power 0 equals 1

Technically, is indeterminate due to this contradiction. However, computer theory requires for mathematical recursions to work correctly. Martin Davis (founder of modern computer theory) chose rule #2 and defined .