# Tagged: math

# Theorem Proving in Mathematics

The very foundation of mathematics as we know it! Or, well, that evil thing math teachers had invented so they could torture the students. And we all know *that* very well … Anyway, I’m one of the tortured this fall, so let’s talk the math!

Mathematical proving is a way of convincingly demonstrating that some mathematical statement is necessarily true^{[1]}. There are several different types and ways of proofs and proving things, but one thing is common among all of them — a proof can only be obtained from unquestionable truths (axioms) by some sort of deductive reasoning. Experience, intuition or belief are not valid arguments when it comes to mathematical proving.

When you show that your statement works for every possible element from the **universe**, your statement or **proposition** becomes a **theorem**. Now, let’s have a look at some of the techniques that are frequently used to prove stuff.

## Direct Proof

Direct proof in mathematics is a way of proving that some statement is true by showing that the statement can be deduced from generally anything that is **known to be true** (which are some basic truths — **axioms** and all **previously proven theorems**). It’s most common for proving conditional statements in a form of **A → B**.

Formally speaking, when constructing a direct proof, were looking for a sequence of statements A_{1}, A_{2}, …, A_{n} so (A_{1} → A_{2}) ∧ … ∧ (A_{n-1} → A_{n}) ∧ T, where T = A → B is the statement we’re proving.

It sounds weird, but it’s really simple. Take for instance solving an equation. Almost any 5th grader can do that, right? If you think about that, the sequence of steps you go through in order to get to the value of **x** is a sort of a direct proof. You have some **precondition** (the equation) and some **expected result** (e.g. x = 5). Also there are some **basic axioms** that your math teacher told you (like subtracting 5 of both sides of the equation). While solving the equation, you try to come up with the right sequence of steps that will get you from to .

The solution looks like this:

We have proven that with the given precondition, **x = 5**. Formally speaking, .

## Proof by Induction

More precisely proof by *mathematical* induction. This proof is often used when we need to show, that something is true for an infinitely large universum (natural numbers for instance). It’s tied to the universal quantification in predicate logic.

The proof consists of two steps. At first, **base case** is proved for some element from the universe, then an **induction rule** is used to prove all other cases.

- The
**basis (base case)**: showing that the statement holds when*n*is equal to the**lowest**value that*n*is given in the question. Usually,*n*= 0 or*n*= 1. - The
**inductive step**: showing thatthe statement holds for some**if***n*,the statement also holds when**then***n*+ 1 is substituted for*n*.

The principle can be illustrated on the “domino effect” on a row of falling dominoes.

**Base case**— The first domino will fall.**Induction rule**— Whenever a domino falls, its next neighbor will also fall.

## Proof by Contradiction

Proof by contradiction is rather common as well. In this proof, it is shown that if some statement were so, a logical contradiction occurs, hence the statement must be not so. It starts by adding a statement to the preconditions, that we expect to be false. Then we try to show why the precondition is so, but in the process we find some **contradiction**.

Textbook case of the proof by contradiction is proving that a language is not regular by pumping theorem. We say, that a language is regular then pumping lemma states, that if a language is regular, some conditions and restrictions must be met.

Here’s an example proof from wikipedia^{[1]}:

Suppose that were a

rational number, so by definition whereaandbare non-zero integers with no common factor. Thus, . Squaring both sides yields 2b^{2}=a^{2}. Since 2 divides the left hand side, 2 must also divide the right hand side (as they are equal and both integers). Soa^{2}is even, which implies thatamust also be even. So we can writea= 2c, wherecis also an integer. Substitution into the original equation yields 2b^{2}= (2c)^{2}= 4c^{2}. Dividing both sides by 2 yieldsb^{2}= 2c^{2}. But then, by the same argument as before, 2 dividesb^{2}, sobmust be even. However, ifaandbare both even, they share a factor, namely 2. This contradicts our assumption, so we are forced to conclude that is anirrational number.

At first we make an assumption which is followed by sequence of steps, that should be valid, if the former statement is so until we find a contradiction, therefore the opposite is true.

## Summary

Proofs in mathematics can be a little … eh, well, fricking intimidating at first. They’re strictly formal, sometimes very hard to understand and it might seem almost impossible to come up with one, when you need to. Proving theorems requires a lot of knowledge and experience. Proofs in math might not be for anybody, but it’s good to know they’re there :-).

## Sources

# Basic Computer Science

There is a couple of very basic definitions and axioms in computer science. I consider them to be very important, because everything that comes later is based on them. And if you don’t fully comprehend the basic stuff, it will be very hard to understand anything further. That’s why I decided to write a whole post on these trivial definitions.

## Alphabet

Yeah, I’m not kidding. There’s a formal definition for alphabet. And what’s worse: it actually makes sense. I just wonder what would a kinder-gardener say on this :-D. Anyway, here it goes:

**Definition 1.1.** An **alphabet** is a finite non-empty set of *symbols.*

Alphabets are usually denoted by Greek big sigma * Σ*. A set

*Σ*can be referred to as alphabet when it’s not empty, but also not infinitely big.

*Σ = {a, b, c}*is an alphabet*Σ = {0, 1}*is an alphabet*Σ = {}*is**NOT**an alphabet*Σ = all integers*; is**NOT**an alphabet

Content of an alphabet are *symbols*. A symbol is some indivisible or atomic unit that can have some meaning (not necessarily). For example, if* Σ = {righteous, dude} *were alphabet, **righteous** and **dude** would be considered to be atomic indivisible elements (even though they contain multiple characters). Some folks also choose to omit the *finite* word from the definition. But that’s for some very advanced stuff and I’m guessing that finite alphabets will be more than sufficient for us.

## String

Another fundamental thing is a string. **String** or a **word** is a sequence of some symbols (the order is important). Strings usually contain symbols from only one alphabet. In that case we say string over is a finite sequence of symbols from . The formal definition is this:

**Definition 1.2**. Let be an alphabet.

- empty string is string over
- if is a string over and is a symbol from , then is a string over
*y*is string over only when we can derive it by applying rules 1 and 2.

There are some more basic definitions like string length, concatenation, reversation that are useful and important, but they might be a little intimidating at first, so let’s skip ahead to languages.

## Language

What is a **formal language**? We need to define first. is a set of all existing strings over alphabet . For example, let , then all positive binary numbers .

Then a formal language **L** over alphabet is a subset of . Formally said, . Basically, language is a *set of strings*. In context of programming languages, a language would be a set of all possible programs in that programming language. You see, that in most practical cases the set will be **infinite** (as it is in the programming language case). So, it’s not very practical to describe languages by enumerating all possible sentences of the language. One way of describing a language is with things called **formal grammars**. But we’ll get on to that later.