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).
551
questions
1
vote
2
answers
88
views
Well-Ordering Principle From Recursion Theorem
As far as I understand, in intuitionistic logic we have neither (i) the well-ordering principle nor (ii) the recursion theorem. But can one deduce one from the other? I believe we cannot deduce (ii) ...
- 3,584
0
votes
0
answers
24
views
Order isomorphism on a subset and a segment
I am trying to understand Theorem 1.7.4 of Devlin's Joy of Sets. The Theorem states:
There is no isomorphism of $X$ onto a segment of $X$ (supposing $X$ is a woset).
The difficulty I am having is that,...
3
votes
2
answers
373
views
Construction of two uncountable sequences which are "interleaved"
I believe the answer to my following question is no, but some things about uncountable sets/sequences can be really counterintuitive so I wanted to double check:
Does there exist a pair of uncountable ...
- 107
0
votes
1
answer
124
views
Why is well-ordering needed to define the statement "$\forall i, \, P(i) \implies P(i + 1)$"?
I have learned a proof that the well ordering principle is equivalent to the inductive property for $\mathbb{N}$, and have understood it. However, I am confused as to the following statement my notes ...
- 3,029
1
vote
1
answer
95
views
What are the order types of computable pseudo-ordinals with no c.e. descending chains?
The notion of a “computable pseudo-ordinal”, i.e. a computable linearly ordered set with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the ...
- 10.4k
2
votes
2
answers
80
views
Does every well-ordered set obeying the non-induction Peano axioms have a well-ordering compatible with the successor operation?
Let $N$ be a well-ordered set together with a unary operation $s$ that obeys the following axioms (they are just the Peano axioms without induction):
$0 \in N$
for each $n \in N$ we have $s(n) \in N$
...
- 1,175
0
votes
0
answers
66
views
Does a total or well ordering has a countable cofinal
I read a post sometime earlier asking about the cardinality of total ordering on a set, which I forgot about the detail but led me to this question.
For a total/well-ordered set $A$ does there exist ...
- 1,732
3
votes
4
answers
687
views
Why can't well ordered sets have infinite decreasing subsequences?
Chapter 2 of Mathematics for Computer Science presents the following:
Define the set $\mathbb F$ of fractions that can be expressed in the form $\frac{n}{n+1}$. Define $\mathbb N$ as the set of ...
- 47
0
votes
1
answer
172
views
Countable versus uncountable dense linear orders
Let $(\Omega,\leq)$ be a dense linear order without endpoints.
If $\Omega$ is countable, we know by Cantor that $(\Omega,\leq)$ is order-isomorphic to $(\mathbb{Q},\leq)$.
Suppose that $\Omega$ is not ...
- 799
0
votes
2
answers
172
views
$\mathbb{N}\times\{0,1\}$ and $\{0,1\}\times \mathbb{N}$ not isomorphic
Show that the sets $W=\mathbb{N}\times\{0,1\}$ and $W'=\{0,1\}\times\mathbb{N}$, ordered lexicographically are non-isomorphic well-ordered sets.
Any hints on how to prove this?
- 357
1
vote
0
answers
174
views
Prove: $X$ is well orderable $\implies$ $X \times X$ is well orderable [duplicate]
I am studying a course on ZF Set Theory and have recently been considering whether or not $X$ being well orderable implies that $X \times X$ is well orderable.
More formally my question is the ...
- 4,331
6
votes
1
answer
264
views
Does there exist an infinite set admitting precisely four linear orders?
I am studying a course on ZF Set Theory where I encountered the following question:
Does there exist a set admitting precisely four linear orders?
Since any set with $n$ elements exhibits $n!$ ...
- 4,331
2
votes
1
answer
189
views
Is the set of all linear orders on $\mathbb{N}$ linearly orderable?
In studying the issue of linear orders and well ordering in the context of ZF Set Theory (without the Axiom of Choice), I have recently been thinking about the following question:
Is the set of all ...
- 4,331
1
vote
1
answer
70
views
Induction principle on well ordered set
I'm new and very grateful this site exists. If I do something wrong, feel free to tell me.
I have to prove the following:
Let $S$ be a subset of a well ordered set $L$ with the conditions:
a) $0_L \in ...
- 291
0
votes
1
answer
59
views
Well Ordering Principle Proof without mathematical induction with different approach
Denote $\Bbb Z_0$ be the set of all non-negative integers.
Well Ordering Principle for $\Bbb Z_0$. Every non-empty subset $S$ of $\Bbb Z_0$ has a least element; that is, there exists $m \in S$ such ...
- 447