Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
12 views

Trying to find faster growing variants of the successor function

The successor function $S : \alpha \mapsto \alpha \cup \{\alpha\}$ where $\alpha$ is an ordinal is notable for being a strictly increasing function that has no fixed points, because it is ...
0
votes
1answer
25 views

The cartesian product of a well-ordered set with $[0,1)$ is a linear continuum in dict. order

Definition: A linear continuum is a simply ordered set $L$ such that: (1): $L$ has the least upper bound property; (2): For every $x<y$ in $L$ there is a $z$ sucht that $x<z<y$. I ...
1
vote
0answers
52 views

Given a poset with a join such that any pair has a meet, find a total order with a special property.

Let $(A,\geq)$ be a partially ordered set such that there exists the join $\bigvee A$, i.e. $a\in A$ such that $a\geq b$ for any $b\in A$; for any pair $(b,c)\in A\times A$ there exists the meet $b \...
0
votes
1answer
32 views

Cardinal of all well-orders of $\mathbb{N}$ [duplicate]

Lets consider the set $$ A = \{R\subset\mathbb{N}^2:R \text{ is a well-order of } \mathbb{N}\} $$ Now, it's clear that $\aleph_1\leq|A|\leq2^{\aleph_0}$(Since all the well-orders of $\mathbb{N}$ are ...
4
votes
2answers
81 views

Why are ordinals multiplied in reverse order

When two ordinals, $\alpha$ and $\beta$, are multiplied together, $\beta$ is taken as the most significant multiplicand and $\alpha$ as the least significant multiplicand in the product $\alpha \cdot \...
1
vote
1answer
25 views

Show that the lexicographic ordering $≤_l$ on $A\times B$ for $A$ well ordered by $≤$ and $B$ well-ordered by $≤'$ is well-ordered.

Q: Show that the lexicographic ordering $≤_l$ on $A\times B$ for $A$ well ordered by $≤$ and $B$ well-ordered by $≤'$ is well-ordered. A: I have previously shown that this lexicographic ordering is ...
0
votes
1answer
26 views

Let $≤$ be a total order on $A$. For each $u\in A$, let $s(u)=\{x\in A:x<u\}$…Prove that $≤$ is a well-ordering on $A$.

Q: Let $≤$ be a total order on $A$. For each $u\in A$, let $s(u)=\{x\in A:x<u\}$. Suppose that for every $u\in A$ and $X$, if $X\subseteq s(u)$ is nonempty, then $X$ has a $≤$-least element. ...
2
votes
0answers
26 views

Provable well-founded ordering

Quote from Sieg/Parsons commentary on Gödel's Zilsel lecture: ...it has to be clarified how to grasp ... specific countable ordinals ... That can be archieved in the system $S_1$ with function ...
0
votes
3answers
47 views

Prove that for every natural number $a$ there are integers $t \geq 0$ and $r$ such that $a = 3^t r$ and 3 does not divide r.

Prove that for every natural number $a$ there are integers $t \geq 0$ and $r$ such that $a = 3^tr$ and $3 \not | r$. Would I use the well ordering principle for this? There’s so many variables so I’m ...
0
votes
1answer
38 views

Zermelo's Proof of the Well Ordering Theorem

I am trying to find the paper by Zermelo in the early 1900's in which he proved the Well Ordering Theorem (implicitly using the axiom of choice). Does anyone know where I can find this?
0
votes
1answer
31 views

Directed set and partially/totally ordered sets.

I am barely new to order theory and this motivates if the question is trivial. I understood the definitions of preorder, partially and totally ordered sets and well ordered sets. In particular there ...
0
votes
1answer
47 views

Indexing of uncountable sets and uncountable collections of sets, uncountable intersections containing a point

Definitions Let $\mathcal{A}$ be an uncountable collection of sets so that if $I_{\mathcal{A}}$ is the index set of elements of $\mathcal{A}$ then $|I_{\mathcal{A}}|\not=\aleph_{0}$ (I mean this to ...
0
votes
1answer
133 views

Intuition behind Well Ordering Principle and Axiom of Choice

I am learning about Axiom of Choice and Well Ordering Principle from Munkres's Topology book, but I can't quite wrap my head around it properly. I have these questions: [Munkres 0.4.3] If $A = A_1 \...
0
votes
1answer
62 views

Given $S \hookrightarrow T$ construct $U ≈ T$ disjoint from $S$ in Z set theory?

I was recently thinking about the fact (in ZFC) that, given a (first-order) structure $A$ that embeds into another structure $B$, there is some structure $C$ isomorphic to $B$ such that the domain of $...
0
votes
1answer
68 views

Why is the Axiom of Well-ordered Choice not strong enough to prove Zorn's Lemma?

This is based on this question: How strong is the axiom of well-ordered choice? The "axiom of well-ordered choice" says that any transfinitely-indexed family of sets has a choice function. The ...
11
votes
1answer
186 views

How strong is the axiom of well-ordered choice?

I sometimes see references to the "Axiom of Well-Ordered Choice," but I'm not sure how strong it is. It states that every well-ordered family of sets has a choice function. By "well-ordered family," ...
0
votes
0answers
36 views

Help understanding Well-Ordering Theorem [duplicate]

Forgive me for my lack of formal notation, I haven't taken any classes on set theory, or any advanced math topics for that matter. From my understanding based on the wikipedia entries, a well-ordered ...
1
vote
1answer
37 views

Proof by contradiction and the well ordering principle

I have a question regarding proof by contradiction and the well ordering principle on integers. Okay lets says for example an arbitrary value $p$ is a positive integer and which I assume is the ...
0
votes
3answers
48 views

Help solving this proof using Well Ordering Principle

Let $a_1,a_2, ... , a_n ∈ \Bbb{N} $ . Prove that there exists $ l ∈ \Bbb{N} $ such that $a_i | l$ for all $i ∈ \{1,2,...,n\}$ and if $x ∈ \Bbb{N} $ is such that each $a_i$ divides $x$, then $l | x$. ...
4
votes
1answer
117 views

Set or list compression

Apologies for poor use of terms, I do not understand enough of the problem to even ask the right questions. My main question is, what domain of mathematics is this problem and is it solved problem ...
0
votes
0answers
46 views

Showing $\Gamma(\alpha\times\alpha)\leq\omega^\alpha$. [duplicate]

I'm trying to prove Exercise 3.5 in Set Theory by Thomas Jech: $$ \Gamma(\alpha\times\alpha) \leq \omega^\alpha $$ where $\Gamma(\alpha\times\beta)=\operatorname{otp}(\{(\zeta,\delta)\mid(\zeta,\delta)...
1
vote
1answer
56 views

Isomorphism from limit ordinals to ordinals: is there a fixed point?

Let $\kappa > \omega$ be some limit ordinal, and let $L$ be the set of limit ordinals less than $\kappa$. Since $(L,<)$ is well-ordered, it must be isomorphic to some ordinal $\lambda$ via a map ...
0
votes
2answers
20 views

Proving that a set of relating elements is infinite

I want to prove the following: Let $<$ be a well-founded relation on a set X such that $\leq$ is a total order. Show that the set $$\{x\in X: x < y\}$$ is infinite for some $y \in X$. I ...
1
vote
1answer
40 views

Well-Ordering Irrationality

Let $D$ be a positive integer and the let the square root of $D$ be a real number. Assuming that the square root of D is not an integer (i.e. $D$ is not a perfect square), use Well-Ordering to prove ...
0
votes
2answers
49 views

Well-founded relation, well-order.

On the set $\mathbb{N}\cup \{0\}$ we define the relation of strict divisibility with $$ a \text{ strictly divides } b \Leftrightarrow a | b \text{ and } a \neq b.$$ Do we get a well-founded relation?...
2
votes
2answers
29 views

Let $A$ be a chain. $B,C$ subsets of $A$ s.t $A= B\cup C$. If $B$ and $C$ are well-ordered then A is well-ordered.

My attempt: Assume that $B$ and $C$ are well-ordered and A is not. Since A is not well-ordered it contains an infinite descending sequence $\{a_i\}_{i=0}^\infty$. If the sequence has a limit $l$ $\in$...
0
votes
1answer
194 views

Lemma for proving Zermelo's theorem

I'm trying to understand the following lemma in Bourbaki's set theory (chapter III, §2,no. 3,Lemma 3): Lemma 3: Let $E$ be a set, let $S$ be a subset of $P(E)$, and let $p$ be a mapping of $S$ into $...
-2
votes
1answer
51 views

Well order of naturals [closed]

I have an exercise that asks me for 15 non-isomorphic well order types of natural numbers, I have some, can you help me with other well uncommon orders? Thank you
3
votes
1answer
73 views

Linearly ordering the power set of a well ordered set with ZF (without AC)

As the title says, my question is, how one can use only ZF-theory to prove that the power set of A, whereby (A, <) is a well-ordering, can be linearly ordered?
0
votes
0answers
25 views

Infinite descendant sequences

"Show that the order $(A,<)$ is well ordering if and only if there no exists infinite descendant sequences in $A$". Can you help me whit this problem, please, what happens is that my professor isn'...
1
vote
1answer
24 views

proof of Well Ordering Principle over positive integers

Theorem If $A$ is any nonempty subset of $\mathbb{Z}^+$, there is some element $m \in A$ such that $m \leq a$, for all $a \in A$ where such $m$ is the minimal element of $A$. (AA: Dummit and Foote) ...
0
votes
0answers
44 views

There exists a minimal uncountable well ordered set. [duplicate]

There exists a well-ordered set $A$ having a largest element $\Omega$ such that the section $S_\Omega$ of $A$ by $\Omega$ is uncountable but every other section is countable. Can anyone make me ...
4
votes
2answers
71 views

Well ordering and maximal chains in power set

Let $M$ be a set and "$\le$" a well-ordering of $M$. For $x \in M$ define: $$ M_{\le x} := \{ y \in M \ \vert\ y \le x \} $$ The map $$ f : M \to \mathcal{P}(M) \ ,\ x \mapsto M_{\le x}$$ is injective ...
1
vote
1answer
52 views

What is a simple method of combining an infinite (or finite) set of well-orders into one well-order?

Let $$W = \{W_1, W_2, W_3, \ldots\}$$ denote an infinite (or finite) set of well-orders on $\mathbb{N}$ and $\alpha_i$ is an ordinal (order type) that corresponds to $W_i$, assuming that $\alpha_1 \ge ...
3
votes
1answer
42 views

Isomorphic subsets of countable total orders

Suppose $(\Omega,\leq)$ is a totally ordered set, with $\Omega$ infinite and countable. If $S$ is an infinite subset of $\Omega$, then $(S,\leq)$ denotes the induced totally ordered set. Are there ...
0
votes
1answer
42 views

Question in Proof That Every Well-Ordering is a Total-Ordering

I am trying to make sense of the following: Theorem: Let $R$ be a relation on a set $A$. If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$. Proof: Suppose $x,y\...
0
votes
3answers
54 views

For- and backwards well-ordered set is finite.

I'm working on the following problem and can't seem to come up with a satisfactory proof. Let $X$ be a totally ordered set which is well-ordered forwards and backwards. Show that $X$ is finite. I ...
1
vote
2answers
463 views

Could every Hausdorff space be induced by a total order relation [closed]

Let $(H,\mathcal T)$ is a Hausdorff space then is there any total order relation on $H$ such that the topological space induced by the order relation be the same $(H,\mathcal T)$? Thanks a lots ...
0
votes
2answers
110 views

Showing that $[0, \omega_1]$ is compact. [duplicate]

I want to show that $[0, \omega_1]$ is compact, where $\omega_1$ is the least uncountable ordinal, and I have just been introduced to the concepts of ordinals. The tips I have seen to showing this ...
1
vote
1answer
67 views

Prove the comparability theorem for well ordered sets using transfinite induction

My question is about the same proof discussed here, but I am confused about more than this question addresses. In Naive Set Theory, Halmos phrases the comparability theorem as follows: The ...
0
votes
1answer
22 views

Well ordering principle question

Is every non empty subset of the integers well ordered and does this mean that every subset contains a least element? Are the positive rationals well ordered? i believe not. Is this because of the ...
1
vote
0answers
30 views

Showing that the class of finite subsets of a well-ordered class can be well-ordered

We know that if $(X, <)$ is a well-ordered class, then $\mathcal{P}(X)$ can be totally ordered by the following: $$A<^*B\ \text{iff min}(A\Delta B) \in A $$ where $\Delta$ is the symmetric ...
1
vote
1answer
35 views

Showing a Group Can Be Totally Ordered

If every finitely generated subgroup of a group $G$ is totally ordered, what approach should I take to prove that $G$ is also totally ordered? Should I define a map that takes elements from the ...
0
votes
0answers
22 views

Prove that every finitely generated subgroup of a totally ordered group can be totally ordered.

Prove that every finitely generated subgroup of a totally ordered group can be totally ordered. A group can be totally ordered if there is a total order $\leq $ on that group. Is the proof of this ...
1
vote
1answer
57 views

The reasoning behind $\sup\{\alpha\beta+\alpha\zeta\mid\zeta<\gamma\}=\alpha\beta+\sup\{\alpha\zeta\mid\zeta<\gamma\}$

Let $\alpha,\beta,\gamma$ be ordinals. Then $\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$. I'm been looking for some proofs of this theorem on MSE and found that the gist is the equality $\sup\{\...
1
vote
1answer
53 views

Is there a standard ordering of non-ordinal order types?

Two ordered sets have the same order type if there exists an order isomorphism between them. The order type of a well-ordered set is called an ordinal number. There is a standard ordering of the ...
0
votes
3answers
59 views

Sequential compactness of $S_\Omega$ and unbounded sequences.

I'm currently trying to prove that The space $S_\Omega$ is sequentially compact. where $S_\Omega$ is the first uncountable ordinal (i.e. it is well ordered, uncountable and all proper sections are ...
0
votes
1answer
86 views

Immediate successor of an element in a linearly orders set

In the book of Algebra by Hungerford, at page 15, it is asked that However, doesn't what is asked to prove contradict with the statement that it follows ? Moreover, consider $(\mathbb{R}, \leq)$, ...
0
votes
1answer
33 views

Must order-preserving bijections preserve immediate predecessors?

I am attempting to show that $A_1=\{1,2\} \times \mathbb{N}$ and $A_2=\mathbb{N} \times \{1,2\}$ do not have the same order type under the dictionary order. Now $(2,1)\in A_2$ has no immediate ...
2
votes
1answer
120 views

Equivalence Induction and Well-Ordering

I need some help please. I am trying to get to grips with proving the equivalence between mathematical induction (MI) and well-ordering principle (WOP). As a theorem, I have Principle of ...