All Questions
Tagged with well-orders discrete-mathematics
32
questions
2
votes
1
answer
42
views
Are these two notions of weak well-foundedness equivalent?
Background (optional): I have a state transition system $Q$ with two "kinds" of transitions: progress-making ($\delta_P : Q \times \Sigma \rightarrow Q$) and non-progress making ($\delta_N : ...
- 685
0
votes
1
answer
41
views
Prove $\sum_{i=0}^n 2^i=2^{n+1}-1$ using WOP
So I defined my predicate $P(n)$ according to the theorem, and then I said there there exists an integer $n\ge0$ such that $P(n)$ is false. And I let $C$ be the set of all such $n$. And by WOP, there ...
0
votes
1
answer
51
views
Detemine whether the interval [4,8] is well-ordered. Explain.
I don't think this interval is well-ordered because the subset (4,8) would not have a smallest value. I'm stuck on how to show (4,8) has no smallest value.
- 15
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
2
votes
0
answers
51
views
Using the Principle of Well Order, show that for all $n \in N$ it holds that $4^n -1$ is divisible by 3.
Using the Principle of Well Order, show that for all $n \in N$ it holds that $4^n -1$ is divisible by 3.
I have already defined the set of counterexamples $C$, then I proved that for $n=1$ the ...
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
3
votes
4
answers
687
views
Why can't well ordered sets have infinite decreasing subsequences?
Chapter 2 of Mathematics for Computer Science presents the following:
Define the set $\mathbb F$ of fractions that can be expressed in the form $\frac{n}{n+1}$. Define $\mathbb N$ as the set of ...
- 47
1
vote
0
answers
81
views
Every Non empty subset has a least element implies linear order
Suppose $(A,R)$ be structure where R is a binary relation on $A$.
Suppose $A$ has the property that every Non empty subset of $A$ has a least element w.r.t. the relation $R$. Then $R$ is a linear ...
user1072974
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
1
answer
95
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 ...
- 1,454
2
votes
1
answer
83
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.
...
- 1,454
0
votes
0
answers
73
views
The Well-Ordering principle
I came out with this proof for the Well Ordering principle but couldn't find anything similar on the internet and was wondering if it's wrong
...
- 29
0
votes
0
answers
246
views
What is the order type of a lexicographic ordering on the natural numbers?
I know that the order type of an ordering is the unique ordinal that it is order-isomorphic to. And I know that a lexicographic ordering on $\mathbb{N}$ x $\mathbb{N}$ is a well-order, so there ...
- 13
0
votes
0
answers
335
views
How many different posets, well-order relations are there on a set of size n.
can any one help me i can't find total number of partial orders on a set of size n
also help me with total number of well-orders on a set of size n ..
OEIS has Number of partially ordered sets ("...
0
votes
1
answer
146
views
Well ordering principle for mini tetris
Prove using well ordering principle that for all $n\ge 0$, the number $T_n$ of tilings of a $n \times 2$ tetris board is : $\frac{3^{n+1} + (-1)^{n}}{4}$
I am using MIT OCW to learn this on my own.
...
- 439