6

Can a totally ordered set with a last element but no first element exist, or is this contradictory? An example of such a set would be a set that is ordered from largest to smallest, with there being no largest element: "...... > 5 > 4 > 3 > 2 > 1" or vice versa such as - "....... < -3 < -2 < -1 < 0".

This question arises from the fact that I got into an exchange with a friend of mine regarding infinite regresses, which I asserted, in terms of causation, are logically coherent. He stated that the mathematical equivalent of such is absurd, stating the following (my paraphrasing of what I understood him to be saying):

"If you were to stipulate A as the last element such that A cannot exist within the set unless it is proceeded by B, then this is to stipulate an infinite number existing, which doesn't exist. The reason for this is that if each element depends on the element prior to it, and the elements go back infinitely, then A relies on an element infinitely prior to it, that element can either be infinite or finite, if it is finite, then it is not infinitely prior to A, meaning that it (A) relies on an actually infinite number or index, which is NaN. What I am trying to point out, is that if A is considered the last element, which each element depending on the last ad infinitum, then A must be dependent on an element infinitely prior to itself (seeing that dependency is transitive), and the index of that element must either be finite or infinite, but it cannot be finite, meaning that it must be infinite, but infinity is not a number, resulting in a problem."

This seems to make sense, but something about it feels very off, I am not a mathematician nor am I intimately familiar with mathematics (I haven't engaged with anything beyond two basic introductory discrete math classes), could someone please clarify this?

Thank You

Improve this question
4
  • 2
    Frankly speaking, I'm a little bit puzzled by the way you are mixing negative integers with "infinite regress"... You received a lot of good answers regarding the mathematical side: we have no issue with it. Maybe it is worth considering that there is no reason to "read" the sequence of (negative) numbers in a "temporal" way nor as a sort of "causal chain". Maybe the physical universe is finite and it have a definite start (and a future end) and at the same time the infinity of numbers is a "useful" product of our mind.
    – Mauro ALLEGRANZA
    Jun 22 at 8:17
  • 1
    I OTOH believe the negative integers are a mental construct created by infinite regress in aligniment with a teleological aim and salute your interpretation of them as generative language and not objectively existing.
    – J D
    Jun 22 at 19:19
  • 1
    That there are sets with such properties (e.g. gnasher729's answer) is my standard counterargument to "infinite regress is obviously impossible". :-)
    – Pablo H
    Jun 23 at 14:00
  • 2
    You have answered your own question with the example "....... < -3 < -2 < -1 < 0"
    – Daron
    Jun 23 at 17:35

6 Answers 6

Reset to default
13

Can a totally ordered set with a last element but no first element exist, or is this contradictory?

Taking the usual mathematical definition of total order, and taking "last element" to mean an element l such that all other elements of the set are ordered before l, and supposing we accept infinite totally ordered sets at all, yes, such sets can have last elements. Start with any such set S and its ordering relation R, and suppose that it does not already have a last element.

  • If S has a first element, f, subject to R
    Define relation R' for elements a and b of S as a R' b if and only if b R a. Then R' is a total ordering over S, S is still infinite, and f is the last in S relative to R'.

  • If S does not have a first element subject to R
    Choose any element e of S. S has no first element relative to R, so the set of all elements of S that are ordered before e must be infinite. The set consisting of e and all its predecessors is also infinite, it is totally ordered by R, and it has e as its last element.

Alternatively, if we have an infinite set S that is totally ordered by a relation R, such that S has no last element relative to R, then we can form a totally ordered set with a last element by adding one to S. That is,

  • choose an arbitrary l that is not a member of S.
  • define S' as the union on S and {l}.
  • define R' over S' as a R' b if and only if a and b are in S and a R b, OR b == l.

Examples: the negative integers have the desired properties under the usual < relation. So do all real intervals that are closed on the right and open on the left. And the extended real numbers less -∞.

The argument presented to the contrary has numerous flaws, among them:

  • It relies on the premise that no infinite number exists. There are no such numbers in the real numbers, but the extended real numbers do contain infinite numbers. So do the Cardinal Numbers.

  • It relies on being able to assign integer indexes to the elements of the set. This is possible for the rational numbers (though the indices do not correlate with numerical order), but not for the real numbers.

  • It relies on each element of the set having an immediate predecessor. This is true for the integers, but not for the rational numbers under the usual < relation.

  • It relies on the proposition that the last element "depends on" all the prior elements, but "depends on" is not well defined, and there does not appear to be a consistent way to define it that supports the argument.

    Would your friend object to the premise that each element of the set is related to all the infinitely many others via the ordering relation? Then their issue would not be with there being a last element, but with there being any infinite, totally ordered sets at all.

    Or if your friend were thinking in terms of constructing one element from another, then they would just be wrong. One does not need to generate the last element from all the lesser ones. If one even wants to define a method of generation at all, then one can start from the last element instead of ending with it.

Improve this answer
12
  • 1
    "So do all real intervals that are closed on the right": ...and open on the left. (Otherwise the interval would have a first element as wall as a last element.)
    – TonyK
    Jun 22 at 18:25
  • 2
    @MaxMaxman: xis an immediate predecessor of y if x < y and there is no intermediate element z such that x < z < y. So you can see that no rational number y has an immediate predecessor x, because the rational number z = (x + y)/2 is an intermediate element.
    – TonyK
    Jun 22 at 18:31
  • 1
    @MaxMaxman, very qualitatively, you cannot assign integer indexes to the real numbers because the real numbers are too dense. There are more of them, in the appropriate infinite sense of "more", than there are integers (or rational numbers). But that's a topic for a 400-level Topology course.
    – John Bollinger
    Jun 22 at 19:03
  • 5
    The statement that you cannot assign integer indexes to real numbers, also known as uncountability of the reals, has a rather elementary proof-by-contradiction; see here for example. Nonetheless, it's the kind of proof that kind of knocks your socks off (it certainly did that to me when I was a mathematical baby).
    – Lee Mosher
    Jun 22 at 19:25
  • 1
    @MaxMaxman, that is precisely the question of countability. As this answer already says, it is possible to map (all) the rational numbers to (distinct) integer indices. You can then order them by those indices and have an immediate predecessor for each one (possibly with the exception of a first one). But that order does not look anything like the one produced by the < relation. Here's an example of such a construction: homeschoolmath.net/teaching/rational-numbers-countable.php.
    – John Bollinger
    Jun 24 at 13:37
6

Take the negative integers.

But remember that arbitrarily large numbers don’t require an infinite item. There are arbitrarily large and small integers, but no infinite ones.

Improve this answer
4

Your friend's reasoning doesn't hold up.

The argument that your friend is making is the following. Suppose that a totally ordered set with a last element, but no first element, exists. Then:

  1. Each element of the set depends on the element prior to it.
  2. The elements go back infinitely.
  3. Because of 1 and 2, each element depends on another, which depends on another, and so forth in an infinite chain.
  4. Because of 3, each element x depends on some element y which is infinitely prior to x.
  5. Because of 4, the index of the element y must be of infinite magnitude.
  6. However, the index of every element is an integer, and no integer is of infinite magnitude.
  7. Statements 5 and 6 contradict each other. Thus, we have proven, by contradiction, that a totally ordered set with a last element, but no first element, cannot exist.

The flaw here is that statement 4 does not actually follow from statement 3.

Your friend appears to be committing a logical fallacy, which we could call "generalizing to the infinite case." The general form of the fallacy is to note that a property holds in arbitrarily large finite cases or that arbitrarily large finite objects of some kind exist, and to conclude that the property also holds in infinite cases or that infinite objects of the same kind also exist. In this case, your friend is noting that each element (and, in particular, the last element A) depends on other elements that are arbitrarily large finite distances away from them, and falsely concluding that each element (in particular, A) depends on an element which is an infinite distance away from it (infinitely far from A).

However, your friend is in good company. Before the late 19th century, nobody knew how to reason rigorously about infinity, and pretty much every mathematician used generalizing to the infinite case as a tool for proving things, because it was the only thing we had. (Leibniz called it the law of continuity.) It was not until around the turn of the century that mathematicians such as Dedekind, Cantor, and Zermelo developed set theory to the point where it was possible to reason rigorously and reliably about infinite sets.

I think every modern set theory asserts that the set of all negative integers exists (except for those set theories which don't assert that infinite sets exist at all). In particular, ZFC certainly asserts that it exists. This contradicts your friend's conclusion.

Improve this answer
3

The axioms of choice and foundation are independent:

Of course the axiom of choice is consistent with the failure of the axiom of foundation. To get Fraenkel's model with the atoms, you usually start with a model of ZFA+AC. You can find the relevant proofs in Jech "The Axiom of Choice" in Chapter 4. (Note that atoms are usually obtained by weakening extensionality, not foundation. To get to foundation one has some way to go. You can find the details in Felgner's "Models of ZF set theory", and more about independence of various statements.)

I think there's an SEP article where they say something like "or you could let 0 be the largest number" but I'm not sure what they meant by that (and I can't find the article, with the actual precise wording, right now; I'll keep looking, though).

ADDENDUM: moreover, it seems possible to have "infinitely large numbers." That is what e.g. ℵ0 and ω are supposed to be, after all.

Regarding the broader issue, see esp. §2.4 of "Metaphysical Grounding" in the SEP.

Improve this answer
15
  • I'm not sure what the point of the quote is, but the Axiom of Choice is related to well ordering, not to total ordering, which is the topic of the question.
    – David Gudeman
    Jun 21 at 19:58
  • @DavidGudeman "A relation is a strict well ordering if and only if it is a well-founded strict total order. The distinction between strict and non-strict well orders is often ignored since they are easily interconvertible."
    – Kristian Berry
    Jun 21 at 20:00
  • @KristianBerry Thanks a thousand for the response (though I will probably need to spend a few hours reading up on the AC and the AF), could you explain how their being independent from one another has any bearing on the dilemma? In terms of the addendum, I am unsure if it works. If we are to say that A depends on some element indexed as omega (w), assuming that each element is dependent on the one prior to it, wouldn't the element after w be indexed as (w-1), which, as I understand it, isn't well defined. Perhaps you could clarify. Much appreciated
    – Max Maxman
    Jun 21 at 21:06
  • @MaxMaxman there's actually a surreal number known exactly as ω - 1. And the surreal number system is totally ordered. But so the relevance of the foundation axiom's independence, here, is that one can define nonstandard ordinals that proceed from the "head" stage of an infinitely descending sequence. Maybe these wouldn't be best called "ordinals" then, granted (I'm not 100% sure how consistent the terminology is, here, but note that Hamkins holds that "being an ordinal" is not always an absolute property).
    – Kristian Berry
    Jun 21 at 21:19
  • 2
    Not being a mathematician seems like a good reason not to bring up abstruse mathematical concepts like well-foundedness--the property that each subset has a least element. I just don't think that property is relevant to discussions of whether an infinite causal chain can exist.
    – David Gudeman
    Jun 21 at 22:38
3

(a): if you take the standard axioms, say ZFC, then yes. The naturals underneath the typical ordering form such a set.

(b): the key difference between you and your friend is how to mathematically model causation. If you model causation as a total order, then yes, an infinite regress might be logically coherent. Your friend, however, does not. If you can agree with how to model causation formally, you might find a resolution with your friend.

(c): for an example of how we might formally talk about causation, see Koons 1996 or https://plato.stanford.edu/entries/causal-models/. Koons is a brief read, and uses mereology to help express a number of causal principles. The SEP entry uses directed graphs to model causality.

(d): more generally, please see https://plato.stanford.edu/entries/infinite-regress/. Infinite regress arguments are very much still discussed today. Dagher has a forthcoming paper for causal finitism that may be of interest to you.

Improve this answer
5
  • The standard natural numbers in ZFC don't have a largest element in their set, though? Since omega or N isn't an element of itself.
    – Kristian Berry
    Jun 21 at 19:32
  • Thanks @KristianBerry. OP: "an example of such a set would be... with no largest element". Perhaps OP can clarify.
    – emesupap
    Jun 21 at 19:52
  • 1
    No, you're right, I have a bad habit of conflating "last" with "largest."
    – Kristian Berry
    Jun 21 at 19:53
  • @emesupap Thank you for the response, it is greatly appreciated, though it seems as if my initial post wasn't very descriptive. In terms of (a), I was under the assumption that the naturals were ordered in the manner "1 < 2 < 3........", with the first element being 1, not the reverse as I put in the initial posting ("...... > 5 > 4 > 3 > 2 > 1"), the difference being that there is no first element, which ostensibly leads to problems from an angle of dependency. Does this make a meaningful difference? Thank you for taking the time to answer
    – Max Maxman
    Jun 21 at 20:49
  • If by first element you mean least element, then the naturals will no longer suffice. You can just use the integers. There are many examples, although (again, in ZFC), all discrete total orders with no lower or upper bound "look" like integers (elementary equivalence)
    – emesupap
    Jun 21 at 23:30
3

Looks like you answered your own question:

Yes, "....... < -3 < -2 < -1 < 0" is a totally ordered set with a last element and no first element, and there is no contradiction here. There is an infinite number of elements before 0, but there is no element "infinitely prior to 0". Each element is only a finite number of steps before 0.

And even if there was, that still wouldn't be a contradiction.

Take the set (-1, 1] of all real numbers strictly greater than -1 and less than or equal to 1. It has a greater element, 1, and no smallest element. There is an infinite number of elements prior to 1, and in fact, every element except 1 itself is "infinitely prior to 1". Indeed for any element x < 1 you can construct the infinite sequence x < (x+1)/2 < (x+2)/3 < (x+3)/4 < (x+4)/5 < ... < 1.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .