Questions tagged [well-orders]

For questions about well-orderings and well-ordered sets. Depending on the question, consider adding also some of the tags (elementary-set-theory), (set-theory), (order-theory), (ordinals).

A well-order is a linear order where every non-empty set has a minimal element. Equivalently, it is a partial ordering where every non-empty set has a minimum.

We say that a set $A$ is well-ordered if it comes with a well-order of $A$; and that it is well-orderable if there is a well-ordering of $A$. Assuming the axiom of choice (or equivalently, Zorn's lemma) every set is well-orderable. That is Zermelo's theorem.

Well-ordered sets are exactly the linear orders on which we can perform recursive definitions and inductive proofs. The simplest examples include all the finite linear orders, and the natural numbers.

On the other hand, the rational numbers, and the real numbers, are all examples of linear orders which are not well-ordered.

The study of well-orders goes hand in hand with the study of ordinals, which are order types of well-ordered sets, and the von Neumann ordinal assignment, which gives us a specific well-ordered set isomorphic to a given well-order.

538 questions
4
votes
2 answers

Maximal element of infinite well ordered set

Can an infinite well ordered set $A \subseteq \mathbb{R}$ have a greatest element? I've read it a couple of times that the answer is yes, but I just couldn't agree with that. If set $A$ is well ordered, then surely it has least element. Okey, but…
Paul
  • 686
3
votes
1 answer

Does descending chain imply well ordering without axiom of choice?

I can prove no descending chain implies well ordering. Take any subset $S$, assume it has no least element, then we can construct a function $f: S \to S$ such that $f(x) < x$, then use recursion theorem to prove there is a descending chain. However…
Rui Liu
  • 567
2
votes
2 answers

Use the Well ordering principle to prove

Is there a process that is capable of generating an infinitely long sequence of natural numbers $a_1, a_2, a_3, \ldots$ such that for all $n \ge 1, a_n \ge a_{n+1}$? I know i have to use the well ordering principle to prove this. You assume that…
bow123
  • 53
  • 5
2
votes
2 answers

determining if a set is well ordered set

consider following question I am able to easily see that set of positive rationals is not well ordered set but I have difficulty coming to conclusion with this set of positive rationals with denominator less than 200 Is this well ordered set or…
manifold
  • 1,485
2
votes
1 answer

Linking robot motion rules to a derived variable for a state-machine -> to prove termination

We have a robot moving around on an $(x,y)$-grid, with $x$ and $y$ both being non-negative integers. I.e., the robot is moving in the space $\mathbb{N} \times \mathbb{N} = \mathbb{N}^2$. The robot terminates when reaching $(0,0)$. If the robot is…
1
vote
2 answers

Proving a set $(X, \le)$ is well ordered.

Give an example of a well ordered set $(X,\le)$ in which there exists an element $x_0$ such that there are infinitely many elements $x\in X$ such that $x\lt x_0$. Let $X=${$A_i | i \in \mathbb N$}$\cup \mathbb N$ where $A_i=${$1,2,...,i$}. Let the…
Alex
  • 649
0
votes
1 answer

How many automorphisms are there for $ \langle \omega , < \rangle $?

How many automorphisms are there for $ \langle \omega , < \rangle $? I'm not sure how to start this, although I expect there to be an upper bound of $2^{\aleph_0}$. ($\aleph_0^{\aleph_0} = 2^{\aleph_0}$) Update: Could the answer just be $1$? Since…
0
votes
1 answer

A question about well-orders with the same domain

Let $A$ be a set and suppose there are two relations on $A$, say $R$ and $S$, such that $(A,R)$ and $(A,S)$ are well-orders with the same order type, i.e. $(A,R)\cong(A,S)\cong(\alpha,\in)$ for some ordinal $\alpha$. Is it true that that $R=S$? I…
Seba Thei
  • 236
0
votes
0 answers

Prove $n^2 < 2^{n+1}$ by well-ordering

Please help me prove $n^2 ≤ 2^{n+1}$ by the well-ordering (not induction) $n\in\Bbb N \setminus \{{0\}}$ I've assumed that $n=1$ is not counter example so $m > 1$ and now try with $n = m-1$. $$(m-1)^2 ≤ 2^{m-1+1} = 2^m$$ I'm stuck here.
0
votes
1 answer

Well founded orders

1) Let $M : =\mathbb{N} \cup \{-1,0\} $. We define the relation $R \subset M \times M$, whereas $\lfloor y \rfloor := max \{m \in \mathbb{Z} : m \leq y\}$ \ $ R :=\{ (x,y) \in M \times M: x < \lfloor \frac{y}{2} \rfloor \}$ 1) Is R well-founded? 2)…
Parinn
  • 537
0
votes
1 answer

Initial segment of a well-ordered set

I'm reading Kuratowski's "Set theory", and here is a question from the Chapter 7. Let $A$ be a well-ordered set and $X$ its initial segment, i.e. $X$ is a proper subset of $A$, and $\forall x\in X$ if there exists the predecessor $x^-$ of $x$, then…
0
votes
1 answer

Two well orderings agreeing on a subset of an uncountable set.

Suppose $X$ is an uncountable set and $\prec_1, \prec_2$ are two well orderings on $X$. Show that there is an uncountable $Y \subseteq X$ such that $\prec_1, \prec_2$ agree on $Y$. How do I show that there is this uncountable $Y \subseteq X$? And…
taupi
  • 377
0
votes
1 answer

Well ordering principle question

Is every non empty subset of the integers well ordered and does this mean that every subset contains a least element? Are the positive rationals well ordered? i believe not. Is this because of the fact that this set has no minimal element? Does…
0
votes
1 answer

how to prove the existence and uniqueness of the prime factorization of any natural number.

Use the Well-Ordering Principle to prove the Fundamental Theorem of Arithmetic, i.e. the existence and uniqueness of the prime factorization of any natural number. hi dear all, I checked two videos of the theorems on Youtube, but I don't know how to…
Leric
  • 1
0
votes
1 answer

lexicographic ordering is not a well ordering

I'm new to discrete mathematics, here is the question I need to proof: Let X be the set of all possible words on the usual English alphabet (the words are just finite strings of letters and need not correspond to actual words). Show that the usual…
Elena
  • 11
1
2