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
Let R be a binary relation on a finite set A with a, b ∈ A
If there is a path from a to be in R, then there is a path of length at most |A|
Path Theorem
To prove that certain sets, such as the set of real numbers, are uncountable by constructing an element not in any assumed complete list through differing values along a diagonal.
Diagonalization Principle
Property of a set with respect to an operation, where performing the operation on elements of the set always results in an element that is also within the set.
Closure
i.e.
Natural numbers are closed under addition (nat num n + m will equal nat num)
Natural numbers are not closed under subtraction
(nat num n - m could not equal nat num [negative num])
Integers are closed under subtraction
(int n - m can equal a neg num)
The reflexive, transitive closure of a relation.
- (Kleene star)
Any finite set with elements that are called symbols
Σ
Alphabet
Difference between Σ and Σ*
Σ refers to the set of individual symbols or characters (the alphabet)
Σ* refers to the set of all possible finite strings (or words) that can be formed using the alphabet Σ
The simple joining of two strings by appending the second string to the end of the first.
◦
Informal concatenation
The precise operation of combining two strings from a formal language, creating a new string by appending all symbols of the second string to the first, preserving order.
◦
Formal concatenation
A sequence of characters within a word that can be written as v in w = xvy, where x and y are potentially empty strings.
Substring
The set of all strings that can be formed by concatenating zero or more strings from L. It is specific to formal languages and operations.
Kleene star * of a language
The set of all strings that can be formed by concatenating one or more strings from the language L.
Excludes the empty string.
Kleene plus K^+
Relation consists of all ordered pairs where the first and second elements are swapped. If R contains (a, b), then this contains (b, a)
Inverse relation
