Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been referred to this website, hopefully you have the background in set theory to help me out here.

Got two questions, the first is on number systems arising out of set theory and the second is a small one about functions. I've tried to be as clear as possible but please bear with me; the only reason I'm posting this is because I'm so confused.

I'm trying to get my bearings on the set-theoretic construction of the natural numbers. Just as I was confused looking at the the way the reals could be axiomatically defined, or constructed by Cantor or Dedekind, or thinking that Cauchy, Weierstrass etc... all had different constructions so now am I going through that with the various explanations of the natural numbers as originating from set theory.

The Peano axioms can be taken as the starting point, but I found out that they could be taken as a theorem in set theory, so I've been trying to do that. It seems that one way is to look at the idea of an ordinal which is a transitive set whose elements are also transitive. But there's also this idea of equivalence classes that apparently lead to contradictions in ZFC. Also there's the Axiom of Infinity method in the wiki link I've given below. Perhaps there's even more, or these are the same in some way I can't see?

A problem arises for me as I've come to believe that rational numbers are defined as a set of equivalence classes, but Wikipedia says that equivalence classes are ruled out of axiomatic set theory so what replaces Q when dealing with ZFC? When you remove equivalence classes from the picture what defines the rational numbers in ZFC? I'm sure whatever you do will generalize to the reals.

I think the question could best be put as follows:

Starting from the most fundamentals, i.e., the axioms of a specific model of set theory, what is the logical and linear progression of topics that leads to the construction of $\mathbb{N}$, then $\mathbb{Z}$, then $\mathbb{Q}$, then $\mathbb{R}$, then $\mathbb{C}$? It seems to me that there are at least two possible methods this way, one using Von Neumann ordinals (with an axiom of infinity?), while the other uses the ideas of relations/equivalence classes etc... If you know anything about how to do this & understand the distinctions between the various methods of doing this could you just let me know, hopefully with a few analogies!

As an aside, I just read earlier that the difference between the Riemann & Lebesgue integrals can be explained by the analogy of a shop taking in money, the Riemann integral adds the money up as it comes in all through the day while the Lebesgue integral separates the coins out at the end of the day according to a certain scheme (i.e. the idea of measure). I'm sure there exists a nice way to picture the two (or more) schemes for constructing the number systems! (I read this earlier & I had to mention it as it would just be so helpful!).

I think equivalence classes originated with Frege & Russell used them but they run into contradictions which ZFC surmounts but Quine's set theory removes the contradictions & allows the use of equivalence classes. I'm sure there is more than just the use of equivalence classes that distinguishes these two seperate constructions. Is it fair to group this into Frege/Russell/Quine on one side & ZFC-Neumann on the other? What about the axiom of infinity description in the wiki link below? Also, I assume that the construction of the number systems in the "Elementary Set Theory with a Universal Set" link below is just the Frege-Quine idea right, I mean it's not another new one is it?

Some links might be helpful for reference of what I'm talking about:

So, that is the current state of my thoughts on this topic, it's taken me a quite a while to figure this meagre stuff out & to find good sources which aren't at the graduate level to learn properly. If I hadn't read all this conflicting stuff I'd be happy to just use the following sources as my main material:

Basically if you could help me clean up my thoughts as regards the above stuff I've written, i.e. 3 different constructions 1) ZFC, 2) Frege Equivalence Relations, 3) Axiom of Infinity & the ∈ relation statement then I could move on to greener pastures!


My second question is brief, just on the topic of a function. First a function is the idea of $y = f(x)$ in school. Then a function is the same thing with domains and ranges. Then you see that a function is really a special case of a mapping $f\colon A \to B$ defined by $f\colon a \mapsto f(a)$.

But the latest thing I've read is that a function is really a set $(A,B,F)$ which is also written as $((A,B),F)$, & I assume it's to indicate order, i.e. a Kuratowski ordered pair, and $F$ is really $F \subseteq A \times B$. This is obviously a relation & it's dictated by the rule [ $$\forall(a\in A)\exists(b\in B)\Bigl( (a,b)\in F\wedge \bigl(f(a)=b\bigr)\Rightarrow (a,b)\in F\Bigr).$$

I'll admit that's not exactly clear, if it's possible to clean this up & clarify it please let me know. For example, where has the little $f$ come from? The general idea here makes a lot of sense & seeing as math is always employing set theory I wish they'd just use this notation from the beginning in books.

So the question is, is this the final resting place for the definition of a function? Could you clean this up for me? Could you give me some references where this definition is explained more clearly, I can't find anything other than a mention on wikipedia & the Ali Nesin set theory notes in the link I've given above.

Thanks so much, I know it's asking a lot of your time!

share|improve this question
1  
Given the length of what you wrote, it would help if you used formatting to make the actual questions more apparent. I stopped reading half-way without finding them... –  Mariano Suárez-Alvarez Jan 12 '11 at 14:43
    
If you keep reading you'll see I sum up everything at the end. The point is that I have to convey the confusion I feel with regard to this issue because the various issues are exactly what has me confused! If I could have boiled it down to an easy question I'd understand it & not need to post lol, if you re-read it all you need focus on is the last paragraph and clarify the details in the body of the post should you need to :) –  sponsoredwalk Jan 12 '11 at 14:48
1  
Just as a comment, ZFC has no issues with equivalence relations, per se. That is, ZFC can think of $\mathbb{Q}$ as equivalence classes of pairs elements of $\mathbb{Z}$, which is thinks of as equivalence classes of pairs of elements in $\mathbb{N}$. The problem only arises when the "set" of elements in an equivalence class is not actually a set - it's too large or too pathological or whatever. –  Jason DeVito Jan 12 '11 at 14:51
    
The discussion of this topic in this link: --- wikipedia.org/wiki/Ordinal_number#Definition_of_an_ordinal_as_an_equivalence_cla‌​ss --- is what has me confused about the particular issue of equivalence classes. Am I to believe that equivalence relations/classes are used in both the Neumann/ZFC formulation as well as the Quine-Frege system? If so that takes away my worries about constructing Q & R from some unknown methods but I'm sure there is a characteristic distinction between both strutures, if anyone could clarify the details it would be extremely helpful! –  sponsoredwalk Jan 12 '11 at 15:01
3  
@sponsoredwalk: Why are you concerned with these foundational technicalities? Only because they are mentioned in passing in Wikipedia? That's not the best place to look for solid expositions on number systems. Instead, see a good textbook, e.g. Ebbinghaus et. al. Numbers. The size considerations that are mentioned in Wikipedia are really of no concern when performing the "small" constructions of N,Z,Q,R. If your primary interest is the number systems (vs. set-theory and associated foundational matters) then these technicalities can be safely ignored for the time being. –  Bill Dubuque Jan 12 '11 at 15:24
show 7 more comments

3 Answers

up vote 2 down vote accepted

A problem arises for me as I've come to believe that rational numbers are defined as a set of equivalence classes, but wikipedia says that equivalence classes are ruled out of axiomatic set theory so what replaces Q when dealing with ZFC? When you remove equivalence classes from the picture what defines the rational numbers in ZFC?

If ZFC weren't capable of talking about equivalence classes it would be a pretty terrible theory. What you probably read is something like the fact that you can't define cardinals as equivalence classes of sets under bijection, and you can't define ordinals as equivalence classes of well-ordered sets under order-preserving bijection. In both cases the problem is that the thing you're trying to take equivalence classes with respect to is too big to be a set, so you can't apply the usual operations of set theory to it. But equivalence classes on sets are perfectly well-defined in the usual way.

(Page 77, notice at the top of the page they say that ∈ is a "well-founded relation". My knowledge of Naive set theory tells me that ∈ is one of two undefinable constructs that you're supposed to take as given (I could quote the sources of this if needed), but here they call it a relation. Surely they don't mean relation in the subset of the cartesian product way do they?

The word "relation" is being used externally here rather than internally. Given a first-order theory $T$ (such as ZFC), models of $T$ are sets equipped with certain functions and relations specified by the theory $T$ satisfying the axioms of the theory, and in ZFC there are no functions and the only relation is $\in$. So this is not naive set theory; this is just set theory. In set theory (as opposed to naive set theory) one must carefully distinguish between "internal" and "external" notions, and the word "relation" here is being used externally.

share|improve this answer
    
Yes that makes sense, I quoted the paragraph that confused me in a response a few minutes ago. I didn't understand the distinction @Bill Dubuque, I am using more than one book to learn this theory currently I've just asked the specific questions in my post which really are about the multiplicity of theories regarding the construction of the number systems & the post contains my confusion about what goes where. I have no problem learning the axiomatic theory from Suppes & Stoll & Truss but none of these books, from my browsing, have answered the questions in my post above. –  sponsoredwalk Jan 12 '11 at 15:52
add comment

Your definition of function is incorrect.

The idea of a "function-as-an-ordered-triple" is the following: to describe a function, we must describe three things: the domain, the codomain, and the rule by which each element of the domain is assigned an element of the codomain. In this setting, we say two functions are equal if and only if they have the same domain, the same codomain, and the same value at every point in the domain.

(Note that we don't always abide by these conventions; for example, we often think of the functions $f\colon\mathbb{R}\to\mathbb{R}$ and $g\colon\mathbb{R}\to[0,\infty)$ given by $f(x)=g(x)=x^2$ as "the same", even though the have different codomain; but in order to be able to talk about "surjective functions", the codomain is important).

So a function requires you to specify three things: the domain, the codomain, and the rule. The rule is a special kind of relation between elements of the domain and elements of the codomain, so it is a subset of the cartesian product of the domain and the codomain. If the domain is $A$ and the codomain is $B$, then the function will be a subset $F\subseteq A\times B$. Not every relation will do, however. What are the two properties that distinguish a function from an arbitrary relation? They are:

  1. Every element of the domain $A$ must have an image in $B$.
  2. Each element of the domain $A$ has only one image in $B$.

Translating this into logical formulas, we have:

  1. $\forall(a\in A)\exists(b\in B)\Bigl( (a,b)\in F\Bigr)$.
  2. $\forall(a\in A)\forall(b,b'\in B)\Bigl( \bigl((a,b)\in F\wedge (a,b')\in F\bigr)\rightarrow (b=b')\Bigr)$.

When we write $F\colon A\to B$, we mean that we are looking at a triple of the form $(A,B,F)$ with $F\subseteq A\times B$ and which satisfies 1 and 2 above. When we write $F(a)=b$, we mean that $(a,b)\in F$.

The first condition says that every element of $A$ has at least one image; the second says that every element of $A$ has at most one image.

Given this, we can define "function from $A$ to $B$" as:

Definition. Let $A$ and $B$ be sets. A function $F$ from $A$ to $B$ is an ordered triple $(A,B,F)$, with $F\subseteq A\times B$ such that $$\forall(a\in A)\exists(b\in B)\Bigl((a,b)\in F\Bigr)\wedge \forall(a\in A)\forall(b,b'\in B)\Bigl( \bigl((a,b)\in F\wedge (a,b')\in F\bigr)\rightarrow (b=b')\Bigr).$$

Under this definition, two functions $(A,B,F)$ and $(X,Y,G)$ are equal if and only if $A=X$ (same domain), $B=Y$ (same codomain), and $F=G$ (same pairs; hence, same value at every element of the domain).

share|improve this answer
    
This is a very clear explanation of the ordered triple & it's motivation, thank you. I must press you further if you'll allow me, in the definition of a binary relation I tend to think of the picture of a mapping going from elements in set A to elements in set B by an arrow mapping elements. When dealing with a binary operation • the set is written as (A,•). Seeing as the relation is defined as • := { (a,a') | (a∈A) ⋀ (a'∈A)}, is it fair to think of the set (A,•) as being the ordered triple (A,A,•)? –  sponsoredwalk Jan 13 '11 at 7:37
    
I say this because when you think about the set {1} it is equal to the set {1,1,1} & it just seems to make sense to me that (A,A,•) = (A,•) & you can picture it in terms of two sets A with the arrows linking elements. Is it ridiculous to picture two sets that are exactly the same being linked in the normal way you'd picture two sets being linked with a normal mapping? –  sponsoredwalk Jan 13 '11 at 7:38
    
@sponsoredwalk: A binary operation on $A$ is a function with domain $A\times A$ and codomain $A$: it takes as inputs pairs of elements, and returns elements. For example, $+$ is a binary operation on $\mathbb{N}$: you input two numbers (the summands), and the output is a number (their sum). So as a triple, it would be $(\mathbb{N}\times\mathbb{N},\mathbb{N},+)$. As a set of ordered pairs, $+$ consists of pairs with first entry a pair and second entry a number; e.g., $((2,3),5)\in +$, because $+(2,3)$ (what we usually write as "$2+3$") is $5$. (cont...) –  Arturo Magidin Jan 13 '11 at 14:19
    
@sponsoredwalk: (cont...) There is an important difference between sets and ordered tuples. By the Axiom of Extension, $\{1\}$ is the same as $\{1,1\}$. But the ordered 2-ple $(A,A)$ is not the same as the ordered $1$-tuple $(A)$; an ordered $n$-tuple of elements of $A$ is a function from $\{1,2,3,\ldots,n\}$ to $A$ (we define ordered pairs separately to begin with, then we can use this definition). –  Arturo Magidin Jan 13 '11 at 14:21
add comment

As regards your second question about the definition of a function: Not only is it true that for every a in A, there exists b in B s.t. (a,b) in F, it is more strongly the case that there exists a /unique/ b in B satisfying that constraint (hopefully this will work, I'm still learning the markup language here):

∀(a∈A)∃(b∈B) ((a,b)∈F ∧ ∀(x∈B)( (a,x)∈F ⇒ x=b)

This allows us to then use f(a) as well-defined notation for a unique b in B for each a in A.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.