## Implementing a Semaphore in Java

Today we will take a glimpse at semaphores and have a look at an implementation based on locks.

More ...

## Implementation of Sorting Algorithms in Java

This document is a list of common sorting algorithms and their implementations in Java. The algorithms have been written by myself. I have tested them with the JUnit tests you can find at the end of this article, however, I do not guarantee that the implementations are 100% correct. Feel free to comment below or write me an email if you find a mistake.

More ...

## A short proof of Cantor's theorem

Cantor’s theorem states that for any set $$S$$ we have $$S \preceq \mathcal{P}(S)$$ and $$S \nsim \mathcal{P}(S)$$. In words this means that the cardinality of $$\mathcal{P}(S)$$ is strictly bigger than the cardinality of $$S$$.

Unlike some of my other posts, this one is strictly mathematical.

First we will have a look at the definitions and then we will prove Cantor’s theorem:

Two sets $$A$$, $$B$$ are equinumerous, denoted $$A \sim B$$ if there exists a bijection $$A \to B$$

A set $$B$$ dominates a set $$A$$, denoted $$A\preceq B$$, if $$A\sim C$$ for some $$C \subseteq B$$.

The second definition is equivalent to the existence of an injective funtion $$A \to B$$, namely the bijection $$A \to C$$.

Let $$S$$ be any set. The power set of $$S$$, denoted by $$\mathcal{P}(S)$$, has a strictly greater cardinality than $$S$$ itself.

The proof is split into two parts. First we will show $$S \preceq \mathcal{P}(S)$$ and then in a second step we will show $$S \nsim \mathcal{P}(S)$$.

Part 1 : $$S \preceq \mathcal{P}(S)$$

By definition of $$\preceq$$ we need to find an injection from $$S$$ to $$\mathcal{P}(S)$$. We can constructively define an injection as follows: $$g: S \to \mathcal{P}(S)$$ with $$g(x) = \{x\} \in \mathcal{P}(S)$$.

Now we need to show that $$g$$ is indeed an injection. For $$g$$ to be an injection, the following must hold: $$\forall x,y \in S, x \neq y :g(x) \neq g(y)$$

It is clear that $$\{x\} \neq \{y\}$$. This however implies $$g(x) = \{x\} \neq \{y\} = g(y) \implies g(x) \neq g(y)$$ which is exactly what we had to show. Therefore $$g$$ is injective, which shows us, by definition 2, that $$S \preceq \mathcal{P}(S)$$.

This leads us to the conclusion that $$S \preceq \mathcal{P}(S)$$

Part 2 : $$S \nsim \mathcal{P}(S)$$

Assume for the sake of contradiction that $$S \sim \mathcal{P}(S)$$. Then, by definition, there exists a surjection $$f : S \to \mathcal{P}(S)$$. We now define the set $$T := \{x \in S\| x \not \in f(x)\}$$. The set $$T$$ looks very abstract, but that doesn’t really matter, we just constructed this set with this property to ensure we will get a contradiction at the end.

Since $$f$$ is surjective $$\exists x \in s : f(x) = T$$, for every $$T \in \mathcal{P}(S)$$. Let’s now look at this $$x$$ for which $$f(x) = T$$. There are two options:

• Case 1: if $$x \in T$$, then $$x \in f(x)$$ since $$T = f(x)$$, but this implies $$x \not \in T$$ by Definition of $$T$$. This contradicts our assumption.
• Case 2: if $$x \not \in T$$ then since $$T = f(x)$$ implies $$x \not \in f(x)$$, thus $$x \in T$$ by Definition of $$T$$. This however is a contradiction.

Since we have found a contradiction in both cases, our assumption $$S \sim \mathcal{P}(S)$$ must be wrong. This means there does not exist a surjection from $$S$$ to $$\mathcal{P}(S)$$ which implies that $$S \nsim \mathcal{P}(S)$$

This concludes our proof of Cantor’s Theorem.

This proof uses the definitions from ETH Zurichs Discrete Mathematics Course and is based on materials from the course. 