Solutions — Theorems with Proofs (Part 2)
Full statements and proofs for every item in the theorem list. Where the exam lets you choose (“any two”, “any one”), proofs for all the reasonable options are given so you can pick whichever you’re asked for or were taught to prefer. Recall the scoring: theorem/statement = 1 mark, proof = 3 marks (split as 0.5/0.5 and 1.5/1.5 when two statements are asked).
⚠️ Sourcing note: Sections 6–9 (composition of relations and functions) are not covered by any file in your project — only “Examples” decks for relations exist there, not the main lecture deck with the actual theorem statements/proofs (the list cites “slide 13” and “slide 29” of a deck that isn’t among your uploads). The proofs below for those four items use standard definitions consistent with your confirmed course conventions (the -then- composition order, notation), but please check them against your actual lecture slides if you get the chance, in case your course phrases the definition of “function” or uses different variable names.
1. Properties of logical operators (slide 8)
Proposition. For every proposition , the following are tautologies (always true).
All ten properties are proved below by truth table — for any two propositions/connectives, two sides of a biconditional are logically equivalent exactly when they have the same truth value in every row.
Idempotence
| T | T | T |
| F | F | F |
Both columns equal in every row, so both equivalences are tautologies.
Commutativity
| T | T | T | T | T | T |
| T | F | T | T | F | F |
| F | T | T | T | F | F |
| F | F | F | F | F | F |
The and columns agree row-by-row, and likewise for and .
Absorption laws
| T | T | T | T | T | T |
| T | F | T | T | F | T |
| F | T | T | F | F | F |
| F | F | F | F | F | F |
Both derived columns match the -column in every row.
Associativity
| T | T | T | T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | T | F | F | T | F |
| T | F | T | T | T | T | T | F | F | F | F |
| T | F | F | F | T | T | T | F | F | F | F |
| F | T | T | T | T | T | T | T | F | F | F |
| F | T | F | T | T | T | T | F | F | F | F |
| F | F | T | T | T | F | T | F | F | F | F |
| F | F | F | F | F | F | F | F | F | F | F |
In every row, matches , and matches .
De Morgan’s laws
| T | T | T | F | F | T | F | F |
| T | F | T | F | F | F | T | T |
| F | T | T | F | F | F | T | T |
| F | F | F | T | T | F | T | T |
matches , and matches , in every row.
Distributivity
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | F | T |
| T | F | T | T | T | F | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Both columns match in every row, in each table.
Inference rules
Law of contrapositive:
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
The two implication columns agree in every row.
Modus ponens:
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
The final column is T in every row, so the formula is a tautology.
Syllogism:
| full formula | |||||||
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
The final column is T throughout.
Property 10:
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | F | F | F |
| F | F | T | T | T | T |
The two right columns agree in every row.
2. Properties of the subset relation (slide 6)
Proposition. For every set :
Transitivity: .
Proof. Assume and . By definition of , and . Fix any with . Then (first assumption), and so (second assumption). Hence , i.e. .
Antisymmetry: .
Proof. Assume and . By definition of : and . Combining these, . By the definition of set equality (two sets are equal iff they have exactly the same elements), this means .
(The remaining two properties on this slide — and — are not listed as askable proof questions, but are quick to note: holds vacuously since there is no , so the implication is true for every ; holds since is trivially true.)
3. Properties of set union and set intersection (slide 12)
Proposition. For every set :
Properties of union
1. Idempotence: . Proof. . (1) definition of ; (2) idempotence of .
2. Associativity: . Proof. . (1) definition of ; (2) associativity of .
3. Commutativity: . Proof. . (1) definition of ; (2) commutativity of .
4. Property of : . Proof. . (1) definition of ; (2) definition of (no element belongs to it); (3) .
5. . Proof. () Suppose . We always have (every element of is in , by definition of ). Conversely, if then or ; in the first case too, since ; in the second case trivially. So . By antisymmetry of (Section 2), . () Suppose . For any , we have (by definition of ), hence (since ). So .
Properties of intersection
1. Idempotence: . Proof. . (1) definition of ; (2) idempotence of .
2. Associativity: . Proof. Analogous to union, using associativity of in place of : .
3. Commutativity: . Proof. . (1) definition of ; (2) commutativity of .
4. Property of : . Proof. . (1) definition of ; (2) definition of ; (3) .
5. . Proof. () Suppose . We always have . Conversely, if then, since , also ; hence . So . By antisymmetry of , . () Suppose . For any , since we get , hence . So .
4. Distributivity of set union and set intersection (slide 14)
Proposition. For every set :
Proof of . (1) definition of ; (2) definition of ; (3) distributivity of over .
Proof of . (1) definition of ; (2) definition of ; (3) distributivity of over .
5. Properties of set complement (slide 17)
Proposition. Let be the universal set. For every :
1. . Proof. . (1) definition of complement; the last step is double-negation elimination.
2. . Proof. . (1) definition of complement; (2) by definition of and (nothing is in , everything relevant is in ).
3. . Proof. . (1) definition of complement; (2) by definition of and .
4. . Proof. . (1) definition of ; (2) definition of complement; (3) by definition of and (a statement and its negation are never both true).
5. . Proof. . (1) definition of ; (2) definition of complement; (3) by definition of and (a statement or its negation is always true).
6. . Proof. (1) definition of ; (2) law of contrapositive; (3) definition of complement.
7. (De Morgan’s law for ). Proof. . (1) definition of complement; (2) definition of ; (3) De Morgan’s law for the logical operators ; (4) definition of .
8. (De Morgan’s law for ). Proof. . (1) definition of complement; (2) definition of ; (3) De Morgan’s law for the logical operators ; (4) definition of .
(Properties 7 and 8 are the De Morgan’s laws for sets.)
6. Associativity of composition of binary relations (slide 13) ⚠️ not in project files — see note above
Proposition. For all relations , , , the composition of binary relations is associative: Here, recall composition is defined so that — i.e. is applied first, then (your course’s confirmed convention).
Proof. For any and :
(1) definition of composition (applied to the inner and outer compositions); (2) reordering and regrouping of the existential quantifiers and conjunctions, which is always logically valid. Since was arbitrary, .
7. Inverse of the composition of binary relations (slide 13) ⚠️ not in project files — see note above
Proposition. For all relations and :
Proof. For any and :
(1) definition of composition; (2) definition of inverse relation (swap coordinates). Since was arbitrary, .
8. Composition of functions is a function (slide 29) ⚠️ not in project files — see note above
Definition (function). A relation is a function from to if (every has exactly one image under ).
Theorem. Let and be functions. Then the composition (apply first, then ) is a function from to .
Proof. Let be arbitrary; we must show there is exactly one with .
Existence. Since is a function and , there exists a (unique) with . Since is a function and , there exists a (unique) with . By definition of composition, .
Uniqueness. Suppose and . By definition of composition, there exist with and . Since is a function, and force (call this common value ). Then and ; since is a function, .
So every has exactly one image under , i.e. is a function from to .
9. Composition of injective functions is injective (slide 29) ⚠️ not in project files — see note above
Definition (injective). A function is injective if .
Theorem. Let and be injective functions. Then is injective.
Proof. Let with , i.e. . Since is injective, this forces . Since is injective, this in turn forces . Hence is injective.
10. Properties of conjugation and absolute value (slide 14)
Let , with be complex numbers. All ten properties below (excluding the triangle inequality, which is not required) can be proved directly from the algebraic form; any two of the conjugation properties or any two of the absolute-value properties may be asked.
Conjugation properties
1. . Proof. , so .
2. . Proof. , so .
3. . Proof. , so . On the other hand, . The two sides agree.
4. . Proof. .
5. . Proof. .
Absolute value properties (and the link between them)
6. . Proof. .
7. If then . Proof. By property 6, . Since , also , so we may divide both sides by : . This shows is the multiplicative inverse of .
8. , and if then . Proof. . If then or , so , hence .
9. . Proof. .
10. . Proof. Using property 6 repeatedly: . Since absolute values are non-negative, taking square roots gives .
11. Multiplication in polar form (slide 19)
Theorem. Let be nonzero complex numbers given in polar form, and , where are their absolute values and are arguments. Then the product in polar form is i.e. multiplying two complex numbers multiplies their absolute values and adds their arguments.
Proof.
(1) commutativity of multiplication; (2) expanding the product using ; (3) the trigonometric addition formulas and .
12. roots of a complex number (slide 21)
Theorem. Let be a nonzero complex number and . The roots of — i.e. the complex numbers with — are
Proof. We use the fact (from De Moivre’s formula) that for any , . We also use the fact that two complex numbers in polar form are equal exactly when their absolute values agree and their arguments differ by an integer multiple of :
Now, is equivalent to , which by the fact above holds if and only if:
As ranges over all integers, takes exactly distinct values modulo , obtained by letting (further integer values of just repeat these arguments, shifted by a multiple of ). Hence has exactly distinct roots, given by for as stated.
13. Permutations without repetition (slide 7)
Theorem. Let . The number of permutations of an -element set (the number of ways to order all of its elements in a sequence) is .
Proof (combinatorial argument). The first element of the sequence can be chosen in different ways. After this, the second element can be chosen in different ways (one element has already been used), the third in ways, and so on, until the last element, which can be chosen in exactly way. By the multiplication principle, the total number of orderings is .
Proof (by induction on , more formal). Let . Base step: . There is exactly way to order elements (the empty sequence), so . Inductive step: Suppose and (inductive hypothesis). The first element of the sequence can be chosen in ways; by the inductive hypothesis, the remaining elements can then be ordered in ways. By the multiplication principle, the elements can be ordered in ways, so .
14. Permutations with repetition (slide 11)
Definition. Let be distinct objects and . A sequence of length containing each exactly times is a permutation with repetition of with repetition numbers .
Theorem. The number of permutations with repetition of distinct objects with repetition numbers is
Proof. If all elements were treated as distinguishable (e.g. by labelling repeated copies), there would be possible orderings. However, we do not wish to distinguish between identical copies of the same object: for each kind , only the set of positions occupied by copies of matters, not which particular copy sits where. Fixing the positions assigned to kind , the copies of occupying these positions can be permuted among themselves in ways without producing a different sequence. Hence in the count of , every genuinely distinct sequence (with repetition) was counted times. Dividing out this overcounting, the number of permutations with repetition is .
15. Variations without repetition (slide 13)
Definition. Let be a set and . A sequence of length formed from elements of , containing each element of at most once, is a -variation (without repetition) of .
Theorem. Let . The number of -variations without repetition of an -element set is
Proof. Let . The first element of the sequence can be chosen in different ways from the set . After this, the second element can be chosen in different ways (the element already used cannot be chosen again). Continuing this way, the third element can be chosen in ways, and so on, until the element, which can be chosen in ways. By the multiplication principle, the total number of -variations is . If , there are not enough distinct elements in to fill positions without repetition, so has no -variation without repetition.
16. Variations with repetition (slide 15)
Definition. Let be a set and . A sequence of length formed from elements of , where any element of may occur more than once, is a -variation with repetition of .
Theorem. Let . The number of -variations with repetition of an -element set is .
Proof. The first element of the sequence can be chosen in different ways. Since repetition is allowed, the second element can again be chosen in different ways, independently of the first; likewise for every subsequent position. By the multiplication principle, the total number of sequences of length is .
17. Combinations without repetition (slide 18)
Definition. Let . A -element subset of a set is a -combination (without repetition) of . For with , the binomial coefficient is defined as .
Theorem. Let . The number of -combinations of an -element set is
Proof. Let be an -element set and suppose . First, count the -variations without repetition of — i.e. sequences of distinct elements where order matters — there are of these (Section 15). Now, if we stop distinguishing the order of the chosen elements, each -element subset of corresponds to exactly of these ordered sequences (the number of ways to arrange elements into order). So the count over-counts each subset by a factor of . Dividing out gives the number of -element subsets: . If , an -element set clearly has no -element subsets.
18. Combinations with repetition (slide 21)
Definition. Let . A -combination with repetition (or -multiset) from a set is a selection of elements from , where repetition is allowed and order does not matter (only how many times each element of is chosen).
Theorem. Let , . The number of -combinations with repetition of an -element set is
Proof. Let . Every -combination with repetition of can be encoded as a – sequence: write the number of times was chosen as that many ‘s, then a as a separator, then the number of times was chosen as that many ‘s, then a separator, and so on up to . Such a sequence contains exactly ones (the total number of elements chosen) and zeros (the separators between the kinds of element), so it has length . Conversely, every such – sequence of length with exactly ones corresponds to exactly one -combination with repetition. The number of such sequences equals the number of ways to choose which of the positions hold the ‘s, which is . Hence the number of -combinations with repetition of is .
19. Binomial theorem (slide 24)
Theorem. For any and ,
Proof. Write as a product of factors: . By the distributive law, expanding this product gives a sum of terms, each obtained by choosing either or from each of the brackets and multiplying the choices together. Every such term has the form for some (where is the number of brackets from which was chosen). For a fixed , the term appears once for every way of choosing which of the brackets contribute an (the rest then contribute ); this can be done in different ways. Hence the coefficient of in the expansion is , giving .
20. Properties of binomial coefficients (slide 25)
Proposition. For every with :
1. Symmetry rule: .
Proof. By the theorem on combinations without repetition, equals the number of -element subsets of an -element set . We count these subsets a second way: for each -element subset , the complementary set is an -element subset of , and this correspondence is a bijection between -element subsets and -element subsets of . So the number of -element subsets equals the number of -element subsets, i.e. .
2. Pascal’s identity: if .
Proof. Let be an -element set; by definition has subsets of size . We count these subsets a second way. Fix one element . The -element subsets of split into two disjoint groups:
- those containing : choosing such a subset amounts to choosing the remaining elements from (which has elements), giving subsets;
- those not containing : such a subset must have all of its elements chosen from , giving subsets.
Adding these two disjoint counts gives the total: .
For every :
3. .
Proof. By the theorem on combinations without repetition, for each , is the number of -element subsets of an -element set . Summing over all from to counts every subset of exactly once (each subset has some definite size between and ), so the sum equals the total number of subsets of , which is (Section “Sets”).
4. .
Proof. Apply the Binomial theorem with : . Since (for ; for both sides equal trivially, consistent with the convention ), we get .
21. Handshaking theorem (slide 6)
Theorem (Handshaking theorem). Let be a graph (where assigns to each edge its endpoint(s), is the edge set and the vertex set), and for let denote the degree of (the number of edges incident to , counting each loop twice). Then the sum of the degrees of all vertices of equals twice the number of edges:
Proof (by induction on the number of edges). Base step: If , there are no edges, so every vertex has degree ; both sides of the equality are . Inductive step: Suppose the statement holds whenever a graph has edges, for some (inductive hypothesis). Let be a graph with edges. Remove one edge from to obtain a graph with edges; by the inductive hypothesis, . Now add the edge back to to recover . Adding increases the degree-sum by exactly : if joins two distinct vertices, each of their degrees increases by (total ); if is a loop at a single vertex, that vertex’s degree increases by (since a loop is counted twice in the degree). Either way, . So the statement holds for , completing the induction.
End of answer key. Sections 6–9 should be double-checked against your actual relations/functions lecture slides if you can get hold of them, since that deck wasn’t part of your uploaded project files.