All Questions
Tagged with well-orders proof-writing
20
questions
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 ...
- 377
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
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 ...
- 11
1
vote
0
answers
174
views
Prove: $X$ is well orderable $\implies$ $X \times X$ is well orderable [duplicate]
I am studying a course on ZF Set Theory and have recently been considering whether or not $X$ being well orderable implies that $X \times X$ is well orderable.
More formally my question is the ...
- 4,331
0
votes
1
answer
70
views
Initial segment of well ordered set
An initial segment (B) of an well-ordered set $(A,<)$ is a subset $X⊊A$ such that, for all $x \in X$ and for all $y∈A$ such that $y<x, y∈X$.
I want to prove that this set is equal to $A_z =$ { $...
- 3
0
votes
0
answers
80
views
Order-Preserving Bijective Function
Consider the question:
Show that any two open intervals of $\mathbb{R}$ are isomorphic.
Definition. Given two well-ordered sets $(A, <_A)$, $(B, <_B)$, we say that $A$ and $B$ are isomorphic if ...
- 95
1
vote
1
answer
278
views
Well ordering theorem and Zorn's lemma implies the axiom of choice.
I am curently studying the well ordering theorem's(WOL) and zorn's lemmas's(ZL) equivalence with the axiom of choice(AOC). I have constucted the proofs of WOL and ZL implying AOC as below:
...
- 183
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
0
votes
2
answers
249
views
Do we need to rigorously prove why a set is non-empty with non-negative integers?
For proofs using Well-Ordering Principle(WOP), can we prove the set is a non-empty set of nonnegative integers simply by "stating"?
Eg of what I mean by "stating":
Given any integer $n$ and any ...
- 413
0
votes
2
answers
810
views
Proving two sets $A, B$ are order isomorphic
Let $A, B$ be well ordered sets. If $A$ is order isomorphic to a subset of $B$, and $B$ is order isomorphic to a subset of $A$, prove that $A, B$ are order isomorphic.
I know that two well ordered ...
- 596
2
votes
0
answers
87
views
Mathematics for Computer Science Prob. 2.6 Well Ordering Principle
Problem
(From Mathematics for Computer Science (Lehman, Leighton, Meyers), Prob. 2.6)
You are given a series of envelopes, respectively containing 1, 2, 4,
..., $2^m$ dollars. Define
Property m: For ...
- 2,866
1
vote
1
answer
73
views
Sets well ordered under different operations Proving
$(a)\quad R^+ \cup \{0\}, <$
$(b)\quad [0,1], >$
$(c)\quad \text{The set of integers divisible by 5}, <$
$(d)\quad \{\{0,1,...,n\}|n ∈ N\},⊆$
I believe that:
(a) Is not well-ordered ...
- 233
1
vote
1
answer
365
views
How can I prove this by well ordering principle?
So the problem is that:
Use the Well Ordering Principle (WOP) to prove that
$2+4+···+2n = n(n+1)$
for all $n > 0$.
1.My first thought is that we can create a set named $C::=\{n>0\mid2+4+·...
- 63
1
vote
1
answer
127
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 ...
- 402
0
votes
3
answers
202
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$.
...
