uu.seUppsala University Publications

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Lindström quantifiers and higher-order notions on finite structuresPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 1999 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Uppsala: Acta Universitatis Upsaliensis , 1999. , 115 p.
##### Series

Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 15
##### Keyword [en]

Mathematics, Finite model theory, generalized quantifiers, higher-order quantifiers and
operators, bijective Ehrenfeucht-Fraïssé games, quantifying over quantifiers, isomorphism quantifiers
##### Keyword [sv]

MATEMATIK
##### National Category

Mathematics
##### Research subject

Mathematical Logic
##### Identifiers

URN: urn:nbn:se:uu:diva-1218ISBN: 91-506-1389-8OAI: oai:DiVA.org:uu-1218DiVA: diva2:160775
##### Public defence

2000-01-14, Room 247, Building 2, Polacksbacken, Uppsala University, Uppsala, 13:15
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt375",{id:"formSmash:j_idt375",widgetVar:"widget_formSmash_j_idt375",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt381",{id:"formSmash:j_idt381",widgetVar:"widget_formSmash_j_idt381",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt387",{id:"formSmash:j_idt387",widgetVar:"widget_formSmash_j_idt387",multiple:true});
Available from: 1999-12-24 Created: 1999-12-24Bibliographically approved

The expressive power of first-order logic is very limited on finite structures. One important way to obtain stronger logics is to add Lindström quantifiers, and another is to add higher-order quantification. We investigate two different ways of combing the two approaches. We define second-order generalised quantifiers by adapting the definition of Lindström quantifiers to a second-order setting. We also introduce existential and universal higher-order quantification where the objects quantified over are Lindström quantifiers rather than relations or higher-order relations.

Second-order generalized quantifiers are generally very expressive, but they can be sensitive to the underlying logic. We construct quantifiers which do not increase the expressive power of fist-order logic, but which dramatically increase the power of some modest extensions of it. For some combinations of syntactic types and classes of finite structures, almost any countable logic is equivalent to a uniformly obtained sublogic of first-order logic with a quantifier of the given type. We show this for any type on the class of ordered structures, and for any non-monadic type on all structures. It alsoholds for monadic types with arity at most n on structures of arity, at most 2^{n}-1. For all types it holds for structures with at most binary relations. The latter is shown by introducing a second-order bijective game, and proving that there is an effcient strategy for one of the players. The stategy is then used to define the desired quantifier.

First-order logic extended with quantification over Lindström quantifiers is decidable on finite structures, and contains an arity hierarchy. The existential fragment Σ^{Q}_{1} includes inflationary fixed point logic extended with the ability to express that two defined structures are non-isomorphic, and is included in Σ^{1}_{1} with the same extension. We show that Σ^{Q}_{1} is equivalent to the latter on rigid structures, and to the former on monadic structures, but neither equivalence holds in general. The fragment Σ^{Q}_{n+1}, allowing *n*+1 alternating levels of quantifiers, is included in the n-th level of the exponential hierarchy, and is equivalent to it on rigid structures.

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1080",{id:"formSmash:lower:j_idt1080",widgetVar:"widget_formSmash_lower_j_idt1080",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1081_j_idt1083",{id:"formSmash:lower:j_idt1081:j_idt1083",widgetVar:"widget_formSmash_lower_j_idt1081_j_idt1083",target:"formSmash:lower:j_idt1081:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});