Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji:
http://hdl.handle.net/11320/6280
Pełny rekord metadanych
Pole DC | Wartość | Język |
---|---|---|
dc.contributor.author | Koch, Sebastian | - |
dc.date.accessioned | 2018-02-08T08:10:30Z | - |
dc.date.available | 2018-02-08T08:10:30Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Formalized Mathematics, Volume 25, Issue 2, Pages 121–139 | - |
dc.identifier.issn | 1426-2630 | - |
dc.identifier.uri | http://hdl.handle.net/11320/6280 | - |
dc.description.abstract | SummaryIn preparation for the formalization in Mizar [4] of lotteries as given in [14], this article closes some gaps in the Mizar Mathematical Library (MML) regarding relational structures. The quotient order is introduced by the equivalence relation identifying two elements x, y of a preorder as equivalent if x ⩽ y and y ⩽ x. This concept is known (see e.g. chapter 5 of [19]) and was first introduced into the MML in [13] and that work is incorporated here. Furthermore given a set A, partition D of A and a finite-support function f : A → ℝ, a function Σf : D → ℝ, Σf (X)= ∑x∈X f(x) can be defined as some kind of natural “restriction” from f to D. The first main result of this article can then be formulated as: ∑x∈Af(x)=∑X∈DΣf(X)(=∑X∈D∑x∈Xf(x)) After that (weakly) ascending/descending finite sequences (based on [3]) are introduced, in analogous notation to their infinite counterparts introduced in [18] and [13].The second main result is that any finite subset of any transitive connected relational structure can be sorted as a ascending or descending finite sequence, thus generalizing the results from [16], where finite sequence of real numbers were sorted.The third main result of the article is that any weakly ascending/weakly descending finite sequence on elements of a preorder induces a weakly ascending/weakly descending finite sequence on the projection of these elements into the quotient order. Furthermore, weakly ascending finite sequences can be interpreted as directed walks in a directed graph, when the set of edges is described by ordered pairs of vertices, which is quite common (see e.g. [10]).Additionally, some auxiliary theorems are provided, e.g. two schemes to find the smallest or the largest element in a finite subset of a connected transitive relational structure with a given property and a lemma I found rather useful: Given two finite one-to-one sequences s, t on a set X, such that rng t ⊆ rng s, and a function f : X → ℝ such that f is zero for every x ∈ rng s \ rng t, we have ∑ f o s = ∑ f o t. | - |
dc.language.iso | en | - |
dc.publisher | DeGruyter Open | - |
dc.subject | quotient order | - |
dc.subject | ordered finite sequences | - |
dc.title | About Quotient Orders and Ordering Sequences | - |
dc.type | Article | - |
dc.identifier.doi | 10.1515/forma-2017-0012 | - |
dc.description.Affiliation | Johannes Gutenberg University, Mainz, Germany | - |
dc.description.references | Grzegorz Bancerek. Tarski’s classes and ranks. Formalized Mathematics, 1(3):563–567, 1990. | - |
dc.description.references | Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41–46, 1990. | - |
dc.description.references | Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107–114, 1990. | - |
dc.description.references | Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi: 10.1007/978-3-319-20615-817. | - |
dc.description.references | Czesław Byliński. Finite sequences and tuples of elements of a non-empty sets. Formalized Mathematics, 1(3):529–536, 1990. | - |
dc.description.references | Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1): 55–65, 1990. | - |
dc.description.references | Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153–164, 1990. | - |
dc.description.references | Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357–367, 1990. | - |
dc.description.references | Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47–53, 1990. | - |
dc.description.references | Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to algorithms. MIT Press, 3. ed. edition, 2009. ISBN 0-262-53305-7, 978-0-262-53305-8, 978-0-262-03384-8. http://scans.hebis.de/HEBCGI/show.pl?21502893_toc.pdf. | - |
dc.description.references | Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165–167, 1990. | - |
dc.description.references | Jarosław Kotowicz. Partial functions from a domain to the set of real numbers. Formalized Mathematics, 1(4):703–709, 1990. | - |
dc.description.references | Gilbert Lee and Piotr Rudnicki. Dickson’s lemma. Formalized Mathematics, 10(1):29–37, 2002. | - |
dc.description.references | Michael Maschler, Eilon Solan, and Shmuel Zamir. Game theory. Cambridge Univ. Press, 2013. ISBN 978-1-107-00548-8. doi: 10.1017/CBO9780511794216. | - |
dc.description.references | Takashi Mitsuishi, Katsumi Wasaki, and Yasunari Shidama. Property of complex functions. Formalized Mathematics, 9(1):179–184, 2001. | - |
dc.description.references | Yatsuka Nakamura. Sorting operators for finite sequences. Formalized Mathematics, 12 (1):1–4, 2004. | - |
dc.description.references | Konrad Raczkowski and Paweł Sadowski. Equivalence relations and classes of abstraction. Formalized Mathematics, 1(3):441–444, 1990. | - |
dc.description.references | Piotr Rudnicki and Andrzej Trybulec. On same equivalents of well-foundedness. Formalized Mathematics, 6(3):339–343, 1997. | - |
dc.description.references | Bernd S. W. Schröder. Ordered Sets: An Introduction. Birkhäuser Boston, 2003. ISBN 978-1-4612-6591-7. https://books.google.de/books?id=hg8GCAAAQBAJ. | - |
dc.description.references | Wojciech A. Trybulec. Non-contiguous substrings and one-to-one finite sequences. Formalized Mathematics, 1(3):569–573, 1990. | - |
dc.description.references | Wojciech A. Trybulec. Pigeon hole principle. Formalized Mathematics, 1(3):575–579, 1990. | - |
dc.description.references | Wojciech A. Trybulec and Grzegorz Bancerek. Kuratowski – Zorn lemma. Formalized Mathematics, 1(2):387–393, 1990. | - |
dc.identifier.eissn | 1898-9934 | - |
dc.description.volume | 25 | - |
dc.description.issue | 2 | - |
dc.description.firstpage | 121 | - |
dc.description.lastpage | 139 | - |
dc.identifier.citation2 | Formalized Mathematics | - |
Występuje w kolekcji(ach): | Formalized Mathematics, 2017, Volume 25, Issue 2 |
Pliki w tej pozycji:
Plik | Opis | Rozmiar | Format | |
---|---|---|---|---|
forma-2017-0012.pdf | 376,91 kB | Adobe PDF | Otwórz |
Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL