D421 Discrete Math: Functions and Relations - Set 1 - Part 2

Correct Answer: A relation that is reflexive, symmetric, and transitive

An equivalence relation satisfies all three properties: reflexivity, symmetry, and transitivity. It partitions a set into equivalence classes.

Correct Answer: Disjoint equivalence classes

An equivalence relation divides a set into disjoint equivalence classes whose union is the whole set.

Correct Answer: Equality (=)

Equality is reflexive, symmetric, and transitive, making it an equivalence relation. Less than fails reflexivity and symmetry.

Correct Answer: If (a, b) and (b, a) are both in R, then a equals b

A relation is antisymmetric if the only way both (a, b) and (b, a) can be in R is when a = b. Less-than-or-equal is antisymmetric.

Correct Answer: A relation that is reflexive, antisymmetric, and transitive

A partial order is reflexive, antisymmetric, and transitive. The subset relation and less-than-or-equal are common examples.

Correct Answer: A relation assigning each element of A exactly one element of B

A function assigns to each element of the domain A exactly one element of the codomain B.

Correct Answer: The domain

A is the domain, the set of inputs. B is the codomain, and the actual outputs form the range or image.

Correct Answer: The set into which the function maps, containing all possible outputs

The codomain is the target set B. The range (image) is the subset of the codomain actually produced by the function.

Correct Answer: The range is the set of actual outputs; the codomain is all possible outputs

The range is the set of values the function actually takes, which is a subset of the codomain. They are equal only for surjective functions.

Correct Answer: Different inputs always map to different outputs

An injective function maps distinct inputs to distinct outputs: if f(a) = f(b) then a = b.

Correct Answer: Every element of the codomain is the image of some input

A surjective function covers the entire codomain: every element of B equals f(a) for at least one a in A.

Correct Answer: A function that is both injective and surjective

A bijection is both one-to-one and onto, establishing a perfect pairing between domain and codomain. Only bijections have inverses.

Correct Answer: A bijective function

A function has an inverse if and only if it is bijective, since each output must correspond to exactly one input and every output must be used.

Correct Answer: f(g(x))

The composition (f ∘ g)(x) means apply g first, then apply f to the result: f(g(x)).

Correct Answer: 3x + 2

(f ∘ g)(x) = f(g(x)) = f(3x) = 3x + 2, applying g first and then f.

Correct Answer: The function that maps every element to itself

The identity function id(x) = x maps every element of A to itself and acts as the neutral element for composition.

Correct Answer: f⁻¹(x) = x − 5

To invert f(x) = x + 5, solve y = x + 5 for x, giving x = y − 5, so f⁻¹(x) = x − 5.

Correct Answer: No, because there are more inputs than outputs

By the pigeonhole principle, mapping 3 inputs to only 2 outputs forces at least two inputs to share an output, so f cannot be injective.

Correct Answer: If n items go into m containers with n greater than m, some container holds more than one

The pigeonhole principle states that if more items are placed into fewer containers than items, at least one container must hold more than one item.

Correct Answer: Bijection

Two sets have equal cardinality precisely when a bijection exists between them, pairing their elements one to one.