All Questions
Tagged with well-orders induction
38
questions
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
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
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
0
votes
2
answers
92
views
I dont understand induction on well-orders
Question: (Induction on well-orders) Suppose < is a well-order on A. Suppose $\phi(x)$ is a formula such that for every y $\in A$, if $\phi(x)$ holds for all $x<y$, then $\phi(y)$ holds for all ...
1
vote
2
answers
89
views
Induction extended to ordered pairs: Application of the First Principle of Finite Induction to proving Bertrand’s Ballot Theorem.
In this question, the comments stated the existence of Bertrand’s Ballot Theorem. In reading the article, I found a peculiar application of proof by induction. The text is as follows:
We loosen the ...
- 6,672
1
vote
2
answers
145
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,...
- 143
0
votes
0
answers
59
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 ...
- 137
1
vote
1
answer
34
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+...
- 21
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
320
views
Well-ordered sets two examples
Say I have the following two sets:
$\mathbb{R} \cup \{ 0\}$ under < (less than operator)
$\{(a,b) | a,b \in \mathbb{Z^+} \}$ under $(a,b) \prec (c,d) \iff (a<c) \land (b <d)$.
For $\mathbb{...
- 313
3
votes
3
answers
159
views
Proving $n\leq3^{n/3}$ for $n\geq0$ via the Well-Ordering Principle [2]
I know this question was already asked in here, but it was never marked as answered and all the solutions base themselves on the fact that $3(m-1)^3 < m$, what comes from assuming $3^m < m$ and ...
- 165
1
vote
1
answer
79
views
Does "normal" induction work in any well-ordered set?
This is a follow up from this question.
I want to prove whether the usual "induction theorem" works in a general well-ordered set $A$:
If $(A,\preccurlyeq)$ is a well-ordered chain, $\Phi(\...
- 8,728
0
votes
2
answers
147
views
Can the well-ordering principle of the natural numbers replace the principle of mathematical induction in Peano axioms?
The well-ordering principle of the natural numbers states that the natural numbers are well-ordered through it's usual ordering.
I've already seen a demonstration of the principle of mathematical ...
- 3,901
1
vote
1
answer
113
views
Questions about the Strong Induction Principle and the Well Ordering Principle
The Strong Induction Principle (SIP) is presented in Hrbacek and Jech's Introduction to Set Theory (3 Ed) as follows:
Let $P(x)$ be a property. Assume that, for all $n \in \mathbb{N}$,
(*) if $P(k)$ ...
- 307
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