Skip to main content

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
54 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 \...
Mark Fischler's user avatar
5 votes
3 answers
462 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 ? ...
InTheSearchForKnowledge's user avatar
1 vote
1 answer
64 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\}$? ...
Nat Kuhn's user avatar
  • 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$, ...
John's user avatar
  • 4,432
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 ...
MGIO's user avatar
  • 117
2 votes
1 answer
168 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 ...
Cathartic Encephalopathy's user avatar
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 ...
Joe's user avatar
  • 20.7k
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 ...
Manuel Bonanno's user avatar
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$, ...
user107952's user avatar
  • 21.3k
0 votes
1 answer
63 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$...
eitan.sh21's user avatar
1 vote
1 answer
80 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 ...
boyler's user avatar
  • 375
2 votes
1 answer
41 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 : ...
soktinpk's user avatar
  • 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 ...
MB7800's user avatar
  • 83
0 votes
2 answers
35 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,\ ...
Richard Mahler's user avatar
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 ...
lelouch_l8r4's user avatar
6 votes
0 answers
148 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 ...
L. R.'s user avatar
  • 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 &...
Thedby's user avatar
  • 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 ...
Maddie VePrice's user avatar
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 ...
Arbbor1's user avatar
-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 ...
lucas's user avatar
  • 39
2 votes
0 answers
74 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 ...
rea_burn42's user avatar
2 votes
1 answer
84 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 ...
Ben123's user avatar
  • 1,266
3 votes
1 answer
72 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 $\...
Chad K's user avatar
  • 4,953
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.
Abigail Webb's user avatar
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&...
Lim do's user avatar
  • 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 ...
Mathforest's user avatar
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 ...
Mailbox's user avatar
  • 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 ...
lelouch_l8r4's user avatar
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 $\...
Alphie's user avatar
  • 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 ...
Vector's user avatar
  • 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\...
Alphie's user avatar
  • 4,827
0 votes
2 answers
144 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 ...
Cynicrom's user avatar
  • 316
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 ...
Pecan Lim's user avatar
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-...
Transfinite Pyramid Scheme's user avatar
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 ...
Marcos Daniel Castaeda Ramirez's user avatar
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, ...
Eunseong So's user avatar
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 ...
lohg's user avatar
  • 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,...
imida k's user avatar
  • 295
3 votes
1 answer
457 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"...
bad at math's user avatar
1 vote
1 answer
125 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^{<...
hteica's user avatar
  • 428
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-...
Keplerto's user avatar
  • 463
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 ...
Manuel Bonanno's user avatar
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 ...
Mave's user avatar
  • 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 $...
cento18's user avatar
  • 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 ...
user107952's user avatar
  • 21.3k
1 vote
2 answers
86 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) ...
fweth's user avatar
  • 3,574
0 votes
0 answers
23 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,...
brocolliSally's user avatar
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 ...
psychicmachinist's user avatar
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 ...
Princess Mia's user avatar
  • 3,009
1 vote
1 answer
94 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 ...
Keshav Srinivasan's user avatar

1
2 3 4 5
12