2
$\begingroup$

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!

  • 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...2011-01-12
  • 0
    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 :)2011-01-12
  • 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.2011-01-12
  • 0
    The discussion of this topic in this link: --- wikipedia.org/wiki/Ordinal_number#Definition_of_an_ordinal_as_an_equivalence_class --- 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!2011-01-12
  • 4
    @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.2011-01-12
  • 0
    I agree with Bill. If you are really interested in this subject you should find a textbook.2011-01-12
  • 0
    @sponsoredwalk: You really should not have two disparate questions in the same question. The second half (about functions as triples) should have been posted as a separate question, though I've answered it here. If you really thought there should be some connection between the two, you could have linked to this question from the latter. Also: what you did with the links was ill done; if there is a limit to the links you can post, did you wonder why that is? As it was, you made it impossible for people to follow them easily, essentially forcing them to do the work you were not willing to do.2011-01-12
  • 0
    1: I gave links as background material to the things I was saying just as an aid to the curious reader in case I'd confused them. It makes sense seeing as this question originates out of my confusion in the first place but the links are irrelevant if I am understood, the "access forbidden" link works fine for me. 2: The question about functions is not dispirate, I was asking about the set-theoretic definition of a function & since my question was asking about different models of set theory I just thought it was natural someone would point out any difference in the Frege use of a function to2011-01-13
  • 0
    the Neumann use, I see that I didn't make that explicitly clear, I thought it but should have put it in clearer. I merely seperated that part off to highlight it's importance as an outgrowth of the possibly differing explanation of the usage of a function I was afraid existed, obviously not. Let me repeat, I said at the very start I was confused as hell about this particular topic & apologised IN ADVANCE for forcing anyone to due undue work, accusing me of not being willing to do the work just isn't fair seeing as I'd mentioned in advance that I was aware I'd written a confusing post.2011-01-13
  • 0
    I'm very greatful for the helpful responses & to you for cleaning up my post, I originally wrote it on another forum with clean links but couldn't do it on this site, nor figure out how to use LaTeX. I did wonder why there was a limit to the links but when you're asking a serious question that relies on 5-6 sources in those links what am I to do? If I hadn't linked to them I'd be goaded (again) for the size of my post or some other triviality, I didn't expect that on here. Accusing me of not being willing is just not fair, if I wasn't willing I wouldn't have posted this.2011-01-13
  • 0
    @sponsoredwalk: I have never encountered any problems with putting "too many links"; I suspect the problem is how you were trying to add them. The access problem seems fixed now, so I modified that. But the second question, about functions, *is* separate and independent from the first question. It should really have been done as a separate question; as I said, you can link to previous questions if you want to provide some background.2011-01-13
  • 0
    All excellent suggestions for texts on your list-particularly the Wolf book. His references will be more then adaquate to give you proper direction.2011-09-10

3 Answers 3

1

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.

5

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).

  • 0
    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,•)?2011-01-13
  • 0
    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?2011-01-13
  • 0
    @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...)2011-01-13
  • 0
    @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).2011-01-13
3

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.

  • 0
    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.2011-01-12