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).
523
questions
4
votes
0
answers
79
views
Why does proof of Zorn's lemma need to use the fact about ordinals being too large to be a set?
I'm not understanding why its necessary to invoke the knowledge about ordinals in order to prove Zorn's lemma.
The Hypothesis in Zorn's lemma is
Every chain in the set Z has an upper bound in Z
Then ...
- 41
7
votes
1
answer
98
views
What does the cardinality alone of a totally ordered set say about the ordinals that can be mapped strictly monotonically to it?
For any cardinal $\kappa$ and any totally ordered set $(S,\le)$ such that $|S| > 2^\kappa$, does $S$ necessarily have at least one subset $T$ such that either $\le$ or its opposite order $\ge$ well-...
2
votes
0
answers
46
views
Using the Principle of Well Order, show that for all $n \in N$ it holds that $4^n -1$ is divisible by 3.
Using the Principle of Well Order, show that for all $n \in N$ it holds that $4^n -1$ is divisible by 3.
I have already defined the set of counterexamples $C$, then I proved that for $n=1$ the ...
0
votes
1
answer
92
views
Well-ordering theorem and cardinality of real numbers
If we assume that the axiom of choice is right, the well-ordering theorem can be verified.
So, the set of real numbers also can be constructed by well-ordering property.
By the well-ordering property, ...
0
votes
0
answers
96
views
Prove that if $A$ is any well-ordered set of real numbers and $B$ is a nonempty subset of $A$, then $B$ is well-ordered.
To prove: if $A$ is any well-ordered set of real numbers and $B$ is a nonempty subset of $A$, then $B$ is well-ordered.
My attempt: Suppose towards a contradiction that given any well-ordered set of ...
- 1
1
vote
0
answers
41
views
Limit Countable Ordinal - is it a limit of a intuitive sequence of ordinals?
I am studying set theory, ordinal part.
Set theory is new to me.
I know that commutativity of addition and multiplication
can be false in infinite ordinal world.
$ \omega $ = limit of sequence $\, 1,2,...
- 285
3
votes
1
answer
167
views
Difference between partially ordered, totally ordered, and well ordered sets.
I just started studying set theory and I'm a bit confused with some of these relation properties.
Given a set A = {8,4,2}, and a relation of order R such that aRb means "a is a multiple of b"...
- 41
1
vote
1
answer
101
views
a proof idea: Every well-ordered set has an order-preserving bijection to exactly one ordinal.
I have seen a proof of the statement, and its usually by transfinite induction. And I'm trying to find out why my proof doesn't work, it seems too simple:
Let $X$ be a well-ordered set. Define $X^{<...
- 367
2
votes
1
answer
99
views
Intuitionistic well-orderings of uncountable sets
The well-ordering principle has always been considered to be highly unconstructive, as far as I know. However, I think intuitionistic mathematics can be compatible with the existence of a well-...
- 343
0
votes
1
answer
40
views
If i have an a well ordered set in which every chain admits an upper bound then the maximal element is unique
It is clear that the Zorn lemma guarantees the existence.
I prove that the minimal element is unique, and obviously the set is totally ordered.
So because the uniqueness of the successor of all ...
0
votes
1
answer
41
views
Using WOP to prove certain naturals can be written a certain way.
$\newcommand{\naturals}{\mathbb{N}}$
Use the Well-Ordering Principle to prove that every natural number greater than or equal to 11 can be written in the form $2s+5t$, for some natural numbers $s$ and ...
- 11
0
votes
1
answer
59
views
A couple of well ordering proofs.
I'm having trouble understanding a couple of things when studying well orderings and ordinals.
I know that given a well ordering $(A,<)$ there is no $a\in A$ s.t. $(A,<)\cong (A_a,<)$ where $...
- 391
2
votes
1
answer
45
views
What is the generalization of well-orders to partial orders?
Every well-ordered set is linearly ordered. However, is there a notion of well-orders that generalizes to partial orders? Maybe, the generalized definition will be that every non-empty subset has a ...
- 19.2k
1
vote
2
answers
63
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,522
0
votes
0
answers
18
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
367
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
117
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 ...
- 2,135
1
vote
1
answer
74
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 ...
- 9,974
2
votes
2
answers
68
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,145
0
votes
0
answers
28
views
A class of linear orderings with a convexity property on ordinals
I am looking for a reference for the following class of linear orderings on a non-zero ordinal $\lambda$.
Define $\lambda^-$ as the predecessor of $\lambda$ if $\lambda$ is a successor, and set $\...
- 5,033
0
votes
0
answers
53
views
Are there any guessing principles in set theory which guess well-orders of sets?
$\Diamond(\omega_1)$ was introduced by Jensen and is known to imply $\mathsf{CH}$ and the existence of a Souslin tree. It is the statement that there is a sequence (in particular a $\Diamond$-sequence)...
- 1,714
0
votes
0
answers
58
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,280
3
votes
4
answers
558
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
113
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 ...
- 779
0
votes
0
answers
23
views
Does this beginningless-past thought experiment result in several possible non-well-ordered sets?
Assume there is an infinitely large universe with a beginningless past in which two eternal particles move at a constant speed of 1 km per “day” with respect to each other. Intuitively (to me), it ...
- 1
0
votes
0
answers
41
views
Exercise 4 of Chapter 7 in Enderton's Elements of Set Theory
Let $<$ be the usual ordering on the set $P$ of positive integers. For $n$ in $P$, let $f(n)$ be the number of distinct prime factors of $n$. Define the binary relation $R$ on $P$ by
$$
mRn \iff [f(...
- 133
0
votes
2
answers
143
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?
- 317
1
vote
0
answers
172
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 ...
- 3,741
6
votes
1
answer
258
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!$ ...
- 3,741
2
votes
1
answer
154
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 ...
- 3,741
1
vote
1
answer
69
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 ...
- 191
0
votes
1
answer
38
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 ...
- 393
6
votes
1
answer
114
views
Sequence of quadratic surds over nonnegative integers without having to delete or sort?
I am trying find an strictly increasing iterative sequence that gives this set sorted: $$[a+\sqrt{b}: a,b \in \mathbb{N_0}].$$ These are a subset of constructable numbers. When I look at it, there are ...
- 31
13
votes
1
answer
612
views
Why do we need "canonical" well-orders?
(I asked this question on MO, https://mathoverflow.net/questions/443117/why-do-we-need-canonical-well-orders)
Von-Neumann ordinals can be thought of "canonical" well-orders, Indeed every ...
- 5,403
1
vote
0
answers
67
views
Every Non empty subset has a least element implies linear order
Suppose $(A,R)$ be structure where R is a binary relation on $A$.
Suppose $A$ has the property that every Non empty subset of $A$ has a least element w.r.t. the relation $R$. Then $R$ is a linear ...
user1072974
2
votes
2
answers
125
views
What is the meaning of "induction up to a given ordinal"?
Given an ordinal $\alpha$, what does it mean: "induction up to $\alpha$"? When $\alpha=\omega$, is this is ordinary mathematical induction? Also, Goodstein's Theorem is equivalent to "...
- 4,078
1
vote
1
answer
89
views
Question about a proof that any well-ordered set is isomorphic to a unique ordinal
I am studying a proof that every well-ordered set is isomorphic to a unique ordinal. However, I don't understand why $A = pred(\omega)$ (see yellow).
One direction is clear:
Let $x \in pred(\omega)$, ...
- 1,017
2
votes
1
answer
61
views
non-wellordered linear order that doesn't contain a copy of $\omega^*$ in ZF?
Obviously a wellorder cannot contain a copy of $\omega^*$ (the dual order of $\omega$), and this can be proven in ZF. In ZFC, it is easy to prove any linear order which is not a wellorder does contain ...
- 4,074
2
votes
1
answer
39
views
Intersection of a chain of closed sets
I was recently attempting proving a conjecture of mine about the existence of certain minimal nonempty closed sets in a topological space. I opted to use Zorn's Lemma, and the proof would go through ...
- 1,153
2
votes
2
answers
244
views
Product of Countable Well-Ordered Set with $[0,1)$ is Homeomorphic to $[0,1)$
As part of a proof that the long line is locally Euclidean, I'd like to prove the following:
Proposition. If $A$ is a countable well-ordered set, then $A \times [0,1)$ with the dictionary order is ...
- 2,169
0
votes
0
answers
73
views
Order type of this order over naturals
For no specific reason other than curiosity, I find myself wondering of a way to formalize a specific order of the natural numbers based on a sort of "recursive prime number factorization", ...
- 82
0
votes
1
answer
41
views
Initial segment of well ordered set
An initial segment (B) of an well-ordered set $(A,<)$ is a subset $X⊊A$ such that, for all $x \in X$ and for all $y∈A$ such that $y<x, y∈X$.
I want to prove that this set is equal to $A_z =$ { $...
- 3
1
vote
1
answer
73
views
How do you prove that there exists a highest element of any finite, nonempty subset of Natural Numbers? Is the following algorithmic proof valid?
Since the given set, $C \subset \mathbb{N}$ is non empty, hence by well ordering principle there exists $\alpha \in C$ which is the lowest element in C. Also, since the set $C$ is finite, $\quad \...
- 184
0
votes
0
answers
55
views
Partial order, well order and initial segment
I saw the following definition for initial segment in https://digitalcommons.kennesaw.edu/cgi/viewcontent.cgi?article=2161&context=facpubs
If $\leq$ is a partial order in a set $X$, then a chain ...
- 451
6
votes
1
answer
209
views
Riddle: finite set that contains one of the three numbers
A colleague told me this two-part riddle:
PART $\mathbb{N}$:
Three players sit in a circle, each having a positive integer number
$x_i$ written on their hat. Every player can see only the numbers of
...
- 3,429
1
vote
1
answer
47
views
"Name" for this order relation of binary sequence
I am trying to define a Matrix $M_n$ of dimension $2^n \times n$ where each row corresponds to a element of the set $\{0,1\}^n$. To avoid ambiguity, I using an order relation over the set $\{0,1\}^n$ ...
- 509
0
votes
1
answer
42
views
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^{\...
- 177
1
vote
1
answer
44
views
Is the class of well-ordered sets a pseudo-elementary class? [closed]
I know that the class of well-ordered sets is not an elementary class. But, is it at least a pseudo-elementary class? If not, what is the proof?
- 19.2k
1
vote
1
answer
38
views
What is the class of models of the $\forall$-theory of the class of well-ordered sets?
I know that the class $W$ of well-ordered sets is not an axiomatizable class. However, it does have an associated first-order theory $Th(W)$. Now, consider the $\forall$-part of the theory $Th(W)$, ...
- 19.2k
0
votes
0
answers
100
views
Cantor-Bendixson derivative sets
I try to show that a compact subset $A\subset \mathbb{C}$ is at most countable if and only if there exists a countable ordinal number $\alpha$ (i.e $\alpha <\omega_{1},$ where $\omega_{1}$ is ...
- 51