Constructing Nonlinear Well-Founded Orders

  • Thread starter Thread starter dirtybiscuit
  • Start date Start date
  • Tags Tags
    Set
Click For Summary
SUMMARY

The discussion focuses on the construction of nonlinear well-founded orders using functions that map sets to natural numbers. Specifically, it highlights that any function ƒ: S→N can define a well-founded order on set S by the relation x < y if ƒ(x) < ƒ(y). Examples provided include lists ordered by length, binary trees by depth or number of nodes, and the integers ℤ ordered by absolute value. The confusion arises from the misconception that nonlinear orders lack comparability, which is clarified by emphasizing that the usual ordering of ℤ is not applicable in this context.

PREREQUISITES
  • Understanding of well-founded orders and their definitions
  • Familiarity with functions and mappings in set theory
  • Basic knowledge of nonlinear order concepts
  • Comprehension of absolute value and its implications in ordering
NEXT STEPS
  • Research the properties of well-founded orders in set theory
  • Explore examples of nonlinear orders beyond integers, such as graphs
  • Study the implications of absolute value in ordering sets
  • Learn about the differences between linear and nonlinear orders in depth
USEFUL FOR

Mathematicians, computer scientists, and students studying order theory, particularly those interested in set theory and its applications in algorithms and data structures.

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.
 

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
Avoid unpleasant integrals in solving IVP
  • · Replies 3 ·
Replies
3
Views
2K
Does a refl/anti-symm relation on a set A have this property?
  • · Replies 1 ·
Replies
1
Views
1K
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
3K
Least Upper Bound Property ⇒ Archimedean Principle
  • · Replies 1 ·
Replies
1
Views
2K
My first exercise on Group Theory
  • · Replies 7 ·
Replies
7
Views
2K
Prove Hausdorff's Maximality Principle by the W.O.P.
  • · Replies 2 ·
Replies
2
Views
2K
Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
  • · Replies 3 ·
Replies
3
Views
2K