\\Q(n) ≡ ∀k,m∈ℕ ( k+m = n ⇒ ( m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ) ⇒ ∃x,y∈ℕ ( k·x = m·y+1 ) ) )

Given a ∈ ℕ
	If ∀i∈ℕ ( i<a ⇒ P(i) )
		Given b ∈ ℕ
			Given c ∈ ℕ
				If b + c = a
					If  c > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | b ∧ d | c )

						If b = c
							c > 1 ∧ c | c ∧ c | c
							c > 1 ∧ c | b ∧ c | c
							∃d∈ℕ ( d > 1 ∧ d | b ∧ d | c )
							¬∃d∈ℕ ( d > 1 ∧ d | b ∧ d | c )
							⊥
							∃x,y∈ℕ (b·x = c·y+1 ) ) )

						If b < c
							If b = 0
								c > 1 ∧ c | 0 ∧ c | c [c|o lemma]
								c > 1 ∧ c | b ∧ c | c

@user21820 My progress so far with PA5.

@Prithubiswas I don't understand why you wrote "Let u ∈ ℕ such that b.u ≥ c", because it isn't what you want, which is the next line.

I switched up by mistake.

And it seems you're following the proof outline I gave, so why not do the next few steps? Or are you trying to see if you can figure out without looking?

@user21820 Yes I am following your 2 hints. But at this point I am not making any progress . Maybe I have to think more 🤔.

@Prithubiswas Oh so you haven't looked at the outline yet? Ok no wonder you don't have the next step.

No I haven't looked at the outline yet. I want to develop the ability to solve a problem with as less hints as possible.

That case is k > m, and the point of "let x∈ℕ be minimum such that k·x ≥ m" is to get as close to m as possible using a multiple of k.

Then look at the discrepancy and try to use the strong induction hypothesis.

Ugh I shouldn't have used "x" there in my hint... conflicting with my later use of "x".

Anyway, using your variables, you have b·u ≥ c and u is minimum. So what can you say about the leftover?

Sorry the case was "k < m" or "b < c" in your variables; I mixed up.

I just realized that for some reason I missed a simpler proof that doesn't require the use of well-ordering inside the strong induction. I guess I am just too used to whacking a problem with powerful tools that I didn't see the subtle solution. You can try finding this simpler proof if you want, meaning just the first hint suffices. @Prithubiswas @F.Zer

Hey! Is this room meant to be a room where anyone can ask a question concerning basic mathematics? I have questions regarding sets and how they work

@F.Zer @Prithubiswas: Second hint for the simpler proof: Inside the strong induction on Q, given k,m∈ℕ satisfying m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ), first prove k ≠ m, then split cases. If k > m, apply the induction property to get a solution for (k−m,m) and then from that get a solution for (k,m). If k < m, similarly get a solution for (k,m−k) and from that a solution for (k,m).

@MaxH Yes. What is your question?

@user21820 In everyday maths one usually uses naive set theory, meaning every collection of "objects" is a set and the objects are called the elements of a set. This is basically the perspective I have, meaning I do not know much about any other set theory. When first writing down a set such as $\{1,2,3,4,...\}$ or $\{A,B,C,...\} what is meant by this? Is this the collection of symbols/strings that are in the set? (assuming that I have not yet defined natural numbers).

@MaxH I'm not sure what you mean by "naive set theory". Too naive and you would have a useless system that proves 0 = 1.

What I mean is that I could also define the natural numbers to be $\{I,II,III,IV,...\}$ and the only difference between this and $\{1,2,3,...\}$ would be the strings/symbols used, so this should make a difference right? Probably no one would say that $\{1,2\}=\{I,II\}$ as sets.

And if you haven't defined "1", then you cannot use it anywhere in mathematics, regardless of whether using set theory or not.

Same for "A".

I thought this is a term that is used commonly. It means, as far as I know, that a set is just an unordered collection of objects that are distinct.

Ok, but in introductory courses, sets such as $\{A,B,C\}$ or $\{I,II\}$ are used, how can this be?

Thank you for your help by the way.

@MaxH Whichever introductory course ever writes "{I,II,III,IV,...}" without first defining I,II,III,IV is a bad course.

1,2,3 are understood universally as the first few positive natural numbers, so there's less problem if they write "{1,2,3,...}".

But still the point remains that 1,2,3 must be defined or declared as constants if you want to do rigorous mathematics.

Alright, so the way this works is the following, as far as I understand: One assumes that the natural numbers are a set containing objects (one doesn't know what objects are). One axiom now states that one of the objects is $0$, therefore I give the object this symbolic expression. Another axiom states that the successor of every preceding natural number is also a natural number. Now I define the symbols $1:=s(0), 2:=s(1)$ and so on, right? I could do the same thing for the symbols $0,I,II,III$

Correct.

what would make the sets $\{0,1,2,3,...\} and $\{0,I,II,III...\}$ different?

One would not consider them to be equal right?

Uh... In the first place you can't write down sets like that. Every single occurrence of "..." is found almost only in non-rigorous mathematics.

But you know what I mean, right?

Secondly, don't talk about set theory first. Understand basic PA (Peano Arithmetic) first; "1+1" and "2" are different strings. But 1+1 = 2.

In the books I read this is common usage, so I adapted it.

I know what you mean, but we need to be more precise than lousy books if we want to have a proper understanding.

That 1+1=2 is the case because they are defined to be the same object, as far as I know. I understand this I think.

The way I imagine this is that a set is a "space" with some objects in it, that I imagine to be points in the space. I can give those objects different names, such as 1 or also 0+1, that doesn't change that they are the same object.

That's not really a correct reason. 3·2 = 1+5.

And "3·2" and "1+5" are not names, unlike maybe "2". You might have defined "2" to mean "1+1", but it doesn't explain why 3·2 = 1+5.

That 3 * 2=1+5 is because 3*2 is defined to be the object that one gets when adding 2 3 times, thus 3*2=2+2+2 which is defined to be the same object as 6 which is again defined to be the same object as 1+5

That's better but still not really correct.

What would be the correct way then?

Is my "visualization/intuition" false as well?

"3·2" is defined to satisfy the equation "3·2 = 2+2+2".

But 3·2 is simply 6, not something "defined".

You need to always precisely distinguish between the string and what we intend/define it to represent.

1+5 is also simply 6.

What do you mean by "is symply"? As far as I understand I would need to define the symbolic expression "1+5" to refer to the same object as the symbolic expression "6"

Which can be seen by the "point in space" visualization.

No that's now definitely wrong.

This is the way I read it in books. I don't know another explanation.

The ":=" symbol is used for addition. Meaning, for example, $1+5:=6$, which should mean that its defined to be the same object that 6 refers to, shouldn't it?

I see your problem now.

I couldn't get a good grasp of what your problem was until your last message. The short answer is that you necessarily cannot think of everything in terms of "definitions". Mathematics is based on definitions and either axioms or deductive rules or both. Not just definitions.

Ok, but how does that contradict what I was saying?

I am still unsure what is wrong about what I wrote.

Basic arithmetic is best captured by the axiomatization of ℕ called "Peano Arithmetic" (which you can find as a section halfway down this post). Take a look and tell me whether you understand the logical symbols and what each axiom in the list states.

For now you can ignore the induction axioms. Just tell me whether you understand the PA− axioms.

Yes I think I do. I used the 5 axioms that 0 is a natural number, the successor is a natural number and so on. I thought these are the "standard" ones.

In your post you write that you adapted them from Wikipedia. And in the addition section of that wikipedia article it says that addition is recursively defined, for exmaple 0+a=a.

This should be what I meant, right? But yours seems to be a different axiomization

@MaxH No, you're looking at the wrong place. The section that says addition can be recursively defined in set theory or second-order logic have nothing to do with what is now named PA.

I linked specifically to only one section, not the entire article. And wikipedia is not a good place to learn anything, although it is a good place to find better references.

@MaxH Those are outdated and impractical. But let's get back to the point. You can see that there is no "definition" anywhere (in the axiomatization I gave you). These are just pure axioms. They don't define anything in terms of anything.

Also, suppose you define "3" to represent "(1+1)+1". Then you can prove from the axioms the sentence "3 = 1+2". There is again no notion of definition except in the definition of "3".

Definitely no "definition" of "+" or "1+2".

Yes, I looked at both sections. The one that you linked seems to have it as an axiom.

I just did that in order to find the axioms that I used, just to make sure.

So do you get the point here? It's important to understand what 100% correct mathematics is for basic arithmetic, before we move on to anything to do with sets.

Ok, I see that they are different.

But what difference do they really make?

I mean, would it make a real difference if I used the axioms that I am used to?

In this case the answers I gave above, that 1+5 is defined to be the same object as 6 would be correct, wouldn't it?

@MaxH No. It's still wrong. As I said above, that section claiming that we can define addition and multiplication recursively has nothing to do with PA. We cannot do recursive definitions of that kind within PA. We can do it within a strong enough foundational system, but you certainly don't know how to rigorously do it at this point, so don't confuse yourself with it now.

Ok. I certainly do not have any knowledge in set theory or logic, which is a problem I guess.

I only used "everyday mathematics" and it has never been talked about which logical/foundational system we are using

This is why I wanted to use the axioms I am familiar with, assuming the system that we are in is strong enough.

Couldn't I assume that I work within this strong foundational system in which I can use those axioms?

Let's put it this way; you wouldn't need to ask me about "{1,2,3,...}" if you knew enough about the basic logic underlying mathematics. If you want to clear up that conceptual misunderstanding, you need to focus on the basics, not try to run when you cannot walk yet.

Right now, just recognize that there are no definitions needed in PA. For convenience, we define "2" to mean "1+1" and "3" to mean "(1+1)+1", but the arithmetic operations themselves are not defined but simply governed by the axioms. Do you get that or not?

By writing "2" to mean "1+1" you are saying that they are both the same object? If you mean that, then yes, I understand that.

That's not the main point......

> the arithmetic operations themselves are not defined but simply governed by the axioms. Do you get that or not?

Yes I get that its an axiom that "2=1+1". I suppose that I don't see what difference it makes for it to be an axiom or a definition. However, the axiom says that within my system "2=1+1" is correct, right?

What? Are you actually reading what I wrote? Or is your native language not English?

My native language is indeed not english.

I said that the main point you need to understand is that "+" and "·" are not defined but simply governed by the axioms.

"1+(1+1)" is not defined as referring to the same object as "(1+1)+1".

From the axioms you can prove "1+(1+1) = (1+1)+1". And that's all there is to it. A plain equality. They are simply equal, not by definition but by proof from axioms.

Yes, but that is also what I meant, sorry if I said something misleading. Surely it is an axiom in the list of axioms you provided and no one is saying that it is a definition in the axioms you presented.

As far as I know, axioms are just assumed to be true, thus by doing this, the statement $1+1=2$ is true, assuming the axioms you linked.

No you are still not getting it. There are many things that are not in the list, such as "(1+1)·(1+1) = (((1+1)+1)+1".

Even "1+(1+1) = (1+1)+1" is not in the list, although it directly comes from one of the axioms, but that requires a deductive step.

Yes, but I can deduce this assuming the axioms.

So it is logic and the axioms that govern "+" and "·", not definitions. Do you get that?

Yes, I think I do.

Good. It is exactly the same for set theory. We have a specification of what are the axioms (and there are infinitely many of them), and that's all there is to govern set theory.

When people write "{1,2,3,...}", anyone who knows basic logic can translate that into a rigorous version, say { x : x∈ℕ ∧ x>0 }.

The first version is just non-rigorous and it really makes little sense to ask what it means. What you can ask is what the rigorous version means.

Now you probably can see where this is going. "{I,II,III,...}" makes no sense at all, and if you are asked to translate it into a rigorous version, guess what you will give me? { x : x∈ℕ ∧ x>0 }.

→ 8 messages moved to Sandbox

And the rigorous version is having "abstract objects" that are not referred to by numbers, whereas in {1,2,3,...} I have symbolic expressions that are supposed to refer to these abstract objects?

@MaxH Maybe that's one way to put it, but I'm uncomfortable with discussing expressions that are non-rigorous simply because I can't even tell what precisely people have in mind when they write them.

The same would then apply to {I,II,III,...} since they are defined to be (which means that they are names) for the objects in the natural numbers.

Well, I am just trying to make sense of what is written in introductory math books..

@MaxH Yes, if you pre-define I = 1 and II = 2 and III = 3, then {1,2,3} = {I,II,III}.

This is by the axioms governing the term-forming syntax using the curly braces and commas.

{1,2,3} = { x : x=1 ∨ x=2 ∨ x=3 }. And there are rules/axioms governing the membership in { x : x=1 ∨ x=2 ∨ x=3 }.

Yes, that would also make sense using the intuition I gave earlier, which is hopefully fine.

Yes, that makes sense.

about the putting efforts bit I am putting efforts I learnt PL including the syntax and what a WFF, string etc is in PL on my own after you told me to

In the book I read it says though, that one could also introduce the number system {I,II,III,...} and show that this obeys the axioms. He then goes on saying that one could argue that this differs from {1,2,3,...} meaning that they are not equal but "only" bijective to {1,2,3,...}. Would this not contradict what we discussed?

@PaxDaga I told you to do the exercises. Why didn't you? I didn't ask you to do anything else, nor to read up on anything else, because all that would just confuse you and waste my time.

@MaxH I think it means that the author was not defining I = 1 and II = 2 and so on. See? This is why it pays to be precise.

We have no idea what the author had in mind, because there was no precision.

Yes, he must have not defined them to be equal, because that way the would obviously be equal. This is why I thought the difference lies in the "representation" or rather the use of symbols.

@MaxH But it isn't a matter of symbols, so I hope you have that concept cleared up.

Wouldn't that mean that any two models of the natural numbers are identical, since they only differ by symbols?

It is often said that they are bijective, which is obvious, but I wonder if they are litearlly equal.

Hmm I don't think you have cleared up that conceptual misunderstanding at all. I thought it was already clear earlier that this has nothing to do with symbols. If you define c = 3, then c is simply the same as 3.

Yes that is clear to me

@MaxH: I need to go now, but consider this. Take the list of PA− axioms, make a copy, and replace every "ℕ" in that copy by "M".

Do not add any other axioms (assumptions) about M or ℕ.

Now think a bit. You can do exactly the same basic arithmetic using either axiomatization.

Yes, I can see that

However, the objects in ℕ and the objects in M may be completely different, especially if we use a different "0" and "1" as well.

Okay, I think that is where I am going wrong

Just to make things simple, replace "0" by "z" and "1" by "i" too in the copy.

Using different $N$ and $M$ which might have different objects. I did not think about that

You can see that nothing tells you any relation between the members of ℕ and those of M.

But they internally behave the same way.

Thank you for your help and time. I hope that I can ask some follow-up questions in case they come up.

@MaxH Sure. See you next time.

Have a nice day!

@MaxH Same to you!

This room is for learning, not pretending to know. Anyone who thinks they know everything already are not welcome here.

@user21820 I am not sure what you meant by "leftover".

@Prithubiswas b·u is just barely more than c. By how much? What can you say about that?

You mean:

b·u ≥ c
If b.u = c
    .
    .
If b.u > c
    Let p ∈ ℕ such that b.u = c + p
    b.u = c + p
    .
    .

@user21820 is this what you meant?

@Prithubiswas That's right! But it's good to use the lemma ∀x,y∈ℕ ( x ≤ y ⇒ ∃z∈ℕ ( x+z = y ) ), so that you don't unnecessarily split case. And you can prove good stuff about p. That's the whole motivation for using well-ordering in that way in the first place.

Which is why I described it as "whacking", because when I was looking for a proof I immediately saw that if k < m then I can get a multiple of k minus m to be small enough to apply the induction hypothesis, so I just "whacked" using well-ordering to get what I wanted. But it turns out that if we just try (k,m−k), it already works (with a different path to the conclusion).

@user21820 What are some of the things I should try to prove about "p" ?

@Prithubiswas It's small.

What does the well-ordering automatically imply about it?

@user21820 You mean some upper bound for "p"?

Do you have one?

not yet. But is that what you meant by "It's small"?

Yes. If you want me to be less vague in my hints, let me know.

→ 3 messages moved to Sandbox

@PaxDaga: I already told you what to do. Stop spamming this room.

→ 2 messages moved to Sandbox

Hey @user21820 I have a follow up question, in case you want to help and have some time, just let me know.

@MaxH Just post your question. I'll respond when I have the time.

Alright

So I think what confused me was the following. I thought that one wants to define what a set of natural numbers is rather than what the set of natural numbers is. If I assume axiomatically that there exists a set called \mathbf{N} that satisfies the Peano-Axioms, then one would have one collection of objects, namely the ones that are in this assumed set. Thats why I can't have \mathbf{N}=\{I,II,III,IV,...\} unless i explicitly define $I$ to be the 1 element, $II:=s(1)$ and so on.

However, one oculd also define any set to be called a set of natural numbers, if it satisfies the axioms. That way, I could regard a set whose objects are {I,II,III,...} and prove that this actually satisfies the peano axioms. I just wonder, what guarantees me that there is a set {I,II,III,...}? In other words, what guarantees me that there is a set with different objects than the \mathbf{N} i defined in my previous message, such that I can define the objects in this new set to be I,II,III,...

This would then leave me with two different sets, since they contain different objects (potentially, I think one can't really say if they are different or the same here) that both satisfy the axioms. Thus they are isomorphic/bijective but not equal.

I hope this isn't to confusing, please ask if something is unclear.

@MaxH That's right. In any foundational system for mathematics, something guarantees a model of PA (i.e. a structure ⟨ℕ,0,1,+,·,<⟩ satisfying the axioms of PA). In the system in the post I linked you to, I explicitly do so. In vanilla ZFC set theory, it takes a lot of work to prove the existence of a model of PA. But every system must do so otherwise we will never call it "foundational". That's why I explicitly do so rather than sneak in something like the "axiom of infinity" in ZFC.

And what guarantees a distinct model of PA? Well it's actually easy. Just define ⟨M,z,i,p,t,l⟩ = ⟨ ℕ[>0] , 1 , 2 , ( M x , M y ↦ x+y−1 ) , ( M x , M y ↦ (x−1)·(y−1)+1 ) , < ⟩ and check that it is also a model of PA.

I just shifted everything by 1.

Thanks! But I didnt actually mean to have two different models of PA in the sense you gave it. I rather wanted the existence of a set of the form {I,II,III,...} which differs from the N i gave. One could generalize and ask if for all symbols I can come up with, in this case the symbols I,II,III,... there exists a set that I can define its objects to be exactly those symbols. And in this case I explicitly want its objects to be different from the objects in the set N.

@MaxH ℕ[>0] ≠ ℕ, so it does differ from ℕ.

In particular, there must be an injection from ℕ into S, otherwise you can't do it.

So it becomes kind of a dumb question because an injection from ℕ into S almost trivially yields a model of PA whose domain is contained by S. If you want exactly S, then there must be a bijection from ℕ to S, which makes the question become even dumber.

And there is no way around this.

I'm going off now, so I'll respond next time!

Im not sure what you mean by a set S of objects. Suppose you give me some random symbols you like, like idk A,B,C,I,III,\alpha,\lambda (pretend that you give me an infinite amount of symbols). Can there always be a set that has these symbols as objects? And in this case I want countably infinitely many that are different from the objects that lie in N.

What I have in mind is that in everyday mathematics basically everything I can write down is a set. Thus I would like to know how this can be formalized or if this is the case. What even would a "collection of objects" be? Objects are as far as I know really abstract and have no definition (maybe I am wrong here).

But in the sense described above I would like to find objects that differ from other objects and in this sense control them.

Its a bit difficult to find words for what I am looking for, I hope I described it well enough.

@user21820 See you next time!

@user21820 This message should be quoted here. Do I need to assume that such an M exists by axioms? Or do I somehow get this M as well? Because in this case I would have possibly different objects than the ones in N, as you say, but I could use the symbols I want for the objects in M, thus gaining a set with different objects and the symbols I want.