Constructing Nonlinear Well-Founded Orders

  • Thread starter Thread starter dirtybiscuit
  • Start date Start date
  • Tags Tags
    Set
Click For Summary
The discussion centers on understanding nonlinear well-founded orders, specifically how certain functions define these orders. A function ƒ: S→N creates a well-founded order by comparing values, as seen in examples like lists by length and binary trees by depth. The confusion arises with the absolute value ordering of ℤ, where elements appear comparable, yet the order is nonlinear because not all pairs of elements can be compared directly. The key point is that while some elements seem ordered, the definition of nonlinear orders allows for incomparability among certain elements. This highlights the distinction between linear and nonlinear orders in set theory.
dirtybiscuit
Messages
8
Reaction score
1

Homework Statement


My teacher has notes online that say:

A Simple Construction Technique for WellFounded Orders
Any function ƒ : S→N defines a wellfounded order on S by
x < y iff ƒ(x) < ƒ(y).

Example:
Lists are wellfounded by length. Binary trees are wellfounded by depth, by number of nodes, or by number of leaves. ℤ is wellfounded by absolute value.
Derivations for a grammar are wellfounded by length. These orders are nonlinear.

I am having trouble understanding how these are non-linear orders. Particularly "ℤ is wellfounded by absolute value". From my understanding a linear order is where each element in the set is comparable to the other elements of the set.

So for the abs of ℤ the order I think we get is:
0, -1, 1, -2, 2, -3, 3, ...

which seems like -1 < -2 < 3 and so on because of the way we defined it and thus they are comparable. Am I misunderstanding something in this?
 
Physics news on Phys.org
dirtybiscuit said:
which seems like -1 < -2 < 3 and so on because of the way we defined it and thus they are comparable.
Right.
The usual ordering of Z is not relevant here.
 

Thread 'Distance between a Clock's hands when the distance is increasing most rapidly'

Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?
View full post »

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Is the Max Function a Norm in R^3?
  • · Replies 6 ·
Replies
6
Views
2K
Does a refl/anti-symm relation on a set A have this property?
  • · Replies 1 ·
Replies
1
Views
1K
Avoid unpleasant integrals in solving IVP
  • · Replies 3 ·
Replies
3
Views
2K
How Do Vector Spaces of Linear Maps Differ from Standard Vector Spaces?
  • · Replies 9 ·
Replies
9
Views
2K
How should I find ## x_{2}(t) ## for this nonlinear integro-differential equation?
  • · Replies 6 ·
Replies
6
Views
2K
Least Upper Bound Property ⇒ Archimedean Principle
  • · Replies 1 ·
Replies
1
Views
2K
Prove Hausdorff's Maximality Principle by the W.O.P.
  • · Replies 2 ·
Replies
2
Views
2K
Prove ##a + b = b + a## using Peano postulates
  • · Replies 3 ·
Replies
3
Views
2K
Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
  • · Replies 3 ·
Replies
3
Views
893