Let AC and AI denote the collections of graphs with vertex set ω and which have, respectively, no infinite independent subgraph, and no infinite complete subgraph. Both AC and AI are coanalytic sets of reals that are not analytic, and they are disjoint by Ramsey’s theorem. We prove that there exists a Borel set separating AC and AI, and we discuss the sense in which this is an infinite analogue of a weak version of.

In computer networks, vertices represent hosts or servers, and edges represent as the connecting medium between them. In localization, some special vertices are selected to locate the position of all vertices in a computer network. If an arbitrary vertex stopped working and selected vertices still remain the resolving set, then the chosen set is called as the fault-tolerant resolving set. The least number of vertices in such resolving sets is called the fault-tolerant metric dimension of the network. Because of (...) the variety of applications of the metric dimension in different areas of sciences, many generalizations were proposed, and fault tolerant is one of them. In this paper, we computed the fault-tolerant metric dimension of triangular snake, ladder, Mobius ladder, and hexagonal ladder networks. It is important to observe that, in all these classes of networks, the fault-tolerant metric dimension and metric dimension differ by 1. (shrink)

Study, with text of the Yogasūtra of Patañjali, text on Yoga philosophy.

O objetivo deste artigo é apresentar a analogia básica entre arquitetura e retórica antiga a partir dos tratados De Architectura, de Vitrúvio, e o De Oratore, de Cícero. A analogia se verifica na definição do artífice, dos gêneros e partes das técnicas e dos fins de cada uma delas. Para tanto, tomaram-se como referência as fontes do tratado vitruviano, que menciona a influência de Varrão na gramática, de Lucrécio na filosofia e de Cícero no método oratório. A analogia com Cícero (...) serve tanto para conferir autoridade ao modelo de arquiteto vitruviano quanto para diferenciar a arquitetura das demais ciências, sobretudo a filosofia, objeto de debate na obra ciceroniana. (shrink)

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types (...) of questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an (...) effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

A graph’s entropy is a functional one, based on both the graph itself and the distribution of probability on its vertex set. In the theory of information, graph entropy has its origins. Hex-derived networks have a variety of important applications in medication store, hardware, and system administration. In this article, we discuss hex-derived network of type 1 and 2, written as HDN 1 n and HDN 2 n, respectively of order n. We also compute some degree-based entropies such as (...) Randić, ABC, and G A entropy of HDN 1 n and HDN 2 n. (shrink)

How many words—and which ones—are sufficient to define all other words? When dictionaries are analyzed as directed graphs with links from defining words to defined words, they reveal a latent structure. Recursively removing all words that are reachable by definition but that do not define any further words reduces the dictionary to a Kernel of about 10% of its size. This is still not the smallest number of words that can define all the rest. About 75% of the Kernel turns (...) out to be its Core, a “Strongly Connected Subset” of words with a definitional path to and from any pair of its words and no word's definition depending on a word outside the set. But the Core cannot define all the rest of the dictionary. The 25% of the Kernel surrounding the Core consists of small strongly connected subsets of words: the Satellites. The size of the smallest set of words that can define all the rest—the graph's “minimum feedback vertex set” or MinSet—is about 1% of the dictionary, about 15% of the Kernel, and part-Core/part-Satellite. But every dictionary has a huge number of MinSets. The Core words are learned earlier, more frequent, and less concrete than the Satellites, which are in turn learned earlier, more frequent, but more concrete than the rest of the Dictionary. In principle, only one MinSet's words would need to be grounded through the sensorimotor capacity to recognize and categorize their referents. In a dual-code sensorimotor/symbolic model of the mental lexicon, the symbolic code could do all the rest through recombinatory definition. (shrink)

We consider three problems concerning alpha conversion of closed terms (combinators). (1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables. (2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N. (3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way. We obtain the following results. (...) (1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs. (2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2). (3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given. There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand. (shrink)

A poset is well‐partially ordered (WPO) if all its linear extensions are well orders; the supremum of ordered types of these linear extensions is the length, of p. We prove that if the vertex set X is infinite, of cardinality κ, and the ordering ⩽ is the intersection of finitely many well partial orderings of X,, then, letting, with, denote the euclidian division by κ (seen as an initial ordinal) of the length of each corresponding poset: where denotes the (...) least initial ordinal greater than the ordinal. This inequality is optimal. This result answers questions of Forster. (shrink)

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math.38(1) (1971) 69–83] and denoted H3, is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.I, eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work (...) of Sauer [Coloring subgraphs of the Rado graph, Combinatorica26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica26(2) (2006) 183–205], the Ramsey theory of H3 had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin.2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math.185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph G, there is a finite number T(G) such that for any coloring of all copies of G in H3 into finitely many colors, there is a subgraph of H3 which is again universal homogeneous triangle-free in which the coloring takes no more than T(G) colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code H3 and the development of their Ramsey theory. (shrink)

Let G V, E be a simple undirected complete graph with vertex and edge sets V and E, respectively. In this paper, we consider the degree-constrained k -minimum spanning tree problem which consists of finding a minimum cost subtree of G formed with at least k vertices of V where the degree of each vertex is less than or equal to an integer value d ≤ k − 2. In particular, in this paper, we consider degree values of (...) d ∈ 2,3. Notice that DC k MST generalizes both the classical degree-constrained and k -minimum spanning tree problems simultaneously. In particular, when d = 2, it reduces to a k -Hamiltonian path problem. Application domains where DC k MST can be adapted or directly utilized include backbone network structures in telecommunications, facility location, and transportation networks, to name a few. It is easy to see from the literature that the DC k MST problem has not been studied in depth so far. Thus, our main contributions in this paper can be highlighted as follows. We propose three mixed-integer linear programming models for the DC k MST problem and derive for each one an equivalent counterpart by using the handshaking lemma. Then, we further propose ant colony optimization and variable neighborhood search algorithms. Each proposed ACO and VNS method is also compared with another variant of it which is obtained while embedding a Q-learning strategy. We also propose a pure Q-learning algorithm that is competitive with the ACO ones. Finally, we conduct substantial numerical experiments using benchmark input graph instances from TSPLIB and randomly generated ones with uniform and Euclidean distance costs with up to 400 nodes. Our numerical results indicate that the proposed models and algorithms allow obtaining optimal and near-optimal solutions, respectively. Moreover, we report better solutions than CPLEX for the large-size instances. Ultimately, the empirical evidence shows that the proposed Q-learning strategies can bring considerable improvements. (shrink)

The problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in the category of graphs with a vertex coloring by two colors. It is not known whether this problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable.

In this book, the authors provide a detailed discussion of some problematic of some critical issues of the philosophical research field known as “moral psychology”. The common thread that ideally combines the eight essays concerns the definition and demarcation of the “moral mind”, as a set of cognitive and affective capabilities, attitudes, psychological mechanisms that have practical relevance when we wonder how to act or we evaluate the of action of others. The subtitle (persons, reasons, virtues) means to focus on (...) the vertexes that draw an ideal triangulation within which lies the practical space characterizing and nourishing the moral life of human beings. (shrink)

A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We (...) show that, if A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs. (shrink)

The number of edges in a shortest walk from one vertex to another vertex of a connected graph G is known as the distance between them. For a vertex x and an edge e = a b in G, the minimum number from distances of x with a and b is said to be the distance between x and e. A vertex x is said to distinguish two distinct edges e 1 and e 2 if the (...) distance between x and e 1 is different from the distance between x and e 2. A set X of vertices in a connected graph G is an edge metric generator for G if every two edges of G are distinguished by some vertex in X. The number of vertices in such a smallest set X is known as the edge metric dimension of G. In this article, we solve the edge metric dimension problem for certain classes of planar graphs. (shrink)

Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.

In lieu of an abstract, here is a brief excerpt of the content:From Politics to Philosophy and Theology:Some Remarks about Foucault's Interpretation of Parrêsia in Two Recently Published SeminarsCarlos LévyAt the beginning of his seminar entitled Le courage de la vérité, Foucault gives a first definition of parrêsia (2009, 10–12), which I take as my point of departure.Parrêsia is a fundamental political concept; it denotes outspokenness, and Foucault distinguishes between two versions of it, one negative, the other positive. The first (...) meaning implies the articulation of everything, "n'importe quoi" (whatever), an expression that in French is indeed derogatory. For Foucault this meaning finds an illustration in a passage from Plato's Republic in which the philosopher describes the appalling state of the democratic city, where everyone tries to impose their own desires on others.1 The positive meaning implies that truth will be stated "without dissimulation, reservation, set clause, or rhetorical ornament that could encode or hide it" (2009, 11). But Foucault says that to effectuate this positive meaning it is not enough to merely state everything and state it truthfully. It is also necessary for the speaker of parrêsia, the parrêsiastês, to personally involve himself in what he says and to take a risk. As Foucault says himself, this is to speak "truth while taking the risk of violence" (2009, 12). [End Page 313] This risk is nonetheless attenuated by what Foucault calls "the parrêsiastic play," that is, the capacity of the interlocutor (assembly, tyrant) to tolerate outspokenness.Even though Foucault never sets the problem out in these terms, one may construe parrêsia as both a passion, since it entails an emotional investment, and a virtue, insofar as it is still linked to courage. It is common to say that somebody has "a passion for the truth" or that he has "the courage of his convictions." However, Foucault uses the term "passion" very sparingly. An analysis of word frequency in his seminars for the period 1982 to 1984 reveals that the term "virtue" occurs often, while "passion" is almost entirely absent, except about tragedy (2008, 105–35). By refraining from speaking of the "passion of truth," Foucault rejects the possibility of analyzing the concept of parrêsia in a more unitary way. For him, there is a good and a bad parrêsia, a situation that emphasizes the difficulties usually inherent in dualism: how can two opposite realities coexist, especially within the same concept? These difficulties are carefully analyzed in the seminars, but there is also a methodological difficulty: do historical sources force us to accept the dualistic interpretation or, better, the reconstruction proposed by Foucault in such a persuasive way? Or do they prompt us to introduce the notion of passion, somehow or other, as being present even in the "good" parrêsia?In my view, one does not compromise Foucault's position by saying that, for him, the dualism inherent in political parrêsia has a functional nature. It is linked to what he calls the right functioning and the worsening functioning of democracy, as they are articulated in his seminar of 2 February 1983 (2008, 157–69). In his exposé some postulates are expounded using the metaphor of the rectangle: the existence of parrêsia requires democracy, and thus democracy forms the first vertex of this rectangle. But one of the most interesting elements in Foucault's subsequent seminars is his effort to demonstrate that parrêsia can nevertheless exist under tyranny without its most essential features being undermined.Democracy, in Foucault's opinion, can't be lively and dynamic without the second vertex, which he calls "le pôle de l'ascendant"—the pole of ascending leadership; that is, in his own words, "the problem of those who, speaking before others and above them, are heard by them, persuade them, lead them, and have control over them" (2008, 157). Foucault's use of the term "problem" is itself somewhat... problematic. It is not clear why the existence of this ascendancy is a problem to the extent that it can be seen as the condition of a democratic and parrêsiastic functioning. In Foucault's [End Page 314] own words, the... (shrink)

Domination is a structural complexity of chemical molecular graphs. A dominating set in a graphG=V,Eis a subsetS⊆Vsuch that each vertex inV\Sis adjacent to at least one vertex inS. The domination numberγGof a graphGis the minimum size of a dominating set inG. In this paper, computer-aided approaches for obtaining bounds for domination number on torus graphs are here considered, and many new exact values and bounds are obtained.

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as set (...) of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

Description logic knowledge bases can be used to represent knowledge about a particular domain in a formal and unambiguous manner. Their practical relevance has been shown in many research areas, especially in biology and the Semantic Web. However, the tasks of constructing knowledge bases itself, often performed by human experts, is difficult, time-consuming and expensive. In particular the synthesis of terminological knowledge is a challenge that every expert has to face. Because human experts cannot be omitted completely from the construction (...) of knowledge bases, it would therefore be desirable to at least get some support from machines during this process. To this end, we shall investigate in this work an approach which shall allow us to extract terminological knowledge in the form of general concept inclusions from factual data, where the data is given in the form of vertex- and edge-labelled graphs. Because such graphs appear naturally within the scope of the Semantic Web in the form of sets of Resou... (shrink)

Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f, w = (...) min d w, t, d w, s is referred as distance between f = t s an edge and w a vertex. d w, f 1 ≠ d w, f 2 implies that two edges f 1, f 2 ∈ E are resolved by node w ∈ V. A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, e dim Γ for a graph Γ. A set B of some nodes of Γ is a mixed metric generator if any two members of V ∪ E are resolved by some members of B. Such a set B with least cardinality is termed as mixed metric dimension, m dim Γ. In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph T n, m, line graph of dragon graph L T n, m, paraline graph of dragon graph L S T n, m, and line graph of line graph of dragon graph L L T n, m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs. (shrink)

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of (...) forbidden induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: –There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs.–Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f.Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

In the thesis some combinatorial statements are analysed from the reverse mathematics point of view. Reverse mathematics is a research program, which dates back to the Seventies, interested in finding the exact strength, measured in terms of set-existence axioms, of theorems from ordinary non set-theoretic mathematics. After a brief introduction to the subject, an on-line (incremental) algorithm to transitively reorient infinite pseudo-transitive oriented graphs is defined. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is computably (...) true. Interval graphs and interval orders are the common theme of the second part of the thesis. A chapter is devoted to analyse the relative strength of different characterisations of countable interval graphs and to study the interplay between countable interval graphs and countable interval orders. In this context the theme of unique orderability of interval graphs arises, which is studied in the following chapter. The last chapter about interval orders inspects the strength of some statements involving the dimension of countable interval orders. The third part is devoted to the analysis of two theorems proved by Rival and Sands in 1980. The first principle states that each infinite graph contains an infinite subgraph such that each vertex of the graph is adjacent either to none, or to one or to infinitely many vertices of the subgraph. This statement, restricted to countable graphs, is proved to be equivalent to ACA_0 and hence to be stronger than Ramsey's theorem for pairs, despite the similarity of partial order with finite width contains an infinite chain such that each point of the poset is comparable either to none or to infinitely many points of the chain. For each k less than or equal to 3, the latter principle restricted to countable poset of width k is proved to be equivalent to ADS. Some complementary results are presented in the thesis. (shrink)

We study vertex operators in 4D conformal field theory derived from quantized gravity, whose dynamics is governed by the Wess-Zumino action by Riegert and the Weyl action. Conformal symmetry is equal to diffeomorphism symmetry in the ultraviolet limit, which mixes positive-metric and negative-metric modes of the gravitational field and thus these modes cannot be treated separately in physical operators. In this paper, we construct gravitational vertex operators such as the Ricci scalar, defined as space-time volume integrals of them (...) are invariant under conformal transformations. Short distance singularities of these operator products are computed and it is shown that their coefficients have physically correct signs. Furthermore, we show that conformal algebra holds even in the system perturbed by the cosmological constant vertex operator as in the case of the Liouville theory shown by Curtright and Thorn. (shrink)

A topological index can be focused on uprising of a chemical structure into a real number. The degree-based topological indices have an active place among all topological indices. These topological descriptors intentionally associate certain physicochemical assets of the corresponding chemical compounds. Graph theory plays a very useful role in such type of research directions. The hex-derived networks have vast applications in computer science, physical sciences, and medical science, and these networks are constructed by hexagonal mesh networks. In this paper, we (...) determined the exact values of vertex-edge-degree-based topological descriptors for hex-derived networks HDN 1 p and HDN 2 p, which are generated by the hexagonal network of dimension p. (shrink)

Set-theoretic and category-theoretic foundations represent different perspectives on mathematical subject matter. In particular, category-theoretic language focusses on properties that can be determined up to isomorphism within a category, whereas set theory admits of properties determined by the internal structure of the membership relation. Various objections have been raised against this aspect of set theory in the category-theoretic literature. In this article, we advocate a methodological pluralism concerning the two foundational languages, and provide a theory that fruitfully interrelates a `structural' perspective (...) to a set-theoretic one. We present a set-theoretic system that is able to talk about structures more naturally, and argue that it provides an important perspective on plausibly structural properties such as cardinality. We conclude the language of set theory can provide useful information about the notion of mathematical structure. (shrink)

Multiverse Views in set theory advocate the claim that there are many universes of sets, no-one of which is canonical, and have risen to prominence over the last few years. One motivating factor is that such positions are often argued to account very elegantly for technical practice. While there is much discussion of the technical aspects of these views, in this paper I analyse a radical form of Multiversism on largely philosophical grounds. Of particular importance will be an account of (...) reference on the Multiversist conception, and the relativism that it implies. I argue that analysis of this central issue in the Philosophy of Mathematics indicates that Radical Multiversism must be algebraic, and cannot be viewed as an attempt to provide an account of reference without a softening of the position. (shrink)

We consider the classification problem for several classes of countable structures which are “vertex-transitive”, meaning that the automorphism group acts transitively on the elements. We show that the classification of countable vertex-transitive digraphs and partial orders are Borel complete. We identify the complexity of the classification of countable vertex-transitive linear orders. Finally we show that the classification of vertex-transitive countable tournaments is properly above \ in complexity.

The theory of lower previsions is designed around the principles of coherence and sure-loss avoidance, thus steers clear of all the updating anomalies highlighted in Gong and Meng's "Judicious Judgment Meets Unsettling Updating: Dilation, Sure Loss, and Simpson's Paradox" except dilation. In fact, the traditional problem with the theory of imprecise probability is that coherent inference is too complicated rather than unsettling. Progress has been made simplifying coherent inference by demoting sets of probabilities from fundamental building blocks to secondary representations (...) that are derived or discarded as needed. (shrink)

Set-theoretic pluralism is an increasingly influential position in the philosophy of set theory (Balaguer [1998], Linksy and Zalta [1995], Hamkins [2012]). There is considerable room for debate about how best to formulate set-theoretic pluralism, and even about whether the view is coherent. But there is widespread agreement as to what there is to recommend the view (given that it can be formulated coherently). Unlike set-theoretic universalism, set-theoretic pluralism affords an answer to Benacerraf’s epistemological challenge. The purpose of this paper is (...) to determine what Benacerraf’s challenge could be such that this view is warranted. I argue that it could not be any of the challenges with which it has been traditionally identified by its advocates, like of Benacerraf and Field. Not only are none of the challenges easier for the pluralist to meet. None satisfies a key constraint that has been placed on Benacerraf’s challenge. However, I argue that Benacerraf’s challenge could be the challenge to show that our set-theoretic beliefs are safe – i.e., to show that we could not have easily had false ones. Whether the pluralist is, in fact, better positioned to show that our set-theoretic beliefs are safe turns on a broadly empirical conjecture which is outstanding. If this conjecture proves to be false, then it is unclear what the epistemological argument for set-theoretic pluralism is supposed to be. (shrink)

This is an extensively revised edition of Mr. Quine's introduction to abstract set theory and to various axiomatic systematizations of the subject.

Michael Potter presents a comprehensive new philosophical introduction to set theory. Anyone wishing to work on the logical foundations of mathematics must understand set theory, which lies at its heart. Potter offers a thorough account of cardinal and ordinal arithmetic, and the various axiom candidates. He discusses in detail the project of set-theoretic reduction, which aims to interpret the rest of mathematics in terms of set theory. The key question here is how to deal with the paradoxes that bedevil set (...) theory. Potter offers a strikingly simple version of the most widely accepted response to the paradoxes, which classifies sets by means of a hierarchy of levels. What makes the book unique is that it interweaves a careful presentation of the technical material with a penetrating philosophical critique. Potter does not merely expound the theory dogmatically but at every stage discusses in detail the reasons that can be offered for believing it to be true. Set Theory and its Philosophy is a key text for philosophy, mathematical logic, and computer science. (shrink)

The iterative conception of set is typically considered to provide the intuitive underpinnings for ZFCU (ZFC+Urelements). It is an easy theorem of ZFCU that all sets have a definite cardinality. But the iterative conception seems to be entirely consistent with the existence of “wide” sets, sets (of, in particular, urelements) that are larger than any cardinal. This paper diagnoses the source of the apparent disconnect here and proposes modifications of the Replacement and Powerset axioms so as to allow for the (...) existence of wide sets. Drawing upon Cantor’s notion of the absolute infinite, the paper argues that the modifications are warranted and preserve a robust iterative conception of set. The resulting theory is proved consistent relative to ZFC + “there exists an inaccessible cardinal number.”. (shrink)

Proposals for allocating scarce lifesaving resources in the face of the Covid-19 pandemic have aligned in some ways and conflicted in others. This paper attempts a kind of priority setting in addressing these conflicts. In the first part, we identify points on which we do not believe that reasonable people should differ—even if they do. These are (i) the inadequacy of traditional clinical ethics to address priority-setting in a pandemic; (ii) the relevance of saving lives; (iii) the flaws of first-come, (...) first-served allocation; (iv) the relevance of post-episode survival; (v) the difference between age and other factors that affect life-expectancy; and (vi) the need to avoid quality-of-life judgments. In the second part, we lay out some positions on which reasonable people can and do differ. These include (i) conflicts between maximizing benefits and priority to the worst off; (ii) role-based priority; and (iii) whether patients’ existing lifesaving resources should be subject to redistribution. (shrink)