Sets, Relations and Functions

1Inclusion-exclusion for two sets

For finite sets, the size of a union is not the sum of the sizes. Each element of the intersection would be counted twice if you added n(A) and n(B) alone, so n(A\cup B)=n(A)+n(B)-n(A\cap B). For three sets the same idea continues: add the singles, subtract the pairwise overlaps, then add back the triple overlap that was subtracted too often.

When a problem gives a universal set and asks how many elements lie in none of the named subsets, compute the union first and subtract from the total.

Figure. Partition of A\cup B into only A, the overlap A\cap B, and only B. Adding n(A)+n(B) counts the overlap twice, so subtract it once.

How it works

1. Add the partsWrite n(A)+n(B). Every element of A\cap B has been counted twice.
2. Subtract the overlap onceReplace the double count by a single count: subtract n(A\cap B).
3. Neither, if askedIf a universe U is given, n(U)-n(A\cup B) is the count outside both sets.

2Subsets of a finite set

A set with n elements has 2^n subsets: for each element there are two choices — include it or leave it out — and the choices multiply. That count includes the empty set and the set itself.

The number of non-empty subsets is therefore 2^n-1. "Proper subset" wording in a question needs a careful read: some papers exclude only the set itself, others also exclude the empty set — match the definition the paper is using.

Figure. A 4-element set has 2^4=16 subsets, one yes-or-no choice per element. Dropping the empty set leaves 16-1=15 non-empty subsets.

How it works

1. One bit per elementLabel the elements 1,\ldots,n. A subset is a choice of yes/no for each label.
2. MultiplyIndependent binary choices give 2\times 2\times\cdots\times 2=2^n subsets.
3. Drop the empty set if askedNon-empty count is 2^n-1.

3Reflexive, symmetric, transitive

A relation R on a set A is a subset of A\times A. Three properties are examined constantly: R is reflexive if aRa for every a\in A; symmetric if aRb always forces bRa; transitive if aRb and bRc together force aRc.

Each property is independent of the others. A relation can be symmetric and not transitive, reflexive and not symmetric, and so on — the exam asks you to test the definition, not to guess from a name.

Check the three axioms on pairs: a loop at every element (reflexive), every arrow reversible (symmetric), and closed chains (transitive). The table in this concept lists all three.

How to test

1. Fix the ground setWrite A explicitly. Reflexivity is meaningless until you know every element that must appear on the diagonal.
2. Check each axiomFor a finite R, scan pairs for the symmetric and transitive failures; confirm every (a,a) for reflexivity.
3. Name only what holdsReport each property that survives. Do not call it an equivalence until all three hold.

4Equivalence relations and partitions

A relation that is reflexive, symmetric and transitive is an equivalence relation. Equivalence relations are exactly the relations that partition the ground set into disjoint equivalence classes: a and b lie in the same class precisely when aRb.

Counting equivalence relations on a finite set is the same as counting partitions of that set — the Bell numbers. On a 3-element set there are exactly 5 equivalence relations.

How it works

1. Confirm all three axiomsReflexive, symmetric and transitive — miss one and it is not an equivalence.
2. Read the classesThe class of a is \{x: aRx\}. Distinct classes are disjoint and their union is A.
3. Count via partitionsEach partition of A is the class set of exactly one equivalence relation. For |A|=3 the Bell number is 5.

5One-one, onto and bijective

A function f:A\to B is one-one (injective) when distinct inputs give distinct outputs: f(x_1)=f(x_2) forces x_1=x_2. It is onto (surjective) when every element of B is an image. It is bijective when it is both.

Only bijections are invertible. When an inverse exists, f^{-1}(f(x))=x and f(f^{-1}(y))=y. A calculus shortcut for injectivity on an interval: if f' keeps a constant sign, f is strictly monotonic and therefore one-one.

Figure. y=x^3 is strictly increasing, hence one-one; y=x^2 fails injectivity because two x-values share each positive height. Onto depends on the chosen codomain.

How to test

1. One-oneAssume f(x_1)=f(x_2) and deduce x_1=x_2, or show f' does not change sign on the interval.
2. OntoFor an arbitrary y\in B, solve f(x)=y and show a solution in A always exists.
3. InverseDeclare invertibility only after both tests pass.

6Counting functions and onto maps

The number of functions from a set of m elements to a set of n elements is n^m: each of the m inputs may land on any of n outputs. The number of one-one functions, when m\le n, is \dfrac{n!}{(n-m)!} — an injection is an ordered selection of m distinct images.

Onto maps are counted by inclusion-exclusion: \sum_{r=0}^{n}(-1)^r\binom{n}{r}(n-r)^m. For a two-element codomain the formula collapses to a shortcut — 2^m-2 — total maps minus the two constant functions.

Figure. Maps from a 4-set to a 2-set: 2^4=16 functions in all. Onto maps drop the two constant functions, leaving 16-2=14.

How it works

1. Total mapsEach of m domain elements has n choices, so n^m functions.
2. InjectionsChoose distinct images in order: n(n-1)\cdots(n-m+1)=\dfrac{n!}{(n-m)!} for m\le n.
3. Onto to a 2-setSubtract the two constant maps from 2^m to leave 2^m-2.

7Composition and natural domain

Composition is (g\circ f)(x)=g(f(x)) — apply f first, then g. Composition is associative but generally not commutative: g\circ f and f\circ g need not even both be defined, let alone equal. Associativity still holds in the form (h\circ g)\circ f=h\circ(g\circ f) whenever both sides are defined.

The natural domain of a real function is the largest subset of \mathbb{R} on which the expression makes sense. Exclude values that make a denominator zero or a square-root argument negative. For f(x)=\sqrt{x} the domain is x\ge 0; for \log x it is x>0.

Figure. y=\sqrt{x} is drawn only for x\ge 0: the curve starts at the origin and never enters x<0. That missing half-line is the natural-domain cut.

How it works

1. Read inside-outIn g\circ f, evaluate f(x) first; that output must lie in the domain of g.
2. Do not swapCheck whether f\circ g is even defined before claiming equality with g\circ f.
3. Carve the domainFor a formula, strike out points where a denominator vanishes or a root/log argument leaves its allowed set.