One reason that 1 is often excluded from the prime numbers is that if it was included, it would complicate the theorems, proofs, and exposition by the endless repetition of "not equal to 1".
> One reason that 1 is often excluded from the prime numbers is that if it was included, it would complicate the theorems, proofs, and exposition by the endless repetition of "not equal to 1".
This is true and compelling as things developed, but I think it's an explanation of where history brought us, rather than a logical inevitability. For example, I can easily imagine, in a different universe, teachers patiently explaining that we declare that the empty set is not a set, to avoid complicating theorems, proofs, and exposition by the endless repetition of "non-empty set."
(I agree that this is different, because there's no interesting "unique factorization theorem" for sets, but I can still imagine things developing this way. And, indeed, there are complications caused by allowing the empty set in a model of a structure, and someone determined to do so can make themselves pointlessly unpopular by asking "but have you considered the empty manifold?" and similar questions. See also https://mathoverflow.net/questions/45951/interesting-example....)
That's an interesting thought, but I think that'd break the usual trick of building up objects from the empty set, a set containing the empty set, then the set containing both of those and so forth.
That universe would be deprived from the bottomless wellspring of dryness that is the set theoretic foundations of mathematics. Unthinkable!
> That universe would be deprived from the bottomless wellspring of dryness that is the set theoretic foundations of mathematics. Unthinkable!
"Wellspring of dryness" is quite a metaphor, and I take it from that metaphor that this outcome wouldn't much bother you. I'll put in a personal defense for set theory, but only an appeal to my personal taste, since I have no expert, and barely even an amateurish, knowledge of set theory beyond the elementary; but I'll also acknowledge that set-theoretic foundations are not to everyone's taste, and that someone who has an alternate foundational system that appeals to them is doing no harm to themselves or to me.
> That's an interesting thought, but I think that'd break the usual trick of building up objects from the empty set, a set containing the empty set, then the set containing both of those and so forth.
In this alternate universe, the ZF or ZFC axioms (where C becomes, of course, "the product of sets is a set") would certainly involve, not the axiom of the empty set, but rather some sort of "axioms of sets", declaring that there exists a set. Because it's not empty, this set has at least one element, which we may extract and use to make a one-element set. Now observe that all one-element sets are set-theoretically the same, and so may indifferently be denoted by *; and then charge ahead with the construction, using not Ø, Ø ∪ {Ø}, Ø ∪ {Ø} ∪ {Ø ∪ {Ø}}, etc. but *, * ∪ {*}, * ∪ {*} ∪ {* ∪ {*}}, etc. Then all that would be left would be to decide whether our natural numbers started at the cardinality 1 of *, or if we wanted natural numbers to count quantities 1 less than the cardinality of a set.
A good example of this is the natural numbers. Algebraists usually consider zero to be a natural number because otherwise, it's not a monoid and set theorists want zero because it's the size of the empty set. My number theory textbook defined natural numbers as positive integers, but I'm not entirely sure why.
> My number theory textbook defined natural numbers as positive integers, but I'm not entirely sure why.
Since both the inclusion and exclusion of zero are accepted definitions depending on who’s asking, books usually just pick one or define two sets (commonly denoted as N_0 and N_1). Different topics benefit from using one set over the other, as well as having to deal with division by zero, etc. Number theory tends to exclude zero.
Oh my, it had never occurred to me that one could disagree, not just about whether the natural numbers include 0 or don't, but also about how to denote "natural numbers with 0" and "natural numbers without." Personally, I'm a fan of Z_{\ge 0} and Z_{> 0}, which are a little ugly but which any mathematician, regardless of their preferred conventions, can read and understand without further explanation.
> Many (most?) results are easier to write if you allow the empty set. For example:
> "The intersection of two sets is a set."
Many results in set theory, yes! (Or at least in elementary set theory. I'm not a set theorist by profession, so I can't speak to how often it arises in research-level set theory.) But, once one leaves set theory, the empty set can cause problems. For the first example that springs to mind, it is a cute result that, if a set S has a binary operation * such that, for every pair of elements a, b in S, there is a unique solution x to a*x = b, and a unique solution y to y*a = b, then * makes S a group ... unless S is empty!
In fact, on second thought, even in set theory, there are things like: the definition of a partial order being a well ordering would become simpler to state if the empty set were disallowed; and the axiom of choice would become just the statement that the product of sets is a set! I'm sure that I could come up with more examples where allowing empty sets complicates things, just as you could come up with more examples where it simplifies them. That there is no unambiguous answer one direction or the other is why I believe this alternate universe could exist, but we're not in it!
I don’t see why it’s a problem that the empty set cannot be a group. The empty set, being empty, lacks an identity element. Thus all groups are non-empty.
The same is true for any structure which posits the existence of some element. Of course it cannot be the empty set.
> I don’t see why it’s a problem that the empty set cannot be a group. The empty set, being empty, lacks an identity element. Thus all groups are non-empty.
It's not necessarily a problem that the empty set cannot be a group. (Although the only reason that it cannot is a definition, and, similarly, the definition of a field requires two distinct elements, which hasn't stopped some people from positing that it is a problem that there is then no field with one element.)
The problem is that there's a natural property of magmas (sets with binary operation), namely the uniquely solvability condition I mentioned, that characterizes "group or the empty set," which is more awkward than just characterizing groups. Or you may argue, fairly, that that's not a problem, but it is certainly an example where allowing the empty set to be a set complicates statements, which is all that I was meaning to illustrate. Hopefully obviously, without meaning seriously to suggest that the empty set shouldn't be a set.
(I remembered in the course of drafting this comment that https://golem.ph.utexas.edu/category/2020/08/the_group_with_... discusses, far more entertainingly and insightfully than I do, the characterization that I mention, and may have been where I learned it.)
If you don’t allow the empty set to be a set then you break the basic operations of set theory. For example, to show two sets are disjoint you compare their intersection with the empty set.
In an alternative axiomatization (without the empty set) you’re going to need to create some special element which belongs to every set and then your definition of disjoint sets is that their intersection is equal to the trivial set containing only the special element. What a clumsy hack that would be!
And if we treat zero as not a number, it would make division much easier to define. I wrote that sentence as a joke but now I wonder if maybe it’s true. Does addition really need to have an identity? Maybe we just saw that multiplication has an identity and got a bit carried away. I’m not too sure about this negative number business while we’re at it. Could be that we just took a wrong turn somewhere.
> And if we treat zero as not a number, it would make division much easier to define. I wrote that sentence as a joke but now I wonder if maybe it’s true. Does addition really need to have an identity?
It probably doesn't, but, if you want to allow negative numbers, then addition is partial unless you have 0. It's perfectly reasonable to disallow negative numbers—historically, negative numbers had to be explicitly allowed, not explicitly disallowed—but it does mean that subtraction becomes a partial operation or, phrased equivalently but perhaps more compellingly, that we have to give up on solving simple equations for x like x + 2 = 1.
Well you did say you were okay with set intersection being partial (or I guess also set difference for the more direct analogy). Maybe not everything needs a solution. (Plus we’ve just gone from division being partial to subtraction being partial…but when I say that I begin to suspect that this argument has been made a lot before and we decided that the negative numbers get to stay. I don’t have anything against them personally but they’re probably less natural than the empty set being a set.)
I might be reading too much into what you’re saying about the empty set though and you just mean we could use the word “set” to mean “non-empty set” and then say something like “set-theoretic set” to mean what we now mean when we say “set.” But that sounds like a mouthful.
> Well you did say you were okay with set intersection being partial (or I guess also set difference for the more direct analogy).
Good point!
> I don’t have anything against them personally but they’re probably less natural than the empty set being a set.
An interesting idea, which history supports: 0 was considered as a number before negative numbers were, and we still usually consider only "natural sets" and not "negative sets" (except for Schanuel: https://doi.org/10.1007/BFb0084232).
> I might be reading too much into what you’re saying about the empty set though and you just mean we could use the word “set” to mean non-empty set and then say something like “set-theoretic set” to mean what we now mean when we say “set.”
Right, or a different word entirely, just like we refer to 1 only as a number that's not prime, not as a "number-theoretic prime." But, anyway, the analogy was just the first one that sprang to mind; it doubtless has many infelicities that could be improved by a better analogy, if it's not just a worthless idea overall.
Yeah I guess what I got stuck on is that we don’t currently have a word for “a set that’s not a set” (I guess a class?) like we do for a number that’s not a prime but I think I was just lacking linguistic imagination.
The concept of “one” holds a dual role. It represents a countable unit: something you can put in a bowl and also stands for indivisibility itself. When you divide any quantity by an indivisible unit, you’re simply counting how many of those indivisibles fit within it. Then comes 2: the first number that is divisible, but only by itself and the indivisible one. That’s what makes it prime. A prime is a number divisible only by itself and by 1, the indivisible origin of all counting.
Your explanation is true of every prime. I’m pretty sure GP just meant that “2 is the only prime with the additional characteristic of being an even number”. So it’s odd (read “interesting”) in that sense, like if it would be if (for example) any number were to be the sole prime composed of exactly X digits.
And the reason we'd have to constantly exclude 1 is that it behaves in a qualitatively different way than prime numbers—and understand what this means and why that's the case is the real insight here.
Yes, it's more of a convention where we assume language like "...ignoring the trivial case of 1 being an obvious factor of every integer." It's not interesting or meaningful, so we ignore it for most cases.
"...ignoring the trivial case of 1 being an obvious factor of every integer."
I remember quite a big chunk of GEB formally defining how integers are really not trivial! The main problem seems to be is that you soon end up with circular reasoning if you are not razor sharp with your definitions. That's just in an explainer book 8)
Correct, it's impossible to specifically and formally define the natural numbers so that addition and multiplication work. Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers.
>Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers
This isn't correct. This is only true for first-order theories of the natural numbers using the axiom schema of induction. Second-order Peano arithmetic with the full axiom of induction has the natural numbers as its only model. This property is called "categoricity" and you can find the proof here [1] if you're interested
This isn't correct. While it's true that in second order logic the natural numbers admit categoricity, second order logic lacks axiomatic semantics. So yes, there is a single set which can be called the natural numbers in second order logic (namely the intersection of all sets that satisfy Peano's axioms), but this set has no interpretation.
You can adopt Henkin semantics to give the naturals an interpretation, which is still second order logic, but then you're back to lacking a categorical model of the naturals.
> So yes, there is a single set which can be called the natural numbers in second order logic (namely the intersection of all sets that satisfy Peano's axioms), but this set has no interpretation.
Can you explain what you mean here? Full semantics for second-order logic has a unique interpretation i.e. the standard natural numbers
My understanding is you can specifically and formally define the natural numbers with addition and multiplication, although multiplication means the language is no longer decidable.
You can define natural numbers with just addition ( Presburger arithmetic ) and it’s decidable.
Im not sure how undecidable <=> “will define things that are similar to natural numbers but are not” but maybe I am missing something
If a sentence S is undecidable from your axioms for the natural numbers then there are two models A and B satisfying those axioms where A satisfies S and B satisfies not S. So which one is the standard natural numbers, is it A or B?
Either A or B will be an example of something that satisfies your definition of natural numbers and yet is not the natural numbers.
> Correct, it's impossible to specifically and formally define the natural numbers so that addition and multiplication work. Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers.
Are such objects not inevitably isomorphic to the natural numbers?
Can you give an example of a formal definition that leads to something that obviously isn't the same as the naturals?
In that article you'll see references to "first order logic" and "second order logic". First order logic captures any possible finite chain of reasoning. Second order logic allows us to take logical steps that would require a potentially infinite amount of reasoning to do. Gödel's famous theorems were about the limitations of first order logic. While second order logic has no such limitations, it is also not something that humans can actually do. (We can reason about second order logic though.)
Anyways a nonstandard model of arithmetic can have all sorts of bizarre things. Such as a proof that Peano Axioms lead to a contradiction. While it might seem that this leads to a contradiction in the Peano Axioms, it doesn't because the "proof" is (from our point of view) infinitely long, and so not really a proof at all! (This is also why logicians have to draw a very careful distinction between "these axioms prove" and "these axioms prove that they prove"...)
All of these models appear to contain infinitely sized objects that are explicitly named / manipulable within the model, which makes them extensions of the Peano numbers though, or else they add other, extra axioms to the Peano model.
If you (for example) extend Peano numbers with extra axioms that state things like “hey, here are some hyperreals” or “this Goedel sentence is explicitly defined to be true (or false)” it’s unsurprising that you can end up in some weird places.
I know this is a great book, it’s been on my to-read list for about 5 years. But I never get to it. Is there not another (shorter) discussion I could read on this? Even an academic paper would be acceptable.
I mean it's logically impossible to formally and specifically define the natural numbers without introducing a logical inconsistency. The best you can do is define a set that has all the properties of natural numbers but will also define things that aren't natural numbers as well.
As an analogy you could imagine trying to define the set of all animals with a bunch of rules... "1. Animals have DNA, 2. Animals ingest organic matter. 3. Animals have a nervous system. 4. ... etc..."
And this is true of all animals, but it will also be true of things that aren't animals as well, like slime molds which are not quite animals but very similar to them.
Okay so you keep adding more rules to narrow down your definition and stamp out slime molds, but you find some other thing satisfy that definition...
Now for animals maybe you can eventually have some very complex rule set that defines animals exactly and rules out all non-animals, but the principle is that this is not possible for natural numbers.
We can have rules like "0" is a natural number. For every natural number N there is a successor to it N + 1. If N + 1 = M + 1 then N = M. There is no natural number Q such that Q + 1 = 0.
Okay this is a good starting point... but just like with animals there are numbers that satisfy all of these rules but aren't natural numbers. You can keep adding more and more rules to try to stamp these numbers out, but no matter how hard, even if you add infinitely many rules, there will always be infinitely many numbers that satisfy your rules but aren't natural numbers.
In particular what you really want to say is that a natural number is finite, but no matter how hard you try there is no formal way to actually capture the concept of what it means to be finite in general so you end up with these mutant numbers that satisfy all of your rules but have infinitely many digits, and these are called non-standard natural numbers.
The reason non-standard natural numbers are a problem is because you might have a statement like "Every even integer greater than 2 can be written as the sum of two primes." and this statement might be true of the actual natural numbers but there might exist some freak mutant non-standard natural number for which it's not true. Unless your rules are able to stamp out these mutant non-standard natural numbers, then it is not possible to prove this statement, the statement becomes undecidable with respect to your rules. The only statements you can prove with respect to your rules are statements that are true of the real natural numbers as well as true of all the mutant natural numbers that your rules have not been able to stamp out.
So it's in this sense that I mean that it's not possible to specifically define the natural numbers. Any definition you come up with will also apply to mutant numbers, and these mutant numbers can get in the way of you proving things that are in principle true about the actual natural numbers.
It seems you know what you are on about! Thank you for a cracking comment.
I've always had this feeling that the foundations (integers etc) are a bit dodgy in formal Maths but just as with say Civil Engineering, your world hasn't fallen apart for at least some days and it works. Famously, in Physics involving quantum: "Shut up and calculate".
Thankfully, in the real world I just have to make web pages, file shares and glittery unicorns available to the computers belonging to paying customers. Securely ...
The foundational aspect equivalent of integers in IT might be DNS. Fuck around with either and you come unstuck rather quickly without realising exactly why until you get suitably rigorous ...
I'm also a networking bod (with some jolly expensive test gear) but that might be compared to pencils and paper for Maths 8)
This is true and compelling as things developed, but I think it's an explanation of where history brought us, rather than a logical inevitability. For example, I can easily imagine, in a different universe, teachers patiently explaining that we declare that the empty set is not a set, to avoid complicating theorems, proofs, and exposition by the endless repetition of "non-empty set."
(I agree that this is different, because there's no interesting "unique factorization theorem" for sets, but I can still imagine things developing this way. And, indeed, there are complications caused by allowing the empty set in a model of a structure, and someone determined to do so can make themselves pointlessly unpopular by asking "but have you considered the empty manifold?" and similar questions. See also https://mathoverflow.net/questions/45951/interesting-example....)