Challenges

Six mathematicians attend a party. Any two mathematicians either both know each other or both don't know each other. Prove that there must be a group of at least three mathematicians that either all know or all don't know each other.

In the script, you are told that the tuple $(a,b)$ can be uniquely defined as the set $\{\{a\},\{a,b\}\}$. (this means that for any tuples $t_1$ and $t_2$: $t_1=t_2\iff S_{t_1}=S_{t_2}$, where $S_{t_1},S_{t_2}$ are the corresponding sets)

For an arbitrary set $A$, we define $A^*=\bigcup\limits_{n=1}^\infty A^n$ as the set of finite sequences in $A$ (where $A^n=\times_{i=1}^n A$).

Find a way of uniquely defining each element of $A^*$ as a set and prove its correctness. (this set should only be made up of elements of $A$, or nested sets containing elements of $A$)

You are not allowed to assume that the set definition of a tuple shown in the script is adequate, and you are welcome to use a different definition.

Given a set $A$ and a relation $\rho$ on $A$, explain how $\rho^k$ ($k \in \mathbb{N}$) can be computed by the means of modified matrix multiplications.

For any $n\in\mathbb N\setminus\{0\}$ and $k\in\{1,\ldots,n\}$, find a relation $\rho$ on $A=\{1,\ldots, n\}$ satisfying $\rho^k=\rho$ and $\rho^i\neq\rho^j\forall i,j\in\{1,\ldots,k-1\},i\neq j$.

The goal of this exercise is to show that the set of all real numbers between 0 and 1, denoted $[0, 1]$, is uncountable.

In this week's lectures, you encountered the set $\{0, 1\}^{\infty}$ of semi-infinite bitstrings. Cantor's diagonalization argument proves that this set is uncountable.

Through a slight modification of Cantor's diagonalization argument, one can also prove that the set of real numbers $[0, 1]$ is uncountable. However, this exercise prohibits you from using that method.

Instead, use Theorem 3.16 (Bernstein–Schröder theorem) to show $[0, 1] \sim \{0, 1\}^{\infty}$, i.e., show that there is a bijection between these two sets to prove they are equinumerous. Then, conclude that $[0, 1]$ must be uncountable.

Let $A$ be an arbitrary set, and $\text{Eq}(A)$ the set of equivalence relations on $A$.

Prove that $(\text{Eq}(A);\subseteq)$ is a lattice.

Consider the function $f:\mathbb R_{\ge0}\mapsto \mathbb R_{\ge0}$ defined by $f(x)=\frac{1}{1+2\lfloor x\rfloor-x}$ for all $x\in \mathbb R_{\ge0}$.

Prove that the sequence $(u_n)_{n\in\mathbb N}$ defined for all $n\in\mathbb N$ as:

visits every nonnegative rational number exactly once.