Questions: Sets, Relations, and Functions in Discrete Mathematics

Question 1

The relation R = {(1,a), (1,b), (2,c)} has domain {1, 2} and codomain {a, b, c}. Is R a function?

• A. Yes — every domain element appears in at least one pair
• B. No — element 1 is paired with two different codomain elements
• C. No — element c is not paired with any domain element
• D. Yes — if we take the first occurrence of each domain element

Answer: (B)

A function requires every domain element to map to exactly one codomain element. Element 1 maps to both a and b, which violates this rule — R is a relation but not a function. Option A describes a property of relations in general, not functions specifically. Option C confuses the domain with the codomain: the requirement that every domain element has an output doesn't say anything about which codomain elements get 'hit' — that is the surjection question.

Question 2

A bijection exists from set A to set B. What does this guarantee?

• A. Both A and B are finite sets
• B. A and B have the same cardinality
• C. Every element of A is numerically less than every element of B
• D. A and B are subsets of a common larger set

Answer: (B)

A bijection is a function that is both injective (one-to-one: distinct inputs give distinct outputs) and surjective (onto: every codomain element is hit by at least one input). A bijection establishes a perfect one-to-one correspondence between elements, which is the definition of equal cardinality. This works for infinite sets too — the bijection f(n) = 2n from ℤ to the even integers proves they have the same cardinality even though the even integers seem 'smaller'.

Question 3

Every equivalence relation on a set A partitions A into disjoint equivalence classes that together cover all of A.

• T. True
• F. False

Answer: True

This is the fundamental equivalence-classes theorem. Reflexivity guarantees every element is in at least one class (it belongs to its own class). Symmetry and transitivity together guarantee that being in the same class is a consistent, well-defined grouping. The resulting classes are disjoint (no element can belong to two different classes) and exhaustive (every element belongs to exactly one). This partition interpretation is often the most useful way to think about equivalence relations.

Question 4

A function that is injective (one-to-one) is expected to also be surjective (onto).

• T. True
• F. False

Answer: False

Injection and surjection are independent properties. The function f: ℤ → ℤ defined by f(n) = 2n is injective (distinct inputs give distinct outputs) but not surjective (odd integers are never in the image). A function can be injective without being surjective, surjective without being injective, both (bijection), or neither. Only when domain and codomain are finite sets of equal size does injectivity force surjectivity — but that is a special case, not a general rule.

Question 5

Why must a function map every domain element to exactly one codomain element — what fails if it maps to zero elements, or to two elements?

Model answer: If an element maps to zero outputs, the function is undefined on part of its domain — it fails to be a total function, making expressions like f(x) meaningless for those inputs. If an element maps to two different outputs, the function becomes ambiguous — f(x) would simultaneously equal two different values, undermining the whole point of a function as a deterministic mapping. A well-defined function must be both total (defined everywhere on the domain) and single-valued (one output per input).

Partial functions (undefined on some inputs) and multivalued relations (multiple outputs) are both legitimate mathematical objects, but they are not functions. The single-valuedness condition is what allows functions to be composed, inverted (when bijective), and reasoned about deterministically. Many of the key theorems about functions — and their algorithmic interpretations in computer science — depend on this uniqueness property.