TOCWA HO1

Universal Set

A set that contains all objects under consideration, denoted U

Element

An object within a set

Subset (A ⊆ B)

A set whose elements can all be found in another defined set; every element of C is also in D

Proper Subset (A ⊂ B)

A subset that is not equal to the set it belongs to

Power Set ℘(A)

The set of all subsets of a defined set

Empty Set (⌀)

A set having no elements in it

Finite Set

A set that contains no element or a finite number of elements

Infinite Set

A set that contains an infinite number of elements

List Notation

Describing a set by listing all its elements; suitable only for finite sets. Ex. {1, 2, 4, 24, 37}

Predicate Notation

Describing a set by stating a shared property/condition for all elements. Ex. {x | x is a letter of the English alphabet}

Recursive Rule

Describing a set by defining rules that generate its elements. Ex. Set C of even numbers >3: a) 4∈C; b) if x∈C, then x+2∈C

Union (A ∪ B)

{x | x ∈ A or x ∈ B}

Intersection (A ∩ B)

{x | x ∈ A and x ∈ B}

Difference (A − B)

{x | x ∈ A and x ∉ B}

Complement (A′)

{x ∈ U : x ∉ A}

Cartesian Product (A × B)

{(a, b) | a ∈ A and b ∈ B}

Concatenation (A·B)

{ab | a is in A, and b is in B}

Relation

Links existing between objects; pertains to relationships between elements of sets

Binary Relation

If A and B are any sets, R ⊆ A × B is a binary relation from A to B; R ⊆ A × A is a relation on A

Domain of a Relation

The set of values for which a specific function is defined; {a | <a,b> ∈ R for some b}

Range of a Relation

The set of values that a function takes; {b | <a,b> ∈ R for some a}

Relation as a Matrix

Representation of a relation R between sets A (m elements) and B (n elements) as an m×n matrix

Relation as a Graph

Representation of a relation using n nodes (for a set of n elements) with edges showing the relation R

Reflexive Relation

For each a ∈ A, a is related to a; (a,a) ∈ R for every a ∈ A

Irreflexive Relation

For each a ∈ A, a is not related to a (not the negation of reflexive)

Symmetric Relation

aRb implies bRa is true

Antisymmetric Relation

aRb implies bRa is false

Transitive Relation

If aRb and bRc are true, then aRc is also true

Equivalence Relation

A relation that is reflexive, symmetric, and transitive

Function

A specific kind of relation that relates exactly one output to each admissible input

One-to-one Function

A one-to-one correspondence between elements of two different sets

Many-to-one Function

A many-to-one correspondence between elements of two different sets

Onto Function

Every element of set B has at least one corresponding element from set A

Bijection

A function that is one-to-one and onto at the same time

Surjection

A function that is many-to-one and onto at the same time

Into Function

At least one element of set B has no corresponding element from set A

Alphabet Set (Σ)

A finite set of symbols used to form strings

Σ*

Set of all strings over an alphabet Σ (including the empty string)

Σ+

Set of all strings over a non-empty alphabet Σ (excluding the empty string)

Epsilon (ε)

Empty string

Grammar (V, T, P, S)

A formal system defining a language: V=variables, T=terminals, P=productions, S=start symbol

Regular Expression (R)

A pattern that describes a set of strings

Set of States (Q)

The complete set of states in an automaton

Set of Final States (F)

The accepting states in an automaton

Transition Function (∆)

Function/set defining state transitions or output symbols

Stack Symbol (Γ)

A symbol used in a pushdown automaton's stack

Initial Stack Symbol (Z0)

The starting symbol placed on the stack

Blank Symbol (B)

Symbol representing an empty cell on a Turing machine tape

Instantaneous Description <l, q, r>

A snapshot of a Turing machine's configuration (left tape, state, right tape)

k-Equivalence Class (∏k)

A partition of states based on equivalence after k steps

Homomorphism Function (h)

A function that maps symbols/strings from one alphabet to another while preserving structure