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