d420 Discrete Math: Functions and Relations - Set 4 - Part 1

Correct Answer: A subset of the Cartesian product A×B

A relation from set A to set B is a subset of the Cartesian product A×B, which consists of ordered pairs where the first element is from A and the second element is from B.

Correct Answer: The set of possible output values

The codomain of a function is the set of possible output values that the function can map to, though not every element in the codomain must have a corresponding element in the domain.

Correct Answer: The set of all images of elements in the domain

The range of a function is the set of actual output values (or images) that are mapped from the elements of the domain.

Correct Answer: Every element of the domain maps to a unique element of the codomain

An injective function is one in which distinct elements in the domain map to distinct elements in the codomain.

Correct Answer: Every element of the codomain has at least one preimage

A surjective function (or onto function) ensures that every element of the codomain is the image of at least one element in the domain.

Correct Answer: A function that is both injective and surjective

A bijection is a function that is both injective (one-to-one) and surjective (onto), meaning it establishes a one-to-one correspondence between elements of the domain and the codomain.

Correct Answer: The result of applying one function to the result of another function

Function composition is the process of applying one function to the result of another function, often written as f(g(x)).

Correct Answer: A subset of the Cartesian product of two sets

A binary relation is a subset of the Cartesian product of two sets, representing relationships between pairs of elements from those sets.

Correct Answer: The set of all elements related to a given element under an equivalence relation

An equivalence class consists of all elements that are related to a specific element under an equivalence relation.

Correct Answer: To return the same input as the output

The identity function is a function that returns the same value as its input, often written as I(x)=x.

Correct Answer: A function that reverses the effect of the original function

The inverse of a function undoes the effect of the original function, meaning that applying the function and its inverse successively returns the original input.

Correct Answer: Every element in the set is related to itself

A reflexive relation is one in which every element is related to itself, meaning for all elements a, (a,a) is in the relation.

Correct Answer: If a is related to b, then b is related to a

A symmetric relation is one in which if one element is related to another, the reverse relation also holds.

Correct Answer: If a is related to b and b is related to a, then a=ba = ba=b

An antisymmetric relation is one where if A is related to B and B is related to A, then A must equal B.

Correct Answer: If A is related to B and B is related to C, then A is related to C

A transitive relation is one where if A is related to B and B is related to C, then A must also be related to C.

Correct Answer: A binary relation that is transitive and antisymmetric but not reflexive

A strict partial order is a binary relation that is transitive and antisymmetric, meaning it does not contain self-loops.

Correct Answer: Every pair of elements is comparable

In a total order, every pair of elements is comparable, meaning one is always either less than or greater than the other.

Correct Answer: A graph with directed edges and no cycles

A directed acyclic graph (DAG) is a graph with directed edges that contains no cycles.

Correct Answer: A tree with one designated vertex as the root

A rooted tree is a tree with a designated root vertex, from which all other vertices are connected in a hierarchical manner.

Correct Answer: A subgraph that includes all vertices of the original graph and is a tree

A spanning tree is a subgraph that includes all vertices of the original graph but contains no cycles, forming a tree.