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
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