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
0
votes
0
answers
55
views
Is every strict ordering by inclusion a well-ordering?
Given a set $s$ which is transitive and completely ordered by inclusion, that is, such that
$z \in s \rightarrow z \subset s$ and $\left( x \in s \wedge y \in s \wedge x \neq y \right) \rightarrow
\...
- 41.9k
5
votes
3
answers
488
views
Motivation of inventing concept of well-ordered set?
I've started studying set theory for a while. I understand what is an ordered sets but i still fail to see what motivated mathematicians to invent these concept.
Could you please enlightment me ?
...
- 1,350
1
vote
1
answer
72
views
Is there something missing in Jech's proof of Zermelo's Well-Ordering Theorem?
Here is the proof from p. 48 of the Millennium Edition, corrected 4th printing 2006:
My question: how do we know that there is any ordinal $\theta$ such that $A=\{a_\xi\,\colon\xi<\alpha\}$? ...
- 307
3
votes
2
answers
98
views
Proving the shortlex ordering is a well-ordering
Let $(A,<)$ be a nonempty linearly ordered set, and let $\operatorname{Seq}(A)$ denote the set of finite sequences of elements of $A$. That is, $f\in\operatorname{Seq}(A)$ is a function $f:n\to A$, ...
- 4,442
0
votes
1
answer
88
views
Iterative argument in math proofs
I am reading proof of subspace of $\mathbb{R^n}$ has a basis. And most of them like this(classic proof): let $S\subset\mathbb{R^n}$ ,if $v_1\neq0$ and $<v_1>=S$, we finished proof, otherwise, we ...
- 117
2
votes
1
answer
169
views
When does a set of real numbers have a minimal element?
I Believe the answer is when the set is closed in the sense of standard topology (we exclude $\mathbb{R}$) itself.
Examples:
Point sets have a minimum, and they are closed.
Closed interval also have ...
2
votes
0
answers
106
views
How does one prove without the axiom of choice that the product of a collection of nonempty well-ordered sets is nonempty?
Suppose $\{X_{\alpha}\}_{\alpha\in\mathcal A}$ is an indexed family of nonempty well-ordered sets, where $X_{\alpha}=(E_{\alpha},\le_{\alpha})$ for each $\alpha$. It seems intuitively obvious that we ...
- 20.8k
1
vote
1
answer
78
views
Complete iff Compact in Well-Ordered space
Let $T=(S, \leq, \tau)$ a well-ordered set equipped with order topology (defined here).
Definition 1: $T$ is called complete iff every non-empty subset of $T$ has a greatest lower bound (inferior) and ...
- 188
2
votes
1
answer
127
views
Is the first-order theory of the class of well-ordered sets the same as the first-order theory of the class of ordinals?
Consider the class $K$ of well-ordered sets $(W,\leq)$. Although that class is not first-order axiomatizable, it has an associated first-order theory $Th(K)$. Now consider the class of ordinals $On$, ...
- 21.5k
0
votes
1
answer
64
views
Partial order on sets and application of Zorn's Lemma to construct well-ordered subset
I would appreciate help with the following question:
Let $(A,<)$ a linear ordered set.
a. Let $F\subseteq P(A)$. Prove that the following relation is a partial order in $F$: $X\lhd Y$ for $X,Y\in F$...
- 35
1
vote
1
answer
81
views
Any subset of a well-ordered set is isomorphic to an initial segment of this well-ordered set.
I wanted to prove the fact for which I have a sketch of proof: Let $(W,\leq )$ be a well-ordered set and $U$ be a subset of $W$. Then considering the restriction of $\leq $ to $U\times U$, we have ...
- 375
2
votes
1
answer
42
views
Are these two notions of weak well-foundedness equivalent?
Background (optional): I have a state transition system $Q$ with two "kinds" of transitions: progress-making ($\delta_P : Q \times \Sigma \rightarrow Q$) and non-progress making ($\delta_N : ...
- 685
0
votes
0
answers
30
views
Well-founded Relation on infinite DAGs
A well-founded relation on set $X$ is a binary relation $R$ such that for all non-empty $S \subseteq X$
$$\exists m \in S\colon \forall s \in S\colon \neg(s\;R\;m).$$
A relation is well-founded when ...
- 83
0
votes
2
answers
38
views
Confusion about the validity of the proof of Trichotomy of order for natural numbers in Tao's Analysis
It's well-known that in Tao's Analysis I P28, he provides a provement of Trichotomy of order for natural numbers as follows.
Denote the number of correct propositions among the three (i.e. $a<b,\ ...
1
vote
1
answer
121
views
Partition of $\mathbb R$ in convex subsets/badly ordered sets
Background: These questions come from two different exercises, but since the first is much shorter and of the same kind of one of the others, I preferred to put everything in only one thread. (We work ...
- 509
6
votes
0
answers
149
views
Existence of uncountable set of functions on natural numbers
For $f,g:\mathbb{N}\rightarrow \mathbb{N}$ we write $f\leq g$ iff $f(n)\leq g(n)$ for all $n\in \mathbb{N}$. Let $\mathcal{S}\subseteq \{f\vert f:\mathbb{N}\rightarrow \mathbb{N}\}$ be a set of ...
- 113
0
votes
1
answer
56
views
Reordering algorithm to fragment consecutive sequences of ones as much as possible
Recently, I came across the following problem:
Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$.
We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$.
We call a &...
- 1
0
votes
1
answer
41
views
Prove $\sum_{i=0}^n 2^i=2^{n+1}-1$ using WOP
So I defined my predicate $P(n)$ according to the theorem, and then I said there there exists an integer $n\ge0$ such that $P(n)$ is false. And I let $C$ be the set of all such $n$. And by WOP, there ...
0
votes
0
answers
46
views
Prove that an infinite well ordered set X has equal cardinality to the set X∪{a}, where 'a' does not belong to X.
Found this question in a book of analysis as a corollary. Before the question is introduced (as an exercise), the book introduced Theorem of Recursion on Wosets and Comparability Theorem. For ...
- 1
-1
votes
1
answer
52
views
Is this set uncountable? $A = \{A_n \colon n \in \mathbb{N}\}$ where $A_n$ is the set $\mathbb{N}$ with the number $n$ removed from it
The set in the title is presented in this answer as an example of a similar set to the $P(\mathbb{N})$ (in the context of explaining the necessity of the axiom of choice in the existence of a well ...
- 39
2
votes
0
answers
75
views
Law of Trichotomy for Well-Orderings
Often in beginning set-theory courses, and in particular in Jech's book Set Theory, it is proved from scratch that given any two well-orderings, they are isomorphic or one is isomorphic to an initial ...
- 97
2
votes
1
answer
85
views
Given two well-orders $\langle A,R \rangle$ and $\langle B,S \rangle$, one of the following holds.
Let $\langle A,R \rangle$ and $\langle B,S \rangle$ be two well-orders, and let $\text{pred}(A,x,R) := \{y \in A \;|\; yRx\}$ and similarly for $\text{pred}(B,z,S)$.
It is claimed that one of the ...
- 1,307
3
votes
1
answer
73
views
Is it consistent with ZC that a well-order of type $\omega_\omega$ does not exist?
Working in Zermelo's set theory (with choice for simplicity) - the construction in Hartogs' theorem shows that starting with a set $X$, there is a set $X'$ in at most $\mathcal{P}^4(X)$ (where $\...
- 4,963
0
votes
1
answer
51
views
Detemine whether the interval [4,8] is well-ordered. Explain.
I don't think this interval is well-ordered because the subset (4,8) would not have a smallest value. I'm stuck on how to show (4,8) has no smallest value.
- 15
3
votes
1
answer
95
views
Order type of N and Q
Studying linear orderings, I learned two theorems.
Suppose two linearly ordered sets A and B satisfy the following:
(1) countably infinite,
(2) dense, i.e. if x<z then there exists y such that x&...
- 53
0
votes
0
answers
37
views
The arithmetic of first uncountable ordinal number
I think, I know the proof of 1+ω0 = ω0. (ω0 is countable ordinal s.t ω0=[N]). To prove this, I can define a function f: {-1,0,1,2,...}->{0,1,2,...} by f(x)=x+1. But if ω1 is first uncountable ...
1
vote
3
answers
1k
views
Shouldn't the Well Ordering Principle apply only to sets with at least two elements?
From what I've been taught in school, the well-ordering principle states that every non-empty set must have a least element. To me, the least element of some set $X$ is an element $a$ such that, for ...
- 927
3
votes
1
answer
80
views
Hessenberg sum/natural sum of ordinals definition
I was given the following definition of Hessenberg sum:
Definition. Given $\alpha,\beta \in \text{Ord}$ their Hessenberg sum $\alpha \oplus \beta$ is defined as the least ordinal greater than all ...
- 509
5
votes
1
answer
75
views
Exercise 7.1.6 Introduction to Set Theory by Hrbacek and Jech
This is exercise 7.1.6 of the book Introduction to Set Theory 3rd ed. by Hrbacek and Jech.
Let $h^{*}(A)$ be the least ordinal $\alpha$ such that there exists no function with domain $A$ and range $\...
- 4,827
0
votes
1
answer
106
views
Prove that $\mathbb N \times \mathbb N$ is well ordered under $\le$
We define an ordering $\mathbb N \times \mathbb N$, $\le$ as follows:
$(a, b) \le (c, d)$ iff $a \le c$ and $b \le d$. I tried to prove that $\mathbb N \times \mathbb N$ is well ordered under this ...
- 377
2
votes
1
answer
42
views
If $X_1$,$X_2$ are wosets isomorphic to ordinals $\alpha_1,\alpha_2$ then $X_1\times X_2$ is isomorphic to $\alpha_2\cdot \alpha_1$
I want to prove the following:
Let $X_1$,$X_2$ be wosets, isomorphic to ordinals $\alpha_1,\alpha_2$ respectively. Then $X_1\times X_2$, with the lexicographic order, is isomorphic to $\alpha_2\cdot\...
- 4,827
0
votes
2
answers
145
views
Can every statement that can be proved using the well-ordering principle be proved using weak mathematical induction?
The following is problem 30 of chapter 4.4 of Discrete Mathematics with Applications, 3rd ed. by Susanna Epp:
Prove that if a statement can be proved by the well-ordering principle, then it can be ...
- 346
4
votes
0
answers
105
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
8
votes
1
answer
109
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
51
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
130
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
146
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
46
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,...
- 295
3
votes
1
answer
467
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
126
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^{<...
- 438
2
votes
1
answer
110
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-...
- 503
0
votes
1
answer
58
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 ...
- 188
0
votes
1
answer
46
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
67
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
51
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 ...
- 21.5k
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