quantitative methods prelim

Sets

These are used to describe a collection of objects.

Elements

These are the objects within a set.

Subset

This is a set that contains elements that can all be found in another defined set or a universal set.

Power Set

This is the set of all subsets of a defined set.

Empty Set

It is 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

This method is suitable only for finite sets. It is done by listing all its elements.

Predicate notation

This method is done by stating a shared property or condition that holds for all the elements in the set.

Recursive rule

This method is made by defining a set of rules that generate or define its elements.

Union

If there are two sets C and D, then their union is denoted by C U D.

Intersection

If there are two sets C and D, then their intersection is denoted by C n D.

Difference

If there are two sets C and D, then their difference is denoted by C - D.

Complement

The complement of a set, which is a subset of a larger set U, is denoted by C'.

Cartesian Product

If there are two sets C and D, then their Cartesian product is denoted by C x D.

Concatenation

If there are two sets C and D, then their concatenation is denoted by C . D.

Relations

These are links existing between objects; therefore, it pertains to relationships between elements of sets.

Binary Relation

If A and B are any sets R subset A x B, R is called a binary relation from A to B or between A and B.

Domain Relation

The domain refers to a set of values for which a specific function is defined.

Range Relation

The range refers to the set of values that a specific function takes.

Reflexive

A relation on A is said to be reflexive if, for each a in A, a is related to a.

Irreflexive

A relation on A is said to be irreflexive if, for each a in A, a is not related to a.

Symmetric

A relation R on A is symmetric if aRb implies bRa is true.

Antisymmetric

A relation R on A is antisymmetric if aRb implies bRa is false.

Transitive

A relation R is said to be transitive for a, b, c in A if aRb and bRc are true, then aRc is also true.

Equivalence Relation

A relation R is said to be an equivalence relation on a set if R is reflexive, symmetric, and transitive.

Function

It may refer to a specific process or as correspondence. It is generally represented in set-theoretic terms as a specific kind of relation where exactly one output is related to each admissible input.

One-to-one Function

There is a one-to-one correspondence between the elements of two different sets.

Many-to-one Function

There is a many-to-one correspondence between the elements of two different sets.

Onto Function

This function has every element of set B with at least one corresponding element from set A.

Into Function

This function has at least one element of set B that has no 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.

Alphabet

It refers to a finite collection of symbols denoted by Sigma.

String/word

It refers to a set of symbols from an alphabet.

Language

This is a dynamic set of visual, auditory, or tactile symbols of communication and the specific elements used in language manipulation.

Grammar

It is defined as a set of 4-tuple V, T, P, and S representing non-terminals, terminals, productions, and start symbol.

Type 0 grammar (Unrestricted grammar)

Defines recursively enumerable languages with no restrictions on either side of productions except having at least one non-terminal on the LHS.

Type 1 grammar (Context-sensitive grammar)

Defines context-sensitive languages where all productions length of LHS is less than or equal to length of RHS.

Type 2 grammar (Context-free grammar)

Defines context-free languages where LHS is a single non-terminal and RHS is a string of terminals and non-terminals.

Type 3 grammar (Regular grammar)

Defines regular languages where rules are restricted to a single non-terminal on the LHS and a single terminal/string on RHS.

Graph

An abstract representation of a set of objects where some pairs of objects are connected by directed or undirected links.

Directed Graph

A graph with edges that have a direction (with arrow heads).

Undirected Graph

A graph with edges that have no direction (without arrow heads).

Incident

This occurs when an edge meets a vertex.

Degree

This pertains to the number of edges incident on a vertex.

Isolated Verte

xThis refers to a vertex of a graph having no incident edge.

Pendant Verte

xThis refers to a vertex of degree one.

Walk/Path

A finite alternating sequence of vertices and edges, starting and ending with vertices.

Tree

An undirected graph composed of vertices and edges with a specially designed vertex called root and no cycles.

Root

A specially designed vertex which has no predecessors and from which there is a path to every vertex.

Leaf Node / Terminal Node

The vertex of a tree having degree one.

Non-terminal Node

Nodes in a tree other than the leaf nodes.

Parent

In a rooted tree, vertex p is the parent of vertex q if p immediately precedes q on the path from the root to q.

Child

In a rooted tree, vertex q is a child of vertex p if q immediately succeeds p on the path from the root to q.

Siblings

Two vertices in a rooted tree that have the same parent.

Depth of a node

The length of the path, or the number of edges from the root of the tree to the target node.

Level of the tree

The set of all nodes at a given depth.

Height of a tree

The length of the path from the root to the deepest node in the tree.

Theorem

A formula, proposition, or statement that can be logically true by proving.

Proof by Induction

A mathematical technique used to prove a statement, formula, or theorem to be true for every natural number using a Base Step and an Inductive Step.

Proof by Contradiction

A proving technique involving the logical negation of the expected result to arrive at a contradiction.

Proof by Example

A technique of proving that involves deriving conclusions based on one or more examples.