Discrete Mathematics for Computer Science

276 CHAPTER^4 Functions

codomain injection

collision resolution strategy injective function

decreasing mapped to

decrypt one-to-one (1-1)

domain onto

encoded partial function

encrypted preimage

equal range

floor recursive definition

function recursively

graph of a function restriction

graph of a partial function strictly decreasing

greatest integer function strictly increasing

hashing function surjection

horizontal line test surjective function

identify function total function

image undefined

increasing vertical line test

independent

4.3-4.5 Summary

TERMS

commutative infinite sequence

composition invertible

decreasing inverse

F list

(F + G) sequence

(F • G) stream

(F/G) strictly decreasing

finite sequence strictly increasing

increasing subsequence

4.6 Summary

TERMS

ceiling k to 1

decreasing subsequence nonterminating

Dirichlet Drawer Principle rationals numbers as decimals

finite repeating

floor terminating

increasing subsequence

THEOREMS

Erdds Generalized Pigeon-Hole Principle

Erdds and Szeker6s Pigeon-Hole Principle