1. Foundations

1.1 Mathematical logic

1.2 Set theory

1.1 Mathematical logic

1.1.5 Problems

Problems for Propositions and propositional formulas

Problem (Examples of propositions)

Which of the following statements are propositions, and which are not propositions?

Problem (Own examples of propositions)

Formulate at least

Problem (Propositional formulas)

Give examples of formulas \( {\mathcal R}(x) \) with one, \( {\mathcal S}(x,y) \) with two, and \( {\mathcal T}(x,y,z) \) with three variables such that

Problem (Unsolved problems in mathematics)

Formulate two unsolved mathematical problems.

Problem (Unsolved problems in mathematics)

Write down all prime numbers up to 500, and highlight all twin primes. What does the twin prime conjecture state?

Problem (Prime triples)

Prime triples are triples of three consecutive prime numbers \( (p,p+2,p+4). \) Prove that \( (3,5,7) \) is the only prime triple. Proceed as follows:

What are the next steps?

Problems for Logical connectives

Problems for Propositional laws of equivalence

Problem (Law of double negation)

Prove the following equivalence using a truth table. \[ \neg\neg a\equiv a \]

Problem (Idempotence laws of propositional logic)

Prove the following equivalences using truth tables.

Problem (Commutative laws of propositional logic)

Prove the following equivalences using truth tables.

Problem (Associative laws of propositional logic)

Prove the following equivalences using truth tables.

Problem (Distributive laws of propositional logic)

Prove the following equivalences using truth tables.

Problem (Merging of disjunction and conjunction)

Prove the following equivalences using truth tables.

Problem (Equvialences of implication)

Prove the following equivalences using truth tables.

Problem (de Morgan's laws of propositional logic)

Prove the following equivalences using truth tables.

Problems for Methods of proof

Problem (Tautologies and contradictions)

Prove that the negation of a tautology gives a contradiction and vice versa.

Problem (Examples of propositional tautologies I)

Prove that the following propositions are propositional tautologies:

Proposition (ii) is also known as reductio ad absurdum.

Problem (Examples of propositional tautologies II)

Prove that the following propositions are propositional tautologies:

Problem (Examples of propositional tautologies III)

Prove that the following propositions are propositional tautologies:

Problem (Further tautologies for an axiomatic approach)

The following rules are used in → R.E. Hodel chapter 3, section 3.1 for an axiomatic approach of propositional logic. Prove that these rules are propositional tautologies.

Problem (Further propositional tautologies)

Prove that the following propositions are propositional tautologies:

1.1.6 Questions

1.2 Set theory

1.2.1 Characterisation of sets

We do not define the term set. Rather, we give two possibilities to characterise sets, namely,

\[ M=\{m_1,m_2,m_3,\ldots\}, \]

\[ M=\{x\in X\,:\,p(x)\}, \]

The relation \( \in \) is a dichotomy in the following sense \[ \mbox{either}\quad x\in X\quad\mbox{or}\quad\neg(x\in X), \] there is no third possibility, and so, for example, the proposition \[ p(x)\,:\,(x\in X)\wedge(x\not\in X), \] where \( x\not\in X \) means \( \neg(x\in X), \) is a contradiction.

Examples:

Specifying the elements:

Specifying a defining property:

The relation \( = \) between two set is defined in → this paragraph.

The empty set \( \emptyset \) contains no element by agreement. It is a subset of every set, see → this paragraph. The Zermelo-Fraenkel axiomatic set theory ensures the existence of one and only one empty set. In particular, \[ \{x\in X\,:\,p(x)\} \] is a possible representation of the empty set if \( p(x) \) is contradictory. Every set other than the empty set contains at least one element.

A set is called finite if the number of its elements is a finite number. Otherwise it is called infinite.

Video tutorial

Problems

1.2.2 Set relations and set operations

We begin with the following set relations.

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we write

where \( A\not= B \) means \( \neg(A=B). \)

Set equality \( A=B \) can be expressed using the subset relation \[ A=B\quad\mbox{if and only if}\quad A\subseteq B\ \mbox{and}\ B\subseteq A. \] Finally, \( A\supseteq B \) means \( B\subseteq A \) and \( A\supset B \) means \( B\subset A. \)

Now we come to basic set operations.

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we define their union, their intersection, and their difference as

Example: Let the set \( \Omega=\{0,1,2,3,4,5,6\} \) be given together with the subsets \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\}\,. \] Then we determine

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we define their cartesian product as \[ A\times B:=\{(x,y)\,:\,x\in A,\ y\in B\}\,. \]

The symbol \( a:=b \) means that the new term \( a \) is defined as the known term \( b. \)

Example: The cartesian product of the set \( A=\{1,2,3\} \) and \( B=\{a,b\} \) ist \[ A\times B=\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}\,. \]

Definition: Let \( A\subseteq X \) be a subset of a superset \( X. \) Then we define the complement of \( A \) w.r.t. \( X \) as \[ A^c:=\{x\,:\,x\in X\setminus A\} \]

Union, intersection, difference, cartesian product and complement of sets are again sets.

Video tutorial

Problems

1.2.3 Idempotence, commutativity, associativity

We begin with the following idempotence laws of set theory.

Proposition: Let \( A \) be an arbitrary set. Then there hold

Proof: We only prove (i), and (ii) is left as an exercise. We use the idempotence laws of propositional logic from → this paragraph to calculate \[ A\cup A =\{x\,:\,x\in A\vee x\in A\} =\{x\,:\,x\in A\} =A, \] and (i) follows.\( \qquad\Box \)

Next we prove that the operators \( \cup \) and \( \cap \) are commutative.

Proposition: Let \( A \) and \( B \) be two arbitrary set. Then there hold

Proof: The commutative laws of propositional logic from → this paragraph yield \[ A\cup B =\{x\,:\,x\in A\vee x\in B\} =\{x\,:\,x\in B\vee x\in A\} =B\cup A, \] and this shows (i). Statement (ii) is left as an exercise.\( \qquad\Box \)

There also hold the associative laws of set theory.

Proposition: Let \( A, \) \( B \) and \( C \) be two arbitrary set. Then there hold

Proof: We prove (i). Using the associative rules from → this paragraph we get \begin{align} (A\cup B)\cup C &= \{x\,:\,x\in A\vee x\in(A\cup B)\vee x\in C\} \\[0.6ex] &= \{x\,:\,x\in(A\cup B)\cup C\} \\[0.6ex] &= \{x\,:\,x\in A\cup(B\cup C)\} \\[0.6ex] &= \{x\,:\,x\in A\vee x\in(B\cup C)\} \\[0.6ex] &= A\cup(B\cup C) \end{align} Statement (ii) is left as an exercise.\( \qquad\Box \)

Video tutorial

Problems

1.2.4 Operations with the empty set

We represent the empty set \( \emptyset \) by a set \[ \{x\,:\,q(x)\} \] with a contradiction \( x, \) i.e. \( q(x) \) is false for all possible \( x. \) Now, if \( p(x) \) denotes any proposition, we have \[ p(x)\vee q(x)\equiv p(x),\quad p(x)\wedge q(x)\equiv q(x) \] which can be proved by means of truth tables.

Proposition: Let \( A \) be an arbitrary set. Then there hold

Proof: We prove (i), and (ii) remains as an exercise. Let \( \emptyset \) be represented by \( \{x\,:\,q(x)\} \) with a contradiction \( q(x). \) Then \[ A\cup\emptyset=\{x\,:\,x\in A\vee q(x)\}=\{x\,:\,x\in A\}=A, \] and the statement follows.\( \qquad\Box \)

Proposition: Let \( A \) be an arbitrary set. Then there hold

Proof: We prove (i), and (ii) remains as an exercise. The proposition \( (x\in A)\wedge(x\not\in A) \) is a contradiction and, therefore, \[ \{x\,:\,(x\in A)\wedge(x\not\in A)\} \] represents the empty set. Thus, we obtain \[ A\setminus A=\{x\,:\,(x\in A)\wedge(x\not\in A)\}=\emptyset \] which proves the statement.\( \qquad\Box \)

Video tutorial

Problems

1.2.5 Calculus rules for sets

Generalizing the identities from propositional logic \[ a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c),\quad a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c) \] we infer the following distribution laws of set theory.

Proposition:

Let \( A, \) \( B \) and \( C \) be three sets. Then there hold

Proof: We prove (i) and leave (ii) as an exercise. Choose an \( x\in A\cap(B\cup C) \) arbitrarily. Then, using the distribution laws of propositional logic in the third line, applied to the propositions \( x\in A \) etc., we get

\[ \begin{array}{lll} x\in A\cap(B\cup C) & \longrightarrow & (x\in A)\wedge(x\in B\cup C) \\ & \longrightarrow & (x\in A)\wedge(x\in B\vee x\in C) \\ & \longrightarrow & (x\in A\wedge x\in B)\vee(x\in A\wedge x\in C) \\ & \longrightarrow & (x\in A\cap B)\vee(x\in A\cap C) \\ & \longrightarrow & x\in(A\cap B)\cup(A\cap C). \end{array} \]

Thus, it holds \( x\in(A\cap B)\cup(A\cap C) \) under the assumption \( x\in A\cap(B\cup C), \) and since \( x \) is chosen arbitrarily, we infer the implication \[ A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C). \] The reverse implication \( \supseteq \) also remains as an exercise.\( \qquad\Box \)

The de Morgan laws of propositional logic can be transferred to set theory as follows.

Proposition:

Let \( A \) and \( B \) be two subsets of a superset \( X. \) Then there hold

Video tutorial

Problems

1.2.9 Problems

Characterisation of sets

Problem (Elements of sets)

Determine all elements of the following sets.

Here \( \mathbb N=\{1,2,3,\ldots\} \) is the set of the natural numbers and \( \mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\} \) the set of the integers.

Problem (Finding characterising properties)

Find a characterising property for each of the following sets.

Problem (An example of the empty set)

Determine the elements of the following sets. Which set is emtpy?

Problems for Set relations and set operations

Problem (Exercise on set operations)

Let a base set \( \Omega=\{0,1,2,3,4,5,6\} \) and subsets \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\} \] of \( \Omega \) be given. Determine \[ \Omega\setminus A,\quad \Omega\setminus B,\quad A\cup B,\quad A\cap B,\quad A\setminus B,\quad B\setminus A. \]

Problem (Cartesian products of sets)

Determine the cartesian product \( M\times N \) of the following sets:

Problems for Idempotence, commutativity, associativity

Problem (Idempotence law of set theory)

Let \( A \) be a set. Prove \[ A\cap A=A. \]

Problem (Commutative law of set theory)

Let \( A \) and \( B \) be a two set. Prove \[ A\cap B=B\cap A. \]

Problem (Associative law of set theory)

Let \( A, \) \( B \) and \( C \) be a three set. Prove \[ (A\cap B)\cap C=A\cap(B\cap C). \]

Operations with the empty set

Problem (Disjunction and conjunction with a contradiction)

Let \( p \) be a proposition, and let \( q \) be a contradiction. Prove \[ p\vee q\equiv p,\quad p\wedge q\equiv q. \]

Problem (Intersection with the empty set)

Let \( A \) be a set. Prove \[ A\cap\emptyset=\emptyset. \]

Problem (Subtracting the empty set)

Let \( A \) be a set. Prove \[ A\setminus\emptyset=A. \]

Problem (Calculating with the complement)

Let \( A\subseteq X \) be a subset of a superset \( X, \) and let \( A^c \) denote the complement of \( A \) w.r.t. \( X. \) Prove:

Problems for Calculus rules for sets

Problem (Distribution laws of set theory)

Let \( A, \) \( B \) and \( C \) be three sets. Prove \[ A\cup(B\cap C)=(A\cup B)\cap(A\cup C). \]

Problem (Merging intersection and union)

Let \( A \) and \( B \) be two sets. Prove:

Problem (de Morgan laws of set theory)

Let \( A \) and \( B \) be two subsets of a supersete \( X. \) Prove:

Problem (Difference of three sets)

Let \( A, \) \( B \) and \( C \) be three sets. Prove:

Problem (Further distributive laws)

Let \( A, \) \( B \) and \( C \) be three sets. Prove:

Problem (Mixed operations I)

Let \( A \) and \( B \) be two sets. Prove:

Problem (Mixed operations II)

Let \( A \) and \( B \) be subsets of a superset \( X \) with complements \( A^c \) and \( B^c \) in \( X. \) Prove:

Problem (Difference and complement)

Let \( A \) and \( B \) be subsets of a superset \( X \) with complements \( A^c \) and \( B^c \) in \( X. \) Prove:

Problem: (Contained in or even equal?)

Let \( A, \) \( B, \) \( C, \) \( D \) be any sets. Which of the following statements is true, which is false? Prove or give a counterexample.

Problem (Symmetric difference)

The symmetris difference of two sets \( A \) and ( B \) is defined as \[ A\triangle B:=(A\setminus B)\cup(B\setminus A). \] Prove:

Problems for Maps between sets

Problem (Injective und surjective mappings)

Find own examples of sets \( A, \) \( B \) a mappings \( f\colon A\to B \) such that:

Problem (Mapping subsets)

Let \( f\colon A\to B \) be a mapping between two sets \( A \) and \( B, \) and let \( M,N\subseteq A \) be two subsets of \( A \) such that \( M\subseteq N. \) Prove \[ f(M)\subseteq f(N). \]

Problem (Associativity of the composition)

Let three mappings \( f, \) \( g \) and \( h \) be given such that \[ f\colon A\longrightarrow B,\quad g\colon B\longrightarrow C,\quad h\colon C\longrightarrow D \] with three sets \( A, \) \( B \) and \( C. \) Prove \[ h\circ(g\circ f)=(h\circ g)\circ f, \] where the composition \( \circ \) is defined as follows \[ \begin{array}{l} g\circ f\colon A\longrightarrow C\quad\mbox{means} \\[0.4ex] (g\circ f)(a):=g(f(a))\quad\text{for}\ a\in A\quad\text{etc.} \end{array} \]

Problem (Non-commutativity of the composition)

Give an example which shows that the composition of two mappings \( f\colon A\to A \) and \( g\colon A\to A \) on a set \( A \) is not necessarily commutative, i.e. it does not hold \[ (f\circ g)(a)=(g\circ f)(a)\quad\text{for all}\ a\in A. \] Can you give an example for which this relation is true?

Problem (Set mapping and its inverse)

Let \( A \) and \( B \) be two non-empty sets, and let \( f\colon A\to B \) and \( g\colon B\to A \) be two mappings with the property \[ g\circ f(a)=a\quad\text{for all}\ a\in A. \] Prove:

Problem (Properties of the composition)

Let \( f\colon A\to B \) and \( g\colon B\to C \) be two mappings between the sets \( A, \) \( B \) and \( C. \) Prove:

Problem (Union, intersection and difference I)

Let \( f\colon X\to Y \) be a mapping between the sets \( X \) and \( Y. \) Prove that for all \( A,B\subseteq X \) with \( A\cap B\not=\emptyset \) the following are true:

Problem (Injectivity and surjectivity on complements)

Let \( f\colon X\to X \) be a mapping on a superset \( X, \) and let \( A\subseteq X \) be a subset with complement \( A^c\subseteq X. \) Prove:

Problem (Composition of a mapping and its inverse)

Let \( f\colon X\to Y \) be a mapping, and let \( A\subseteq X \) and \( B\subseteq Y \) be subsets. Prove:

Problem (Example of an invertible mapping)

Let \( A,B=\{1,2,3,4\} \) be two sets, and let the mapping \( f\colon A\to B \) be given as \[ f(1)=4,\quad f(2)=1,\quad f(3)=3,\quad f(4)=2. \] Determine the inverse \( f^{-1}. \)

Problem (Union, intersection and difference II)

Let \( f\colon A\to B \) be a mapping between the non-empty sets \( A \) und \( B. \) Let \( \Omega,\Theta\subset B \) be two proper subsets. Prove:

Problem (Strictly monotone functions are injective)

Let the function \( f\colon\mathbb R\to\mathbb R \) be strictly monotone, i.e. it holds \[ \begin{array}{ll} \text{either} &\quad f(x_1)\lt f(x_2)\quad\text{for all}\ x_1,x_2\in\mathbb R\ \text{with}\ x_1\lt x_2 \\[0.6ex] \text{or} &\quad f(x_1)\gt f(x_2)\quad\text{for alle}\ x_1,x_2\in\mathbb R\ \text{with}\ x_1\lt x_2\,. \end{array} \] Prove that \( f \) is injective.

Problem (Mappings on finite sets)

Let \( A \) and \( B \) be two finite sets. Prove:

Let additionally \( |A|=|B|. \) Prove:

Cardinality of sets

Problem: (Power sets of finite sets)

Determine the power sets of the following sets \( M: \)

Problem (Power set on union and intersection)

Let \( A \) and \( B \) be two sets.

\[ {\mathcal P}(A\cup B)={\mathcal P}(A)\cup{\mathcal P}(B). \]

\[ {\mathcal P}(A\cap B)={\mathcal P}(A)\cap{\mathcal P}(B). \]

Damit ist alles gezeigt.\( \qquad\Box \)

Quantifiers

Problem: (Mathematical propositions with quantifiers)

By \( \mathbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\} \) we denote the set of integers. Reformulate the following propositions as formulas using quantifiers. Which proposition is true, which is false?

Problem: (From Peano's axioms for natural numbers)

By \( \mathbb N=\{1,2,3,\ldots\} \) we denote the set of natural numbers. Reformulate the following axioms for \( \mathbb N \) as formulas using quantifiers.

Problem: (Rewriting formulas in words)

Rewrite the following formulas with your own words.

Problem: (Rewriting formulas in words)

Negate the following definition of continuity of a function \( f\colon\Omega\to\mathbb R \) at a point \( x_0\in\Omega: \) \[ \forall\varepsilon\gt 0\,\exists\delta\gt 0\,\forall x\in\Omega\,(|x-x_0|\lt\delta\to|f(x)-f(x_0)|\lt\varepsilon). \]

1.2.10 Questions