CSE240 -- Exam 2 Vocab Flashcards
proof by contradiction
Assume theorem is false, then show that some logical inconsistency arises as a result of the assumption.
proof by cases
Of a universal statement–breaks domain for the variable x into different classes and gives a different proof of each class.
bidirectional proof
Proving a statement of the form “P if and only if Q” where both directions of the implication must be proven.
set
Collection of objects. Objects may be of various types.
element
Each object in a set.
roster notation
Definition of a set where a list of elements enclosed in curly braces w/ the inidividual elements separated by commas.
empty set
Set with no elements. Denoted by ∅. Also referred to as “null set” and can be denoted by {}.
finite/infinite
Set that is either empty or whose elements ccan be numbered 1 through n for some positive integer n / set that is not ___.
cardinality
Denoted by |A| where A is a finite set, the number of distinct elements in A.
containment
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.
set builder notation
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)}
N, Z, Z+, Q, R
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.
universal set
Denoted by variable U, is a set that contins all elements mentioned in a particular context.
Venn diagram
Pictorially represents sets–a rectangle denotes the universal set U, and oval shapes denote sets within U.
subset
If every element in A is also an element of B, then A is a ____ of B, denoted as A ⊆ B.
proper subset
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.
power set
Denoted P(A), is the set of all subsets of A.
union
Denoted A ∪ B, the set of all elements that are elements of A or B.
intersection
Set of elements that are common to both sets, denoted by the symbol ∩.
generalized (possibly infinite) union/intersection
Union of an arbitrary (possibly infinite) collection of sets.
set difference
Denoted A - B, set of elements that are in A but not in B.
complement
Set of all elements in U that are not elements of A.
ordered pair
Items written in (x, y).
ordered tuple
Ordered list of three items, denoted (x, y, z).
entry
Individual element, for example the first ANSWER in the ordered pair (x, y) is x.
string
A sequence of characters.
alphabet
Set of characters used in a set of strings.
length
Number of characters in the string.
binary string
A string with alphabet {0, 1}.
bit
A character in a binary string.
empty string
Unique string with a length of 0 and is usually denoted by the symbol lambda.
concatenation
____ of s and t (denoted st) is the string obtained by putting s and t together.
Cartesian product
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}
disjoint
Two sets A and B are ____ if the intersection of the two sets is empty (A ∩ B = 0).
partition
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.
function
Maps elements from one set X to elements of another set Y.
domain
target (co-domain)
range
arrow diagram
floor/ceiling
one-to-one/injection
onto/surjection
one-to-one correspondence/bijection
inverse
composition
identity function
logarithm function
sequence
term
index
finite sequence
initial and final term
explicit formula
increasing
decreasing
non-decreasing
non-increasing
geometric sequence
common ratio
arithmetic sequence
common difference
recursive sequence
recurrence relation
initial terms
Fibonacci sequence
summation
index
lower and upper limit
base case
inductive step
inductive hypothesis
induction (regular and strong)
factorial
recursive definition
recursion
recursive set
basis step
recursive step
root
binary tree (perfect or full)
structural induction
