Sets, Relations, and Languages Flashcards
A collection of objects ( denoted by { } )
Set
Objects comprising a set are called ( denoted by ∈ )
Elements
What is a relative complement?
For sets A and B, x is an element of A and not an element of B
What is the set of all subsets ( denoted by 𝒫(A) or 2^A )
Power set
Any set R such that R ⊆ A x A is called
A set of ordered pairs, (m, n), where m is from the set M, n is from the set N, and m is related to n by some rule
Binary relation
A function that maps every element in the codomain to an element in the domain
onto function
A function that maps each input value to a unique output value
one-to-one function
A function that establishes a binary relationship between two sets
into function
The set of all ordered pairs where one element is from the first set and the other is from the second set ( A and B (a, b) )
Cartesian product
What are natural numbers?
N = { 0, 1, 2, 3, … }
What are integers and positive integers?
Z = { …, -3, -2, -1, 0, 1, 2, 3, … }
Z+ = { 1, 2, 3, … } ( Also called positive natural numbers N+)
An ordered list of numbers (called “terms”) that often follow a specific pattern or rule, where the order of the terms matters
Sequence
A relationship on a set, generally denoted by ∼ , ≈, or ≡ that is reflexive, symmetric, and transitive for everything in the set
Equivalence relation
A division of a set A is a grouping of non-empty, disjoint subsets whose union equals A
Partition
A binary relation on a set that is reflexive, antisymmetric, and transitive
Denoted by ≤
Order relation
Set A (nonempty) ordered by an order relation R
Poset
Sets that have a one-to-one and onto (bijective) correspondence between their elements.
Equinumerous sets
A relationship between sets which compares their relative size
Sets are equipotent A ~ B
|A| or |B|
Cardinality of sets
Also can be
cardA or cardB
A set that contains a specific number of elements, where the number of elements is a non-negative integer.
Finite set
A set that contains an unbounded or limitless number of elements.
*Dedekind Theorem
Infinite set
A set has the same cardinality as the set N natural numbers
|A| = |N|
Countably infinite
For any set A, the power set of A has a strictly greater cardinality than A itself
There is no one-to-one correspondence between A and P(A), meaning P(A) is always larger than A, even if A is an infinite set
Cantor Theorem
If you have two sets A and B, the number of functions from set A to set B is |B|^|A|
The total number of possible functions from A to B is calculated by raising the size of B to the power of the size of A. Each element in A has |B| choices for its image, so the product for all elements of A gives the total number of functions.
Counting Functions Theorem
If n items are placed into m containers, and n > m, then at least one container must contain more than one item.
Pigeonhole Principle