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

Correct Answer: Injective

With more inputs than outputs, the pigeonhole principle forces two inputs to share an output, so f cannot be injective.

Correct Answer: |A| at least |B| (for finite sets)

To cover every element of B, there must be at least as many inputs as outputs, so |A| ≥ |B| for finite sets is necessary.

Correct Answer: The inclusion-exclusion principle

Counting surjections requires inclusion-exclusion to subtract mappings that miss one or more codomain elements.

Correct Answer: Non-negative real numbers

Squaring any real number yields a non-negative result, so the image (range) is the set of non-negative reals.

Correct Answer: No, because f(−2) = f(2)

Since distinct inputs like −2 and 2 give the same output 4, the function is not injective over all reals.

Correct Answer: Not an equivalence relation

An equivalence relation requires all three properties; lacking transitivity disqualifies it.

Correct Answer: Associative

Function composition is associative, meaning (f ∘ g) ∘ h = f ∘ (g ∘ h), but it is generally not commutative.

Correct Answer: No

In general f ∘ g does not equal g ∘ f; the order of composition matters.

Correct Answer: No element is related to itself

An irreflexive relation contains no pair (a, a); the strictly-less-than relation is irreflexive.

Correct Answer: 9

Each of the 2 inputs has 3 possible outputs, giving 3² = 9 functions.

Correct Answer: The range equals the codomain

A surjective (onto) function has range equal to its codomain, meaning every element of B is an output.

Correct Answer: The equality relation

A relation that is symmetric (equivalence) and antisymmetric (order) can only relate equal elements, so it is equality.

Correct Answer: Injective

If f and g are both injective, their composition is injective, since distinct inputs stay distinct through both maps.

Correct Answer: Surjective

If f and g are both surjective, their composition is surjective, since the outputs cover the entire final codomain.

Correct Answer: Directed graph or 0-1 matrix

Relations are commonly represented by directed graphs (arrows between related elements) or 0-1 matrices marking related pairs.

Correct Answer: Element i is related to element j

An entry of 1 at position (i, j) indicates that (i, j) is in the relation, meaning element i relates to element j.

Correct Answer: The smallest transitive relation containing it

The transitive closure adds the minimum pairs needed to make a relation transitive while containing the original.

Correct Answer: Permutation

A bijection from a set to itself is a permutation, rearranging the elements among themselves.

Correct Answer: 24

The number of permutations of 4 elements is 4! = 24.

Correct Answer: Reflexive, symmetric, and transitive

The universal relation containing all pairs is reflexive, symmetric, and transitive, hence an equivalence relation with a single class.