Independence-friendly logic (original) (raw)
Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and in 1989) is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of can characterize the same classes of structures as existential second-order logic.
Property | Value |
---|---|
dbo:abstract | Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and in 1989) is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of can characterize the same classes of structures as existential second-order logic. For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and , and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix , which expresses that depends on , and depends on , but does not depend on . The introduction of IF logic was partly motivated by the attempt of extending the game semantics of first-order logic to games of imperfect information. Indeed, a semantics for IF sentences can be given in terms of these kinds of games (or, alternatively, by means of a translation procedure to existential second-order logic). A semantics for open formulas cannot be given in the form of a Tarskian semantics; an adequate semantics must specify what it means for a formula to be satisfied by a set of assignments of common variable domain (a team) rather than satisfaction by a single assignment. Such a team semantics was developed by Hodges. Independence-friendly logic is translation equivalent, at the level of sentences, with a number of other logical systems based on team semantics, such as dependence logic, dependence-friendly logic, exclusion logic and independence logic; with the exception of the latter, IF logic is known to be equiexpressive to these logics also at the level of open formulas. However, IF logic differs from all the above-mentioned systems in that it lacks locality: the meaning of an open formula cannot be described just in terms of the free variables of the formula; it is instead dependent on the context in which the formula occurs. Independence-friendly logic shares a number of metalogical properties with first-order logic, but there are some differences, including lack of closure under (classical, contradictory) negation and higher complexity for deciding the validity of formulas. Extended IF logic addresses the closure problem, but its game-theoretical semantics is more complicated, and such logic corresponds to a larger fragment of second-order logic, a proper subset of . Hintikka has argued that IF and extended IF logic should be used as a basis for the foundations of mathematics; this proposal has been met in some cases with skepticism. (en) Lógica de independência amigável (do inglês Independence-Friendly, Lógica IF), proposta por Jaakko Hintikka e Gabriel Sandu em 1989, objetiva ser uma alternativa mais natural e intuitiva à clássica lógica de primeira ordem (FOL). Lógica do SE é caracterizada por quantificadores ramificados. Esta é mais expressiva que FOL porque permite que sejam expressas relações independentes entre variáveis quantificadas. Por exemplo, a fórmula ∀a ∀b ∃c/b ∃d/a φ(a,b,c,d) ("x/y" deve ser lida como "x independente de y") não pode ser expressa em FOL. Isso é porque c depende apenas de a, e d depende apenas de b. Lógica de primeira ordem não pode expressar esses independências por qualquer reordenação linear de quantificadores. Em parte, a lógica do SE foi motivada pela semântica de jogos para jogos com Informação perfeita. A lógica IF é a tradução equivalente a lógica de segunda ordem existencial e também com dependência lógica de Väänänen e com a lógica de primeira ordem estendida com quantificadores de Henkin. Embora compartilhe várias propriedades meta lógicas com a lógica de primeira ordem, existem algumas diferenças, incluindo a falta de fechamento sob negação e uma complexidade superior para decidir a validade das fórmulas. A lógica IF expandida remete ao problema do fecho, mas sacrifica a semântica de jogos no processo, e isso pertence propriamente a um fragmento superior da lógica de segunda ordem. A proposição de Hintikka de que a lógica IF e sua versão estendida ser usada como fundações da matemática tem sido visto com ceticismo por outros matemáticos, incluindo Väänänen e Solomon Feferman. (pt) |
dbo:wikiPageExternalLink | https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/finite-partiallyordered-quantification/115E0CF95F881AF1B95A9D72DE54D6FF http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.37.5740&rep=rep1&type=ps http://www.johnsymons.net http://www.glyc.dc.uba.ar/santiago/papers/iflso.pdf https://web.archive.org/web/20070921164444/http:/www.cambridge.org/uk/catalogue/catalogue.asp%3Fisbn=9780521876599 https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/some-combinatorics-of-imperfect-information/20CEDF9ED53B639FAACF1B9741C87DC0 https://www.sciencedirect.com/science/article/pii/B9780444817143500096 http://math.stanford.edu/~feferman/papers/hintikka_iia.pdf. http://www.math.ucla.edu/~asl/bsl/0803/0803-004.ps http://dare.uva.nl/document/1273 https://link.springer.com/article/10.1007/BF01049180 https://link.springer.com/article/10.1023/A:1017905122049 https://link.springer.com/content/pdf/10.1023%2FA%3A1016184410627 https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19700160802 https://www.academia.edu/33499634/Is_Hintikkas_logic_first_order https://projecteuclid.org/download/pdfview_1/euclid.ndjfl/1091030856 https://planetmath.org/iflogic |
dbo:wikiPageID | 1974007 (xsd:integer) |
dbo:wikiPageLength | 42859 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1109972837 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Dependence_logic dbr:Alice_ter_Meulen dbr:Jouko_Väänänen dbr:Validity_(logic) dbr:Decidability_(logic) dbr:Compositional dbr:Consistency dbr:Craig_interpolation dbr:Analytical_hierarchy dbr:Branching_quantifier dbr:Löwenheim–Skolem_theorem dbr:Skolemization dbr:Compactness_theorem dbr:Structure_(mathematical_logic) dbc:Philosophical_logic dbr:Wilfrid_Hodges dbr:Game_semantics dbr:Synthese dbc:Non-classical_logic dbc:Systems_of_formal_logic dbr:First-order_logic dbr:Foundations_of_mathematics dbr:Journal_of_Logic,_Language_and_Information dbr:Existential_second-order_logic dbr:Recursively_enumerable dbr:Isomorphic dbr:Jaakko_Hintikka dbr:Imperfect_information dbr:Bulletin_of_Symbolic_Logic dbr:Planet_Math dbr:Solomon_Feferman dbr:Recursively dbr:Second-order_logic dbr:Levy_hierarchy dbr:Tarskian_semantics dbr:Craig's_interpolation_theorem dbr:Co-r.e. dbr:Gödel_number |
dbp:r2ef | refHin1996 (en) |
dbp:ref | refBur2003 (en) refCamHod2001 (en) refEklKol2002 (en) refEnd1970 (en) refFef2006 (en) refFigGorGri2011 (en) refHin2002 (en) refHinSan1989 (en) refHinSan1996 (en) refHod97 (en) refHod97b (en) refJan2002 (en) refKol2001 (en) refKolSym2004 (en) refKonVaa2009 (en) refManSanSev2011 (en) refSan1993 (en) refSan2008 (en) refVää2007 (en) refWal1970 (en) |
dbp:reference | Burgess, John P., "A Remark on Henkin Sentences and Their Contraries", Notre Dame Journal of Formal Logic 44 :185-188 . (en) Figueira, Santiago, Gorín, Daniel and Grimson, Rafael "On the Expressive Power of IF-Logic with Classical Negation", WoLLIC 2011 proceedings, pp. 135-145, ,http://www.glyc.dc.uba.ar/santiago/papers/iflso.pdf. (en) Eklund, Matti and Kolak, Daniel, "Is Hintikka’s Logic First Order?" Synthese, 131: 371-388 June 2002, https://link.springer.com/content/pdf/10.1023%2FA%3A1016184410627. (en) Hodges, Wilfrid , "Compositional semantics for a language of imperfect information". Journal of the IGPL 5: 539–563. (en) Cameron, Peter and Hodges, Wilfrid , "Some combinatorics of imperfect information". Journal of Symbolic Logic 66: 673-684. (en) Kontinen, Juha and Väänänen, Jouko, "On definability in dependence logic" , Journal of Logic, Language and Information 18 , 317-332. (en) Enderton, Herbert B., "Finite Partially-Ordered Quantifiers", Mathematical Logic Quarterly Volume 16, Issue 8 1970 Pages 393–397. (en) Hodges, Wilfrid, "Some Strange Quantifiers", in Lecture Notes in Computer Science 1261:51-65, Jan. 1997. (en) Mann, Allen L., Sandu, Gabriel and Sevenster, Merlijn Independence-Friendly Logic. A Game-Theoretic Approach, Cambridge University Press, . (en) Hintikka, Jaakko , "The Principles of Mathematics Revisited", Cambridge University Press, . (en) Janssen, Theo M. V., "Independent choices and the interpretation of IF logic." Journal of Logic, Language and Information, Volume 11 Issue 3, Summer 2002, pp. 367-387 http://dare.uva.nl/document/1273. (en) Hintikka, Jaakko, "Hyperclassical logic and its implications for logical theory", Bulletin of Symbolic Logic 8, 2002, 404-423http://www.math.ucla.edu/\~asl/bsl/0803/0803-004.ps . (en) Sandu, Gabriel, "On the Logic of Informational Independence and Its Applications", Journal of Philosophical Logic Vol. 22, No. 1 , pp. 29-60. (en) Kolak, Daniel and Symons, John, "The Results are In: The Scope and Import of Hintikka’s Philosophy" in Daniel Kolak and John Symons, eds., Quantifiers, Questions, and Quantum Physics. Essays on the Philosophy of Jaakko Hintikka, Springer 2004, pp. 205-268 , . (en) Sandu, Gabriel, "If-Logic and Truth-definition", Journal of Philosophical Logic April 1998, Volume 27, Issue 2, pp 143–164. (en) Kolak, Daniel, On Hintikka, Belmont: Wadsworth 2001 . (en) Hintikka, Jaakko and Sandu, Gabriel , "Informational independence as a semantical phenomenon", in Logic, Methodology and Philosophy of Science VIII , North-Holland, Amsterdam, . (en) Hintikka, Jaakko and Sandu, Gabriel, "Game-theoretical semantics", in Handbook of logic and language, ed. J. van Benthem and A. ter Meulen, Elsevier 1996 Updated in the 2nd second edition of the book . (en) Feferman, Solomon, "What kind of logic is “Independence Friendly” logic?", in The Philosophy of Jaakko Hintikka ; Library of Living Philosophers vol. 30, Open Court , 453-469, http://math.stanford.edu/\~feferman/papers/hintikka\_iia.pdf. (en) Walkoe, Wilbur John Jr., "Finite Partially-Ordered Quantification", The Journal of Symbolic Logic Vol. 35, No. 4 , pp. 535-555. (en) Väänänen, Jouko, 2007, 'Dependence Logic -- A New Approach to Independence Friendly Logic', Cambridge University Press, , https://web.archive.org/web/20070921164444/http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521876599. (en) |
dbp:wikiPageUsesTemplate | dbt:Cn dbt:Doi dbt:Expand_section dbt:Ill dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Wikicite dbt:Cite_SEP dbt:Isbn |
dct:subject | dbc:Philosophical_logic dbc:Non-classical_logic dbc:Systems_of_formal_logic |
rdf:type | yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Logic105664069 yago:Method105660268 yago:PsychologicalFeature100023100 yago:System105661996 yago:WikicatSystemsOfFormalLogic |
rdfs:comment | Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and in 1989) is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of can characterize the same classes of structures as existential second-order logic. (en) Lógica de independência amigável (do inglês Independence-Friendly, Lógica IF), proposta por Jaakko Hintikka e Gabriel Sandu em 1989, objetiva ser uma alternativa mais natural e intuitiva à clássica lógica de primeira ordem (FOL). Lógica do SE é caracterizada por quantificadores ramificados. Esta é mais expressiva que FOL porque permite que sejam expressas relações independentes entre variáveis quantificadas. (pt) |
rdfs:label | Independence-friendly logic (en) Lógica de independência amigável (pt) |
owl:sameAs | freebase:Independence-friendly logic wikidata:Independence-friendly logic dbpedia-pt:Independence-friendly logic https://global.dbpedia.org/id/f5dL yago-res:Independence-friendly logic |
prov:wasDerivedFrom | wikipedia-en:Independence-friendly_logic?oldid=1109972837&ns=0 |
foaf:isPrimaryTopicOf | wikipedia-en:Independence-friendly_logic |
is dbo:wikiPageRedirects of | dbr:Team_semantics dbr:IF-logic dbr:Independence_friendly_logic dbr:If-logic dbr:If_logic |
is dbo:wikiPageWikiLink of | dbr:Dependence_logic dbr:Index_of_logic_articles dbr:Index_of_philosophy_articles_(I–Q) dbr:Branching_quantifier dbr:Computability_logic dbr:Game_semantics dbr:Giorgi_Japaridze dbr:Daniel_Kolak dbr:Jaakko_Hintikka dbr:Team_semantics dbr:Cirquent_calculus dbr:Second-order_logic dbr:IF-logic dbr:Independence_friendly_logic dbr:If-logic dbr:If_logic |
is foaf:primaryTopic of | wikipedia-en:Independence-friendly_logic |