1. Foundations

1.1 Mathematical logic

1.2 Set theory

1.1 Mathematical logic

1.1.1 Propositions and propositional formulas

Mathematics starts with the

Agreement: A proposition is a statement which is either true (1) or false (0).

The idea of a proposition can not be covered by a definition. For example, our formulation makes use of other undefined notions, here statement, true and false.

Our agreement contains the following principle of bivalence:

⟶  There is no third possibility other than true or false.

Examples:

• The number \( 3 \) is a prime number.
• The number \( 4 \) is a prime number.
• There are infinitely many twin primes.

The first proposition is correct, the second is false. We can not decide whether or not the third proposition is true but we are convinced that it is either true or false.

We can not assign true or false to every linguistic statement. This concerns in particular congratulations, questions, requests and so on, for example:

• Happy birthday!
• Break a leg!
• Speak of the devil!

Mathematical expressions, such as

• \( x+7=28 \)
• \( {\mathcal R}(0,3,1) \)

are called (propositional) formulas. Such a formula turns into a proposition if we replace the ‘placeholder’ \( x \) by a number so that \( x+7=28 \) becomes a true or false proposition, or we interpret \( {\mathcal R}(x,y,z) \) as the relation \( x\lt y\lt z, \) and \( {\mathcal R}(0,3,1) \) becomes false.

Video tutorial

Problems

1.1.2 Logical connectives

We want to denote propositions by small letters \( a, \) \( b, \) \( c \) etc. To each proposition we assign a truth value

Propositions can be connected by the following connectives \[ \neg\,,\quad \vee\,,\quad \wedge\,,\quad \to\,,\quad \leftrightarrow\,. \] In this order they stand for

We define the meaning of this connectives by means of the following truth table:

The equivalence \( \leftrightarrow \) can be written using \( \to \) and \( \wedge \) as follows \[ a\leftrightarrow b\quad\mbox{means}\quad(a\to b)\wedge(b\to a). \] The round brackets indicate the order of the operations. We reach the agreement: From the highest to the lowest priority are to be performed in the following order \( \neg, \) \( \wedge, \) \( \vee, \) \( \to, \) \( \leftrightarrow. \)

Definition: Two propositions \( a \) and \( b \) with the same truth table are called semantically equivalent, written as \( a\equiv b. \)

Example: There hold \[ (a\leftrightarrow b)\equiv(a\to b)\wedge(b\to a), \] and also \[ (a\to b)\equiv(\neg a\vee b) \] as the following truth table shows:

Video tutorial

Problems

1.1.3 Propositional laws of equivalence

In this paragraph we want to provide some important propositional laws of equivalence. We start with the following law of double negation.

Proposition: It holds \[ \neg\neg a\equiv a. \]

The propositions \( \neg\neg a \) and \( a \) are clearly semantically equivalent: if \( \neg\neg a \) has truth value \( 0 \) then \( a \) is \( 1, \) and vice versa. Next we state the so-called idempotence laws of propositional logic.

Proposition: There hold \[ a\equiv a\vee a,\quad a\equiv a\wedge a. \]

We omit a proof and come to the following commutative laws and associative laws of propositional logic.

Proposition: The connectives \( \vee \) and \( \wedge \) are commutative, i.e. \[ a\vee b\equiv b\vee a,\quad a\wedge b\equiv b\wedge a, \] and associative, i.e. \[ a\vee(b\vee c)\equiv(a\vee b)\vee c,\quad a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c. \]

The following distributive laws form our next set of equivalences.

Proposition: There hold

Disjunction \( \vee \) and conjunction \( \wedge \) merge as formulated in the

Proposition: There hold \[ a\equiv a\wedge(a\vee b),\quad a\equiv a\vee(a\wedge b). \]

Furthermore, we will often use certain equivalences for the implication, provided by our next

Proposition: There hold

The first statement (i) is known from → this paragraph, (ii) can be verified by means of a truth table, and (iii) is a compilation of \( a\to b \) and \( b\to a \) together with (i). Finally, we come to the following de Morgan's laws of propositional logic which prescribe how to negate disjunction and conjunction.

Proposition: There hold

Video tutorial

Problems

1.1.4 Methods of proof

Definition: A tautology is a proposition which is always true or a propositional formula which is always true independent of the truth values of its variables.

We give examples of tautologies which are at the same time important methods of mathematical proofs.

Proposition: The following propositions are tautologies:

We want to clarify the following four principle in our own words:

Proposition: The following proposition is a tautology \[ (a\to b)\wedge(a\to\neg b)\to\neg a. \]

In our own words: If \( b \) follows from \( a \) and \( \neg b \) also follows from \( a, \) then \( a \) must be false. This is the so-called reductio ad absurdum.

The opposite of a tautology is a contradiction which is always false.

Video tutorium

Problems

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 about the theory

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.6 Maps between sets

We consider maps \( f\colon A\to B. \)

Definition: A mapping \( f\colon A\to B \) between two sets \( A \) and \( B \) is called

In particular, a mapping \( f\colon A\to B \) is

A bijective mapping \( f\colon A\to B \) assigns each element \( a\in A \) to exactly one element \( b\in B, \) and vice versa, every element \( b\in B \) is mapped to exactly one element \( a\in A \) by means of its inverse mapping \[ f^{-1}\colon B\longrightarrow A \] which exists in this situation. The inverse mapping has the characteristic properties \[ \begin{array}{ll} f^{-1}\circ f(a):=f^{-1}(f(a))=a & \quad\text{for all}\ a\in A, \\[0.6ex] f\circ f^{-1}(b):=f(f^{-1}(b))=b & \quad\text{for all}\ b\in B. \end{array} \]

Definition: A set \( A \) is called finite if there exist a number \( n\in\mathbb N \) and a bijective mapping \[ f\colon\{1,\ldots,n\}\longrightarrow A. \] In this case we set \( |A|:=n. \)

Video tutorial

Problems

1.2.7 Cardinality of sets

The cardinality of a finite set \( A \) with elements \( a_1,\ldots,a_n \) is the number \( n \) of its elements, and for the cardinality we write \[ |A|=n. \] If \( A \) is infinite, we can not speak about any number of elements. We make the following definition instead.

Definition: Two sets \( A \) and \( B \) have the same cardinality if there exists a bijective mapping \( f\colon A\to B. \)

For an arbitrary set \( A \) we denote its power set by \( {\mathcal P}(A). \) The power set \( A \) is the set of all subsets of \( A \), i.e. the elements of the power set are the subsets of \( A. \)

Example: We have \[ {\mathcal P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\} \] because \( \emptyset, \) \( \{1\}, \) \( \{2\} \) and \( \{1,2\} \) are the four possible subsets of \( \{1,2\}. \) Note that the empty set is a subset of any set.

Furthermore, any finite set fufills \[ |A|\lt|{\mathcal P}(A)|=2^{|A|}\,. \]

Video tutorial

Problems

1.2.8 Quantifiers

We will always work with variables \( x,y,\ldots \) as elements from a set \( X,Y,\ldots \) We write \[ x\in X,\quad y\in Y \quad\mbox{etc.} \] and say: \( x \) is an element from \( X \) etc. The following quantifiers are important for all of our investigations.

Definition: Let \( p(x) \) be a propositional formula depending on a variable \( x \) from a set \( X. \) Then we define the universal quantifier \( \forall \) and the existential quantifier \( \exists \) as follows:

„There exists“ means that there is at least one element \( x \) from \( X, \) and there could be more elements than only one.

Example: The function \( f\colon\Omega\to\mathbb R \) is called continuous at a point \( x_0\in\Omega \) if \[ \forall\varepsilon>0\,\exists\delta>0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] or in words:

For all \( \varepsilon\gt 0 \) there is a \( \delta\ge 0 \) such that \( |x-x_0|\lt\delta \) for all \( x\in\Omega \) with \( |f(x)-f(x_0)|\lt\varepsilon. \)

Here we need four variables \( x, \) \( x_0, \) \( \delta, \) \( \varepsilon. \) We say \( x, \) \( \varepsilon \) are bounded by the quantifier \( \forall, \) \( \delta \) is bounded by \( \forall, \) and \( x_0 \) is free.

The relations \( \in \) and \( \lt \) are examples of so-called predicates.

Definition: The universal quantifier \( \forall \) and the existential quantifier \( \exists \) are negated as follows \[ \neg\forall x\,p(x)\equiv\exists x\,\neg p(x),\quad \neg\exists x\,p(x)\equiv\forall x\,\neg p(x). \] The operator \( \neg \) on the left hand sides ranges over \( \forall x\,p(x) \) and \( \exists x\,p(x), \) resp.

Example: We compute \[ \neg\forall x\,\exists y\,p(y)\equiv\exists x\,\neg\exists y\,p(y)\equiv\exists x\forall y\,\neg p(y). \]

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 about the theory

1.3 Zermelo-Fraenkel set theory

1.3.1 Introduction

...

Video tutorial

Problems

1.3.2 The axiom system

...

Axiom of the existence

\( \exists x\,\forall y\,\big[y\not\in x\big] \)

This axiom guarantees the existence of at least one set. In particular, we postulate the existence of the empty set, that is a set which has no elements at all. We denote it by the symbol \( \emptyset. \)

Axiom of the extensionality

\( \forall x\,\forall y\,\big[x=y\,\leftrightarrow\,\forall z\,(z\in x\leftrightarrow z\in y)\big] \)

This axiom defines equality \( x=y \) of two sets \( x \) and \( y. \) Using the symbol \( \subseteq \) we can write \[ x=y\quad\text{if and only if}\quad\quad x\subseteq y\,\wedge\,y\subseteq y. \]

Axiom schema of specification

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,(z\in x\,\wedge\,\varphi(z))\big] \)

This axiom states that for any set \( x \) chosen arbitrarily, there exists a set \( y \) such that \( z\in y \) is true if and only if \( z\in x \) is true and, in addition, \( z \) has a property \( P(z) \) which is expressed as a formula \( \varphi(z) \) where \( z \) is a free variable and not bounded by any quantifier. We write \[ y=\{z\,:\,\varphi(z)\} \] for this set \( y. \) An example of such a formula \( \varphi(z) \) is \( z\in a. \) Note that this axiom is not just an axiom but an axiom schema, and this means that it contains infinite many axioms depending on the infinite range of possible choices of formulas \( \varphi(z). \)

Axiom of pair

\( \forall x\,\forall y\,\exists z\,\forall a\,\big[a\in z\,\leftrightarrow\,(a=x\,\vee\,a=y)\big] \)

This axiom states that for two arbitrary sets \( x \) and \( y \) there exists a set \( z \) which consists only of the two elements \( x \) and \( y. \) We write \[ z=\{x,y\} \] for this set \( z, \) and \( \{x,y\} \) is what we call an unordered pair considering \[ \{x,y\}=\{a\,:\,a=x\,\vee a=y\}=\{a\,:\,a=y\,\vee a=x\}=\{y,x\}\,. \] In case \( x=y \) we write \( \{x\} \) instead of \( \{x,x\}. \) Finally, we set recursively \[ \{a,b,c\}=\{\{a,b\},c\}\,,\quad \{a,b,c,d\}=\{\{a,b,c\},d\}\quad\text{etc.} \]

Axiom of union

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,\exists(w\in x)\,z\in w\big] \)

The set \( y \) is called the union set of \( x. \) It contains all elements of \( x \) and only these elements. We write \[ y=\bigcup x. \] For example, if \( x=\{a,b\}\}, \) then \[ \begin{array}{lll} \displaystyle \bigcup\{a,b\}\!\!\! & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{a,b\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{c\,:\,c=a\,\vee c=b\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists w\,(w=a\,\vee w=b)\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in a\,\vee z\in b \}\,. \end{array} \] In case \( x=\{a,b,c\} \) we have \[ \begin{array}{lll} \displaystyle \bigcup\{a,b,c\}\!\!\! & = & \!\!\!\displaystyle \bigcup\{\{a,b\},c\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in\{a,b\}\,\vee\,z\in c\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in a\,\vee\,z\in b\,\vee\,z\in c\}\,. \end{array} \]

Axiom of infinity

\( \exists x\,\big[\emptyset\in x\,\wedge\,\forall(y\in x)\,y\cup\{x\}\in x\big] \)

...

Axiom of power set

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,z\subseteq y\big] \)

...

Axiom of regularity

\( \forall x\,\big[(x\not=\emptyset)\,\leftrightarrow\,\exists(y\in x)\,x\cap y=\emptyset\big] \)

...

Video tutorial

Problems

1.3.4 Problems

The axiom system

Problem (Uniqueness of the empty set)

Using the axiom of existence and the axiom of extensionality, prove that there exists exactly one empty set \( \emptyset. \)

Problem (Example of an union I)

Problem (Example of an union I)

Verify \[ \bigcup\{\emptyset,\{\empty\}\}=\{\emptyset\}\,. \]

Problem (Example of an union II)

Verify \[ \bigcup\{\emptyset,\{\emptyset,\{\emptyset\}\},\{\{\emptyset\}\}\}=\{\emptyset,\{\emptyset\}\}\,. \]