In [[mathematical logic]], the '''arithmetical hierarchy''', '''arithmetic hierarchy''' or '''Kleene hierarchy''' classifies the set of [[arithmetic formula]]s (or [[arithmetic set]]s) according to their degree of solvability. Layers in the hierarchy are defined as those formulas which satisfy a [[proposition]] (description) of a certain complexity.

== Definition ==

The '''arithmetical hierarchy''' are three families of collections of sets (or [[formula (mathematical logic)|formulas]] called <math>\Pi^0_n</math>, <math>\Sigma^0_n</math>, and <math>\Delta^0_n</math>, for [[natural number]]s ''n''. The collections are recursively defined as

:<math>\Sigma^0_0</math> is the collection of [[recursive set]]s
:<math>\Sigma^0_{n+1}</math> is the collection of [[A-recursive set]] for an <math>A \in \Sigma^0_n</math>
:<math>\Pi^0_n</math> the collection of [[co-A-recursive set]]s
:<math>\Delta^0_n := \Sigma_n \cap \Pi^0_n</math>

Alternatively they can be defined as the collection of arithmetic formulas with a certain number of [[quantification|quantifiers]]. A formula is in the level <math>\Sigma^0_n</math> if it satisfies a proposition quantified first by <math>\exists</math>, and a total of ''n'' alternating existential (<math>\exists</math>) and [[universal quantifier|universal]] (<math>\forall</math>) natural-number quantifiers; formulas are classified as <math>\Pi^0_n</math> in an equivalent fashion, except that the quantifiers commence with <math>\forall</math>. A set is <math>\Sigma^0_n</math> (resp. <math>\Pi^0_n</math>) if and only if it is definable by a formula of that complexity.

Note that it rarely makes sense to speak of <math>\Delta^0_n</math> formulas; the first quantifier of a formula is either existential or universal. So a <math>\Delta^0_n</math> set is not defined by a <math>\Delta^0_n</math> formula; rather, there is a <math>\Sigma^0_n</math> formula and a <math>\Pi^0_n</math> formula, which ''both'' happen to define the set in question.

== Examples ==

* <math>\Sigma_0 = \Pi_0 = \Sigma_1 \cap \Pi_1</math>, the collection of recursive sets

* <math>\Sigma_1</math> are those propositions with one [[existential quantifier]], <math>\exists x_1 : </math> proposition holds. These are precisely the [[recursively enumerable set]]s.

== Properties ==

* <math>\Delta_n \subset \Pi_n</math> and <math>\Delta_n \subset \Sigma_n</math>
* <math>\Pi_n \subset \Pi_{n+1}</math> and <math>\Sigma_n \subset \Sigma_{n+1}</math>
* <math>\Sigma_n \cup \Pi_n \subset \Delta_{n+1}</math>
* <math>\emptyset^{(n)}</math> (the ''n''-the [[Turing jump]] of the empty set) is [[m-complete]] in <math>\Sigma_n</math>
* <math>\mathbb{N} \setminus \emptyset^{(n)}</math> is m-complete in <math>\Pi_n</math>

== Relation to Turing machines ==

Suppose that there is an [[oracle machine]] capable of calculating all the functions in a level <math>\Delta_n</math>. This machine is incapable of solving its own [[halting problem]] (Turing's proof still applies). The halting problem for <math>\Delta_n</math> in fact sits in <math>\Delta_{n+1}</math>.

[[Post's theorem]] describes the close connection between the arithmetical hierarchy and the [[Turing degree]]s.

The [[polynomial hierarchy]] is a "feasible resource-bounded" version of the arithmetical hierarchy, in which polynomial length bounds are placed on the strings involved, or equivalently, polynomial time bounds are placed on the Turing machines involved.

== Also see ==

* [[Recursion theory]]
* [[Analytical hierarchy]]
* [[Interpretability logic]].

== References ==

* [http://www.csc.villanova.edu/~japaridz/ G.Japaridze], ''The logic of the arithmetical hierarchy'', in '''Annals of Pure and Applied Logic''' 66 (1994), pp.89-112.

[[Category:Computability]]
[[Category:Set theory]]
[[Category:Descriptive set theory]]

[[fr:Hiérarchie arithmétique]]

Arithmetische Hierarchie

2005-09-24T16:49:09Z

MathMartin: /* Examples */ rewrote example, added example

Arithmetische Hierarchie

2005-09-24T16:45:39Z

MathMartin: added == Properties ==

Arithmetische Hierarchie

2005-09-24T16:34:41Z

MathMartin: added ==Definition==

2004-09-26T13:41:26Z

MathMartin: merged with material form matrix_(mathematics)

In [[mathematics]], a '''block matrix''' or a '''partitioned matrix''' is a partition of a [[Matrix (mathematics)|matrix]] into rectangular smaller matrices called '''blocks'''. Looking at it another way, the matrix is written in terms of smaller matrices written side-by-side. A block matrix must conform to a consistent way of splitting up the rows, and the columns: we group the rows into some adjacent 'bunches', and the columns likewise. The partition is into the rectangles described by one bunch of adjacent rows crossing one bunch of adjacent columns. In other words, the matrix is split up by some horizontal and vertical lines that go all the way across.

== Example ===

A '''partitioned matrix''' or ''[[block matrix]]'' is a matrix of matrices. For example, take a matrix ''P'':

:<math>P = \begin{bmatrix}
1 & 2 & 3 & 2\\
1 & 2 & 7 & 5\\
4 & 9 & 2 & 6\\
6 & 1 & 5 & 8\end{bmatrix}</math>

We could partition it into a 2×2 partitioned matrix like this:

:<math>P_{11} = \begin{bmatrix}
1 & 2 \\
1 & 2 \end{bmatrix}, P_{12} = \begin{bmatrix}
3 & 2\\
7 & 5\end{bmatrix}, P_{21} = \begin{bmatrix}
4 & 9 \\
6 & 1 \end{bmatrix}, P_{22} = \begin{bmatrix}
2 & 6\\
5 & 8\end{bmatrix}</math>

:<math>P_{\mathrm{partitioned}} = \begin{bmatrix}
P_{11} & P_{12}\\
P_{21} & P_{22}\end{bmatrix}</math>

==Application==
In [[linear algebra]] terms, the use of a block matrix corresponds to having a [[linear mapping]] thought of in terms of corresponding 'bunches' of [[basis vector]]s. That again matches the idea of having distinguished [[direct sum]] decompositions of the [[domain (mathematics)|domain]] and [[range (mathematics)|range]]. It is always particularly significant if a block is the zero matrix; that carries the information that a summand maps into a sub-sum.

Given the interpretation ''via'' linear mappings and direct sums, there is a special type of block matrix that occurs for square matrices (the case ''m'' = ''n''). For those we can assume an interpretation as an [[endomorphism]] of an ''n''-dimensional space ''V''; the block structure in which the bunching of rows and columns is the same is of importance because it corresponds to having a single direct sum decomposition on ''V'' (rather than two). In that case, for example, the [[diagonal]] blocks in the obvious sense are all square. This type of structure is required to describe the [[Jordan normal form]].

This technique is used to cut down calculations of matrices, column-row expansions, and many [[computer science]] applications, including [[VLSI]] chip design. An example is the [[Strassen algorithm]] for fast [[matrix multiplication]].

[[Category:Mathematics]]

Woodbury-Matrix-Identität

2004-07-02T22:02:44Z

MathMartin: changed link name

In [[mathematics]] (specifically [[linear algebra]]), the '''Woodbury matrix identity''' is the following formula for ''n''×''n'' [[matrix (math)|matrices]]:

:<math>
\left( \textrm{A}+\textrm{UC}\textrm{V}\right) ^{-1}=\textrm{A}^{-1}+\textrm{A}^{-1}\textrm{U}\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) ^{-1}\textrm{VA}^{-1}.
</math>

== Applications ==

Often, the matrix ''A'' is numerically large, while ''UCV'' is small, a ''perturbation'' of ''A''. If furthermore the dimensionality of ''C'' is much smaller than that of ''A'', we can get away with inverting only two matrices of this smaller dimension, while re-using the pre-existing inverse ''A''−1.

This is applied, e.g., in the [[Kalman filter]] and other [[least squares | least-squares estimation]] methods, to replace the parametric solution, requiring inversion of a state vector sized matrix, with a condition equations based solution. In case of the Kalman filter this matrix has the dimensions of the vector of observations, i.e., as small as 1 in case only one new observation is processed at a time. This significantly speeds up the often real time calculations of the filter.

== Proof ==

Consider the following [[partitioned matrix]] equation:

:<math>
\begin{bmatrix}
\textrm{A} & \textrm{U}\\
\textrm{V} & -\textrm{C}^{-1}
\end{bmatrix} \begin{bmatrix}
\textrm{D}_{11} & \textrm{D}_{12}\\
\textrm{D}_{21} & \textrm{D}_{22}
\end{bmatrix} = \begin{bmatrix}
\textrm{I} & 0\\
0 & \textrm{I}
\end{bmatrix}
</math>

Write this out into four equations:

:<math>
\begin{matrix}
\textrm{AD}_{11}+\textrm{UD}_{21} & = & \textrm{I} \\
\textrm{AD}_{12}+\textrm{UD}_{22} & = & 0 \\
\textrm{VD}_{11}-\textrm{C}^{-1}\textrm{D}_{21} & = & 0 \\
\textrm{VD}_{12}-\textrm{C}^{-1}\textrm{D}_{22} & = & \textrm{I}
\end{matrix}
</math>

Of these, only the first and third are needed.

Add the third to the first after multiplying by <math>\textrm{UC}</math>:

:<math>
\left( \textrm{A}+\textrm{UC}\textrm{V}\right) \textrm{D}_{11}=\textrm{I}\, \Rightarrow \, \textrm{D}_{11}=\left( \textrm{A}+\textrm{UC}\textrm{V}\right) ^{-1}
</math>

Then, subtract the first from the third after multiplying by <math>\textrm{VA}^{-1}</math>:

:<math>
\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) \textrm{D}_{21}=-\textrm{VA}^{-1}\, \Rightarrow \, \textrm{D}_{21}=-\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) ^{-1}\textrm{VA}^{-1}
</math>

Back substitute into the first equation:

:<math>
\textrm{AD}_{11}-\textrm{U}\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) ^{-1}\textrm{VA}^{-1}=\textrm{I}\, \Rightarrow \textrm{D}_{11}=\textrm{A}^{-1}+\textrm{A}^{-1}\textrm{U}\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) ^{-1}\textrm{VA}^{-1}
</math>

Now we have two different expressions for the sub-matrix <math> \textrm{D}_{11}</math> that should be ''identical''. Thus we obtain:

:<math>
\left( \textrm{A}+\textrm{UC}\textrm{V}\right) ^{-1}=\textrm{A}^{-1}+\textrm{A}^{-1}\textrm{U}\left( \textrm{C}^{-1}-\textrm{VA}^{-1}\textrm{U}\right) ^{-1}\textrm{VA}^{-1}.
</math>

Which completes the proof.

==See also==

* [[Sherman-Morrison-Woodbury formula]]
* [[Schur complement]]

== External links ==

* [http://www.ee.ic.ac.uk/hp/staff/dmb/matrix/identity.html Some matrix identities]