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!

  • 0
    All excelle$n$t suggestio$n$s 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
    @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