CSE 16, Applied Discrete Mathematics Midterm 3

These flashcards cover key concepts from the CSE 16 Applied Discrete Mathematics Midterm 3, focused on exam techniques, mathematical definitions, and properties related to functions and sets.

Exam Instructions

Complete the exam in three hours without outside help or devices.

True or False Questions

Respond with true or false; justification is not required.

Principle of Induction

A method to prove statements for all natural numbers.

Injective Function

A function where each element of the range is mapped to by at most one element of the domain.

Surjective Function

A function where every element of the codomain is mapped to by at least one element of the domain.

Bijective Function

A function that is both injective and surjective.

Cardinality

The number of elements in a set.

Powerset

The set of all subsets of a set, including the empty set and the set itself.

Combinatorial Problems

Problems that involve counting combinations or arrangements of items.

Structural Induction

A proof technique used to establish properties of recursively defined structures.

Recursion

Defining functions or sequences in terms of themselves.

Base Case

The simplest case in induction, which establishes the validity of the induction.

Inductive Step

In induction, the process of proving that if the statement holds for one case, it holds for the next.

Relations in Mathematics

A relationship between elements of one or two sets.

Reflexive Relation

A relation where every element is related to itself.

Antisymmetric Relation

If a and b are related, and a is not equal to b, then b is not related to a.

Transitive Relation

If a is related to b and b is related to c, then a is related to c.

Cardinality of Sets

The measurement of the