Sets and Functions

See set operations A∪BA \cup B, A∩BA \cap B, AcA^c, De Morgan's laws, and injective / surjective / bijective maps as pictures.

(A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c
f bijective  ⟺  ∃g:g∘f=idf \text{ bijective} \iff \exists g: g \circ f = \mathrm{id}

Part of these learning paths

Examples & Exercises

Prove (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c element by element.

x∈(A∪B)c  ⟺  x∉A∪B  ⟺  x∉A and x∉B  ⟺  x∈Ac∩Bcx \in (A \cup B)^c \iff x \notin A \cup B \iff x \notin A \text{ and } x \notin B \iff x \in A^c \cap B^c
Venn diagram with the union lit — complementing leaves only the outside region.
Show proof
  1. Take an element xx. By the definition of complement, x∈(A∪B)c  ⟺  x∉A∪Bx \in (A \cup B)^c \iff x \notin A \cup B.
  2. x∉A∪B  ⟺  ¬(x∈A∨x∈B)x \notin A \cup B \iff \lnot(x \in A \lor x \in B). By the propositional De Morgan's law this is ¬(x∈A)∧¬(x∈B)\lnot(x \in A) \land \lnot(x \in B), i.e. (x∉A)∧(x∉B)(x \notin A) \land (x \notin B).
  3. (x∉A)∧(x∉B)  ⟺  x∈Ac∧x∈Bc  ⟺  x∈Ac∩Bc(x \notin A) \land (x \notin B) \iff x \in A^c \land x \in B^c \iff x \in A^c \cap B^c. Since xx was arbitrary, (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c.

Prove f:A→Bf: A \to B is bijective iff a two-sided inverse g:B→Ag: B \to A exists.

Bijective mode — every dot is hit exactly once.
Show proof
  1. (⇒) For each b∈Bb \in B there is an aa with f(a)=bf(a) = b (surjective), and by injectivity that aa is unique. Call it g(b)g(b); this defines g:B→Ag: B \to A.
  2. g(f(a))=ag(f(a)) = a because the unique element mapping to f(a)f(a) is aa itself; and f(g(b))=bf(g(b)) = b is exactly the definition of g(b)g(b).
  3. (⇐) Suppose such a gg exists. If f(a1)=f(a2)f(a_1) = f(a_2), applying gg gives a1=g(f(a1))=g(f(a2))=a2a_1 = g(f(a_1)) = g(f(a_2)) = a_2 — injective. And for b∈Bb \in B, putting a=g(b)a = g(b) gives f(a)=f(g(b))=bf(a) = f(g(b)) = b — surjective. Hence ff is bijective.

Prove ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert for finite sets, and evaluate it for ∣A∣=5\lvert A\rvert=5, ∣B∣=4\lvert B\rvert=4, ∣A∩B∣=2\lvert A\cap B\rvert=2.

∣A∪B∣=5+4−2=7\lvert A \cup B\rvert = 5 + 4 - 2 = 7
∣A∣=5\lvert A\rvert=5, ∣B∣=4\lvert B\rvert=4, overlap 22 — the union has 77.
Show proof
  1. A∪BA \cup B is the disjoint union of the three pairwise-disjoint pieces A∖BA \setminus B, B∖AB \setminus A, and A∩BA \cap B.
  2. ∣A∣=∣A∖B∣+∣A∩B∣\lvert A \rvert = \lvert A \setminus B \rvert + \lvert A \cap B \rvert and ∣B∣=∣B∖A∣+∣A∩B∣\lvert B \rvert = \lvert B \setminus A \rvert + \lvert A \cap B \rvert (both are disjoint unions).
  3. Adding the two equations gives ∣A∣+∣B∣=∣A∪B∣+∣A∩B∣\lvert A \rvert + \lvert B \rvert = \lvert A \cup B \rvert + \lvert A \cap B \rvert — the overlap was counted twice. Rearranging yields ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert.
  4. Substituting ∣A∣=5\lvert A \rvert = 5, ∣B∣=4\lvert B \rvert = 4, ∣A∩B∣=2\lvert A \cap B \rvert = 2 gives ∣A∪B∣=5+4−2=7\lvert A \cup B \rvert = 5 + 4 - 2 = 7.

1. Number Systems