We define a function:

$f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$

• Well-defined: For every $n \in \mathbb{N}$, we have $n \ge 1$, so $n-1 \ge 0$. Hence $f(n) \in \mathbb{N}_0$, and the function is well-defined.
  
• Injective: Suppose $f(n_1) = f(n_2)$. Then
  $n_1 - 1 = n_2 - 1 \implies n_1 = n_2$.
  Hence $f$ is injective.
  
• Surjective: Let $m \in \mathbb{N}_0$. Define $n = m + 1 \in \mathbb{N}$. Then
  $f(n) = f(m+1) = (m+1)-1 = m$.
  Hence $f$ is surjective.

Conclusion: The function $f(n) = n-1$ is a bijection between $\mathbb{N}$ and $\mathbb{N}_0$.

It is defined as a bijection. The same way square-circles are defined as shapes that are both circles and squares. That does not mean they are logical possibilities, i.e. free from internal contradictions.

And there's a subtle difference between "You can pick any number from N and map it onto a unique number from N0" and "You can pick every number from N and map it onto a unique number from N0".

You wouldn't expect completion from a thread titled "Infinity" would you?

Not really, but ignoring the infinite level of irrelevance of the topic is a pretty important omission.

It is defined as a bijection. — Magnus Anderson

$\mathbb{N}_0$?

Well, no. It is defined as f(n)=n−1 and then shown to be a bijection. That definition does not mention bijectivity at all. At this stage, the function could turn out to be injective, surjective, neither, or both. Nothing is being smuggled in.

While a square-circle is defined using incompatible properties, there is no contradiction in $\mathbb{N}_0$.

N0? — Banno

Not N0 but f(n) = n - 1. That function is a bijection by definition.

It is defined as f(n)=n−1 and then shown to be a bijection. That definition does not mention bijectivity at all. At this stage, the function could turn out to be injective, surjective, neither, or both. Nothing is being smuggled in. — Banno

Yes. It is not explicitly stated in the definition. However, the definition implies it. And because it implies it, it is a bijection by definition.

It's like defining the symbol "S" as "a closed figure with three straight sides". It does not explicitly state that it has 3 angles but it does imply it. So it is correct to say that S has 3 angles by definition.

"By definition" does not mean "explicitly stated by the definition". It means "fixed by the definition ( either explicitly or implicitly )".

In mathematics, functions are defined as sets of input-output pairs. f( n ) = n - 1, in this view, is a set of input-output pairs where every element from N is paired with exactly one element from N0 and vice versa. That makes it a bijection by definition. But that does not mean that the bijection between N and N0 exists, i.e. that it is a logical possibility. It merely means that's what the symbol can represent. It's similar to how simply saying that the term "square-circle" means "a shape that is both a square and a circle" does not mean that square-circles exist.

The seemingly devastating consequences of accepting that no bijection exists between N and N0 is that f( n ) = n - 1 does not exist either, i.e. that it is an oxymoron. The good news is that that's merely a consequence of an incorrect definition of functions. Functions aren't sets of input-output pairs. They are sets of rules.

Not N0 but f(n) = n - 1. That function is a bijection by definition. — Magnus Anderson

Here's the definition again: $f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$

$\quad f(n) = n - 1$ as it stands is not a definition of a bijection. It can't be, because it lacks a domain and a codomain, as provided by $f: \mathbb{N} \to \mathbb{N}_0$

$\quad f(n) = n - 1$ could be applied to any domain, with differing results. With $\mathbb{Z}$ as the domain and codomain also $\mathbb{Z}$, it would be a bijection. If the domain were $\mathbb{N}$ and the codomain $\mathbb{Z}$, bijectivity would again depend on proof, not stipulation.

Yes. It is not explicitly stated in the definition. However, the definition implies it. — Magnus Anderson

An odd thing to say, since making that implication explicit is exactly what the proof presented above does. you treat $\quad f(n) = n - 1$ as if it secretly meant "let $f$ be a bijection defined by $\quad f(n) = n - 1$"; but that is not what is being done. What was done, step by step, was:

1. Define a function by a rule.
2. Specify domain and codomain.
3. Prove that, given those, the function is injective and surjective.

$\quad f(n) = n - 1$ might be bijective, non-surjective, or non-injective depending on the domain and codomain.

Here's the definition again — Banno

I can't quote the entire part, the LaTeX code gets messed up for some reason.

You are right that f( n ) = n − 1 by itself is not a complete definition of a function. A function definition requires a domain and a codomain. I conveniently left those out, assuming that they could be inferred from the context.

I was referring to the N -> N0 variant.

bijectivity would again depend on proof, not stipulation — Banno

When I say the function is bijective by definition, I do not mean that bijectivity is explicitly stated, but that it is an unavoidable consequence of the definition. The "proof" consists solely in unpacking what is already implied by the definition, not in adding any further stipulation.

f(n)=n−1 might be bijective, non-surjective, or non-injective depending on the domain and codomain. — Banno

That's correct. However, I was talking about f: N -> N0, f( n ) = n - 1. That specific variant does imply bijection.

The real problem is being ignored and that is that the fact that a definition implies bijection between N and N0 does not mean that such a bijection exists in the sense of being a logical possibility.

When I say the function is bijective by definition, I do not mean that bijectivity is explicitly stated, but that it is an unavoidable consequence of the definition. The "proof" consists solely in unpacking what is already implied by the definition, not in adding any further stipulation. — Magnus Anderson

Yep. that's what a proof does.

Not really, but ignoring the infinite level of irrelevance of the topic is a pretty important omission. — LuckyR

Why do you say the topic is irrelevant"? The concept of infinite is commonly used in mathematics, so there must be at least some relevance.

Well, no. It is defined as f(n)=n−1 and then shown to be a bijection. — Banno

It is not "shown to be a bijection". It is stipulated to be a bijection. And, it is actually impossible to make that bijection. So what it actually is, is the affirmation of an unjustifiable, impossible, action (bijection). When what is stipulated as done or even doable, as a premise, is actually impossible, this justifies the judgement that it is a false premise.

Yep. that's what a proof does. — Banno

A sound proof requires true premises. A so-called "proof" derived from a false premise, is not a proof at all. Therefore your so-called "proof" is ineptly named because it doesn't fulfil the criteria. It has been refuted. I think you actually know this already, but you tend to deny the obvious brute facts, when they are contrary to what you like to believe in.

@Metaphysician Undercover @Magnus Anderson

It seems to me that this discussion keeps looping because the objection is being framed as an internal refutation of standard mathematical proofs, rather than as a foundational challenge to the notion of existence those proofs rely on.

Both of you have raised worries about the “doability” of bijection for infinite collections, which suggests a rejection of the identification of existence with formal definability and consistency. That’s a substantive philosophical position. But if that’s the objection, then it isn’t a matter of showing that the usual definitions lead to contradictions (they don’t), but of rejecting the underlying framework.

Put differently, the objection seems clearer if stated explicitly at the level of foundations, e.g.:

“I reject the identification of mathematical existence with formal definability. I require a constructive or modal account of possibility, and under that account I deny that completed infinite bijections exist.”

or

“I reject classical set theory in favor of a finitist or constructivist framework, where existence requires explicit construction.”

Framed that way, the disagreement would look less like an accusation about the failure of proof and more like a clash of foundational commitments, which is where I suspect the disagreement really belongs.

I should say in advance that I haven’t read many books on maths, and I wouldn’t consider myself a good mathematician.

Maybe that actually allowed me to look at this from a slightly different angle.

From the comments I’ve read here, it seems to me that the discussion ultimately comes down to the question of what counts as a sound proof.

@Magnus Anderson, your reasoning reminds me of Hume. It seems to me that your requirement for a proof is to list all possible cases (one by one?) and show that a given hypothesis holds in each of them. But just as you can never know with absolute certainty that the sun will rise again (Hume), you also can’t know whether the next line in an infinite list might contradict the hypothesis.

But mathematics, as I understand, is based on definitions and sets of rules (including what counts as a proof and how to present one), not on “real objects” per se. And since the OP is talking about numbers, I think we can safely assume the topic concerns mathematical infinity.

And @Esse Quam Videri nicely laid out exactly which 'practices' of what we might call 'orthodox maths' are being rejected.

Yes! Magnus's objections are framed as an internal problem with a proof, when they should be framed as external problems with the process being used.

If Magus would be a constructivist or intuitionist here, then he might do well to do so explicitly. That would be a legitimate position. But what we have looks like intellectual drift rather than anything solid.



There's a few ways that a constructivist might proceed. They might reject the usual account of what it is to be a mathematical entity, ∃x P(x) is true iff P(x) is derivable in a consistent formal system. They might instead insist on a constructive approach: To assert “∃x P(x)” one must provide a construction (algorithm, procedure, or finite method) that yields such an x.

So an argument might proceed by rejecting $f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$ as a suitable account of a function, on the grounds that it relies on unrestricted quantification over a completed infinite totality, saying something like "We don't yet have a finite or algorithmic construction of the entire inverse mapping, so surjectivity is not constructively justified.”

The trouble is that for $f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$ we do have the inverse mapping: $g: \mathbb{N} \to \mathbb{N}_0, \quad g(n) = n + 1$. So this won't work here.

This wouldn't be a function on which a constructivist might try to stand their ground. There are, of course, other bits of maths were constructivists interestingly differ from classical maths, and there are some interesting philosophical issues here. But one needs a grounding in mathematics in order to be able to express the difficulties with clarity.



A more eccentric approach, and this is perhaps were Magnus is coming from, might reject infinities altogether. This is the most charitable interpretation Ive been able to work out. If Magnus rejects the very idea of infinite totalities, if he rejects $\mathbb{N}$, then his argument might be made consistent, but at a great cost.

On this view, computing n−1 for any given numeral would be fine, and also computing n−1 for any finite set of numerals, say {2,4,6,8}. But somewhat arbitrarily, a finitist would reject applying n−1 to any infinite set. They in effect accept $\quad f(n) = n - 1$ for any finite n, but not for $\mathbb{N}$.

Importantly, on this view the argument given above would not be invalid, or lead to contradiction, but ill-formed, because it relies on $\mathbb{N}$. (added: It's not even true or false, since these notions do not apply to ill-formed formations )

The cost here is the rejection of succession (roughly, that for every number there is another number that is one more than it; or more accurately, that we can talk about such an infinite sequence); and consequently the rejection of the whole of Peano mathematics*. No small thing.

To be sure, this is how Magnus might have argued, but hasn't.

I, like most folk, enjoy talking about infinity, and so would reject such finitism.

* On consideration, this last isn't quite right. we might accept Peano's definition of succession and still not accept that we thereby construct an infinite set. thanks, .

Explicitly specifying a function is acceptable as a constructive proof. Constructivism shares some concerns with finitism, but it is not as bonkers stringent.

Explicitly specifying a function is acceptable as a constructive proof. Constructivism shares some concerns with finitism, but it is not as bonkers stringent. — SophistiCat

I suppose so. I don't see that a constructivist would have issues with f(n)=n-1 or f(n)=n+1. Again, these are not examples with which a constructivist might take issue. They would more typically take issue with LEM, and reductio arguments, and treat infinite collections as potential rather than actual, or as given by generation rules. I've some sympathy for it, after Wittgenstein.

So I think Magnus must be basing his ideas on a finitist intuition. We'll have to see what he says.

The cost here is the rejection of succession (roughly, that for every number there is another number that is one more than it; or more accurately, that we can talk about such an infinite sequence); and consequently the rejection of the whole of Peano mathematics. No small thing. — Banno

Strange as it may sound, Peano arithmetic does not require you to accept natural numbers as a "completed" set. You can have your successor function, you can show that, given the axioms, there are "as many as you want" distinct numerals, and still that does not compel you to accept the totality of all such numerals, N.

Yeah... good point. I overstepped.

So in both classical and constructionist maths, for any number we can construct its successor. Ok.

So constructivism will not help Magnus here. He must resort to finitism - the view that why for any number we can construct its successor, we can't thereby construct the infinite sequence $\mathbb{N}$.

There's no need to list all of the elements. All this talk about constructivism, intuitionism and finitism misses the point ( I do not subscribe to any of these -isms nor do I have to in order to be internally consistent. )

PROOF

1) To say that S is larger than S' means that S' is a proper subset of S.
( A definition that applies to all sets, regardless of their size. )

2) N is a proper subset of N0.

3) Therefore, N0 is bigger than N.

This is an indisputable proof. As indisputable as 2 + 2 = 4.

However, if you're convinced by a fallacious proof, you will normally deny the validity of this one, like a cancer attacking healthy cells.

FALLACIOUS PROOF #1

The first fallacious proof they use to show that N and N0 are of the same size is the observation that, if you add 1 to infinity, you still get infinity. This is true but only in the sense that the result is also an infinite number ( i.e. larger than every integer. ) They make a mistake when they conclude that, just because "infinity" and "infinity + 1" are infinite numbers, it follows that they are equal. It's like saying that 4 equals 5 merely because 4 and 5 are integers.

FALLACIOUS PROOF #2

The second fallacious proof they use is grounded in the premise that, if you can come up with a symbol that is defined as bijection between N and N0, it follows that a bijection between N and N0 exists ( i.e. it's not a contradiction in terms. ) It's like saying that square circles exist merely because there exists a term called "square circle" that is defined as a square circle.

Both of you have raised worries about the “doability” of bijection for infinite collections, which suggests a rejection of the identification of existence with formal definability and consistency. That’s a substantive philosophical position. But if that’s the objection, then it isn’t a matter of showing that the usual definitions lead to contradictions (they don’t), but of rejecting the underlying framework. — Esse Quam Videri

I wouldn't characterize this as "worries". It doesn't worry me at all. I just reject falsity for what it is, and since this matter has little if any influence on my daily life it doesn't worry me.

However I think you should reconsider what you say about contradiction. If "infinite" is defined as without limit, then it is clearly contradictory to say that the bijection could be done. It is also contradictory to say that it is doable. Further, it is also contradictory to say that the natural numbers are "countably infinite". Obviously, "without limit" means cannot be counted, so countable contradicts this.

Framed that way, the disagreement would look less like an accusation about the failure of proof and more like a clash of foundational commitments, which is where I suspect the disagreement really belongs. — Esse Quam Videri

I suggest we call a spade a spade. A falsity is a falsity. A conclusion derived from a false premise is unsound. An unsound argument does not constitute "a proof".

I suppose you could argue that mathematicians produce their own rules, and are not subject to the terms of logic. But what would be the point in giving mathematics such an exemption, to proceed in an illogical way. It seems like it would only defeat the purpose of the pursuit of knowledge, to allow for an illogical form of logic.

Magnus's objections are framed as an internal problem with a proof, when they should be framed as external problems with the process being used. — Banno

This is the reason for the distinction between "true" and "valid". Validity is concerned with the internal process. Truth is concerned with the external relations of the premises. "Proof" requires both, and this is known as soundness.

If Magnus rejects the very idea of infinite totalities... — Banno

Clearly, when "infinite" is defined in the usual way, and the way that we understand the natural numbers to be, "infinite totalities" is contradictory.

In no way does this perspective make it impossible to talk about infinite succession. It only applies standard principles of logic to such talk, denying by the law of noncontradiction things like "infinite totality", and denying as false, premises such as "countably infinite". If application of these standard principles of logic expose some of current mathematics as unsound, then that is a problem, which the mathematicians ought to deal with. They ought to accept this, and not whine about having to throw away a whole lot of work.

So constructivism will not help Magnus here. He must resort to finitism - the view that why for any number we can construct its successor, we can't thereby construct the infinite sequence N

. — Banno

I don't understand this objection. As mentioned above, there is no need to reject the idea of infinite sequence, nor is there a need for finitism. The problem is with the idea that an infinite sequence could be completed. That is talk which is unacceptable.

So, we can talk about tasks which will never be completed, and there is nothing wrong with this talk, it makes sense. We can even define a specific task as being impossible to complete, and this makes perfect sense. We can define counting all the natural numbers as such a task which will never be completed, and there is no problem with talking about this. The problem is when we take a task which we have defined as being impossible to complete, such as counting all the natural numbers. and then start talking about it as if it is possible to complete.

For anyone keen on a heavy read, The Size of Sets is an Open Logic chapter that goes through most of this. It's a work in progress, so a bit patchy. It goes in to great length concerning enumeration, which is pivotal here.

1) To say that S is larger than S' means that S' is a proper subset of S.
( A definition that applies to all sets, regardless of their size. ) — Magnus Anderson

This is false, since that definition applies only to finite sets. For infinite sets, we need something more. Consider that the even numbers form a proper subset of the integers, and yet we could count the even numbers... a bijection.

The objection that we could not actually count the even numbers because there are two many of them is trivial; we have a function f(n)=2n, that when applied to $\mathbb{N}$ gives us every even number. And we have the inverse, g(n)=n/2, which wen applied to the even numbers gives every integer. If your finitism is such that you cannot see that, I can't help you.

This is false, since that definition applies only to finite sets. — Banno

That's a lie you've been shamelessly pushing forward.

The definition does not apply only to finite sets. It applies to all sets. The only reason you think it does not apply to infinite sets is because it leads to contradictions when you use it in combination with your mistaken premise, "If we can define a bijection, then bijection exists." That premise is your mistake. That premise is the main point of dispute. And so far, you've been conveniently ignoring it.

The other thing you conveniently ignore, because you clearly don't understand how definitions work, is that, you cannot blame the definition in this case. When you blame the definition, what you end up doing is changing the set of relations you're talking about, while calling the new relations the same names and insisting that they are the same relations as before.

It's like saying that, for red cars, "same size as" means something different than it does for cars that are not red. For example, that for red cars, "same size as" means "same color as". Therefore, all red cars are of the same size. And whoever says there are red cars that differ in size, you will claim they are wrong, simply because you got yourself in this bunker of confusion. In reality, all that you're doing is changing the relation that you're talking about ( from "same size as" to "same color as" ) while calling it the same name ( "same size as" ) and pretending that it's the same one ( "same size as". ) Instead of talking about the equality of sizes, you're now talking about the equality of colors, while calling it the same name ( "equality of sizes" ) and pretending that you're actually talking about the equality of sizes.

It's an ugly trick. But easy to see through for people who can actually think.

If your finitism is such that you cannot see that — Banno

Only a completely blind person can see any trace of finitism in what I'm saying.

That's a lie you've been shamelessly pushing forward. — Magnus Anderson

Well, it's not just me...

The definition you suggest cannot be used effectively with infinite sets. But enumeration, that is a surjection, will do everything that can be done with your definition and then do more - quite a bit more - with other sets. So your definition is effectively included in yet surpassed by enumeration.

The definition you suggest cannot be used effectively with infinite sets. — Banno

Another lie.

Well, it's not just me... — Banno

It's not only you. I am aware of that. Your confidence is entirely grounded in what someone else said.

The first fallacious proof they use to show that N and N0 are of the same size is the observation that, if you add 1 to infinity, you still get infinity. — Magnus Anderson

Where do you think this claim appears in the proof?

The claim “infinity + 1 = infinity” does not appear anywhere in the proofs I have used.

The second fallacious proof they use is grounded in the premise that, if you can come up with a symbol that is defined as bijection between N and N0, it follows that a bijection between N and N0 exists ( i.e. it's not a contradiction in terms. ) — Magnus Anderson

The proof doesn't just "define a symbol for a bijection"; it provides an explicit function:

$f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$

• f is the name of a function.
• ℕ is the set of natural numbers. Here, on convention, ℕ = {1, 2, 3, …}.
• ℕ₀ is the set of natural numbers including 0, i.e., ℕ₀ = {0,1,2,3,…}.
• → is read as “maps to” or “a function from … to …”.

So we can read the definition as:

f is a function from the natural numbers ℕ to the natural numbers including zero ℕ₀ such that for each natural number n, f(n) is equal to n minus 1.

What is defined here is a function, not a symbol. This is a concrete mapping, not a mere linguistic construct, and it suffices to show that a bijection exists.

What is defined here is a function, not a symbol. This is a concrete mapping, not a mere linguistic construct, and it suffices to show that a bijection exists. — Banno

The symbol we're talking about is this:

f: N -> N0, f( n ) = n - 1

The definition of a symbol specifies what that symbol can be used to represent -- here, a specific bijection between N and N0.

However, that does not tell us anything about whether or not such a bijection is a contradiction in terms.

If it's a contradiction in terms, then bijection between N and N0 cannot possibly exist.

You seem to be arguing that N must be bigger smaller than N U {0} because, well, 0 is left out. Is that right? (Doofus.)

But try this: instead of thinking of the numbers here as things, think of them as labels. In one set, there is something we have labeled "0"; in the other, there isn't, but suppose there isn't not because the 0-thing isn't there, but because we've labeled it "1" instead.

The functions that have been discussed are instructions for switching from one labeling system to another. Isn't it clear that this works, and that there can be no set of objects you could label starting at 0 that you couldn't also label starting at 1? And vice versa. Or starting at 2 and using only even numbers. Or any number of other ways, so long as you are systematic about it. All these sets of labels are clearly equivalent, and in particular all equivalent to just using N. Now how can that be?

Isn't it clear that this works, and that there can be no set of objects you could label starting at 0 that you couldn't also label starting at 1? — Srap Tasmaner

You can't do that. Logic prohibits it. There are more "labels" in N0 than there are in N.

And you're relying on a deceptive "proof". You think that, just because you can create a bijection between any proper subset of N with any equally sized subset of N0, that N and N0 are equal in size.

Why do you say the topic is irrelevant"? The concept of infinite is commonly used in mathematics, so there must be at least some relevance.

Oh I'm not referring to the concept of infinity, that you correctly note is important. Rather what the OP specifically referenced, which is the infinite numbers between infinitely minute numbers.

Isn't it clear that this works, and that there can be no set of objects you could label starting at 0 that you couldn't also label starting at 1?
— Srap Tasmaner

You can't do that. Logic prohibits it. There are more "labels" in N0 than there are in N. — Magnus Anderson

So are you saying there could be a set such that you could label every member of that set starting with 0, but you could not label every member of that set starting at 1? Is that your claim? (And I guess also that "N0" is such a set.)

The symbol we're talking about is this: — Magnus Anderson

That's a group of symbols... so you mean the $f$? And your claim is that the definition
$f: \mathbb{N} \to \mathbb{N}_0, \quad f(n) = n - 1$
"specifies what that symbol can be used to represent", but not that what it represents is not somehow contradictory? OK. Then over to you. If you think there is a contradiction here, it's up to you to show it. Exhibited it as derivations of ⊥.

Hence we come back to what it is for a mathematical object to exist, and the point you seem not to have accepted, that for "classical" maths ∃x P(x) is true iff P(x) is derivable in a consistent formal system - as here. You appear to be rejecting that rejection, while claiming not to reject it. All very difficult to follow. Hence, the impression of an intellectual drift on your part rather than any actual argument.