All Questions
Tagged with well-orders logic
30
questions
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
0
votes
2
answers
145
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 ...
- 346
1
vote
1
answer
126
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^{<...
- 438
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 ...
- 3,029
1
vote
1
answer
95
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 ...
- 10.4k
0
votes
0
answers
66
views
Does a total or well ordering has a countable cofinal
I read a post sometime earlier asking about the cardinality of total ordering on a set, which I forgot about the detail but led me to this question.
For a total/well-ordered set $A$ does there exist ...
- 1,732
1
vote
1
answer
70
views
Induction principle on well ordered set
I'm new and very grateful this site exists. If I do something wrong, feel free to tell me.
I have to prove the following:
Let $S$ be a subset of a well ordered set $L$ with the conditions:
a) $0_L \in ...
- 291
2
votes
2
answers
145
views
What is the meaning of "induction up to a given ordinal"?
Given an ordinal $\alpha$, what does it mean: "induction up to $\alpha$"? When $\alpha=\omega$, is this is ordinary mathematical induction? Also, Goodstein's Theorem is equivalent to "...
- 4,442
0
votes
0
answers
118
views
A Doubt about Well Ordering Principle and Principle of Mathematical Induction
I have had this lingering doubt in my mind for a very long time: One of the standard constructions of N starts by assuming the 5 Peano Axioms, proving that every non-zero is a successor and s(n) is ...
- 21
1
vote
1
answer
100
views
Why does model theory treat well-ordered but uncountable languages?
In model theory, results such as the Compactness theorem and the Löwenheim–Skolem theorem hold true, not only in countable languages, but in well-ordered languages.
I'm not questioning this idea in ...
- 1,779
0
votes
1
answer
56
views
Confusion Regarding Notation in a Proof about two Well-Ordered Sets
This partial proof is taken from A Course in Mathematical Logic for Mathematicians by Yu. I. Manin.
Lemma. Let X and Y be two well-ordered sets. Then exactly one of the following alternatives holds:
(...
- 1,610
0
votes
1
answer
327
views
An elementary error in Principia Mathematica?
This is a quote from page 1, volume III of Principia Mathematica, by Whitehead and Russell: "A 'well-ordered' series is one which is such that every existent class contained in it has a first ...
- 23
0
votes
1
answer
33
views
$\forall x \in X: (y < x \implies y \in E) \implies x \in E$
Let $(X, \leq)$ be well-ordered and non-empty.
If $E \subseteq X$ satisfies
(i) $\min E \in X$
(ii) $\forall x \in X: ((y < x \implies y \in E) \implies x \in E)$
Then $E=X$.
Proof: Assume $...
user745578
2
votes
1
answer
369
views
Disparity between Induction and Well-ordering Principles
Over classical logic, the induction and well-ordering schemas are equivalent. These schemas state the following, given any linear ordering $(W,<)$ and property $Q$ on $W$:
Induction: $∀k{∈}W\ ( \ ∀...
- 59.2k
1
vote
1
answer
91
views
Can order types of well-ordered proper classes be put in one to one correspondence with $V$?
This is a follow-up to my question here. Ordinals are order types of well-ordered sets. Proper classes can be well-ordered too, the most famous example being the class of all ordinals under the ...
- 10.4k