CSE240 -- Exam 2 Vocab

Question 1

proof by contradiction

Answer 1

Assume theorem is false, then show that some logical inconsistency arises as a result of the assumption.

Question 2

proof by cases

Answer 2

Of a universal statement–breaks domain for the variable x into different classes and gives a different proof of each class.

Question 3

bidirectional proof

Answer 3

Proving a statement of the form “P if and only if Q” where both directions of the implication must be proven.

Question 4

set

Answer 4

Collection of objects. Objects may be of various types.

Question 5

element

Answer 5

Each object in a set.

Question 6

roster notation

Answer 6

Definition of a set where a list of elements enclosed in curly braces w/ the inidividual elements separated by commas.

Question 7

empty set

Answer 7

Set with no elements. Denoted by ∅. Also referred to as “null set” and can be denoted by {}.

Question 8

finite/infinite

Answer 8

Set that is either empty or whose elements ccan be numbered 1 through n for some positive integer n / set that is not ___.

Question 9

cardinality

Answer 9

Denoted by |A| where A is a finite set, the number of distinct elements in A.

Question 10

containment

Answer 10

Relationship between sets where one set is a subset of another.

• A ⊆ B means A is contained in B, including the possibility that A and B are equal.
• A ⊂ B means A is properly contained in B, meaning A is a subset of B but not equal to B.

Question 11

set builder notation

Answer 11

Set is deifned by specifying that the set includes all elements in a larger set that also satisfy certain conditions.

Looks like: A = {x ∈ S: P(x)}

Question 12

N, Z, Z+, Q, R

Answer 12

Set of natural numbers (set of all integers that are greater than or equal to 0), set of all integers, set of all positive integers, set of rational numbers (set of real numbers that can be expressed a/b), set of real numbers.

Question 13

universal set

Answer 13

Denoted by variable U, is a set that contins all elements mentioned in a particular context.

Question 14

Venn diagram

Answer 14

Pictorially represents sets–a rectangle denotes the universal set U, and oval shapes denote sets within U.

Question 15

subset

Answer 15

If every element in A is also an element of B, then A is a ____ of B, denoted as A ⊆ B.

Question 16

proper subset

Answer 16

If A ⊆ B and there is an element of B that is not an element of A (that is, A != B), then A is a ____ of B, denoted as A ⊂ B.

Question 17

power set

Answer 17

Denoted P(A), is the set of all subsets of A.

Question 18

union

Answer 18

Denoted A ∪ B, the set of all elements that are elements of A or B.

Question 19

intersection

Answer 19

Set of elements that are common to both sets, denoted by the symbol ∩.

Question 20

generalized (possibly infinite) union/intersection

Answer 20

Union of an arbitrary (possibly infinite) collection of sets.

Question 21

set difference

Answer 21

Denoted A - B, set of elements that are in A but not in B.

Question 22

complement

Answer 22

Set of all elements in U that are not elements of A.

Question 23

ordered pair

Answer 23

Items written in (x, y).

Question 24

ordered tuple

Answer 24

Ordered list of three items, denoted (x, y, z).

Question 25

entry

Answer 25

Individual element, for example the first _ANSWER_ in the ordered pair (x, y) is x.

Question 26

string

Answer 26

A sequence of characters.

Question 27

alphabet

Answer 27

Set of characters used in a set of strings.

Question 28

length

Answer 28

Number of characters in the string.

Question 29

binary string

Answer 29

A string with alphabet {0, 1}.

Question 30

bit

Answer 30

A character in a binary string.

Question 31

empty string

Answer 31

Unique string with a length of 0 and is usually denoted by the symbol lambda.

Question 32

concatenation

Answer 32

____ of ***s*** and ***t*** (denoted ***st***) is the string obtained by putting ***s*** and ***t*** together.

Question 33

Cartesian product

Answer 33

Denoted A x B, is the set of all ordered pairs in which the first entry is in A and the second entry is in B. A x B = {(a, b): a ∈ A and b ∈ B}

Question 34

disjoint

Answer 34

Two sets A and B are ____ if the intersection of the two sets is empty (A ∩ B = 0).

Question 35

partition

Answer 35

_ANSWER_ of a non-empty set A is a collection of non-empty subsets of A such that each element of A is in exactly one of the subsets.

Question 36

function

Answer 36

Maps elements from one set ***X*** to elements of another set ***Y***.

Question 37

domain

Question 38

target (co-domain)

Question 39

range

Question 40

arrow diagram

Question 41

floor/ceiling

Question 42

one-to-one/injection

Question 43

onto/surjection

Question 44

one-to-one correspondence/bijection

Question 45

inverse

Question 46

composition

Question 47

identity function

Question 48

logarithm function

Question 49

sequence

Question 50

term

Question 51

index

Question 52

finite sequence

Question 53

initial and final term

Question 54

explicit formula

Question 55

increasing

Question 56

decreasing

Question 57

non-decreasing

Question 58

non-increasing

Question 59

geometric sequence

Question 60

common ratio

Question 61

arithmetic sequence

Question 62

common difference

Question 63

recursive sequence

Question 64

recurrence relation

Question 65

initial terms

Question 66

Fibonacci sequence

Question 67

summation

Question 68

index

Question 69

lower and upper limit

Question 70

base case

Question 71

inductive step

Question 72

inductive hypothesis

Question 73

induction (regular and strong)

Question 74

factorial

Question 75

recursive definition

Question 76

recursion

Question 77

recursive set

Question 78

basis step

Question 79

recursive step

Question 80

root

Question 81

binary tree (perfect or full)

Question 82

structural induction