We analyze a solitaire game in which a demon rearranges some cards after each move. The graph edge coloring theorems of K˝onig (1931) and Vizing (1964) follow from the winning strategies developed.

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each (...) topic. The ability of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (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)

In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph's nodes. Such theories, which we call annotation theories^ can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, (...) including satisfiability, querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPTime- or co-NPTime-complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21]. (shrink)

A concise yet rigorous introduction to logic and discrete mathematics. This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade. The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics (...) of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual. Key Features: Suitable for a variety of courses for students in both Mathematics and Computer Science. Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection of the most important fields of discrete mathematics Concise, clear and uncluttered presentation with numerous examples. Covers some applications including cryptographic systems, discrete probability and network algorithms. Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study. (shrink)

We use methods of reverse mathematics to analyze the proof theoretic strength of a theorem involving the notion of coloring number. Classically, the coloring number of a graph $G=$ is the least cardinal $\kappa$ such that there is a well-ordering of $V$ for which below any vertex in $V$ there are fewer than $\kappa$ many vertices connected to it by $E$. We will study a theorem due to Komjáth and Milner, stating that if a graph is (...) the union of $n$ forests, then the coloring number of the graph is at most $2n$. We focus on the case when $n=1$. (shrink)

Studies to neutrosophic graphs happens to be not only innovative and interesting, but gives a new dimension to graph theory. The classic coloring of edge problem happens to give various results. Neutrosophic tree will certainly find lots of applications in data mining when certain levels of indeterminacy is involved in the problem. Several open problems are suggested.

Special issue in honour of Landon Rabern. This special issue of Discrete Mathematics is dedicated to his memory, as a tribute to his many research achievements. It contains 10 new articles written by his collaborators, friends, and colleagues that showcase his interests.

What is it that evolves in cultural evolution? This is a question easily posed but not so easily answered. According to common interpretations of cultural evolutionary theory, it is not strictly agents that change over time or proliferate during cultural transmission, but their socially transmitted behavior, what they communicate or acquire via social learning – in short: their interactions. This means that we have to put these cultural interactions into an evolutionary setting and show how they evolve within cultural populations, (...) i.e. within social networks. But the social networks themselves also evolve, which brings us to a multi-level approach of cultural evolution, implementing both, individual and group selection. In this paper I will assume that the microlevel is given by a description of cultural agents, their behavior and decisions, whereas the macrolevel describes the dynamics on population structure and in particular population boundaries in social networks (since we are not really able to identify something analogous to ‘species’ in cultural evolution). In this paper, I am going to offer a specific mathematical model, that makes use of game theory for representing the cultural microlevel and graph theory for the cultural macrolevel. It has to be shown, how both can formally be linked in a synthetic attempt. (shrink)

If [Formula: see text] is a closed Noetherian graph on a [Formula: see text]-compact Polish space with no infinite cliques, it is consistent with the choiceless set theory ZF[Formula: see text][Formula: see text][Formula: see text]DC that [Formula: see text] is countably chromatic and there is no Vitali set.

The distinction between the discrete and the continuous lies at the heart of mathematics. Discrete mathematics (arithmetic, algebra, combinatorics, graph theory, cryptography, logic) has a set of concepts, techniques, and application areas largely distinct from continuous mathematics (traditional geometry, calculus, most of functional analysis, differential equations, topology). The interaction between the two – for example in computer models of continuous systems such as fluid flow – is a central issue in the applicable mathematics of the last hundred (...) years. This article explains the distinction and why it has proved to be one of the great organizing themes of mathematics. (shrink)

The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted towards favoring (...) the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win. (shrink)

Fifty years ago, two Princeton professors established game theory as an important new branch of applied mathematics. Gametheory has become a celebrated discipline in its own right, and it now plays a prestigious role in many disciplines, including ethics,due in particular to the neo-Hobbesian thinking of David Gauthier and others. Now it is perched at the edge of business ethics. I believethat it is dangerous and demeaning. It makes us look the wrong way at business, reinforcing a destructive obsession (...) with measurableoutcomes and a false sense of competition. It falsely characterizes or insidiously advocates a style of human behavior that is utterlyunacceptable. To put the matter quite crudely, a person who actually practiced the form of "rationality" advocated by game theory wouldbe something of a monster. (shrink)

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are explored. The (...) Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

Fifty years ago, two Princeton professors established game theory as an important new branch of applied mathematics. Game theory has become a celebrated discipline in its own right, and it npw plays a prestigues role in many disciplines, including ethics, due in particular to the neo-Hobbesian thinking of David Gauthier and others. Now it is perched at the edge of business ethics. I believe that it is dangerous and demeaning. It makes us look the wrong way at business, reinforcing (...) a destructive obsession with measurable outcomes and a false sense of competition. It falsely characterizes or insidiously advocates a style of human behavior that is utterly unacceptable. To put the matter quite crudely, a person who actually practiced the form of "rationality" advocated by game theory would be something of a monster. (shrink)

This book presents a detailed analysis of three ancient models of spatial magnitude, time, and local motion. The Aristotelian model is presented as an application of the ancient, geometrically orthodox conception of extension to the physical world. The other two models, which represent departures from mathematical orthodoxy, are a "quantum" model of spatial magnitude, and a Stoic model, according to which limit entities such as points, edges, and surfaces do not exist in (physical) reality. The book is unique in its (...) discussion of these ancient models within the context of later philosophical, scientific, and mathematical developments. (shrink)

This lively introductory text exposes the student in the humanities to the world of discrete mathematics. A problem-solving based approach grounded in the ideas of George Pólya are at the heart of this book. Students learn to handle and solve new problems on their own. A straightforward, clear writing style and well-crafted examples with diagrams invite the students to develop into precise and critical thinkers. Particular attention has been given to the material that some students find challenging, such as (...) proofs. This book illustrates how to spot invalid arguments, to enumerate possibilities, and to construct probabilities. It also presents case studies to students about the possible detrimental effects of ignoring these basic principles. The book is invaluable for a discrete and finite mathematics course at the freshman undergraduate level or for self-study since there are full solutions to the exercises in an appendix. (shrink)

The primary objective of this study was to propose a functional discrete mathematical model for analyzing folklore fairy tales. Within this model, characters are denoted as vertices, and explicit instances of communication – both verbal and non-verbal – within the text are depicted as edges. Upon examining a corpus of Eastern Slavic fairy tales in comparison to Chukchi fairy tales, unforeseen outcomes emerged. Notably, the constructed models seem to evade establishing certain connections between characters. Consequently, instances where the interactions (...) among fairy tale characters would result in a non-planar graph structure are notably absent. To put it differently, the models refrain from incorporating sub-graphs delineated by the Kuratowski theorem governing planar graphs, specifically the minimal non-planar graphs Κ5 and Κ3,3. Remarkably, even in more extensive texts featuring a larger cast of characters, connections that would yield a non-planar graph pattern are consistently avoided. This leads to the formulation of a hypothesis positing that traditional folk tales adhere to a “planar narrative” design – an identifiable narrative variant characterized by inherent limitations in complexity. This design, in turn, appears deeply entrenched within the societal framework of the cultures that produced these folk narratives. (shrink)

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

We consider Effort Games, a game-theoretic model of cooperation in open environments, which is a variant of the principal-agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called (...) the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project.We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort.We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P-hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series-Parallel Graphs. (shrink)

Metaphysical graphical structuralism is the view that at some fundamental level the world is a mathematical graph of nodes and edges. Randall Dipert has advanced a graphical structuralist theory of fundamental particulars and Alexander Bird has advanced a graphical structuralist theory of fundamental properties. David Oderberg has posed a powerful challenge to graphical structuralism: that it entails the absurd inexistence of the world or the absurd cessation of all change. In this paper I defend graphical structuralism. A sharper formulation, (...) some theorems about such structures, and careful attention to the interaction of metaphysical and mathematical features, shows that the absurdities depend on assumptions that are not essential to the view and brings to light a surprising fact about the necessary structure of fundamental properties. (shrink)

Information protocols (IP's) were developed to describe players who learn their social situation by their experiences. Although IP's look similar to colored multi-graphs (MG's), the two objects are constructed in fundamentally different ways. IP's are constructed using the global concept of history, whereas graphs are constructed using the local concept of edges. We give necessary and sufficient conditions for each theory to be captured by the other. We find that the necessary and sufficient condition for IP theory to be captured (...) by MG theory, which we call SE, excludes relevant game situations. Hence, we conclude that IP theory remains a vital tool and cannot be replaced by MG theory. (shrink)

The mathematical field of graph theory has recently been used to provide counterexamples to the Principle of the Identity of Indiscernibles. In response to this, it has been argued that appeal to relations between graphs allows the Principle to survive the counterexamples. In this paper, I aim to show why that proposal does not succeed.

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left + o\left}.$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our (...) structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left$ to $o\left$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws. (shrink)

Any set x is uniquely specified by the graph of the membership relation on the set obtained by adjoining x to the transitive closure of x. Thus any operation on sets can be looked at as an operation on these graphs. We look at the operations of ordinal arithmetic of sets in this light. This turns out to be simplest for a modified ordinal arithmetic based on the Zermelo ordinals, instead of the usual von Neumann ordinals. In this arithmetic, (...) addition of sets corresponds to concatenating graphs, and multiplication corresponds to replacing each edge of a graph by a copy of another graph. Characterizations for the von Neumann case are also given. (shrink)

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL0 over RCA0 Every locally k-colorable graph is m-colorable.

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly (...) stems from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

An introduction to writing proofs, presented through compelling mathematical statements with interesting elementary proofs. This book offers an introduction to the art and craft of proof-writing. The author, a leading research mathematician, presents a series of engaging and compelling mathematical statements with interesting elementary proofs. These proofs capture a wide range of topics, including number theory, combinatorics, graph theory, the theory of games, geometry, infinity, order theory, and real analysis. The goal is to show students and aspiring mathematicians how (...) to write proofs with elegance and precision. (shrink)

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in Ehrenfeucht-Fraïssé type (...) games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (shrink)

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier $\sf Q$ in ${\rm FO}({\vec Q}_k)$ , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two ${\rm FO}({\vec Q}_1)$ -equivalent models with certain additional structure, yields a pair of ${\rm FO}({\vec Q}_k)$ -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity (...) and planarity. (shrink)

Discrete choice experiments (DCE) are often used to elicit preferences, for instance, in health preference research. However, DCEs only provide binary responses, whilst real-life choices are made with varying degrees of conviction. We aimed to verify whether eliciting self-reported convictions on a 0–100 scale adds meaningful information to the binary choice. Eighty three respondents stated their preferences for health states using DCE and the time trade-off method (TTO). In TTO, utility ranges were also elicited to account for preference imprecision. (...) We verified the properties of the conviction across three areas: (1) response to various choice task modifications (e.g. dominance, increase in complexity, distance from the status quo) and association with rationality violations (e.g. intransitivity); (2) association with test–retest results; (3) relation to the utility difference and imprecision estimated in TTO. Regarding (1), conviction increased in choice tasks with lower complexity, larger relative attractiveness, and lower distance to the status quo. Regarding (2), choices made with above-median conviction were sustained in 90% of the cases, compared to 68% for below-median conviction. Regarding (3), the conviction increases with utility difference and it decreases with utility imprecision; overconfidence seems to prevail: non-zero conviction is reported even for identical utilities. Self-reported conviction in DCE is associated in an intuitive way with the observed choices. It may, therefore, be useful in explaining or predicting behaviour or bridging the gap between the results of various elicitation tasks. (shrink)

Every set can been thought of as a directed graph whose edge relation is ∈. We show that many natural examples of directed graphs of this kind are indivisible: for every infinite κ, for every indecomposable λ, and every countable model of set theory. All of the countable digraphs we consider are orientations of the countable random graph. In this way we find indivisible well‐founded orientations of the random graph that are distinct up to isomorphism, and (...) ℵ1 that are distinct up to siblinghood. (shrink)

For digraphs G, we write V(G) for the set of all vertices of G, and E(G) for the set of all edges of G. A digraph on a set E is a digraph G where V(G) = E.

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi-gated.

Product acceptance determination using similarity measure index by neutrosophic statistics / Muhammad Aslam and Rehan Ahmed Khan Sherwani -- New concepts of strongly edge irregular interval-valued neutrosophic graphs / A.A.Talebi, Hossein Rashmanlou and Masoomeh Ghasemi -- The link between neutrosophy and learning : through the related concepts of representation and compression / Philippe Schweizer -- Neutrosophic soft cubic M-subalgebras of B-algebras / Mohsin Khalid, Neha Andaleeb Khalid and Hasan Khalid -- Alpha, beta and gamma product of neutrosophic graphs / (...) Nasir Shah, Said Broumi, Abdul Raheem and Tahir Imran -- Neutrosophic cubic normal ideal and neutrosophic cubic closed normal ideal of PS-algebra / Mohsin Khalid, Hasan khalid and Neha Andaleeb Khalid -- Neutrosophic multisets : an overview / Vakkas Uluçay -- Neutrosophy as a model for knowledge : the influence of representative models on thinking / Philippe Schweizer -- When neutrosophic theory meets three-way decisions / Rui Ren, Chao Zhang and Deyu Li -- Neutrosophic economic order quantity model with more than one price breaks / R. Surya, M. Mullai and G. Madhan Kumar -- General non-square systems of linear equations in single-valued triangular neutrosophic number environment / S.A. Edalatpanah -- Hesitant neutrosophic soft set relations / Abhijit Saha -- Computer application of neutrosophic set operations / S. Saranya, M. Vigneshwaran, Said Broumi -- Triangular bipolar neutrosophic based transportation problem / Avishek Chakraborty -- Studying neutrosophic variables / Rafif Alhabib and Ahmad Salama -- Decision making for logistics center location selection in trapezoidal neutrosophic environment / Kalyan Mondal and Surapati Pramanik -- Weighted similarity measure and decision making model for clinical application of single valued neutrosophic set / R.Binu and P. Isaac -- Rough neutrosophic set : an overview / Surapati Pramanik -- Some new concepts on normalized SVTN-number and multiple criteria decision making / İrfan Deli and Emel Kırmızı Öztürk. (shrink)

This “fun, brain-twisting book... will make you think” as it explores more than 75 paradoxes in mathematics, philosophy, physics, and the social sciences (Sean Carroll, New York Times–bestselling author of Something Deeply Hidden) Paradox is a sophisticated kind of magic trick. A magician’s purpose is to create the appearance of impossibility, to pull a rabbit from an empty hat. Yet paradox doesn’t require tangibles, like rabbits or hats. Paradox works in the abstract, with words and concepts and symbols, to create (...) the illusion of contradiction. There are no contradictions in reality, but there can appear to be. In Sleight of Mind, Matt Cook and a few collaborators dive deeply into more than 75 paradoxes in mathematics, physics, philosophy, and the social sciences. As each paradox is discussed and resolved, Cook helps readers discover the meaning of knowledge and the proper formation of concepts—and how reason can dispel the illusion of contradiction. The journey begins with “a most ingenious paradox” from Gilbert and Sullivan’s Pirates of Penzance. Readers will then travel from Ancient Greece to cutting-edge laboratories, encounter infinity and its different sizes, and discover mathematical impossibilities inherent in elections. They will tackle conundrums in probability, induction, geometry, and game theory; perform “supertasks”; build apparent perpetual motion machines; meet twins living in different millennia; explore the strange quantum world—and much more. (shrink)

Over the past two decades, gamblers have begun taking mathematics into account more seriously than ever before. While probability theory is the only rigorous theory modeling the uncertainty, even though in idealized conditions, numerical probabilities are viewed not only as mere mathematical information, but also as a decision-making criterion, especially in gambling. This book presents the mathematics underlying the major games of chance and provides a precise account of the odds associated with all gaming events. It begins by explaining in (...) simple terms the meaning of the concept of probability for the layman and goes on to become an enlightening journey through the mathematics of chance, randomness and risk. It then continues with the basics of discrete probability, combinatorics and counting arguments for those interested in the supporting mathematics. These mathematic sections may be skipped by readers who do not have a minimal background in mathematics; these readers can skip directly to the Guide to Numerical Results to pick the odds and recommendations they need for the desired gaming situation. Doing so is possible due to the organization of that chapter, in which the results are listed at the end of each section, mostly in the form of tables. The chapter titled The Mathematics of Games of Chance presents these games not only as a good application field for probability theory, but also in terms of human actions where probability-based strategies can be tried to achieve favorable results. Through suggestive examples, the reader can see what are the experiments, events and probability fields in games of chance and how probability calculus works there. The main portion of this work is a collection of probability results for each type of game. Each game s section is packed with formulas and tables. Each section also contains a description of the game, a classification of the gaming events and the applicable probability calculations. The primary goal of this work is to allow the reader to quickly find the odds for a specific gaming situation, in order to improve his or her betting/gaming decisions. Every type of gaming event is tabulated in a logical, consistent and comprehensive manner. The complete methodology and complete or partial calculations are shown to teach players how to calculate probability for any situation, for every stage of the game for any game. Here, readers can find the real odds, returned by precise mathematical formulas and not by partial simulations that most software uses. Collections of odds are presented, as well as strategic recommendations based on those odds, where necessary, for each type of gaming situation. The book contains much new and original material that has not been published previously and provides great coverage of probabilities for the following games of chance: Dice, Slots, Roulette, Baccarat, Blackjack, Texas Hold em Poker, Lottery and Sport Bets. Most of games of chance are predisposed to probability-based decisions. This is why the approach is not an exclusively statistical one, but analytical: every gaming event is taken as an individual applied probability problem to solve. A special chapter defines the probability-based strategy and mathematically shows why such strategy is theoretically optimal.". (shrink)

The paper shows how the Bohmian approach to quantum physics can be applied to develop a clear and coherent ontology of non-perturbative quantum gravity. We suggest retaining discrete objects as the primitive ontology also when it comes to a quantum theory of space-time and therefore focus on loop quantum gravity. We conceive atoms of space, represented in terms of nodes linked by edges in a graph, as the primitive ontology of the theory and show how a non-local law (...) in which a universal and stationary wave-function figures can provide an order of configurations of such atoms of space such that the classical space-time of general relativity is approximated. Although there is as yet no fully worked out physical theory of quantum gravity, we regard the Bohmian approach as setting up a standard that proposals for a serious ontology in this field should meet and as opening up a route for fruitful physical and mathematical investigations. (shrink)

We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.

We investigate the Ramsey theory of continuous graph-structures on complete, separable metric spaces and apply the results to the problem of covering a plane by functions. Let the homogeneity number[Formula: see text] of a pair-coloring c:[X]2→2 be the number of c-homogeneous subsets of X needed to cover X. We isolate two continuous pair-colorings on the Cantor space 2ω, c min and c max, which satisfy [Formula: see text] and prove: Theorem. For every Polish space X and every continuous (...) pair-coloringc:[X]2→2with[Formula: see text], [Formula: see text] There is a model of set theory in which[Formula: see text]and[Formula: see text]. The consistency of [Formula: see text] and of [Formula: see text] follows from [20]. We prove that [Formula: see text] is equal to the covering number of 2 by graphs of Lipschitz functions and their reflections on the diagonal. An iteration of an optimal forcing notion associated to c min gives: Theorem. There is a model of set theory in which ℝ2 is coverable byℵ1graphs and reflections of graphs of continuous real functions; ℝ2 is not coverable byℵ1graphs and reflections of graphs of Lipschitz real functions. Figure 1.1 in the introduction summarizes the ZFC results in Part I of the paper. The independence results in Part II show that any two rows in Fig. 1.1 can be separated if one excludes [Formula: see text] from row. (shrink)

Ethics of Health Care: A Guide for Clinical Practice, 3E is designed to guide health care students and practitioners through a wide variety of areas involving ethical controversies. It provides a background in value development and ethical theories, including numerous real-life examples to stimulate discussion and thought.

Context: the position of pure and applied mathematics in the epistemic conflict between realism and relativism. Problem: To investigate the change in the status of mathematical knowledge over historical time: specifically, the shift from a realist epistemology to a relativist epistemology. Method: Two examples are discussed: geometry and number theory. It is demonstrated how the initially realist epistemic framework – with mathematics situated in a platonic ideal reality from where it governs our physical world – became untenable, with the advent (...) of non-Euclidean geometry and the increasing abstraction of the number concept. Results: Radical constructivism offers an alternative relativist epistemology, where mathematical knowledge is constructed by the individual knower in a context of an axiomatic base and subject items chosen at her discretion, for the purpose of modelling some part of her personal experiential world. Thus it can be expedient to view the practice of mathematics as a game, played by mathematicians according to agreed-upon rules. Constructivist content: The role played by constructivism in the formulation of mathematics is discussed. This is illustrated by the historical transition from a classical (platonic) view of mathematics, as having an objective existence of its own in the “realm of ideal forms,” to the now widely accepted modern view where one has a wide freedom to construct mathematical theories to model various parts of one’s experiential world. (shrink)

We construct a collection of new topological Ramsey spaces of trees. It is based on the Halpern-Läuchli theorem, but different from the Milliken space of strong subtrees. We give an example of its application by proving a partition theorem for profinite graphs.

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...) model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

Since then we have been engaged in the development of such results of greater relevance to mathematical practice. In January, 1997 we presented some new results of this kind involving what we call “jump free” classes of finite functions. This Jump Free Theorem is treated in section 2.