Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence classes of Cauchy sequences

  1. Sep 8, 2010 #1

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    [itex]\mathbb R[/itex] can be defined as "any (Dedekind-)complete ordered field". This type of abstract definition is a different kind than e.g. the "equivalence classes of Cauchy sequences" construction. I prefer abstract definitions over explicit constructions, so I would be interested in seeing similar definitions for [itex]\mathbb N,\mathbb Z,\mathbb Q,\mathbb C[/itex]. I think I know the answer for [itex]\mathbb Q[/itex] and [itex]\mathbb C[/itex], so my main concerns are [itex]\mathbb N[/itex] and [itex]\mathbb Z[/itex].

    I'm familiar with the following definition of a structure based on Peano's axioms:

    Suppose S is a unary operation on a set N, and that 0 is an element of N. The triple (N,S,0) is said to be a Peano system (let me know if that's not the appropriate term), if

    (1) S is injective
    (2) For all x in N, S(x)≠0
    (3) If [itex]0\in E\subset N[/itex] and [itex]S(x)\in E[/itex] for all x in E, then E=N.

    Just like with the real numbers, it's possible to show that all structures of this sort are isomorphic, so that it doesn't matter which one of them we call "the natural numbers".

    Now how do we include the two binary operations and the total order? Do we have to construct them explicitly from the successor function S, or is there a different way to do it? How about this:

    Suppose S is a unary operation on Z, that + and · are binary operations on Z, that 0 is a member of Z and that < is a binary relation on N. The 6-tuple (Z,S,+,·,0,<) is a "foo" (a term I just made up because I don't know if there is a term for this), if

    (Edit: I have changed this twice after I posted. First I got some of my ideas for the natural numbers and the integers mixed up, and then I made it more complicated than it needs to be. The structure I'm defining here is supposed to be [itex]\mathbb Z[/itex]).

    (1) (Z,+,·) is an abelian ring (with an identity element).
    (2) < is a strict total order.
    (3) [itex]\big(Z-\{n\in Z|n<0\},S,0\big)[/itex] is a Peano system.
    (4) S(0)=1.


    Then we prove that all foos are isomorphic (I haven't tried to do this yet) and decide to call the members of a foo (any foo) "integers".

    Have you seen a definition like this in the literature?

    (And yes, I'm familiar with the construction [itex]0=\emptyset,\ S(n)=\{n\}\cup n[/itex] for the natural numbers. I haven't studied the details yet, but at least I own a good book that covers that very well).
     
    Last edited: Sep 9, 2010
  2. jcsd
  3. Sep 8, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Re: Integers

    A long time ago, I wrote a detailed description of how we can "construct" the various number systems, but I have since lost it! Let me see how much of it I can reconstruct here.

    One way of "constructing" the non-negative integers is to assert that "0" is the empty set, that "1" is the set whose only member is the empty set: { {}} or {0}, 2 is the set whose only members are "0" and "1", etc. We define the "successor" of n (in the sense of the Peano axioms) to be the set containing n and all of its elements. One can then show the Peano axioms are satisified. We can define "addition" in a Peano system by "
    If c= 0, then a+ c= a. If [itex]c\ne 0[/itex] then there exist b such that c is the successor of b: c= s(b). Then we define a+ c= s(a+ b).

    Similarly, If c= 0, we define ac= 0. If [itex]c\ne 0[/itex] then there exist b such that c= s(b) and we define ac= ab+ a.

    The proofs of all the properties of the non-negative integers is can be got from these, basically using "proof by induction" which is, after all, the whole point of Peano's axioms.

    Given the non-negative integers, we can define all integers by looking at the set of ordered pairs (a, b) of non-negative integers. We then define an equivalence relation on this set by "(a, b) is equivalent to (c, d) if and only if a+ d= b+ c". It is easy to show that this is an equivalence relation and we then define the integers to be the set of all equivalence classes defined by this equivalence relation. We define sum by: if [itex]\alpha[/itex] and [itex]\beta[/itex] are such equivalence classes, to find [itex]\alpha+ \beta[/itex], take one member, x, of the set [itex]\alpha[/itex] and one member, y, of [math]\beta[/math]. x and y are non-negative integers, of course. [itex]\alpha+ \beta[/itex] is then defined to be the equivalence class that x+ y belongs to. We define [itex]\alph\beta[/itex] similarly. Of course, one has to show that these are "well-defined"- that is, show that if we chose different x and y from the same equivalence classes, we would still get the same equivalence class for sum and product. Essentially what happens is that there exist one equivalence class of all pairs of the form (x, x)- that is, the two members are equal. That equivalence class is the identity element, 0. Given any positive integer c, there is a set of all pairs (a, b) such that a- b= c. That equivalence class is essentially the number c. There also is a set of all pairs (a, b) such that b- a= c. That equivalence class is essentially the number -c.

    Given the integers, we can define the rational numbers in a similar way: consider the set of all pairs, (a, b), such that a is an integer and b is an integer other than 0. We define "(a, b) is equivalent to (c, d) if and only if ad= bc". We then define addition and multiplication of rational numbers [itex]\alpha[/itex] and [itex]\beta[/itex] by: choose members, (a, b) from [itex]\alpha[/itex] and and (c, d) from [itex]\beta[/itex]. [itex]\alpha+ \beta[/itex] is the equivalence class containing (ad+ bc, bd) and [itex]\alpha\beta[/itex] is the equivalence class containing (ac, bd).
     
  4. Sep 9, 2010 #3

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Integers

    Thank you, but that's not really what I'm looking for. Let me explain what I'm thinking. The complex numbers has a subfield with all the properties of the real numbers. We don't usually say that it's isomorphic to the real numbers, we say that it is the real numbers. Similarly, we don't usually say that [tex]\mathbb Q[/tex] is isomorphic to a subfield of [tex]\mathbb R[/tex]. We say that [tex]\mathbb Q[/tex] is a subfield of [tex]\mathbb R[/tex]. You could argue that the usual terminology is a bit sloppy, but you could also argue that it isn't, and that it's more consistent with the usual terminology to define [tex]\mathbb R[/tex] to be any Dedekind-complete ordered field, than to define it to be specifically the "completion" of [tex]\mathbb Q[/tex]. I also don't want to define [tex]\mathbb R[/tex] to be "the completion of [tex]\mathbb Q[/tex], and all fields that are isomorphic to it", because that's not consistent with how we define the terms we associate with other classes of structures. We don't define the term "vector space" by explicitly constructing one member of each isomorphism class. We do it abstractly, by specifying the properties that a structure has to have to earn the name "vector space". I think it makes more sense to use that approach for all structures, even the ones like [tex]\mathbb R[/tex] and [tex]\mathbb N[/tex], that are so constrained by the abstract definition that there's only one isomorphism class. If we take the approach I'm suggesting, the constructions shouldn't be viewed as definitions, but as proofs that structures with the desired properties exist in ZFC.

    So I'm really looking for a "a ring such that..."-type of definition of the integers, and something similar for the natural numbers.
     
    Last edited: Sep 9, 2010
  5. Sep 9, 2010 #4
    Re: Integers

    I think that the first five pages of this pdf file answer your question. In brief, the integers are the unique ordered commutative ring whose positive elements have the Induction Property. However, the cited paper doesn't prove this statement.

    Petek
     
  6. Sep 9, 2010 #5

    Landau

    User Avatar
    Science Advisor

    Re: Integers

    [itex]\mathbb{Z}[/tex] is the unique ordered integral domain with unit whose non-negative elements are well-ordered.
     
  7. Sep 9, 2010 #6

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Integers

    Thanks guys. Those are the sort of definitions I wanted to see. Fraleigh says that an integral domain is a commutative ring with identity and no divisors of 0, so the only differences between the two definitions are the "induction vs. well-ordering" stuff and the "no divisors of 0" requirement. Hm, Greenleaf proves that there are no divisors of 0 in proposition 2.1.7, and in appendix A, he proves that the induction property is equivalent to the well-ordering of the positive part.

    So as far as I can tell, these two definitions are equivalent. The one Landau posted includes an axiom that can be proved as a theorem (no divisors of 0), so I would prefer to replace "integral domain" with "commutative ordered field with identity" (even though I don't have to).
     
  8. Sep 9, 2010 #7

    Landau

    User Avatar
    Science Advisor

    Re: Integers

    The correct term is "zero divisor". An integral domain is a unital commutative ring without zero divisors, meaning that ab=0 implies a=0 or b=0. Who/what book is Greenleaf? What does prop.2.1.7 assert? Indeed, induction and well-ordening are two sides of the same coin.
     
  9. Sep 9, 2010 #8
    Re: Integers

    "Greenleaf" refers to the pdf file linked in my previous post.

    Petek
     
  10. Sep 9, 2010 #9

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Integers

    Landau: Fraleigh writes "divisors of 0 (or 0 divisors)" in the fourth edition of "A first course in abstract algebra". Doesn't seem like an important distinction. He also says "ring with unity" instead of "ring with identity" (as I did) or "unital ring" (as you did in #7), but that's of course also unimportant. He also defines "unit" as something different than "unity". The former is any element with a multiplicative inverse, and the latter is the multiplicative identity. I've seen the word "unital" in Wikipedia articles.

    Proposition 2.1.7(a) goes roughly like this. Suppose that xy=0 for non-zero x and y. If x and y are both positive, then so is xy, because by his definition of "ordered", the positive part is closed under multiplication. If one or both are negative, we can multiply by -1 once or twice as needed to get an expression of the form ab=0 where ab is actually positive because a and b are positive. So the assumption always leads to a contradiction.
     
    Last edited: Sep 9, 2010
  11. Sep 9, 2010 #10

    Landau

    User Avatar
    Science Advisor

    Re: Integers

    Ah, of course.
    Ok, I had never seen "divisor of zero" before, but you're right: it is not important.

    As for "unit", "identity", and related notions: they are used in so many contexts that there is probably no standard.
     
  12. Sep 9, 2010 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Integers

    Some other characterizations, many equivalent:

    (N,0,+) is the free monoid on 1 element, (Z,0,+) is the free group on 1 element, (Z,0,1,+,*) is the free ring on 0 elements.

    The ring of integers is any ring A such that, for all rings B, Hom(A,B) has a unique element.

    If a field can be made a subfield of every field of characteristic 0, then it is a field of rational numbers.



    Category theory likes the "recursion" characterization of the natural numbers rather than the "induction" characterization:

    In a category with terminal object I (e.g. the one-point set in Set), consider triples (X,f,i) consisting of an object X, an map f:X-->X, and a map i:I-->X, along with the corresponding notion of homomorphism of triples. (In Set, this is a variety of universal algebra with a constant and a unary operation)

    A Natural Number Object is an initial object in the category of such triples. Explicitly, (N,s,z) is a natural number object if and only if, for every other triple (X,f,i), there is a unique map r:N-->X such that:
    • rz = i
    • rs = fr

    In Set, this is the recursion theorem: there is a unique N-indexed X-valued sequence r such that
    • r0 = i
    • rn+1 = f(rn)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook