ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

A new proof of Ajtai’s completeness theorem for nonstandard finite structures (2014)

Springer

In: Archive for Mathematical Logic

add to mindlist on the mindlist

Details

Publication Date: 2014-12-31

Description: Ajtai’s completeness theorem roughly states that a countable structure A coded in a model of arithmetic can be end-extended and expanded to a model of a given theory G if and only if a contradiction cannot be derived by a (possibly nonstandard) proof from G plus the diagram of A , provided that the proof is definable in A and contains only formulas of a standard length. The existence of such model extensions is closely related to questions in complexity theory. In this paper we give a new proof of Ajtai’s theorem using basic techniques of model theory.

Print ISSN: 0933-5846

Electronic ISSN: 1432-0665

Topics: Mathematics

Published by Springer

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit