Set of Non-negative Integers

For the set of non-negative Integers say Z+ the following axioms will hold -
1. 0 ∈ Z+ 
2. Z+ is close under an equivalence relation ' = ' .
3. ∀ x,y ∈  Z+  Then exactly one of the following relation will hold 
                           x > y , x < y , x = y 
4. Def Successor : ∀x ∈  Z+   , y ∈  Z+ and y > x  is the successor of x denoted by S(x) = y if and only if   ∄ b ∈  Z+      s.t    x < b < y . 
The axiom is ∀n ∈  Z+  S(n) ∈  (Z+  - {0}) and S(n) is a injection 

For predicate Logic to formulate induction we use another axiom :-
5. φ(0) =  true  and  ∀n ∈  Z+  φ(n) = true → φ(n+1) = true  
    ⇔  ∀n ∈  Z+  φ(n) = true [ Simple induction ]
    OR,
    φ(0) =  true  and  ∀n ∈  Z+  φ(0) ,φ(1), ... φ(n) =  true → φ(n+1) = true  
    ⇔  ∀n ∈  Z+  φ(n) = true [ Strong induction ]

Irrationality

Irrationality of 2 :-

Let, the converse √ 2 = m / n is where m is Integer and n is Natural and m/n is irreducible over Integer .
Now m² / n² = 2
=>  m² = 2* n²
=> 2 | m²
=> 2 | m  [As only squire of  an even number is even in Integer ]
=> 4 | n²
=> 2 | n
=> 2 | m,n so m/n is not irreducible over Integer . (Contradicts)

Similarly to prove that √p is irrational  where p is prime we will follow the same path .
Let, Irreducible over Integer m/n = √ p  where m is Integer n is Natural
=>   m² = p * n²
=>   p | m => p | n => m/n is reducible (Contradict)

Similarly for p is prime and p^1/a is irrational [ we will assume the same and m^a = p . n^a → p | m → p | n then m/n is reducible so contradicts ]

We can further say if n = p₁^α₁ . p₂^α₂.. [ ∀p_i are primes ] then n^1/a will be irrational
if  ∃α_i can s.t a ∤ α_i.

Some Set Magic

Let's have a set A = {φ , {φ} , {{φ}},....} surely |A| =  ∞ ,
Now →
1. A ∈ A .
2. A is countable

A could be found with this recursive Grammar   →
A = φ | 2^A

Russel gave one paradox like → A = {x | x ∉ x} now does A∈  A?
If A ∈  A then contradict the property of A if A ∉ A it should be inside A by set building property of A .

So when to build such set operation we have to design the Axioms behind the set algebra such that is can't enter to a paradox . If an algebra enter in a paradox it is not well defined .

Sometime we use prove by contradiction . To prove A = 1 (true) we prove !A = 0 (false) . But it does not give us always good result . !A = 0 means A = 1 or A is a paradox . We must have to show that A = 1 in direct method , induction or by construction .

To define anything or to build some logical universe We must follow the exclusion principle . That is we will not include anything in our logical universe which is not necessary to build our universe under the Given observations / tautology .

 

Automata Glimpse

The Automata (Self - Acting ) Theory is the study of abstract machines use to computing problems .

Formal definition

Automaton

An Automaton is represented formally by  (Q,Σ,δ,q₀,F) →

1.  Q is a finite set of states.

2. Σ is a finite set of symbols, called the alphabet of the automaton.

3. δ is the transition function, that is, δ: Q × Σ → Q.

4. q0 is the start state, that is, the state of the automaton before any input has been 
     processed, where q0 ∈ Q.

5. F is a set of states of Q (i.e. F⊆Q) called accept states.

Alphabet 
     An Alphabet is a finite set of symbols .

Language
     An Language on a alphabet Σ is a subset of Σ*

An Automaton is described by an Language which it accepts .

Grammar 
    A Grammar of a Language is a set of rules just what that language follows .

A language must have a grammar to describe and generate it . A Grammar G can be told as the grammar of Language L iff G generates only L .

If G is a Grammar and L is Language generated by it and A is the automaton accepting only that language then we can write this as →

L = L(G)  A = A(L)
Or ,
L ↔ G ↔ A

Normally we have input string in an array/tape . Our machine read them one by one . There is a pointer initially pointed  at q0 and shift according δ to from states to state of Q. The given string is accepted if the pointer reside in an accepting state at the end of the string .


We have many zones of Languages and corresponding Automata and Grammar

Language	Grammar	Automata
Regular	Regular	Finite Automata
Context Free (CFL)	Context Free	PDA
Context Sensitive (CSL)	Context Sensitive	LBA
Decidable / Recursive		TM accepts and rejects
Recursively Enumerable		TM can only accept
Undecidable

Only regular language can be parsed by finite state machines  . CFL can be parsed using FSM and a stack . CSL can be parsed by LBA . The most powerful machine is TM i.e a infinite array and a FSM [Finite state machine ] .  

Some probabilistic Analysis

Let's have x_1,x_2,...x_n ~iid Unif([0,1]) .We have to find the probability P(x_1≤x_2≤...≤x_n ) = the probability that x_1 ≤ x_2 ... ≤ x_n .

Let's see that
P(x_1 ≤ x_2)  = ∫(x_2 = 0 to 1) f(x_2) (∫(x_1 = 0 to x_2) f(x_1)dx_1 ) dx_2  = 1/2! .

We can  find in similar way P(x_1 ≤  x_2 ≤ x_3) = 1/3!

So probability  to be found out = 1/n!

What is the probability that x = x_i one of the elements of x_1,x_2 ... x_n described before will be equals to the max(x_1,x_2,...x_n)?

Ok we have to find Σ ( for all value of x )P(x = x, x = max( ∀ x_i ∈ {x_1,x_2 ... x_n}  , x_i) )
=  P( x = max( ∀ x_i ∈ {x_1,x_2 ... x_n}  , x_i) ) 
=  1 - (F(x))^n

Where F(x) is the cdf of x.

Asymptotic Notation

We sometime become concern about the asymptotic nature of a function specially when we are considering Limit or nature of a function or composite function at Neighbourhood(Nbd) of a point.

We use following definitions :-
Typically we use these notation for x → ∞.
(i) Big -O :-  f = O(g) ↔ ∃ (x₀ , ϵ) ∈ R² s.t. ∀x ≥ x₀  |f(x)| ≤ |ϵg(x)| . 
This g actually represent a asymptotic upper bound of f . 
For more stronger bound we have small-o which is described as :-
f(x) = o(g(x)) ↔  ∀ϵ ∈ R  ∃ x₀ ∈ R s.t.  ∀x ≥ x₀  |f(x)|  ≤ |ϵg(x)| . 

(ii) Big - Ω :-  f = O(g) ↔ g =  Ω(f). Similarly defined ω.
(iii) Big - Θ :-  f = Θ(g) ↔ g =  Θ(f) ↔ g =  O(f) . Similarly defined θ.

Differentiation and Integration

Let, y = y(x)

Differentiation dy/dx is defined as  Lt ( Δx  →  0 ) ( (y(x + Δx ) - y(x)) / Δx ).

Where Δx = small increment of x .

A function is differentiable on a point only if it is continuous  at that point [ Because we have to have the value of y(x) to differentiate ].

Differentiation gives the slope of a function at certain point . [ See any standard book for prove ]

While integration is the anti-differentiation . i.e ∫ (dydx)dx = y + c [ c is arbitrary constant ]

Definition of inegration : g(x) =  ∫ f(x)dx  iff  dg/dx = f

While the physical significance of integration is the definite integration and its explanation as Riemann Integral http://en.wikipedia.org/wiki/Riemann_integral .

Important Limits

There are some important Limits :

1. Lt (x  →  a ) (xⁿ - aⁿ) / (x - a) = n*a^n-1 [ n is rational ] 

[ Prove is easy for n is integer expand the numerator and get the result by eliminating Limit operations . For other rational make n = p/q where p is integer and q is natural ]

2. Lt (x  →  0 ) sin(x)/x = 1 

3. Lt (x  →  0 ) ((1+x)ⁿ - 1)/x = n [ n is rational ]

4.  Lt (x  →  0 ) (e^x- 1)/x = 1 [ n is rational ]

Col.  Lt (x  →  0 ) (1+x)^1/x = e [ From above ] 

Fundamental Limit Theorems

We can build our concept of limit with these .

Theorem 1:

If Lt (x  →  a ) f(x)  = l and Lt (x  →  a ) g(x) = m c is a constant  l,m,c are finite 
  
1.  Lt (x  →  a ) c*f(x) = c * l 

2.  Lt (x  →  a ) (f(x) + g(x)) = l + m

3   Lt (x  →  a ) f(x) * g(x)  = l*m 

Look carefully we assumed that individual limits of f(x) , g(x) for  (x  →  a )  exist and limits are finite .

Theorem 2 :  (Limit Inclusion Theorem)
If Lt (x  →  a ) f(x)  = l and Lt (x  →  l ) g(x)  = g(l) then Lt (x  →  a ) g(f(x))  = g(Lt (x  →  a ) f(x) ) = g(l)

Theorem 3:

If in Neighbourhood of x = a i.e. in Nbd(x = a) f(x) ≤ g(x) then Lt (x  →  a ) f(x) ≤ Lt (x  →  a ) g(x) .

Theorem 4: ( Sandwich Theorem )

If in Nbd(x = a) f(x)  ≤ g(x)  ≤ h(x) and Lt (x  →  a ) f(x) = Lt (x  →  a ) h(x) = l then Lt (x  →  a ) g(x) = l

Limit Continuity and Infinity

To analysis of real number and real function sometimes we get a function like bellow

f(x) = (x - 3)/(x^2 - 9) . If we ask what will be the value at x = 3 . Ans is NaN or undefined .

Now take a close look to this function .

let's calculate f(x + δ) where δ is a positive number small than the smallest number (we can think) .
This been represented as δ → 0 .

Now see what happen if we minimize and minimize δ .

f(x + δ)           δ
0.3225          0.1
0.3322          0.01
0.3332          0.001
0.3333          0.0001

So we see that the value is coming closure to 0.3333... ~ 1/3 as we minimize δ .



This value where the number tends to by decreasing the value of δ is called the limit (here right limit as we did x + δ ) . 

So in notation  Lt  (δ  → 0) ( f(x + δ ) ) = 1/3 .Similarly we can find left limit by doing f(x - δ ) and same procedure .

If left limit and right limit is same then we tell that    Lt (x  →  3 ) f(x) exist and = 1/3 .

Formal Definition of limit : We can say that  Lt (x  →  a ) f(x) exist and = l iff  for (δ  → 0)   0 <| x - a | < δ  
∃ e  → 0 s.t .  | f(x + a) - l | <  e ( right limit )  and  | f(x - a) - l | <  e ( left limit ) .


Continuity : We saw for the previous function that f(3) does not exist . Now if f(3) exist and 
 Lt (x  →  3 ) f(x) = f(3) then we would say that the function is continuous on that point .


Infinity is a concept which is the number greater than any number other than it .

Calculus start with Number Theorem

Calculus means pebble a very small object . The meaning of calculus is to analysis a very large object by going to its smallest part . The target is to integrate differentiate and have some fantastic knowledge of numbers and measured objects .

Ok! first to proceed to calculus  we have a prerequisite of  basic Number theory .

People first started to count objects as 1 , 2 , 3 , 4 ... like this . To simplify counting they form numbers to be written with respect to a base or radix .

For example in decimal  / Metric system base is 10 . i.e if we write 15 it means 10 + 5  .                   1421 = 1000 + 400 + 20 + 1 etc .
In any number system with base r the number written as →
a_n a_(n-1)... a_0  means a_n * r^(n-1) + a_(n-1)*r^(n-2) + .... a_0 * r^0 .

Now Indian scientist first invented from the philosophical study that if we negate a from a  we got something and that is named as 0 ( A revolution ) .

The set N = {1,2,3...} is the set of natural number . Now we add 0 with it . But still we can't find        11 - 20 . So then the negative numbers came . So we had a larger set Z = {0 , ±1,±2...} formed and we called it the set of Integers .

Now to find numbers like 2/5 3/7 we further increase the set and introduce fraction . So the set with integers and fraction uniformly create R = {0 , ±1 ,±1/2  ,2 ,....} the set of Rational Numbers .

But then Also some number remained which can't be represent as ratio of two integers (Rational Numbers )  like √2 .They called irrationals  . Rational and irrationals uniformly create Real Numbers (Re say) .

Then Also some number remains like (√(-1)) . Scientist then introduce another number i = (√(-1)) and called number having i as Complex numbers (C say ) .

Now we have N < Z < R < Re < C [ < here represent  ⊂ ]

Properties : Closed means with respect to that operation on elements of set mention in the  row result will be member of that set .

Sets  Vs  Operation	+	-	*	/(except by 0)	^	√
N	Closed		Closed		Closed
Z	Closed	Closed	Closed
R	Closed	Closed	Closed	Closed	Closed
Re	Closed	Closed	Closed	Closed	Closed
C	Closed	Closed	Closed	Closed	Closed	Closed

Still some numbers are not known like 0^0 Something / 0 etc . IEEE tell them as NaN [ Not a Number ]

A set is called ordered / partial Order if we can Order the elements of the set somehow [Above are all ordered set so any to element a,b of Order set either  a < b or a = b or a > b ].

Cantor did so much work on the measure of the sets .
1. Two sets are equinumerous iff they have bijection .
2. A set is infinite iff it has bijection to some of its proper subset . [ All above sets are infinite ]
3. A set is countable iff it has a bijection with some subset of N. [ Set N,Z,R are countable ]
4. A set is dense if between any two element of that set there is another element of that set . [R,Re,C are dense]

For showing uncountability of one infinite set we use Cantor Diagonalization Principle .


Calculus is the analysis of real numbers . Calculus means algebra with Concept with Limit , Continuity and infinity .

As we already know what is a function we will start with Limit .

Riemann Integral

Well to integrate we sometime think what is the physical importance of integration . We know differentiation is the way to find the slope . So what is integration .

Ok first of all we can see integration as an anti-derivative . Say dy/dx = m(x) then we can find y(b) - y(a) = ∫(x = a to b) m(x)dx .

Another representation of integration is the "summing the infinitesimal elements infinitely" .

Look at the example bellow →

                                                          Diagrams are  From Wikipedia 

The area under the curve can be determine by following way.
 Slice the area by lines parallel to y axis .Now the Area will obviously converge to the 

(a-b)/n * Sum (k = 0 to n-1)f(a+k) when n → ∞ inf. This is the Riemann Integral .