Joel David Hamkins | mathematics and philosophy of the infinite
Time 2021-11-21 11:06:18Web Name: Joel David Hamkins | mathematics and philosophy of the infinite
WebSite: http://jdh.hamkins.org
ID:243148
Keywords:
Hamkins,mathematics,Joel,David,and,the,infinite,philosophy,Description:
keywords: description:I have recently become interested in the hierarchy of relative constructibility in geometry (see the discussion on my Twitter thread). From a given collection of points in the plane, we may proceed to construct other points using the classical tools of straightedge and compass. This induces a hierarchy of relative constructiblity, namely, for any two sets of points $X$ and $Y$ in the plane, we may say that $X$ is constructible from $Y$, written as $$X\trianglelefteq Y$$ if for every point $A\in X$, there is a construction procedure using only straightedge and compass proceeding from points in $Y$ and constructing $A$. And so we are faced with a hierarchy of constructibility.
Perhaps one might ask immediately whether this is genuinely a hierarchy. A central case occurs with pairs of points, since one often proceeds in geometry with the idea of a unit segment having already been fixed.
Question 1. Given two distinct points A and B, suppose that distinct points C and D are constructible by straightedge and compass. Can we go back? That is, must A and B both be constructible from C and D?
The answer, surprisingly, is Yes! This is a sense in which the relative constructibility notion is an equivalence relation rather than a hierarchy, since it shows that if AB can construct CD, than it is also true conversely. Since constructibility is also transitive, this shows that the relative constructibility is an equivalence relation on pairs of points in the plane.
Before addressing the question, let me first dispense with a distracting line of reasoning that suggests a wrong answer to this question. Suppose that we have a segment AB of length $\sqrt[3]2$, a nonconstructible number. Since the constructible numbers are closed under multiplication, this might suggest that from AB we can construct a segment of length 2, and therefore also construct a segment CD of length 1. But from a segment of length 1, we can never construct a segment of length $\sqrt[3]2$, because the duplication of the cube is impossible. So this would suggest a negative answer to the question. Is it right?
But no, this distracting counter-argument is not correct. The reason is that although the constructible numbers are indeed closed under multiplication, the construction methods requires the consultation of a fixed unit segment. That is, to prove that from a segment of length $a$ and a segment of length $b$ one can construct a segment of length $ab$, we require the use of fixed unit segment of length $1$. Indeed, it will follow from our analysis here that one cannot omit this consultation of a unit segment from the construction—we cannot in general construct the cube of a segment just from the segment itself.
So let me prove the answer to question 1 is positive. Suppose that from distinct points AB we can construct distinct points CD. Performing excactly the same construction process again, but proceeding from points CD as input, we construct points EF. From points CD we can see how CD are related to EF, forming a quadrilateral CDFE.
The point is that we may now construct the points A and B from C and D by simply inverting this similarity. (This was also observed by user @ZenoRogue on Twitter.) Namely, the two quadrilaterals ABDC and CDFE are similar, and so have all the same angles. So the line AC is constructible from CD by the angle ACD, which is the same as CEF, and the distance AC is scaled from CE by the same factor that CD is related to EF. So from CD we can construct this similar quadrilateral, and thereby construct both A and B.
Question 2. Given three distinct points forming a triangle ABC, suppose that we can construct triangle DEF by straightedge and compass. Can we go back? That is, must A,B, and C be constructible from D,E,F?
The question is of course similar to question 1, which had a positive answer. Nevertheless, the answer here is negative. The reason is that the original idea we had with question 1 concerning $\sqrt[3]2$ now works here to refute question 2. Namely, let ABC be a right triangle where AB has length 1 but AC has length $\sqrt[3]2$.
From the triangle ABC, we may easily construct the triangle ABD, where AD has length 1, since in fact the point D is constructible from the segment AB alone. But from ABD, which is a right triangle with both legs of length 1, we shall be unable to construct the number $\sqrt[3]2$, and consequently unable to construct the point C. So although ABD is constructible from ABC, the point C is not constructible from points ABD. This is therefore a counterexample to question 2, which therefore must be answered in the negative.
Another argument, offered by Ed Wagstaff, is that from an angle trisection we can construct the original angle, but we cant necessarily construct the trisection from the original angle.
Finally, I should like to understand the nature of the relative hierarchy of constructibility better. $$X\trianglelefteq Y$$ What is the nature of relative constructibility of sets of points in the plane? For example, one question I didnt know how to answer at first is the following:
Question 3. Is the hierarchy of relative constructibility a dense order? That is, if the set $X$ is constructible from $Y$ but not conversely, must there be a set of points $Z$ strictly in between? $$X\lhd Y\quad\implies\quad\exists Z\quad X\lhd Z\lhd Y?$$
In an exchange on Twitter with David Madore, I had thought that we answered the question negatively, but now I am not at all sure of that argument (and thanks to Gabin for the comments below!), and so I have deleted the wrong argument here. Question 3 seems currently to be open.
Share:MoreThis will be talk for the workshop Philosophy of Set Theory held at the University of Konstanz, 3 – 4 December 2021 — in person!
Update: Unfortunately, the workshop has been cancelled (perhaps postponed to next year) in light of the Covid resurgence.
Abstract. I shall analyze the roles and interaction of reflection and urelements in second-order set theory. Second-order reflection already exhibits large cardinal strength even without urelements, but recent work shows that in the presence of abundant urelements, second-order reflection is considerably stronger than might have been expected—at the level of supercompact cardinals. This is joint work with Bokai Yao (Notre Dame).
Share:MoreThis will be a talk 11 November 2021 for the Oslo Seminar in Mathematical Logic, meeting online via Zoom at 10:15am CET (9:15am GMT) at Zoom: 671 7500 0197
Abstract. I shall give an introduction to the logic of infinite games, including the theory of transfinite game values, using the case of infinite draughts as a principal illustrative instance. Infinite draughts, also known as infinite checkers, is played like the finite game, but on an infinite checkerboard stretching without end in all four directions. In recent joint work with Davide Leonessi, we proved that every countable ordinal arises as the game value of a position in infinite draughts. Thus, there are positions from which Red has a winning strategy enabling her to win always in finitely many moves, but the length of play can be completely controlled by Black in a manner as though counting down from a given countable ordinal. This result is optimal for games having countably many options at each move—in short, the omega one of infinite draughts is true omega one.
Infinite-draughts-Oslo-2021DownloadShare:MoreA joint paper with Davide Leonessi, in which we prove that every countable ordinal arises as the game value of a position in infinite draughts, and this result is optimal for games having countably many options at each move. In short, the omega one of infinite draughts is true omega one.
J. D. Hamkins and D. Leonessi, Transfinite game values in infinite draughts, Mathematics arXiv, 2021.
[Bibtex]
@ARTICLE{HamkinsLeonessi:Transfinite-game-values-in-infinite-draughts,author = {Joel David Hamkins and Davide Leonessi},title = {Transfinite game values in infinite draughts},journal = {Mathematics arXiv},year = {2021},volume = {},number = {},pages = {},month = {},note = {Under review},abstract = {},keywords = {under-review},source = {},doi = {},eprint = {2111.02053},archivePrefix = {arXiv},primaryClass = {math.LO},url = {},}Download the paper at arXiv:2111.02053
Abstract. Infinite draughts, or checkers, is played just like the finite game, but on an infinite checkerboard extending without bound in all four directions. We prove that every countable ordinal arises as the game value of a position in infinite draughts. Thus, there are positions from which Red has a winning strategy enabling her to win always in finitely many moves, but the length of play can be completely controlled by Black in a manner as though counting down from a given countable ordinal.
A. Berarducci, A. Fornasiero, and J. D. Hamkins, Is the twin prime conjecture independent of Peano Arithmetic?, Mathematics arXiv, 2021.
[Bibtex]
@ARTICLE{BerarducciFornasieroHamkins:Is-the-twin-prime-conjecture-independent-of-PA,author = {Alessandro Berarducci and Antongiulio Fornasiero and Joel David Hamkins},title = {Is the twin prime conjecture independent of Peano Arithmetic?},journal = {Mathematics arXiv},year = {2021},volume = {},number = {},pages = {},month = {},note = {Under review},abstract = {},keywords = {under-review},source = {},doi = {},eprint = {2110.08640},archivePrefix = {arXiv},primaryClass = {math.LO},url = {http://jdh.hamkins.org/is-the-twin-prime-conjecture-independent-of-peano-arithmetic/},}Download the article at arXiv:2110.08640
Abstract. We show that there is an arithmetical formula $\varphi$ such that ZF proves that $\varphi$ is independent of PA and yet, unlike other arithmetical independent statements, the truth value of $\varphi$ cannot at present be established in ZF or in any other trusted metatheory. In fact we can choose an example of such a formula $\varphi$ such that ZF proves that $\varphi$ is equivalent to the twin prime conjecture. We conclude with a discussion of notion of trustworthy theory and a sharper version of the result.
This work grows in part out of an answer I posted on MathOverflow in 2012.
Share:MoreI shall be interviewed by Nathan Ormond for a discussion on Freges philosophy of mathematics for his YouTube channel, Digital Gnosis, on 10 December 2021 at 4pm.
The interview will include a public comment and question answer session, so please join us to participate!
Share:MoreMr. Davide Leonessi successfully defended his dissertation for the Masters of Science degree in Mathematics and Foundations of Computer Science, entitled Transfinite game values in infinite games, on 15 September 2021. Davide earned a distinction for his thesis, an outstanding result.
Davide Leonessi | Google scholar | Dissertation | arXiv
Abstract. The object of this study are countably infinite games with perfect information that allow players to choose among arbitrarily many moves in a turn; in particular, we focus on the generalisations of the finite board games of Hex and Draughts.
In Chapter 1 we develop the theory of transfinite ordinal game values for open infinite games following [Evans-Hamkins 2014], and we focus on the properties of the omega one, that is the supremum of the possible game values, of classes of open games; we moreover design the class of climbing-through-$T$ games as a tool to study the omega one of given game classes.
The original contributions of this research are presented in the following two chapters.
In Chapter 2 we prove classical results about finite Hex and present Infinite Hex, a well-defined infinite generalisation of Hex.
We then introduce the class of stone-placing games, which captures the key features of Infinite Hex and further generalises the class of positional games already studied in the literature within the finite setting of Combinatorial Game Theory.
The main result of this research is the characterization of open stone-placing games in terms of the property of essential locality, which leads to the conclusion that the omega one of any class of open stone-placing games is at most $\omega$. In particular, we obtain that the class of open games of Infinite Hex has the smallest infinite omega one, that is $\omega_1^{\rm Hex}=\omega$.
In Chapter 3 we show a dual result; we define the class of games of Infinite Draughts and explicitly construct open games of arbitrarily high game value with the tools of Chapter 1, concluding that the omega one of the class of open games of Infinite Draughts is as high as possible, that is $\omega_1^{\rm Draughts}=\omega_1$.
The full dissertation is available:
Transfinite-game-values-in-infinite-gamesDownloadShare:MoreThis will be a talk for the Oxford Seminar in the Philosophy of Mathematics, 1 November, 4:30-6:30 GMT. The talk will be held on Zoom (contact the seminar organizers for the Zoom link).
Abstract. The standard treatment of sets and classes in Zermelo-Fraenkel set theory instantiates in many respects the Fregean foundational distinction between objects and concepts, for in set theory we commonly take the sets as objects to be considered under the guise of diverse concepts, the definable classes, each serving as a predicate on that domain of individuals. Although it is often asserted that there can be no association of classes with objects in a way that fulfills Freges Basic Law V, nevertheless, in the ZF framework I have described, it turns out that Basic Law V does hold, and provably so, along with other various Fregean abstraction principles. These principles are consequences of Zermelo-Fraenkel ZF set theory in the context of all its definable classes. Namely, there is an injective mapping from classes to objects, definable in senses I shall explain, associating every first-order parametrically definable class $F$ with a set object $\varepsilon F$, in such a way that Basic Law V is fulfilled: $$\varepsilon F =\varepsilon G\iff\forall x\ (Fx\leftrightarrow Gx).$$ Russells elementary refutation of the general comprehension axiom, therefore, is improperly described as a refutation of Basic Law V itself, but rather refutes Basic Law V only when augmented with powerful class comprehension principles going strictly beyond ZF. The main result leads also to a proof of Tarskis theorem on the nondefinability of truth as a corollary to Russells argument.
Share:MoreWhat a pleasure it was to be interviewed by Evelyn Lamb and Kevin Knudson for their wonderful podcast series, My Favorite Theorem, available on Apple, Spotify, and any number of other aggregators.
I had a chance to talk about one my most favorite theorems, the fundamental theorem of finite games.
Theorem.(Zermelo 1913) In any two-player finite game of perfect information, one of the players has a winning strategy, or both players have drawing strategies.
Listen to the podcast here: My Favorite Theorem. A transcript is also available.
Philosophy of Mathematics, Exam Paper 122, Oxford University
Wednesdays 12-1 during term, Radcliffe Humanities Lecture Room
Joel David Hamkins, Professor of Logic
This series of self-contained lectures on the philosophy of mathematics is intended for students preparing for Oxford Philosophy exam paper 122. All interested parties from the Oxford University community, however, are welcome to attend, whether or not they intend to sit the exam. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light. Lectures will loosely follow the instructors book Lectures on the Philosophy of Mathematics (MIT Press 2021), with supplemental suggested readings each week.
Previously recorded lectures from last year are available on the lecturers YouTube channel, below.
In light of the earlier lectures being available online, the plan for the lectures this year will be to feel somewhat more free occasionally to focus on narrower topics, and also to entertain at times a discussion format. Therefore kindly bring questions and well-thought-out opinions to the lecture.
The lectures this term will be held in person. The lecturer requests that students be vaccinated, wear masks, and observe social distancing as practicable. If this proves impossible or unsustainable, we shall regretably revert to online lectures on short notice.
Lecture 1. Numbers
Numbers are perhaps the essential mathematical idea, but what are numbers? There are many kinds of numbersnatural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and moreand these number systems provide a fruitful background for classical arguments on incommensurability and transcendentality, while setting the stage for discussions of platonism, logicism, the nature of abstraction, the significance of categoricity, and structuralism.
Lecture 2. Rigour
Let us consider the problem of mathematical rigor in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to the epsilon-delta limit concept, which secured a more rigorous foundation while also enlarging our conceptual vocabulary, enabling us to express more refined notions, such as uniform continuity, equicontinuity, and uniform convergence. Nonstandard analysis resurrected the infinitesimals on a more secure foundation, providing a parallel development of the subject. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devils staircase, space-filling curves, and the Conway base 13 function. Finally, does the indispensability of mathematics for science ground mathematical truth? Fictionalism puts this in question.
Lecture 3. Infinity
We shall follow the allegory of Hilberts hotel and the paradox of Galileo to theequinumerosity relation and the notion of countability. Cantors diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and nonconstructive proof. Zenos paradox highlights classical ideas on potential versus actual infinity. Furthermore, we shall count into the transfinite ordinals.
Lecture 4. Geometry
Classical Euclidean geometry is the archetype of a mathematical deductive process. Yet the impossibility of certain constructions by straightedge and compass, such as doubling the cube, trisecting the angle, or squaring the circle, hints at geometric realms beyond Euclid. The rise of non-Euclidean geometry, especially in light of scientific theories and observations suggesting that physical reality is not Euclidean, challenges previous accounts of what geometry is about. New formalizations, such as those of David Hilbert and Alfred Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarskis decision procedure points to a tantalizing possibility of automation in geometrical reasoning.
Lecture 5. Proof
What is proof? What is the relation between proof and truth? Is every mathematical truth true for a reason? After clarifying the distinction between syntax and semantics and discussing various views on the nature of proof, including proof-as-dialogue, we shall consider the nature of formal proof. We shall highlight the importance of soundness, completeness, and verifiability in any formal proof system, outlining the central ideas used in proving the completeness theorem. The compactness property distills the finiteness of proofs into an independent, purely semantic consequence. Computer-verified proof promises increasing significance; its role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakening the logical rules.
Lecture 6. Computability
What is computability? Kurt Gödel defined a robust class of computable functions, the primitive recursive functions, and yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Alan Turings machine concept of computability, growing out of a careful philosophical analysis of the nature of human computability, proved robust and laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing had the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P versus NP problem standing in the background of nearly every serious issue in theoretical computer science.
Lecture 7. Incompleteness
David Hilbert sought to secure the consistency of higher mathematics by finitary reasoning about the formalism underlying it, but his program was dashed by Gödels incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, self-reference, and definability, showing senses in which we cannot complete mathematics. After this, we shall discuss the second incompleteness theorem, the Rosser variation, and Tarskis theorem on the nondefinability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength rising above every foundational mathematical theory.
Lecture 8. Set Theory
We shall discuss the emergence of set theory as a foundation of mathematics. Cantor founded the subject with key set-theoretic insights, but Freges formal theory was naive, refuted by the Russell paradox. Zermelos set theory, in contrast, grew ultimately into the successful contemporary theory, founded upon a cumulative conception of the set-theoretic universe. Set theory was simultaneously a new mathematical subject, with its own motivating questions and tools, but it also was a new foundational theory with a capacity to represent essentially arbitrary abstract mathematical structure. Sophisticated technical developments, including in particular, the forcing method and discoveries in the large cardinal hierarchy, led to a necessary engagement with deep philosophical concerns, such as the criteria by which one adopts new mathematical axioms and set-theoretic pluralism.
Share:MoreIn this insightful and remarkable work, Professor Novaes defends and explores at length the philosophical thesis that mathematical proof and deduction generally has a fundamentally dialogical nature, proceeding in a back-and-forth dialogue between two semi-adversarial but collaborative actors, the Prover and the Skeptic, who together aim to find mathematical insight. This view of proof-as-dialogue, she argues, carries explanatory power for the philosophy of mathematical practice, explaining diverse aspects of proof-writing, refereeing, and more, including the multifaceted roles of proof, including proof as verification, proof as certification, proof for communication and persuasion, proof as explanation, and proof as a driver of mathematical innovation.
In extensive, refined scholarly work, Novaes explores the historical and intellectual roots of the dialogical perspective on deduction, tracing the idea from ancient times through medieval philosophy and into the present day, including case studies of current mathematical developments, such as Mochizuki’s claimed proof of the abc conjecture, as well as recent psychological experiments on the role of group reasoning in resolving certain well-known disappointing failures of rationality, such as in the Wason card experiment. Truly fascinating.
On the basis of her work, I have nominated Novaes for the Lakatos Award (given annually for an outstanding contribution to the philosophy of science, widely interpreted, in the form of a book published in English during the current year or the previous five years). Lakatos himself, of course, was a friend of dialogical mathematics—his famous Proofs and Refutations proceeds after all in a dialogue between mathematicians of different philosophical outlooks. Novaes engages with Lakatos’s work explicitly, pointing out the obvious parallels, but also highlighting important differences between her Prover/Skeptic dialogical account and the kind of proof dialogues appearing in Proofs and Refutations. In light of this connection with Lakatos, I would find it especially fitting for Novaes to win the Lakatos Award.
My review on GoodReads
Share:MoreAnyone can learn to count in the ordinals, even a child, and so let us learn how to count to $\omega^2$, the first compound limit ordinal.
The large-format poster is available:
Some close-up views:
I would like to thank the many people who had made helpful suggestions concerning my poster, including Andrej Bauer and especially Saul Schleimer, who offered many detailed suggestions.
Share:MoreI was interviewed 26 August 2021 by mathematician Daniel Rubin on his show, and we had a lively, wideranging discussion spanning mathematics, infinity, and the philosophy of mathematics. Please enjoy!
Contents
0:00 Intro
2:11 Joels background. Interaction between math and philosophy
9:04 Joels work; infinite chess.
14:45 Infinite ordinals
22:27 The Cantor-Bendixson process
29:41 Uncountable ordinals
32:10 First order vs. second order theories
41:16 Non-standard analysis
46:57 The ZFC axioms and well-ordering of the reals
58:11 Showing independence of statements. Models and forcing.
1:04:38 Sets, classes, and categories
1:19:22 Is there one true set theory? Are projective sets Lebesgue measurable?
1:30:20 What does set theory look like if certain axioms are rejected?
1:36:06 How to judge philosophical positions about math
1:42:01 Concrete math where set theory becomes relevant. Tarski-Seidenberg on positive polynomials.
1:48:48 Goodstein sequences and the use of infinite ordinals
1:58:43 The state of set theory today
2:01:41 Joels recent books
Go check out the other episodes on Daniels channel!
Share:MoreDid you know that you can add and multiply orders? For any two order structures $A$ and $B$, we can form the ordered sum $A+B$ and ordered product $A\otimes B$, and other natural operations, such as the disjoint sum $A\sqcup B$, which make altogether an arithmetic of orders. We combine orders with these operations to make new orders, often with interesting properties. Let us explore the resulting algebra of orders!
$\newcommand\Z{\mathbb{Z}}\newcommand\N{\mathbb{N}}\newcommand\Q{\mathbb{Q}}\newcommand\P{\mathbb{P}}\newcommand\iso{\cong}\newcommand\of{\subseteq}$
One of the most basic operations that we can use to combine two orders is the disjoint sum operation $A\sqcup B$. This is the order resulting from placing a copy of $A$ adjacent to a copy of $B$, side-by-side, forming a combined order with no instances of the order relation between the two parts. If $A$ is the orange $\vee$-shaped order here and $B$ is the yellow linear order, for example, then $A\sqcup B$ is the combined order with all five nodes.
Another kind of addition is the ordered sum of two orders $A+B$, which is obtained by placing a copy of $B$ above a copy of $A$, as indicated here by adding the orange copy of $A$ and the yellow copy of $B$. Also shown is the sum $B+A$, with the summands reversed, so that we take $B$ below and $A$ on top. It is easy to check that the ordered sum of two orders is an order. One notices immediately, of course, that the resulting ordered sums $A+B$ and $B+A$ are not the same! The order $A+B$ has a greatest element, whereas $B+A$ has two maximal elements. So the ordered sum operation on orders is not commutative. Nevertheless, we shall still call it addition. The operation, which has many useful and interesting features, goes back at least to the 19th century with Cantor, who defined the addition of well orders this way.
In order to illustrate further examples, I have assembled here an addition table for several simple finite orders. The choices for $A$ appear down the left side and those for $B$ at the top, with the corresponding sum $A+B$ displayed in each cell accordingly.
We can combine the two order addition operations, forming a variety of other orders this way.
The reader is encouraged to explore further how to add various finite orders using these two forms of addition. What is the smallest order that you cannot generate from $1$ using $+$ and $\sqcup$? Please answer in the comments.
We can also add infinite orders. Displayed here, for example, is the order $\N+(1\sqcup 1)$, the natural numbers wearing two yellow caps. The two yellow nodes at the top form a copy of $1\sqcup 1$, while the natural numbers are the orange nodes below. Every natural number (yes, all infinitely many of them) is below each of the two nodes at the top, which are incomparable to each other. Notice that even though we have Hasse diagrams for each summand order here, there can be no minimal Hasse diagram for the sum, because any particular line from a natural number to the top would be implied via transitivity from higher such lines, and we would need such lines, since they are not implied by the lower lines. So there is no minimal Hasse diagram.
This order happens to illustrate what is called an exact pair, which occurs in an order when a pair of incomparable nodes bounds a chain below, with the property that any node below both members of the pair is below something in the chain. This phenomenon occurs in sometimes unexpected contextsany countable chain in the hierarchy of Turing degrees in computability theory, for example, admits an exact pair.
Let us turn now to multiplication. The ordered product $A\otimes B$ is the order resulting from having $B$ many copies of $A$. That is, we replace each node of $B$ with an entire copy of the $A$ order. Within each of these copies of $A$, the order relation is just as in $A$, but the order relation between nodes in different copies of $A$, we follow the $B$ relation. It is not difficult to check that indeed this is an order relation. We can illustrate here with the same two orders we had earlier.
In forming the ordered product $A\otimes B$, in the center here, we take the two yellow nodes of $B$, shown greatly enlarged in the background, and replace them with copies of $A$. So we have ultimately two copies of $A$, one atop the other, just as $B$ has two nodes, one atop the other. We have added the order relations between the lower copy of $A$ and the upper copy, because in $B$ the lower node is related to the upper node. The order $A\otimes B$ consists only of the six orange nodesthe large highlighted yellow nodes of $B$ here serve merely as a helpful indication of how the product is formed and are not in any way part of the product order $A\otimes B$.
Similarly, with $B\otimes A$, at the right, we have the three enlarged orange nodes of $B$ in the background, which have each been replaced with copies of $A$. The nodes of each of the lower copies of $A$ are related to the nodes in the top copy, because in $B$ the two lower nodes are related to the upper node.
I have assembled a small multiplication table here for some simple finite orders.
So far we have given an informal account of how to add and multiply ordered ordered structures. So let us briefly be a little more precise and formal with these matters.
In fact, when it comes to addition, there is a slightly irritating matter in defining what the sums $A\sqcup B$ and $A+B$ are exactly. Specifically, what are the domains? We would like to conceive of the domains of $A\sqcup B$ and $A+B$ simply as the union the domains of $A$ and $B$wed like just to throw the two domains together and form the sums order using that combined domain, placing $A$ on the $A$ part and $B$ on the $B$ part (and adding relations from the $A$ to the $B$ part for $A+B$). Indeed, this works fine when the domains of $A$ and $B$ are disjoint, that is, if they have no points in common. But what if the domains of $A$ and $B$ overlap? In this case, we cant seem to use the union in this straightforward manner. In general, we must disjointify the domainswe take copies of $A$ and $B$, if necessary, on domains that are disjoint, so that we can form the sums $A\sqcup B$ and $A+B$ on the union of those nonoverlapping domains.
What do we mean precisely by taking a copy of an ordered structure $A$? This way of talking in mathematics partakes in the philosophy of structuralism. We only care about our mathematical structures up to isomorphism, after all, and so it doesnt matter which isomorphic copies of $A$ and $B$ we use; the resulting order structures $A\sqcup B$ will be isomorphic, and similarly for $A+B$. In this sense, we are defining the sum orders only up to isomorphism.
Nevertheless, we can be definite about it, if only to verify that indeed there are copies of $A$ and $B$ available with disjoint domains. So let us construct a set-theoretically specific copy of $A$, replacing each individual $a$ in the domain of $A$ with $(a,\text{orange})$, for example, and replacing the elements $b$ in the domain of $B$ with $(b,\text{yellow})$. If orange is a specific object distinct from yellow, then these new domains will have no points in common, and we can form the disjoint sum $A\sqcup B$ by using the union of these new domains, placing the $A$ order on the orange objects and the $B$ order on the yellow objects.
Although one can use this specific disjointifying construction to define what $A\sqcup B$ and $A+B$ mean as specific structures, I would find it to be a misunderstanding of the construction to take it as a suggestion that set theory is anti-structuralist. Set theorists are generally as structuralist as they come in mathematics, and in light of Dedekinds categorical account of the natural numbers, one might even find the origin of the philosophy of structuralism in set theory. Rather, the disjointifying construction is part of the general proof that set theory abounds with isomorphic copies of whatever mathematical structure we might have, and this is part of the reason why it serves well as a foundation of mathematics for the structuralist. To be a structuralist means not to care which particular copy one has, to treat ones mathematical structures as invariant under isomorphism.
But let me mention a certain regrettable consequence of defining the operations by means of a specific such disjointifying construction in the algebra of orders. Namely, it will turn out that neither the disjoint sum operation nor the ordered sum operation, as operations on order structures, are associative. For example, if we use $1$ to represent the one-point order, then $1\sqcup 1$ means the two-point side-by-side order, one orange and one yellow, but really what we mean is that the points of the domain are $\set{(a,\text{orange}),(a,\text{yellow})}$, where the original order is on domain $\set{a}$. The order $(1\sqcup 1)\sqcup 1$ then means that we take an orange copy of that order plus a single yellow point. This will have domain
$$\set{\bigl((a,\text{orange}),\text{orange}\bigr),\bigl((a,\text{yellow}),\text{orange}\bigr),(a,\text{yellow})}$$
The order $1\sqcup(1\sqcup 1)$, in contrast, means that we take a single orange point plus a yellow copy of $1\sqcup 1$, leading to the domain
$$\set{(a,\text{orange}),\bigl((a,\text{orange}),\text{yellow}\bigr),\bigl((a,\text{yellow}),\text{yellow}\bigr)}$$
These domains are not the same! So as order structures, the order $(1\sqcup 1)\sqcup 1$ is not identical with $1\sqcup(1\sqcup 1)$, and therefore the disjoint sum operation is not associative. A similar problem arises with $1+(1+1)$ and $(1+1)+1$.
But not to worrywe are structuralists and care about our orders here only up to isomorphism. Indeed, the two resulting orders are isomorphic as orders, and more generally, $(A\sqcup B)\sqcup C$ is isomorphic to $A\sqcup(B\sqcup C)$ for any orders $A$, $B$, and $C$, and similarly with $A+(B+C)\cong(A+B)+C$, as discussed with the theorem below. Furthermore, the order isomorphism relation is a congruence with respect to the arithmetic we have defined, which means that $A\sqcup B$ is isomorphic to $A\sqcup B$ whenever $A$ and $B$ are respectively isomorphic to $A$ and $B$, and similarly with $A+B$ and $A\otimes B$. Consequently, we can view these operations as associative, if we simply view them not as operations on the order structures themselves, but on their order-types, that is, on their isomorphism classes. This simple abstract switch in perspective restores the desired associativity. In light of this, we are free to omit the parentheses and write $A\sqcup B\sqcup C$ and $A+B+C$, if care about our orders only up to isomorphism. Let us therefore adopt this structuralist perspective for the rest of our treatment of the algebra of orders.
Let us give a more precise formal definition of $A\otimes B$, which requires no disjointification. Specifically, the domain is the set of pairs $\set{(a,b)\mid a\in A, b\in B}$, and the order is defined by $(a,b)\leq_{A\otimes B}(a,b)$ if and only if $b\leq_B b$, or $b=b$ and $a\leq_A a$. This order is known as the reverse lexical order, since we are ordering the nodes in the dictionary manner, except starting from the right letter first rather than the left as in an ordinary dictionary. One could of course have defined the product using the lexical order instead of the reverse lexical order, and this would give $A\otimes B$ the meaning of $A$ copies of $B$. This would be a fine alternative and in my experience mathematicians who rediscover the ordered product on their own often tend to use the lexical order, which is natural in some respects. Nevertheless, there is a huge literature with more than a century of established usage with the reverse lexical order, from the time of Cantor, who defined ordinal multiplication $\alpha\beta$ as $\beta$ copies of $\alpha$. For this reason, it seems best to stick with the reverse lexical order and the accompanying idea that $A\otimes B$ means $B$ copies of $A$. Note also that with the reverse lexical order, we shall be able to prove left distributivity $A\otimes(B+C)=A\otimes B+A\otimes C$, whereas with the lexical order, one will instead have right distributivity $(B+C)\otimes^* A=B\otimes^* A+C\otimes^* A$.
Let us begin to prove some basic facts about the algebra of orders.
Theorem. The following identities hold for orders $A$, $B$, and $C$.
Associativity of disjoint sum, ordered sum, and ordered product.\begin{eqnarray*}A\sqcup(B\sqcup C) \iso (A\sqcup B)\sqcup C\\ A+(B+C) \iso (A+B)+C\\ A\otimes(B\otimes C) \iso (A\otimes B)\otimes C \end{eqnarray*}Left distributivity of product over disjoint sum and ordered sum.\begin{eqnarray*} A\otimes(B\sqcup C) \iso (A\otimes B)\sqcup(A\otimes C)\\ A\otimes(B+C) \iso (A\otimes B)+(A\otimes C) \end{eqnarray*}In each case, these identities are clear from the informal intended meaning of the orders. For example, $A+(B+C)$ is the order resulting from having a copy of $A$, and above it a copy of $B+C$, which is a copy of $B$ and a copy of $C$ above it. So one has altogether a copy of $A$, with a copy of $B$ above that and a copy of $C$ on top. And this is the same as $(A+B)+C$, so they are isomorphic.
One can also aspire to give a detailed formal proof verifying that our color-coded disjointifying process works as desired, and the reader is encouraged to do so as an exercise. To my way of thinking, however, such a proof offers little in the way of mathematical insight into algebra of orders. Rather, it is about checking the fine print of our disjointifying process and making sure that things work as we expect. Several of the arguments can be described as parenthesis-rearranging argumentsone extracts the desired information from the structure of the domain order and puts that exact same information into the correct form for the target order.
For example, if we have used the color-scheme disjointifying process described above, then the elements of $A\sqcup(B\sqcup C)$ each have one of the following forms, where $a\in A$, $b\in B$, and $c\in C$:
$$(a,\text{orange})$$
$$\bigl((b,\text{orange}),\text{yellow}\bigr)$$
$$\bigl((c,\text{yellow}),\text{yellow}\bigr)$$
We can define the color-and-parenthesis-rearranging function $\pi$ to put them into the right form for $(A\sqcup B)\sqcup C$ as follows:
\begin{align*}
\pi:(a,\text{orange})\quad\mapsto\quad \bigl((a,\text{orange}),\text{orange}\bigl) \\
\pi:\bigl((b,\text{orange}),\text{yellow}\bigr)\quad\mapsto\quad \bigl((b,\text{yellow}),\text{orange}\bigl) \\
\pi:\bigl((c,\text{yellow}),\text{yellow}\bigr)\quad\mapsto\quad (c,\text{yellow})
\end{align*}
In each case, we will preserve the order, and since the orders are side-by-side, the cases never interact in the order, and so this is an isomorphism.
Similarly, for distributivity, the elements of $A\otimes(B\sqcup C)$ have the two forms:
$$\bigl(a,(b,\text{orange})\bigr)$$
$$\bigl(a,(c,\text{yellow})\bigr)$$
where $a\in A$, $b\in B$, and $c\in C$. Again we can define the desired ismorphism $\tau$ by putting these into the right form for $(A\otimes B)\sqcup(A\otimes C)$ as follows:
\begin{align*}
\tau:\bigl(a,(b,\text{orange})\bigr)\quad\mapsto\quad \bigl((a,b),\text{orange}\bigr) \\
\tau:\bigl(a,(c,\text{yellow})\bigr)\quad\mapsto\quad\bigl((a,c),\text{yellow}\bigr)
\end{align*}
And again, this is an isomorphism, as desired.
Since order multiplication is not commutative, it is natural to inquire about the right-sided distributivity laws:
\begin{eqnarray*}
(B+C)\otimes A\overset{?}{\cong}(B\otimes A)+(C\otimes A)\\
(B\sqcup C)\otimes A\overset{?}{\cong}(B\otimes A)\sqcup(C\otimes A)
\end{eqnarray*}
Unfortunately, however, these do not hold in general, and the following instances are counterexamples. Can you see what to take as $A$, $B$, and $C$? Please answer in the comments.
Theorem.
If $A$ and $B$ are linear orders, then so are $A+B$ and $A\otimes B$.If $A$ and $B$ are nontrivial linear orders and both are endless, then $A+B$ is endless; if at least one of them is endless, then $A\otimes B$ is endless.If $A$ is an endless dense linear order and $B$ is linear, then $A\otimes B$ is an endless dense linear order.If $A$ is an endless discrete linear order and $B$ is linear, then $A\otimes B$ is an endless discrete linear order.Proof. If both $A$ and $B$ are linear orders, then it is clear that $A+B$ is linear. Any two points within the $A$ copy are comparable, and any two points within the $B$ copy, and every point in the $A$ copy is below any point in the $B$ copy. So any two points are comparable and thus we have a linear order. With the product $A\otimes B$, we have $B$ many copies of $A$, and this is linear since any two points within one copy of $A$ are comparable, and otherwise they come from different copies, which are then comparable since $B$ is linear. So $A\otimes B$ is linear.
For statement (2), we know that $A+B$ and $A\otimes B$ are nontrivial linear orders. If both $A$ and $B$ are endless, then clearly $A+B$ is endless, since every node in $A$ has something below it and every node in $B$ has something above it. For the product $A\otimes B$, if $A$ is endless, then every node in any copy of $A$ has nodes above and below it, and so this will be true in $A\otimes B$; and if $B$ is endless, then there will always be higher and lower copies of $A$ to consider, so again $A\otimes B$ is endless, as desired.
For statement (3), assume that $A$ is an endless dense linear and that $B$ is linear. We know from (1) that $A\otimes B$ is a linear order. Suppose that $xy$ in this order. If $x$ and $y$ live in the same copy of $A$, then there is a node $z$ between them, because $A$ is dense. If $x$ occurs in one copy of $A$ and $B$ in another, then because $A$ is endless, there will a node $z$ above $x$ in its same copy, leading to $xzy$ as desired. (Note: we dont need $B$ to be dense.)
For statement (4), assume instead that $A$ is an endless discrete linear order and $B$ is linear. We know that $A\otimes B$ is a linear order. Every node of $A\otimes B$ lives in a copy of $A$, where it has an immediate successor and an immediate predecessor, and these are also immediate successor and predecessor in $A\otimes B$. From this, it follows also that $A\otimes B$ is endless, and so it is an endless discrete linear order. $\Box$
The reader is encouraged to consider as an exercise whether one can drop the endless hypotheses in the theorem. Please answer in the comments.
Theorem. The endless discrete linear orders are exactly those of the form $\Z\otimes L$ for some linear order $L$.
Proof. If $L$ is a linear order, then $\Z\otimes L$ is an endless discrete linear order by the theorem above, statement (4). So any order of this form has the desired feature. Conversely, suppose that $\P$ is an endless discrete linear order. Define an equivalence relation for points in this order by which $p\sim q$ if and only $p$ and $q$ are at finite distance, in the sense that there are only finitely many points between them. This relation is easily seen to be reflexive, transitive and symmetric, and so it is an equivalence relation. Since $\P$ is an endless discrete linear order, every object in the order has an immediate successor and immediate predecessor, which remain $\sim$-equivalent, and from this it follows that the equivalence classes are each ordered like the integers $\Z$, as indicated by the figure here.
The equivalence classes amount to a partition of $\P$ into disjoint segments of order type $\Z$, as in the various colored sections of the figure. Let $L$ be the induced order on the equivalence classes. That is, the domain of $L$ consists of the equivalence classes $\P/\sim$, which are each a $\Z$ chain in the original order, and we say $[a]_L[b]$ just in case $a_{\P}b$. This is a linear order on the equivalence classes. And since $\P$ is $L$ copies of its equivalence classes, each of which is ordered like $\Z$, it follows that $\P$ is isomorphic to $\Z\otimes L$, as desired. $\Box$
(Interested readers are advised that the argument above uses the axiom of choice, since in order to assemble the isomorphism of $\P$ with $\Z\otimes L$, we need in effect to choose a center point for each equivalence class.)
If we consider the integers inside the rational order $\Z\of\Q$, it is clear that we can have a discrete suborder of a dense linear order. How about a dense suborder of a discrete linear order?
Question. Is there a discrete linear order with a suborder that is a dense linear order?
What? How could that happen? In my experience, mathematicians first coming to this topic often respond instinctively that this should be impossible. I have seen sophisticated mathematicians make such a pronouncement when I asked the audience about it in a public lecture. The fundamental nature of a discrete order, after all, is completely at odds with density, since in a discrete order, there is a next point up and down, and a next next point, and so on, and this is incompatible with density.
Yet, surprisingly, the answer is Yes! It is possiblethere is a discrete order with a suborder that is densely ordered. Consider the extremely interesting order $\Z\otimes\Q$, which consists of $\Q$ many copies of $\Z$, laid out here increasing from left to right. Each tiny blue dot is a rational number, which has been replaced with an entire copy of the integers, as you can see in the magnified images at $a$, $b$, and $c$.
The order is quite subtle, and so let me also provide an alternative presentation of it. We have many copies of $\Z$, and those copies are densely ordered like $\Q$, so that between any two copies of $\Z$ is another one, like this:
Perhaps it helps to imagine that the copies of $\Z$ are getting smaller and smaller as you squeeze them in between the larger copies. But you can indeed always fit another copy of $\Z$ between, while leaving room for the further even tinier copies of $\Z$ to come.
The order $\Z\otimes\Q$ is discrete, in light of the theorem characterizing discrete linear orders. But also, this is clear, since every point of $\Z\otimes\Q$ lives in its local copy of $\Z$, and so has an immediate successor and predecessor there. Meanwhile, if we select exactly one point from each copy of $\Z$, the $0$ of each copy, say, then these points are ordered like $\Q$, which is dense. Thus, we have proved:
Theorem. The order $\Z\otimes\Q$ is a discrete linear order having a dense linear order as a suborder.
One might be curious now about the order $\Q\otimes\Z$, which is $\Z$ many copies of $\Q$. This order, however, is a countable endless dense linear order, and therefore is isomorphic to $\Q$ itself.
This material is adapted from my book-in-progress, Topics in Logic, drawn from Chapter 3 on Relational Logic, which incudes an extensive section on order theory, of which this is an important summative part.
Share:MoreOrder relations are often fruitfully conceived as being stratified into levels in a natural way. The level structure is meant to be compatible with the order, in the sense that as one moves strictly up in the order, one also ascends successively from lower levels to strictly higher levels. With the simple order relation pictured here, for example, we might naturally imagine the least element $0$ on a bottom level, the three middle nodes $a$, $b$, and $c$ on an intermediate level, and node $1$ on a level at the top. With this level structure, as we move up strictly in the order, then we also move up strictly in the hierarchy of levels.
What exactly is a level? Let us be a little more precise. We can depict the intended level structure of our example order more definitely as in the figure here. At the left appears the original order relation, while the yellow highlighted bands organize the nodes into three levels, with node $0$ on the bottom level, nodes $a$, $b$, and $c$ on the middle level, and node $1$ on the top level. This level structure in effect describes a linear preorder relation $\leq$ for which $0\leq a,b,c\leq 1$, with the three intermediate nodes all equivalent with respect to this preorder—they are on the same level.
$\def\#1{\left\langle#1\right\rangle}\newcommand{\of}{\subseteq}\newcommand{\set}[1]{{\,{#1}\,}}\renewcommand\emptyset{\varnothing}$Thus, we realize that a level structure of an order relation is simply a linear preorder relation that respects strict instances of the original order, and the levels are simply the equivalence classes of the preorder. More precisely, we define that a linear grading of an order relation $\A,\preccurlyeq$ is a linear preorder relation $\leq$ on $A$ for which every strict instance of the original order is also graded strictly by the linear preorder; that is, we require that
$$a\prec b\quad\text{ implies }\quad ab$$ Thus, any strictly lower point in the original order is on a lower level, and we define that objects are on the same level if they are equivalent with respect to the preorder. A linearly graded order is a relational structure $\A,\preccurlyeq,\leq$ with two orders on the same domain, the first $\preccurlyeq$ being an order relation on $A$ and the second $\leq$ being a linear preorder relation that grades the first order.
It turns out that there are often far more ways to stratify a given order by levels than one might have expected. For the simple order above, for example, there are thirteen distinct linear grading orders, as shown here.
The conclusion is inescapable that the level concept is not inherent in the order relation itself, for a given order relation may admit a huge variety of different level hierarchies, each of them compatible with the given order.
One should therefore not make the mistake of thinking that if one has an order relation, such as a philosophical reduction notion of some kind or a supervenience relation, then one is automatically entitled to speak of levels of the order. One might want to speak of low-level phenomena or high-level concepts in the order, but one must recognize that the order relation itself does not determine a specific hierarchy of levels, although it does place limitations on the possible stratifications. My point is that there is often surprising flexibility in the nature of the level structure, as the example above shows even in a very simple case, and so what counts as low or high in terms of levels may be much less determined than one expects. In some of the linear gradings above, for example, the node $a$ could be described as high-level, and in others, it is low-level. Therefore if one wants to speak of levels for ones order, then one must provide further elucidation of the stratification one has in mind.
Meanwhile, we often can provide a natural level structure. In the power set $P(X)$ of a finite set $X$, ordered by the subset relation $A\of B$, for example, we can naturally stratify the relation by the sizes of the set, that is, in terms of the number of elements. Thus, we would place the $\emptyset$ on the bottom level, and the singleton sets $\{a\}$ on the next level, and then the doubletons $\{a,b\}$, and so on. This stratification by cardinality doesnt quite work when $X$ is infinite, however, since there can be instances of strict inclusion $A\subsetneq B$ where $A$ and $B$ are both infinite and nevertheless equinumerous. Is there a level stratification of the infinite power set order?
Indeed there is, for every order relation admits a grading into levels.
Theorem. Every order relation $\A,\preccurlyeq>$ can be linearly graded. Indeed, every order relation can be extended to a linear order (not merely a preorder), and so it can be graded into levels with exactly one node on each level.
Proof. Let us begin with the finite case, which we prove by induction. Assume $\preccurlyeq$ is an order relation on a finite set $A$. We seek to find a linear order $\leq$ on $A$ such that $x\preccurlyeq y\implies x\leq y$. If $A$ has at most one element, then we are done immediately, since $\preccurlyeq$ would itself already be linear.
Let us proceed by induction. Assume that every order of size $n$ has a linear grading, and that we have a partial order $\preccurlyeq$ on a set $A$ of size $n+1$. Every finite order has at least one maximal element, so let $a\in A$ be a $\preccurlyeq$-maximal element. If we consider the relation $\preccurlyeq$ on the remaining elements $A\setminus\{a\}$, it is a partial order of size $n$, and thus admits a linear grading order $\leq$. We can now simply place $a$ atop that order, and this will be a linear grading of $\A,\preccurlyeq$, because $a$ was maximal, and so making it also greatest in the grading order will cohere with the grading condition.
So by induction, every finite partial order relation can be extended to a linear order.
Now, we consider the general case. Suppose that $\preccurlyeq$ is a partial order relation on a (possibly infinite) set $A$. We construct a theory $T$ in a language with a new relation symbol $\leq$ and constant symbols $\dot a$ for every element $a\in A$. The theory $T$ should assert that $\leq$ is a linear order, that $\dot a\leq \dot b$, whenever it is actually true that $a\preccurlyeq b$ in the original order, and that $\dot a\neq\dot b$ whenever $a\neq b$. So the theory $T$ describes the situation that we want, namely, a linear order that conforms with the original partial order.
The key observation is that every finite subset of the theory will be satisfiable, since such a finite subtheory in effect reduces to the case of finite orders, which we handled above. That is, if we take only finitely many of the axioms of $T$, then it involves a finite partial order on the nodes that are mentioned, and by the finite case of the theorem, this order is refined by a linear order, which provides a model of the subtheory. So every finite subtheory of $T$ is satisfiable, and so by the compactness theorem, $T$ itself also is satisfiable.
Any model of $T$ provides a linear order $\leq$ on the constant symbols $\dot a$, which will be a linear order extending the original order relation, as desired. $\Box$
This material is adapted from my book-in-progress, Topics in Logic, which includes a chapter on relational logic, included an extended section on orders.
Share:More Recent Comments on The hierarchy of geometric constructibility: can we go back? on The hierarchy of geometric constructibility: can we go back? on The hierarchy of geometric constructibility: can we go back? on Same structure, different truths, Stanford University CSLI, May 2016 on Satisfaction is not absoluteJDH on TwitterMy TweetsBlogroll A kind of libraryAleph zero categoricalBarbara Gail MonteroBenjamin SteinbergCantors AtticCombinatorics and moreGC Math DepartmentGlobal Set Theory TalksGowerss weblogJDH on WikipediaMathblogging.orgMathOverflowPeanos parlourRichard ZachTerence Tao Mathoverflow activityComment by Joel David Hamkins on How true are theorems proved by Coq?@DavidRoberts I have a paper in preparation. See jdh.hamkins.org/…. There will be a revised version of this paper coming out probably in a few months.Comment by Joel David Hamkins on Nice Algebraic Statements Independent from ZF + V=L (constructibility)Yes, I believe one can get instances like that from the universal Sigma1 definable sequence.Comment by Joel David Hamkins on Can the Induction axiom in the Peano arithmetic be replaced by the irrationality of $\sqrt{2}$?@user6976 My book is available at amazon.com/gp/product/B08942KP4Q.Comment by Joel David Hamkins on Model theory of the complex numbers with conjugationYes, it is a (parametric) bi-interpretation of theories.Comment by Joel David Hamkins on The easily bored sequenceNice question! You should say $w$ is nonempty in the claim $R_w(0)\neq R_w(1)$, since this isnt true for the empty word. (Also, you want $v$ nonempty when defining $a$.)Answer by Joel David Hamkins for Is the one-point compactification of $\mathbb{N}$ computably countable?The answer is no. Suppose that there are computable functions $q$ and $s$ as you describe. Let $k$ be a program that performs the following task. It starts enumerating $1$s at the start of the sequence until it discovers that $s(k)$ is defined. (We use the Kleene recursion theorem to know that there is such []Comment by Joel David Hamkins on Scotts trick without regularitySorry, I meant to say $P$ is the class of difference sets, and to refer to the class of ordinals. (But @AsafKaragila, yes, Ord is a set, but in a larger universe!)Comment by Joel David Hamkins on Scotts trick without regularity@EmilJeřábek I would encourage you to summarize your comments in an answer. Im not exactly sure what the question is now. New York LogicTitle TBAResource Sharing Linear Logic, ISub-Kripkean epistemic models IGeneric logical semantics of justifications IIIGeneric logical semantics of justifications IIGeneric logical semantics of justifications.Cut EliminationFunctors and infinitary interpretations of structuresRecursive Reducts of PA IIIKripke completeness of strictly positive modal logics and related problems Cantors Attic activityHeights of models C7XMeta Log in Entries feed Comments feed WordPress.orgTAGS:Hamkins mathematics Joel David and the infinite philosophy
<<< Thank you for your visit >>>
Websites to related : Le PNUD en Tunisie
keywords:
description:
Dans le monde Tunisie
keywords:
description:View Chopstixx menu, Order Chinese food Delivery Online from Chopstixx, Best Chinese Delivery in Elkridge, MD
keywords:Synagogue near me, Temple near me, Jewish temple near me , Shul near me, Shabbat service near me
description:
keywords:
description:
Web Analysis for Truenewsbd24 - truenewsbd24.com
keywords:
description:Moody's Analytics provides award-winning solutions to financial risk practitioners globally. Our data, models, software, and
keywords:A distinctive concept lifestyle store in the heart of Hong Kong, colourliving brings together meticulously selected European home furniture a
Le PNUD au Maroc keywords:
description:
Dans le monde Mar
keywords:
description:
D.H. LawrenceReview0HomeCurrent IssueBack IssuesSubscriptionsArchiveEditorial BoardFuture ConferencesSubmissi
keywords:
description:Want to publish an academic article? Visit Author Services for support & tips on writing, choosing a journal, peer review, makin
keywords:
description:
Skip to contentMenuWeedmaps Home0 new notifications0FavoritesCartOnline Order BagLog inSign upDispensariesDeliveriesMapsBrandsP
Hot Websites