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

Correct Answer: Reflexivity

Because every element relates to itself, the relation is reflexive. Other properties would require checking additional pairs.

Correct Answer: Symmetry

When each pair (a,b) has its reverse (b,a) also present, the relation is symmetric.

Correct Answer: Surjective (hence bijective)

For finite sets of equal size, an injective function must also be surjective, making it bijective.

Correct Answer: The greatest integer less than or equal to x

The floor function ⌊x⌋ gives the largest integer that does not exceed x; for example ⌊3.7⌋ = 3.

Correct Answer: The smallest integer greater than or equal to x

The ceiling function ⌈x⌉ gives the smallest integer not less than x; for example ⌈3.2⌉ = 4.

Correct Answer: 7

The floor of 7.9 is the greatest integer at most 7.9, which is 7.

Correct Answer: 5

The ceiling of 4.1 is the smallest integer at least 4.1, which is 5.

Correct Answer: A constant function

A constant function assigns the same single output value to every input in the domain.

Correct Answer: No

A constant function maps many distinct inputs to the same output, so it is not injective when the domain has more than one element.

Correct Answer: The identity function

Composing a bijection with its inverse yields the identity function, returning each element to itself.

Correct Answer: All elements related to a

The equivalence class [a] consists of every element that is related to a under the equivalence relation.

Correct Answer: Identical or disjoint

Distinct equivalence classes never partially overlap; any two are either exactly the same set or completely disjoint.

Correct Answer: 3

Congruence modulo 3 partitions the integers into three classes based on remainders 0, 1, and 2.

Correct Answer: A partial order relation

A Hasse diagram is a simplified graph that visualizes a partial order by omitting implied reflexive and transitive edges.

Correct Answer: Has no element greater than it

A maximal element has no other element strictly above it, though it need not be greater than every element (that would be a greatest element).

Correct Answer: A partial order in which every pair of elements is comparable

A total order is a partial order where any two elements can be compared; less-than-or-equal on the reals is an example.

Correct Answer: Bijective

The composition of two bijections is itself a bijection, since it is both injective and surjective.

Correct Answer: All pairs (b, a) where (a, b) is in R

The inverse relation reverses each ordered pair, so (a, b) in R becomes (b, a) in R⁻¹.

Correct Answer: Symmetric

If reversing every pair yields the same relation, then (a,b) in R implies (b,a) in R, which is exactly symmetry.

Correct Answer: 2^(n²)

A relation is a subset of the n² ordered pairs in A × A, and there are 2^(n²) such subsets.