# (parentheses)

Blogging about maths and computer science.

## Introduction to software verification via model checking.

I have found a nice set of lecture on software verification:

The course introduces the theory and practice of formal methods for the design and analysis of software systems. The course will cover the underlying logical and theoretical concepts, with focus on the algorithmic solutions, and heuristics to cope with the high computational complexity.

Unfortunately, I cannot embed videos in the post, so I will just provide links to the videolectures:
http://www.lektorium.tv/lecture/?id=12941
http://www.lektorium.tv/lecture/?id=12942

Here are the presentations, used in the lecutres: [ 1 | 2 ]

Written by oh

November 3, 2011 at 6:48 pm

## Proving the Eisenstein’s criteria

Polynomial $A = x^n + a_{n-1}x^{n-1} + .. + a_1 x + a_0$, where each $a_i$ is divisible by some number $p$, is irreducible in $\mathbb Q$ when $p^2$ does not divide $a_0$.
If A is not irreducible then there are some $F$ and $G$ such as $A = FG$.
But that means that $a_0 = f_0 g_0$, which means that $(p | f_0)$ XOR $(p | g_0)$ (since $p^2$ does not divide $a_0$).
Let’s assume that $p | f_0$. Now let’s take a map $Z[x] \rightarrow (Z/pZ)[x]$ (I believe this method is called homomorphism-reduction).
$[A] = x^n$, but $[G] = \cdots + [g_0]$, where $[g_0] \neq 0$.
That is possible only when $[G]$ is constant and $[F] = [A]/[G]$. Which means that $A$ is irreducible.

Note: here $[a]$ denotes $f(a)$ where $f$ is a homomorphism $Z[x] \rightarrow (Z/pZ)[x]$.

Written by oh

September 29, 2011 at 12:42 pm

Posted in Math

Tagged with , ,

## Union of countable sets is countable.

Let’s say we have a possibly infinite collection of countable sets $A_1, A_2, \cdots, A_n, \cdots$, prove that $\bigcup A_i$ is countable too. We are going to do this using Axiom of Choice.

Since every set $A_i$ is countable, there is a set of injections from $N$ to $A_i$, let’s call it $M_i$. Using the axiom of choice we can create a set of maps $\{g_1, g_2, \cdots\}$ from $N$ to $A_i$. Now, we are going to create an injection from $(N, N)$ to $\bigcup A_i$. If $x_k$ is an element of $\bigcup A_i$ then it’s also an element of some set $A_m$. Therefore we can construct $f(z, m) = x_k$ where $x_k = g_m(z)$. And since we know that $(N, N)$ is countable, we can map $N$ to $\bigcup A_i$. QED.

Written by oh

August 29, 2011 at 8:03 pm

Posted in Math

Tagged with ,