# Least and Greatest Solutions of Equations over Sets of Integers

Ontology type: schema:Chapter

### Chapter Info

DATE

2010

AUTHORS ABSTRACT

Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S+T=\{m+n \mid m \in S, \: n \in T\}$\end{document}. These equations were recently studied by the authors (“On equations over sets of integers”, STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Sigma^1_1$\end{document} sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved formXi = ϕi(X1, ..., Xn). Least solutions of such resolved systems represent exactly the recursively enumerable sets. More... »

PAGES

441-452

### Book

TITLE

Mathematical Foundations of Computer Science 2010

ISBN

978-3-642-15154-5
978-3-642-15155-2

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-15155-2_39

DOI

http://dx.doi.org/10.1007/978-3-642-15155-2_39

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1017752782

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Je\u017c",
"givenName": "Artur",
"id": "sg:person.015252371751.76",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
],
"type": "Person"
},
{
"affiliation": {
"id": "http://www.grid.ac/institutes/grid.15098.35",
"name": [
"Department of Mathematics, University of Turku, Finland",
],
"type": "Organization"
},
"familyName": "Okhotin",
"givenName": "Alexander",
"id": "sg:person.012144356031.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48"
],
"type": "Person"
}
],
"datePublished": "2010",
"datePublishedReg": "2010-01-01",
"description": "Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$S+T=\\{m+n \\mid m \\in S, \\: n \\in T\\}$\\end{document}. These equations were recently studied by the authors (\u201cOn equations over sets of integers\u201d, STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\Sigma^1_1$\\end{document} sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved formXi\u2009=\u2009\u03d5i(X1, ..., Xn). Least solutions of such resolved systems represent exactly the recursively enumerable sets.",
"editor": [
{
"familyName": "Hlin\u011bn\u00fd",
"givenName": "Petr",
"type": "Person"
},
{
"familyName": "Ku\u010dera",
"givenName": "Anton\u00edn",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-15155-2_39",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-15154-5",
"978-3-642-15155-2"
],
"name": "Mathematical Foundations of Computer Science 2010",
"type": "Book"
},
"keywords": [
"system of equations",
"set of integers",
"such equations",
"unique solution",
"least solution",
"equations",
"operations of union",
"hyperarithmetical sets",
"enumerable sets",
"integers",
"solution",
"great solution",
"set",
"analytical hierarchy",
"unknowns",
"system",
"intersection",
"hierarchy",
"operation",
"authors",
"Union",
"paper"
],
"name": "Least and Greatest Solutions of Equations over Sets of Integers",
"pagination": "441-452",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1017752782"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-15155-2_39"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-15155-2_39",
"https://app.dimensions.ai/details/publication/pub.1017752782"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:46",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_333.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-15155-2_39"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15155-2_39'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15155-2_39'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15155-2_39'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15155-2_39'

This table displays all metadata directly associated to this object as RDF triples.

100 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0102
3 schema:author Naf20491cdacf4a81b93566ba1355d560
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S+T=\{m+n \mid m \in S, \: n \in T\}$\end{document}. These equations were recently studied by the authors (“On equations over sets of integers”, STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Sigma^1_1$\end{document} sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved formXi = ϕi(X1, ..., Xn). Least solutions of such resolved systems represent exactly the recursively enumerable sets.
7 schema:editor N64b4cc490e85491185e417c19cc969d8
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N95a1eba55dbb4b108c6222ecc52aedaf
12 schema:keywords Union
15 analytical hierarchy
16 authors
17 enumerable sets
18 equations
19 great solution
20 hierarchy
21 hyperarithmetical sets
22 integers
23 intersection
24 least solution
25 operation
26 operations of union
27 paper
28 set
29 set of integers
30 solution
31 such equations
32 system
33 system of equations
34 unique solution
35 unknowns
36 schema:name Least and Greatest Solutions of Equations over Sets of Integers
37 schema:pagination 441-452
39 N8cc78502635c4e48bc5f9e7e943c650d
40 schema:publisher N9d0eb177dcb740c391ab2397bebe3eb2
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017752782
42 https://doi.org/10.1007/978-3-642-15155-2_39
43 schema:sdDatePublished 2022-05-20T07:46
45 schema:sdPublisher Nb6e682a944614eeaa39d580260921688
46 schema:url https://doi.org/10.1007/978-3-642-15155-2_39
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N08998af2709a4cce989468587b544eeb schema:familyName Kučera
51 schema:givenName Antonín
52 rdf:type schema:Person
54 schema:value pub.1017752782
55 rdf:type schema:PropertyValue
56 N4cf0109f295044d092cd00a92cd04999 rdf:first N08998af2709a4cce989468587b544eeb
57 rdf:rest rdf:nil
58 N64b4cc490e85491185e417c19cc969d8 rdf:first Nf7479aff61da43d0a521ea570f94b642
59 rdf:rest N4cf0109f295044d092cd00a92cd04999
60 N8cc78502635c4e48bc5f9e7e943c650d schema:name doi
61 schema:value 10.1007/978-3-642-15155-2_39
62 rdf:type schema:PropertyValue
63 N95a1eba55dbb4b108c6222ecc52aedaf schema:isbn 978-3-642-15154-5
64 978-3-642-15155-2
65 schema:name Mathematical Foundations of Computer Science 2010
66 rdf:type schema:Book
67 N9d0eb177dcb740c391ab2397bebe3eb2 schema:name Springer Nature
68 rdf:type schema:Organisation
69 Naf20491cdacf4a81b93566ba1355d560 rdf:first sg:person.015252371751.76
71 Nb6e682a944614eeaa39d580260921688 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
74 rdf:rest rdf:nil
75 Nf7479aff61da43d0a521ea570f94b642 schema:familyName Hliněný
76 schema:givenName Petr
77 rdf:type schema:Person
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
82 schema:name Applied Mathematics
83 rdf:type schema:DefinedTerm
84 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.15098.35
85 schema:familyName Okhotin
86 schema:givenName Alexander
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
88 rdf:type schema:Person
89 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
90 schema:familyName Jeż
91 schema:givenName Artur
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
93 rdf:type schema:Person
94 grid-institutes:grid.15098.35 schema:alternateName Academy of Finland