An argument involving well-orders

[SSequence]

Few days ago, I posted an answer for a mathoverflow question. The question was of elementary nature.

The question had a lot of views, and my answer didn't get any upvote. Now since I got a downvote, perhaps there was a (major) mistake somewhere in the argument I posted? Tbh I was reasonably confident about my answer [since its not that unusual for accurate answers to go by with 0 upvotes], but the downvote def. confused me a bit.

I left a comment asking the reason for downvote, but it is not very likely that will get a response (would be good if it gets one). It is hard to tell whether the downvote is just impulse or based upon identification of an actual (major) mistake in answer. I would definitely like to know if its the latter.

I didn't think about the answer quite thoroughly (since I posted it after few hours of thinking), so maybe there is some aspect I missed? Nevertheless, I should say that the argument is of basic nature and it looked OK to me on few cursory/initial checks. But sometimes one can keep thinking thinking about along the same (wrong) lines when re-checking (especially when re-checks are not thorough enough). So a "second opinion"/"further input" would be quite helpful.

Link: https://mathoverflow.net/questions/381527/the-sum-of-two-well-ordered-subsets-is-well-ordered

Here is the question (not mine):

if $A,B$ are two well-ordered subsets of $\mathbb{R}$ (or any ordered group — with the induced order of course), the subset $A+B:=\{a+b\,|\,a\in A,b\in B\}$ is well-ordered. How does one see that?

Here is the answer I posted:
Let's suppose the well-order of $A$ and $B$ have order-types $p$ and $q$ respectively. So we use the notation $a_i$ ($i<p$) to denote the $i$-th element of $A$. We have $a_i<a_j$ whenever $i<j<p$. Similarly, we use $b_i$ ($i<q$) to denote the $i$-th element of $B$.

Since $A+B$ is already linearly-ordered, we want to prove that $A+B$ has no infinite descent. In other words, we want to disprove the existence of a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that (i) For all $x$ in domain of $f$ we have $f(x)=a_i+b_j$ (for some $i<p$ and $j<q$) (ii) $f$ is a 1-1 function (iii) For all $i,j \in \mathbb{N}$ (with $j>i$) we must have $f(j)<f(i)$.

So if we have $f(x)=a_i+b_j$ then we can write $\mathrm{first}(f(x))$ and $\mathrm{second}(f(x))$ to denote $a_i$ and $b_j$ respectively. Now we can define $\alpha_0=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \}$. Let's denote $n_0 \in \mathbb{N}$ as the "last" value for which $first(f(n_0))=a_{\alpha_0}$.

Now we define $\alpha_1=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \wedge x>n_0 \}$. Let's denote $n_1 \in \mathbb{N}$ as the "last" value for which $first(f(n_1))=a_{\alpha_1}$.

Now because of $\alpha_1>\alpha_0$, we should get $a_{\alpha_1}>a_{\alpha_0}$ and hence $second(f(n_1))<second(f(n_0))$. So it seems to me that when we define $\alpha_2=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \wedge x>n_1 \}$ and $n_2$ as the "last" value for which $first(f(n_2))=a_{\alpha_2}$, then we should have similarly $second(f(n_2))<second(f(n_1))$. The last inequality is supposed to follow from $a_{\alpha_2}>a_{\alpha_1}$ (because $\alpha_2>\alpha_1$).

The previous paragraph seems to be suggestive of defining $\alpha_i$, $n_i$ generally for all natural numbers $i$ and then creating an infinite descent for the second components:$...<second(f(n_3))<second(f(n_2))<second(f(n_1))<second(f(n_0))$.

And a comment regarding notation that I wrote:

It seems that instead of writing $\alpha_1=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \wedge x>n_0 \}$ it would probably be better to write something like: $\alpha_1=min\{\alpha \in Ord: \exists x \in \mathbb{N}(first(f(x))=a_\alpha \wedge x>n_0)\}$

 

[andrewkirk]

Now we can define $\alpha_0=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \}$

What do you mean by Ord? If you mean the collection of all ordinals, that is not a set, so you cannot simply use the axiom schema of specification as you have done here to define a set being all members of Ord that obey a certain criterion.

Secondly, you need an existential quantifier for $x$, so that you would write:
$$\alpha_0=\min\{\alpha \in Ord\ |\ \exists x\in\mathbb N: first(f(x))=a_{\alpha} \}$$

Thirdly, what do you mean by "last" in

Let's denote $n_0 \in \mathbb{N}$ as the "last" value for which $first(f(n_0))=a_{\alpha_0}$.

If you mean 'smallest' then 'last' seems a strange word to use rather than 'first'. If you mean 'largest' then you need to prove that the collection of all such values has a maximum.

I didn't read past there. Perhaps you can correct these problems. I suggest you try to do so and then see if you can continue the proof.

In general, you need to be more wary of unseen assumptions buried in your statements - eg that something is a set, or that a given set of integers has a maximum.

I don't think that justifies a downvote. I consider downvoting on places like stackexchange or overflow as unnecessarily aggressive. But I can understand how come prickly character may have gotten irritated at the uncareful presentation and taken the lazy way out of just downvoting rather than pointing out problems.

Also, I would not say the question has an elementary nature. It looks difficult to me.

 

[SSequence]

Few points w.r.t. post#1:
(1) In post#1, at some points comparison relation $<$ is used for real numbers and at some points it is used for ordinals.

(2) We can think of $first$ as a function $first:A+B \rightarrow A$. Similarly, we can think of $second$ as a function $second:A+B \rightarrow B$.

(3) If we have $first(f(i))=a_\alpha$ for some specific natural number $i$ and some specific ordinal $\alpha$, then there can't exist arbitrarily large natural numbers $j>i$ such that $first(f(j))=a_\alpha$. This justifies the use of the phrase/word "last" in post#1.

(4) When we write: $\alpha_0=min\{\alpha \in Ord: \exists x \in \mathbb{N}(first(f(x))=a_\alpha)\}$, the existence of minimum is justified due to a lack of infinite descent (in ordinals). If we want to be completely thorough, we could write a bit more working.

 

[SSequence]

What do you mean by Ord? If you mean the collection of all ordinals, that is not a set, so you cannot simply use the axiom schema of specification as you have done here to define a set being all members of Ord that obey a certain criterion.

Secondly, you need an existential quantifier for $x$, so that you would write:
$$\alpha_0=min\{\alpha \in Ord\ |\ \exists x\in\mathbb N: first(f(x))=a_{\alpha} \}$$

For the second comment, see what I wrote towards the end of post#1. I think writing something like:
$\alpha_0=min\{\alpha \in Ord\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$
is definitely better than:
$\alpha_0=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \}$
or
$\alpha_0=min\{\alpha \in Ord: x \in \mathbb{N} \wedge first(f(x))=a_{\alpha} \}$

With regards to first comment, if we are being really strict you are correct. But it is quite clear that $\alpha_0, \alpha_1, \alpha_2,...$ etc. will be well-defined since for all $\alpha_i$ we have $\alpha_i<p$ (with $p$ being an ordinal). So what I wrote for $\alpha_0$ correctly identifies an ordinal [rather than something too big to be a set]. I suppose we could also write:
$\alpha_0=\min\{\alpha \in Ord\ |\ \alpha<p \wedge \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$
or better (formally):
$\alpha_0=\min\{\alpha \in p\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$
Some further comments towards the end [1]. At any rate, this doesn't affect the main point of post#1. In case this is a point of confusion, the last definition [which strictly identifies a minimum of a set (in strict sense) of ordinals] can be taken for $\alpha_0$ (and similar definitions for $\alpha_1,\alpha_2,...$ etc.).

Thirdly, what do you mean by "last" in

If you mean 'smallest' then 'last' seems a strange word to use rather than 'first'. If you mean 'largest' then you need to prove that the collection of all such values has a maximum.

By "last" I did not mean smallest. I meant last occurrence. Because there are finite number of natural numbers $i$ such that $first(f(i))=a_{\alpha_0}$, the natural number $n_0$ is "last value" for which $first(f(n_0))=a_{\alpha_0}$[1]
When I wrote the original def. of $\alpha_0$ with $Ord$, I had in mind something like a "class set". For example, strictly speaking, of course we can't write $f:Ord \rightarrow Ord$ and say $f$ is a function (from perspective of set-theory). However, it is common to call such functions "class functions" (and they can be formalized).

So when I said "class set" above, I meant a function like $f:Ord \rightarrow \{0,1\}$ identifying the elements of $Ord$. For example, we could say something like "all limit ordinals" and it would be a "class set". Same for "all successor ordinals". For example, if we denote the class set for all successor ordinals as $S$, formally we would write it as:
$S=\{\alpha \in Ord \,|\, \exists x \in Ord(x+1=\alpha)\}$
Similarly the class set denoting all limit ordinals as $L$, we can write:
$L=\{\alpha \in Ord \,|\, \alpha \notin S\}$

So when we write $\alpha \in Ord$ instead of writing $\alpha \in p$, what I had in mind was:
(i) The initial specification for $\alpha_0$ identifies a "class set".
(ii) However, what follows after [the part $\exists x\in\mathbb N (first(f(x))=a_{\alpha})$] clearly makes it evaluate to minimum of a set (in strict sense) of ordinals.

So this was my perspective in writing $\alpha \in Ord$ instead of writing $\alpha \in p$. At any rate, this is a tangent to main point in post#1. Since it came up, I thought I would describe what I was thinking. I do agree that writing $\alpha \in p$ seems to be more well-suited since it identifies from the outset that we are talking about $\alpha_0$ as minimum of a set (in strict sense) of ordinals.

 

[SSequence]

So I think I will edit the overflow post with two changes. I was thinking about making these changes before, but didn't make them (to avoid small edits, since every edit is bumped). But these seem reasonably sufficient reasons for edit and do seem to make it easier to understand what I wrote.

(1) Changing:
$\alpha_0=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \}$
to:
$\alpha_0=min\{\alpha \in Ord\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$
or better yet [if the upper-bound was a complicated, non-obvious ordinal (or worse it didn't exist), then there would be a point to use the second definition instead of third. In this case, the below definition seems better than second]:
$\alpha_0=min\{\alpha \in p\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$

EDIT:
One issue I see with the third definition is that for non-limit the "intended definition" would need to be (even though the previous one would work too ... but we will need to add some extra justifications):
$\alpha_0=min\{\alpha \in p+1\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$

Of course we might just define (for both limit and non-limit $p$):
$\alpha_0=min\{\alpha \in p+1\ |\ \exists x\in\mathbb N (first(f(x))=a_{\alpha}) \}$
END

(2) Mention the points I wrote in post#3. They seemed reasonably clear, but it seems it wouldn't hurt to add them.

=============================

Anyway, in case it seemed that I made a thread because of downvote. Well perhaps sort of, but that's a tertiary reason. Net negative score for answers don't matter as much for questions [where net negative leads to deletion]. I wanted to confirm/double-check whether I had a mistake in reasoning or not. In-case of a mistake somewhere in reasoning, please do let me know.

 

[SSequence]

Here is the (slightly) modified version of post#1 with the changes described in previous post incorporated. The main argument (and the text) is unchanged, but it should be a bit easier to read (better notation, some indentation).

BEGIN:
"Let's suppose the well-order of $A$ and $B$ have order-types $p$ (assume limit for simplicity) and $q$ respectively. So we use the notation $a_i$ ($i<p$) to denote the $i$-th element of $A$. We have $a_i<a_j$ whenever $i<j<p$. Similarly, we use $b_i$ ($i<q$) to denote the $i$-th element of $B$.

Since $A+B$ is already linearly-ordered, we want to prove that $A+B$ has no infinite descent. In other words, we want to disprove the existence of a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that (i) For all $x$ in domain of $f$ we have $f(x)=a_i+b_j$ (for some $i<p$ and $j<q$) (ii) $f$ is a 1-1 function (iii) For all $i,j \in \mathbb{N}$ (with $j>i$) we must have $f(j)<f(i)$.

So if we have $f(x)=a_i+b_j$ then we can write $first(f(x))$ and $second(f(x))$ to denote $a_i$ and $b_j$ respectively. Now we can define $\alpha_0=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha)\}$. Let's denote $n_0 \in \mathbb{N}$ as the "last" value for which $first(f(n_0))=a_{\alpha_0}$.

Now we define $\alpha_1=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha \, \wedge \,x>n_0)\}$. Let's denote $n_1 \in \mathbb{N}$ as the "last" value for which $first(f(n_1))=a_{\alpha_1}$. Now because of $\alpha_1>\alpha_0$, we should get $a_{\alpha_1}>a_{\alpha_0}$ and hence $second(f(n_1))<second(f(n_0))$.

So it seems to me that when we define $\alpha_2=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha \, \wedge \,x>n_1)\}$ and $n_2$ as the "last" value for which $first(f(n_2))=a_{\alpha_2}$, then we should have similarly $second(f(n_2))<second(f(n_1))$. The last inequality is supposed to follow from $a_{\alpha_2}>a_{\alpha_1}$ (because $\alpha_2>\alpha_1$).

The previous paragraph seems to be suggestive of defining $\alpha_i$, $n_i$ generally for an arbitrary natural number $i$ and then creating an infinite descent for the second components: $...<second(f(n_3))<second(f(n_2))<second(f(n_1))<second(f(n_0))$. However, this descent goes against the assumption of $B$ being a well-ordered set.Few clarification points:
(1) At some points comparison relation $<$ is used for real numbers and at some points it is used for ordinals.
(2) We can think of $first$ as a function $first:A+B \rightarrow A$. Similarly, we can think of $second$ as a function $second:A+B \rightarrow B$.
(3) If we have $first(f(i))=a_\alpha$ for some specific natural number $i$ and some specific ordinal $\alpha$, then there can't exist arbitrarily large natural numbers $j>i$ such that $first(f(j))=a_\alpha$."
END============================================================================================================================================================================================================================================================

P.S.
One miscellaneous point that I think is worth a brief mention (since I can't edit post#4). When talking about "class sets" towards the end of post#4, one thing to note is that the "minimum" of a "subset of $Ord$" [informal sense] should always be a well-defined ordinal just like the minimum of a "subset of an ordinal".

Post#4 was a fairly scattered/unfocused. The brief point here is that whenever (for defining an ordinal) we write something like:
$min\{ \alpha \in Ord \,|\,$ "insert some condition" $\}$
it is as good as:
$min\{ \alpha \in \beta \,|\,$ "insert some condition" $\}$ ($\beta$ being a fixed ordinal)

Even though the second notion is formal and the first one is (initially) informal, the first notion can be made formal [and hence importantly, it isn't ambiguous or ill-defined]. So I don't think there is an issue with using the first notion.

 

[Office_Shredder]

first and second aren't even well defined as functions, are they?

 

[SSequence]

first and second aren't even well defined as functions, are they?

Eh, good point. Thanks for pointing this out. It is quite helpful and I think you are right. That was silly on my part indeed.

It seems one fix is to do something like this:
We define:
$first(r)=min\{x\in A\,|\, \exists y \in B (x+y=r) \}$
$second(r)=r-first(r)$

But I need to think over it a bit probably. It seems that in general a definition such as one given for $first(r)$ wouldn't necessarily be well-defined [because the set over which we are taking the min has to be non-empty and needs to have a minimum element or better yet ... well-ordered].

However, because $A$ is assumed to be well-ordered, this definition seems to become justified [e.g. any subset of a well-ordered set is well-ordered]. Because here, assuming $r \in A+B$, the set $\{x\in A\,|\, \exists y \in B (x+y=r) \}$ is a (non-empty) subset of $A$.

Edit:
I guess another alternative definition for $first(r)$ (with $r \in A+B$) could go like (this should be equivalent to def. just above it seems):
"Find the smallest value $\alpha<p$ such that $a_\alpha+y=r$ (where $y \in B$). Then $first(r)=a_\alpha$."

Note that some such value $\alpha$ would exist simply because of the virtue of $r \in A+B$ and $A=\{ a_i\, |\, i\in p \}$ (assuming limit $p$).

 

[SSequence]

Just in case it was a bit unclear, at least as I understand currently, the definition(s) of the function $first$ and $second$ I wrote in last post (post#8) together with what I wrote in post#6 [under the begin and end headings] or in OP [but see comment towards end of OP] should be fine. If there is still something that is missing/unclear (or incorrect), then please do let me know.

========================================

As mentioned in post#7, the original description of $first$ and $second$ was indeed ill-defined. As an example suppose that:
$\{4,6\} \subseteq A$
$\{4,6\} \subseteq B$
Then we have:
$10 \in A+B$

However, now if this value $10$ belongs to $range(f)$, then it is ill-defined as to what value of $first(10)$ would be since:
$4+6=6+4=10$

 

[fresh_42]

I think you use a lot of concepts without actually knowing how. E.g. the problem with the definition of $A+B$ where you used the projections 'first' and 'last', but you do not have a direct product, so what is it? An example with numbers cannot be generalized. You can always use the lexicographic ordering on the pairs of $A$ and $B$, however, you used a sort of addition.

Moreover, it is never a good idea to discuss the same subject at two places at the time, which has no clear answer since the problem is ill-defined. Mathoverflow requires a certain level of knowledge compared to the ordinary Stackexchange math page. I did not get the impression that you have this knowledge on set theory and logic, i.e. a professional level, since otherwise you would not use the language you used (begin, end, first,second etc.). This might explain the downvote.

However, your basic questions were: a) Am I right?, and the answer is 'No', simply because you are far too vague in your wording. Set theory and logic requires an especially precise usage of terms, definitions and language in general. If you do not use this strict corset, you are almost automatically wrong. b) Why I got the downvote?' I think this thread offered more than one reason why. Nonetheless we could only guess and guesswork is outside our mission.

This thread is closed now.