Skip to content
Part BCSIR NET December 2023

Measurable sets and functions

Let X be a non-empty finite set and Y = {f−1(0)f^{-1}(0) : f is a real-valued function on X}. Which one of the following statements is true?

  1. A.Y is an infinite set.
  2. B.Y has 2∣X∣2^{|X|} elements.✓ Correct
  3. C.There is a bijective function from X to Y.
  4. D.There is a surjective function from X to Y.

The idea, in plain words

There are endlessly many functions you could write down, but you are not counting functions — you are counting the sets of points where they vanish. Any set of points can be arranged to be the vanishing set, so you are really counting subsets, and there are far more of those than there are points.

Solution

Every subset of X is the zero set of its indicator-complement (f = 1 off the subset, 0 on it)

so Y is the power set of X, with 2∣X∣2^{|X|} > |X| elements.

Why each option is right or wrong

Checked against 2 symbolic computations
  • A.Wrong

    False.

    There are infinitely many real-valued functions on X

    which is what tempts you here — but the map f ↦ f⁻1(0)^{1}(0) is massively many-to-one, and its image is a set of subsets of the finite set X.

    Y is contained in the power set of X

    so |Y| ≤ 2^|X| <∞< \infty.

    Count the image, not the domain.

  • B.Correct

    True.

    Y is exactly the power set of X.

    Any subset S ⊆ X is realised: define f to be 0 on S and 1 off S

    so f⁻1(0)=S^{1}(0) = S.

    Conversely every zero set is a subset of X.

    Hence |Y| = 2^|X|.

  • C.WrongBoundary and endpoint

    False.

    A bijection would need |Y| = |X|

    but |Y| = 2^|X| and 2n>n2^{n} > n for every n ≥ 1 — even the smallest case fails

    since |X| = 1 gives |Y| = 2 (SymPy: 21−1=12^{1} - 1 = 1

    so the gap is already positive).

    For |X| = 3 the sets have 3 and 8 elements.

  • D.WrongBoundary and endpoint

    False.

    A surjection X → Y needs |X| ≥ |Y|, that is n≥2nn \ge 2^{n}

    which holds for no n ≥ 1.

    The inequality runs the other way: the power set is always strictly larger.

2 of these 3 wrong options correspond to a named reasoning error — the same errors recur across subjects.

Related counterexample: A subset of ℝ with measure zero is countable

More on this topic

The chapter behind this: Lebesgue measure and measurable functions — free to read

From Lebesgue Measure and Integration › Measurable sets and functions

Last revised . Found a mistake? Tell us — corrections are the fastest thing we act on.

ShareWhatsAppTelegram