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
3 votes
1 answer
58 views

Continuation of well ordered sets

We shall say that a well ordered set $A$ is a continuation of a well ordered set $B$, if, in the first place, $B$ is a subset of $A$, if, in fact, $B$ is an initial segment of $A$, and if, finally, ...
user avatar
  • 545
2 votes
1 answer
91 views

CH, countable additivity, and Ulam's Theorem

I am seriously struggling in properly getting various steps in the proof of Theorem 1.12.40 (Ulam's Theorem) in Bogachev's first volume on measure theory which concerns the classical statement that ...
user avatar
  • 3,869
0 votes
1 answer
51 views

Is there an order-preserving injection from $\alpha\cdot\alpha+\omega$ to $\mathcal{P}(|\alpha|)$?

Let $\alpha$ be an infinite ordinal. Is there an order-preserving injection from $\langle\alpha\cdot\alpha+\omega,\in\rangle$ to $\langle\mathcal{P}(|\alpha|),\subsetneq\rangle$? I tried to construct ...
user avatar
  • 993
3 votes
2 answers
79 views

Are $\Bbb{R}\times\Bbb{Q}$ and $\Bbb{Q}\times\Bbb{R}$ order-isomorphic?

Consider the two following linear orders, $X=\langle \Bbb{R}\times\Bbb{Q}, <_\text{lex} \rangle$ and $Y=\langle \Bbb{Q}\times\Bbb{R}, <_\text{lex} \rangle$, where $<_\text{lex}$ is the ...
user avatar
  • 993
1 vote
3 answers
52 views

Are suborders of pseudo-well-ordered sets themselves pseudo-well-ordered?

The class $W$ of well-ordered sets is not first-order axiomatizable. However, it does have an associated first-order theory $Th(W)$. I define a pseudo-well-ordered set to be an ordered set $(S;\leq)$ ...
user avatar
  • 13.9k
2 votes
2 answers
61 views

Order type of a set that is ordered but not well-ordered

I looking at ordered sets in the Kolmogorov (Introductory Read Analysis) book. Section 3.5 Definition 2 says the order type of a well ordered set is called an ordinal number. If the set is infinite, ...
user avatar
  • 277
0 votes
2 answers
30 views

Construct the embedding of a subset of a well-order to the full set

I'm trying to build the theory of well-orders without mentioning ordinals. Define a map $f : X \to Y$ between well-ordered sets to be a simulation, if it is an order equivalence (i.e. for all $x_0, ...
user avatar
0 votes
1 answer
27 views

Transfinite Recursion Theorem - Particular case - Enderton

I have the following theorem for any formula $\gamma(x,y)$: Theorem of Transfinite Recursion: Given a well-ordered set $A$ such that for any $f$ there is a unique $y$ such that $\gamma(f,y)$ holds, ...
user avatar
  • 3,430
2 votes
1 answer
52 views

Infinite Lexicographic Order on Bijections is Well-Order

Problem. Prove, without using $\mathsf{AC}$ if possible , that if $\alpha$ and $\beta$ are ordinals such that $\alpha$ is countable and $\beta>1$, then $\alpha^\beta$ is countable. The induction ...
user avatar
  • 993
1 vote
1 answer
19 views

Open sets in $S_\Omega$ (minimal uncountable well ordered set) with the order topology.

$X$ is a well ordered set. $S_\Omega= \{ x:x\in X\text{ and } x<\Omega\}$ such that it is the minimal uncountable well ordered set. The section $S_\Omega$ of $X$ is uncountable and any other ...
user avatar
2 votes
2 answers
80 views

Meaning of 'set of well-ordered sequences'

I'm trying to make sense of a construction of a module given in the following research paper: A New Construction of the Injective Hull, Fleischer, 1968. On the second page, a module $F$ is constructed,...
user avatar
  • 2,827
4 votes
1 answer
185 views

Analyzing the proof of Kirszbraun's theorem

Kirszbraun's theorem 1934 Let $A \subset \mathbb{R}^n$. If $f \colon A \rightarrow \mathbb{R}^m$ is a $L$-Lipschitz function, then there exists an extension $F \colon \mathbb{R}^n \rightarrow \mathbb{...
user avatar
  • 451
3 votes
2 answers
90 views

How exactly does Halmos define an ordered pair?

Halmos writes in "Naive Set Theory": Given the set ${X}$, consider the collection $W$ of all well-ordered subsets of $X$. Explicitly: an elememt of $W$ is a subset $A$ of $X$ together with ...
user avatar
0 votes
0 answers
17 views

What does the second property in Halmos definition of continuation mean?

Halmos defines in his book "Naive Set Theory" that a well-ordered set A is a continuation of a well-ordered set B if B is a subset of A B is an initial segmemt of A the ordering of the ...
user avatar
2 votes
1 answer
55 views

If $Y$ is a closed and bounded subset of an ordered space $X$ then is it compact?

Let be $(X,\preccurlyeq)$ a totally ordered set. So if $Y$ is a bounded and closed subset of $X$ with respect the order topology then is it compact? if this is not generally true then is it true when $...
user avatar
0 votes
1 answer
88 views

How can i show that this set has no smallest element?

This is an example from Halmos book "Naive Set Theory": Let $\omega$ be the set of all natural numbers. Then let $\leqq$ be a relation on $\omega \times \omega$ with $ (a, b) \leqq(x, y)$ ...
user avatar
0 votes
1 answer
60 views

Prove without the well ordering principle that no m exists such that $n < m < n + 1$ for positive integers $m$ and $n$. [duplicate]

I'm trying to prove without the well ordering principle that no integer $m$ exists such that $n < m < n + 1$ for positive integers $m$ and $n$. I know there's a proof here that uses the well ...
user avatar
  • 322
2 votes
1 answer
34 views

On a decomposition of pairs in the transitive closure $T$ of an arbitrary relation $R$

Let $S$ be some set, and let $R$ be a relation with $\operatorname{dom}(R) = \operatorname{ran}(R) = S$. Hence $R \subseteq S \times S$. Let $T$ be the transitive closure of $R$, defined as the ...
user avatar
  • 13.5k
1 vote
0 answers
99 views

Does any non-maximal element of a well-ordered set have a unique successor?

$\newcommand{\setcomplement}[2]{#1 \setminus #2}$ $\newcommand{\singleton}[1]{\left\{#1\right\}}$ $\newcommand{\segment}[2]{\operatorname{Seg}_{#1}\left(#2\right)}$ I wanted to find the smallest ...
user avatar
  • 1,526
1 vote
0 answers
31 views

Condition on proper lower sections on total ordering for it to be a well-ordering

Context: trying to get someone else to do my thinking for me. Reference: Smullyan and Fitting: Set Theory and the Continuum Problem (rev ed. 2010) Chapter $4$: Superinduction, Well-Ordering and Choice:...
user avatar
  • 4,349
1 vote
1 answer
28 views

Why is this step required in the proof of sum of first $n$ odd numbers using the Well Ordering Principle?

I came across this question while doing $\text{6.042J}$ from MITOCW. I have a doubt in the part c, namely, why do we need to manipulate the formula in that way? Here is my solution so far to the ...
user avatar
  • 1,392
2 votes
1 answer
55 views

Showing that 49¢ is not makeable using the given conditions

While going through 6.042J from MITOCW, in the text Mathematics for Computer Science, I came across the following problem at which I'm stuck. Now, I proceeded doing the proof in the following manner. ...
user avatar
  • 1,392
4 votes
1 answer
65 views

Perfect subset of $<_L$

The Bernstein construction of a set without the perfect set property gives, from a $\Sigma^1_2$ well-order of the reals, a $\Sigma^1_2$ set without the perfect set property. What I'd like to know is ...
user avatar
0 votes
1 answer
15 views

A question about well-orders with the same domain

Let $A$ be a set and suppose there are two relations on $A$, say $R$ and $S$, such that $(A,R)$ and $(A,S)$ are well-orders with the same order type, i.e. $(A,R)\cong(A,S)\cong(\alpha,\in)$ for some ...
user avatar
  • 111
1 vote
1 answer
49 views

Well Ordering Principle to prove the Distributive Law of union over the intersection of n sets

I am looking for hints on solving the below problem from a textbook (copied as given): Union distributes over the intersection of two sets: $A\cup (B\cap C)$ Use the above and the Well Ordering ...
user avatar
  • 185
0 votes
0 answers
21 views

Maximum of well-ordered sets and its set of limits

In Judith Roitman's "Introduction to Modern Set Theory", the theorem 34c in the first chapter seems not to hold. Since it seems weird that it is actually the case, especially because my ...
user avatar
  • 315
0 votes
0 answers
34 views

$\gamma<\theta$ iff $\gamma\in\theta$

I'm struggling with my homework: Let $\gamma,\theta$ be order types. Then, $\gamma<\theta$ iff $\gamma\in\theta$. I already proved that if $\gamma\in\theta$, then $\gamma<\theta$. To do the ...
user avatar
  • 135
1 vote
0 answers
24 views

Prove that if W is an initial segment of X×Y then there exists an initial segment V in Y such that X×V is an initial segment of X×Y containing W

Given a ordered set $(X,\preceq)$ for any $\xi\in X$ we call the set $$ I_\xi:=\{x\in X:x⪱\xi\} $$ the initial segment of $\xi$. Now if $(X,\preceq)$ and $(Y,\precsim)$ are two ordered sets then it is ...
user avatar
0 votes
1 answer
95 views

Is the powerset of the real numbers well orderable? [closed]

I know that $\mathbb N$ is well orderable and $\mathscr{P}(\mathbb N)$ (the real numbers) are well orderable, so I was wondering if $\mathscr{P}(\mathscr{P}(\mathbb N))$ is also well orderable. I ...
user avatar
  • 821
5 votes
2 answers
131 views

Does ZF prove that the union of a $\subseteq$-chain of well-orderable sets is again well-orderable?

I'm interested in this mis-transcription of Folland: https://proofwiki.org/w/index.php?title=Zorn%27s_Lemma_Implies_Well_Ordering_Theorem&oldid=356679. It is dubiously stated that the union of a $\...
user avatar
  • 1,356
1 vote
0 answers
48 views

State if each of the objects' set is well-defined or not.

Q. 1.1 taken from book titled: First-Semester Abstract Algebra: A Structural Approach, by: Jessica K. Sklar. State if each of the below objects stated below is a well-defined set or not. $\{z\in \...
user avatar
  • 4,159
3 votes
1 answer
148 views

Every metric space is paracompact (an elegant proof)

I'm studying a different proof to show that each metric space is paracompact in the book: Singh, Tej Bahadur-Introduction to Topology. It is a very elegant construction unlike the inductive method ...
user avatar
3 votes
1 answer
103 views

What is the intuitive meaning of a transitive set?

I'm now working my way through some basic set theory, and I came across the concept of an ordinal. In the book (and many other books), a transitive set is first defined as a set $x$ that satisfies $\...
user avatar
  • 187
2 votes
1 answer
50 views

Relation between a fixed point and being a well-order

I've been trying to prove the following, but with no particular success: Given a linear order $\leq$ on $A$, define $\pi:2^A\to 2^A$ by $X\mapsto\{y\in A: (\forall x < y)(x\in X) \}$. Let $A_0$ be ...
user avatar
  • 11k
0 votes
1 answer
70 views

Supremum in well orderings

Problem *x7.27 from Moschovakis' textbook is asking to define a definite operation $\sup \mathscr E $, such that for every family $\mathscr E$ of well-ordered sets, $\sup \mathscr E$ has the following ...
user avatar
  • 11k
4 votes
2 answers
212 views

Maximal element of infinite well ordered set

Can an infinite well ordered set $A \subseteq \mathbb{R}$ have a greatest element? I've read it a couple of times that the answer is yes, but I just couldn't agree with that. If set $A$ is well ...
user avatar
0 votes
1 answer
49 views

Help understanding construction of the least uncountable ordinal

In my notes the construction of the least ordinal follows from taking the supremum of the image of the set $$ R=\{ A\in \mathcal{P}(\mathbb{N}\times\mathbb{N}) : A\text{ is a well-ordering of a subset ...
user avatar
1 vote
1 answer
43 views

Comparability theorem for well ordered sets using transfinite recursion

Similar questions have already been asked here and here. But I am asking for verification of my proof. Halmos leaves out an "easy" transfinite induction argument, which I have struggled to ...
user avatar
  • 2,085
1 vote
1 answer
53 views

Partial ordered can be extended to total orders

I am studying Halmos' Naïve Set Theory, and in Section 17, Well Ordering, he mentions the following exercise: Prove that if $R$ is a partial order in a set $X$, then there exists a total order $S$ in ...
user avatar
  • 2,085
3 votes
1 answer
69 views

A chain of well ordered sets defines a "unique" well order on the union of chains?

Halmos in his Naïve Set Theory, states the following result in Section 17, Well Ordering: If a collection $\mathscr C$ of well ordered sets is a chain with respect to continuation, and if $U$ is the ...
user avatar
  • 2,085
5 votes
1 answer
159 views

Union of powers of a well-ordered set is well-ordered.

While studing a certain type of rings I was trying to solve the following exercise (which is what I need to prove that this ring is well defined): Let $S$ be a well-ordered subset of an ordered group $...
user avatar
  • 1,462
0 votes
1 answer
39 views

Why to include set inclusion in the definition of continuation of well ordered sets?

In his Naïve Set Theory, Halmos defines, in Section 17, Well Ordering, the following: We shall say that a well ordered set $A$ is a continuation of a well ordered set $B$, if, in the first place, $B$ ...
user avatar
  • 2,085
1 vote
1 answer
119 views

Zorn's lemma and maximal elements

This continues a discussion begun at checking Zorn's lemma on an example where an example was offered to help understand maximal elements and Zorn's lemma. That example used the set {1,...,100} ...
user avatar
6 votes
2 answers
228 views

Strange property of Well-Ordering on an Uncountable Set

Background I was messing around with well-orderings of uncountable sets, and proved the following theorem. It seems a little strange to me, and I am curious if anyone here has encountered something ...
user avatar
1 vote
2 answers
49 views

Well Ordering implies Induction Proof doubt

I’m trying to understand the proof for the fact that that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, if S ⊂ N such that 1 ∈ S and n + 1 ∈ S whenever n ∈ S,...
user avatar
  • 133
7 votes
1 answer
132 views

Any Well-Ordering of $\mathbb{R}$ has no Corresponding Metric

Background I have been doing some reading over winter break so far and found the idea that $\mathbb{R}$ has a well-ordering strange. So I have been thinking about it a little and was wondering if my ...
user avatar
0 votes
0 answers
48 views

Please Check My Proof of Well-Ordering Principle using Induction

Well-Ordering Principle: $\exists m \in A[\forall n \in A (m \in n \vee m = n) ]$ for all $A \subseteq w$ where $w$ is the set of natural numbers and $A \neq \phi$. Base Case: $A_{1} = \{ e_{1} \}$ is ...
user avatar
5 votes
1 answer
125 views

Proof of Comparability Theorem for well-ordered sets using transfinite recursion

I am reading through Halmos's "Naive Set Theory". In Section 18, Halmos uses transfite recursion to prove the Comparability Thereom for well-ordered sets: The assertion is that if $\langle ...
user avatar
0 votes
0 answers
61 views

Prove $n^2 < 2^{n+1}$ by well-ordering

Please help me prove $n^2 ≤ 2^{n+1}$ by the well-ordering (not induction) $n\in\Bbb N \setminus \{{0\}}$ I've assumed that $n=1$ is not counter example so $m > 1$ and now try with $n = m-1$. $$(m-1)...
user avatar
1 vote
1 answer
31 views

Propositional Functions with Well-Ordering/Strong Induction

I'm having trouble with this problem: $P(k)$ is a propositional function in the natural numbers $\mathbb{N}$. $P(1)$ is true. Further, $\forall j,k \in\mathbb{Z}(\, [P(j) \land P(k)] \implies P(j+...
user avatar

1
2 3 4 5
10