Mathematics I: logic, sets, combinatorics and sequences

A first-year university lesson: statements and logical connectives, truth tables, set operations, mathematical induction, permutations and variations, arithmetic and geometric sequences – with worked examples and tests.

1. Logic

A statement is a sentence that is either true ( $⊤$ ) or false ( $⊥$ ). From two statements $p$ and $q$ the connectives $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$ build new statements.

The negation $\neg p$ (“not $p$ ”) is true when $p$ is false and vice versa.

$p$	$\neg p$
$⊤$	$⊥$
$⊥$	$⊤$

The conjunction $p \land q$ (“ $p$ and $q$ ”) is true only when both are true; one false statement is enough to make it false.

$p$	$q$	$p \land q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊥$
$⊥$	$⊥$	$⊥$

The disjunction $p \lor q$ (“ $p$ or $q$ ”) is false only when both are false.

$p$	$q$	$p \lor q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊤$
$⊥$	$⊤$	$⊤$
$⊥$	$⊥$	$⊥$

The implication $p \Rightarrow q$ (“ $p$ implies $q$ ”) is false only when $p$ is true and $q$ is false.

$p$	$q$	$p \Rightarrow q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊤$
$⊥$	$⊥$	$⊤$

The equivalence $p \Leftrightarrow q$ (“ $p$ if and only if $q$ ”) is true when $p$ and $q$ have the same value.

$p$	$q$	$p \Leftrightarrow q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊥$
$⊥$	$⊥$	$⊤$

A tautology is a formula that is true for all values of its statements. It is checked with a truth table.

Example 1. Show that $(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$ is a tautology.

$p$	$q$	$\neg p$	$p \Rightarrow q$	$\neg p \lor q$	$(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$
$⊤$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$	$⊥$	$⊥$	$⊤$
$⊥$	$⊤$	$⊤$	$⊤$	$⊤$	$⊤$
$⊥$	$⊥$	$⊤$	$⊤$	$⊤$	$⊤$

The last column is always $⊤$ : the formula is a tautology, so an implication can be replaced by $\neg p \lor q$ .

Example 2. What is the formula $((p \land \neg q) \lor (\neg p \land q)) \Rightarrow (p \lor q)$ ?

$p$	$q$	$p \land \neg q$	$\neg p \land q$	$(p \land \neg q) \lor (\neg p \land q)$	$p \lor q$	$\Rightarrow$
$⊤$	$⊤$	$⊥$	$⊥$	$⊥$	$⊤$	$⊤$
$⊤$	$⊥$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$
$⊥$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$	$⊤$
$⊥$	$⊥$	$⊥$	$⊥$	$⊥$	$⊥$	$⊤$

It is a tautology too: when exactly one statement is true, “ $p$ or $q$ ” is true as well.

Laws

$p \land q \Leftrightarrow q \land p$ – commutative law of conjunction
$(p \land q) \land r \Leftrightarrow p \land (q \land r)$ – associative law of conjunction
$p \lor q \Leftrightarrow q \lor p$ – commutative law of disjunction
$(p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)$ – associative law of disjunction
$(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ – law of contraposition
$\neg (p \land q) \Leftrightarrow \neg p \lor \neg q$ , $\neg (p \lor q) \Leftrightarrow \neg p \land \neg q$ – De Morgan’s laws

Check yourself:

p = ⊤

q = ⊥

→

p \Rightarrow q

Answer: $⊥$ .

2. Sets

Set operations

$A \cup B = {x ∣ x \in A \lor x \in B}$ – union: the elements in at least one of the sets
$A \cap B = {x ∣ x \in A \land x \in B}$ – intersection: the common elements
$A ∖ B = {x ∣ x \in A \land x \notin B}$ – difference
$A Δ B = (A ∖ B) \cup (B ∖ A)$ – symmetric difference
$A^{c} = \overset{―}{A} = C_{B} A = {x ∣ x \in B \land x \notin A}$ – complement of $A$ in $B$
$P (A) = {X ∣ X \subseteq A}$ – power set: all subsets of $A$ ; if $A$ has $n$ elements, $P (A)$ has $2^{n}$
$A \times B = {(x, y) ∣ x \in A \land y \in B}$ – Cartesian product: all ordered pairs

Example. Sets given by a property, written by listing:

${x ∣ x \in Z \land - 2 \leq x \leq 7} = {- 2, - 1, 0, 1, 2, 3, 4, 5, 6, 7}$
$\{x\mid x\in\mathbb N,\ x\text{ odd}\land x<10\}=\{1,3,5,7,9\}$
${x ∣ x \in R \land x^{2} - 25 = 0} = {- 5, 5}$

For $A = {1, 2, 3, 4}$ and $B = {3, 4, 5}$ :

$A \cup B = {1, 2, 3, 4, 5}$ , $A \cap B = {3, 4}$ , $A ∖ B = {1, 2}$ , $A Δ B = {1, 2, 5}$
$P ({1, 2}) = {\emptyset, {1}, {2}, {1, 2}}$ , ${1, 2} \times {a, b} = {(1, a), (1, b), (2, a), (2, b)}$

3. Mathematical induction

Many properties of natural numbers are proved by the principle of mathematical induction, in three steps:

check: the statement holds for $n = 1$ ;
assumption: the statement holds for $n = k$ ;
proof: then it also holds for $n = k + 1$ .

Example. Prove that $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ .

1) For $n = 1$ : $1 = \frac{1 \cdot 2}{2}$ ✓.

2–3) Let $1 + 2 + \dots + k = \frac{k (k + 1)}{2}$ . Then $1 + 2 + \dots + k + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2}$ , which is the formula for $n = k + 1$ ✓.

4. Combinatorics

Factorial: $n! = n \cdot (n - 1) \dots 3 \cdot 2 \cdot 1$ , $1! = 1$ , $0! = 1$ ; $3! = 6$ , $5! = 120$ .

Permutations (orderings) of $n$ different elements: $P (n) = n!$

If among $n$ elements there are groups of $k_{1}, k_{2}, \dots$ equal ones, permutations with repetition: $P (n; k_{1}, k_{2}, \dots) = \frac{n!}{k_{1}! k_{2}! \dots}$

Example. How many different words can be made from the letters of TEUTA (5 letters, T twice)?

$P (5; 2, 1, 1, 1) = \frac{5!}{2! 1! 1! 1!} = \frac{120}{2} = 60$

Example. How many six-digit numbers with different digits can be written with 0, 1, 2, 3, 4, 5? From all $6!$ orderings subtract those that start with 0 ( $5!$ ):

$6! - 5! = 5! (6 - 1) = 120 \cdot 5 = 600$

Variations without repetition: ordered choices of $k$ of $n$ different elements: $V_{n}^{k} = \frac{n!}{(n - k)!} = n (n - 1) \dots (n - k + 1)$

Example. $n = 10$ , $k = 5$ : $V_{10}^{5} = \frac{10!}{5!} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30240$

Variations with repetition (each element may be chosen more than once): ${\overset{―}{V}}_{n}^{k} = n^{k}$

Example. With the digits 1 and 2 ( $n = 2$ ), two-digit ( $k = 2$ ) and three-digit ( $k = 3$ ) strings:

${\overset{―}{V}}_{2}^{2} = 2^{2} = 4$ : 11, 12, 21, 22; ${\overset{―}{V}}_{2}^{3} = 2^{3} = 8$ : 111, 112, 121, 122, 211, 212, 221, 222.

If the order does not matter, these are combinations: $C_{n}^{k} = (\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ .

5. Sequences

A sequence is a function on the natural numbers: $a_{1}, a_{2}, a_{3}, \dots$ ; $a_{n}$ is the general term.

Example. The first five terms of the sequences:

$a_{n} = \frac{1}{2 n}$ : $\frac{1}{2}, \frac{1}{4}, \frac{1}{6}, \frac{1}{8}, \frac{1}{10}$
$a_{n} = (- 1)^{n} \frac{1}{2^{n}}$ : $- \frac{1}{2}, \frac{1}{4}, - \frac{1}{8}, \frac{1}{16}, - \frac{1}{32}$
$a_{n} = \frac{3 n + 2}{n}$ : $5, 4, \frac{11}{3}, \frac{14}{4}, \frac{17}{5}$
$a_{n} = \frac{(- 1)^{n} n^{2}}{n} = (- 1)^{n} n$ : $- 1, 2, - 3, 4, - 5$

An arithmetic sequence: each term is the previous one plus the same number $d$ (common difference). For example $1, 3, 5, 7, \dots$ ( $d = 2$ ), $4, 10, 16, 22, \dots$ ( $d = 6$ ).

$a_{n} = a_{1} + (n - 1) d$ – general term

$S_{n} = \frac{n}{2} (a_{1} + a_{n}) = \frac{n}{2} (2 a_{1} + (n - 1) d)$ – sum of the first $n$ terms

Example. A phone company earned 2000 € on 1 March, and every following day its earnings grew by 125 €. How much did it earn by the end of March?

Earnings on 31 March: $a_{31} = 2000 + 30 \cdot 125 = 5750$ €

In total over 31 days: $S_{31} = \frac{31}{2} (2000 + 5750) = \frac{31 \cdot 7750}{2} = 120125$ €

A geometric sequence: each term is the previous one times the same number $q$ (common ratio). For example $2, 4, 8, 16, 32, \dots$ ( $q = 2$ ).

$a_{n} = a_{1} q^{n - 1}$ – general term

$S_{n} = a_{1} \frac{q^{n} - 1}{q - 1}$ – sum of the first $n$ terms ( $q \neq 1$ )

Tests

Check yourself with the tests (10 problems each, with solutions):

Mathematics I – foundations – test 1 – Logic: statements and truth tables
Mathematics I – foundations – test 2 – Sets and mathematical induction
Mathematics I – foundations – test 3 – Combinatorics: permutations and variations
Mathematics I – foundations – test 4 – Sequences: arithmetic and geometric