One of the things that we always say is that we can recreate all of mathematics using set theory as a basis. What does that mean? Basically, it means that given some other branch of math, which works with some class of objects O using some set of axioms A, we can define a set-based construction of the objects of S(O), and them prove the axioms A about S(O) using the axioms of ZFC.

Let's take a look at what that means, by showing how all of the proofs of number theory using natural numbers can be wrapped up in set theory.

First, we need to define the class of objects that we're going to talk about. That's the set of natural numbers. (That switch from class to set *was* deliberate; we know that the natural numbers are a set.) We've already seen the basic construction: it's the axiom of infinity. The set of natural numbers starts with 0 - which we represent as ∅. For each additional natural number N, it's represented by the set of all numbers smaller than N:

1. 1 = { 0 } = {∅}

2. 2 = { 0, 1 } = { ∅, {&empty}}

3. 3 = {0, 1, 2} = { ∅, {&empty}, {∅, {∅}}}

4. ...

Now, we need to show that the axioms that define the meaning of the natural numbers are true when applied to this construction. For natural numbers, that means we need to show that the [Peano axioms][peano] are true.

[peano]: http://scienceblogs.com/goodmath/2007/01/basics_natural_numbers_and_int…

The first Peano axiom is that 0 is a natural number. We've got that one.

The second Peano axiom is that every number is equal to itself. No problem, we've already got set equality defined in terms of subsets, so we've got that.

The third and fourth axioms are the symmetry and transitivity of equality. Set equality is transitive and symmetric, so no problem there.

The fifth Peano axiom is that anything equal to a number is a number. There is no way to create a set that will be equal to any of the set-based numbers, but that aren't exactly identical to one of the set-based numbers.

The sixth Peano axiom is that every number has a successor. In the set number construction, given a number, N, the successor N+1 is N∪{N}. So we've got a set based definition of successor; and further, it obviously satisfies the 7th axiom - that a=b if and only if a+1=b+1.

The 8th Peano axiom is an easy one: there is no natural number N such that N+1=0. Since 0=∅, in set terms, that means that there in no N such that N∪{N}=∅. N∪{N} must have *at least* one element: N. So it can't ever be ∅ and voila, axiom 7 is satisfied.

The ninth Peono axiom is induction: and the axiom of infinity is specifically designed to permit inductive proofs. So we've got that.

So - the we've got a construction of the natural numbers using sets; and we can easily prove that the Peano axioms are true and valid for that construction. So using that, any proof about the natural numbers can be reduced to a proof in terms of the axioms of ZFC.

- Log in to post comments

I prefer to read the construction more existentially.

Ifwe have a model of the axioms of ZFthenwe have (at least) one model of the Peano axioms constructed from it. This avoids all that muddled thinking about "the" natural numbers.But more importantly, it's like high-level versus low-level programming languages. To many mathematicians, ZFC is the assembly language: the closest to the "machine code" that humans are meant to be able to read. The natural numbers (as encoded in PA) are like Pascal. Yes, any program written in Pascal can be compiled to a program written in the assembly language, but that's not the point of a compiler to the end user.

A compiler provides a level of shielding of the programmer from the messiness of the assembly language. He can write a program in Pascal and be completely ignorant of the details of the assembler on his specific machine. In fact, he can use a different compiler -- even move his code to a completely different computer system -- and correctly-written code should still compile and execute "correctly" (syntactically, not semantically).

Similarly, the von Neumann numerals shield a mathematician doing arithmetic from the messiness of axiomatic set theory. She can write a proof in arithmetic and be completely ignorant of the details of set theory. In fact, she can use a different set of numerals (say, Church's) -- even move her proof over to a different model of ZF entirely -- and a correctly-written proof will still be (syntactically, if not semantically) valid.

The upshot is that we can go ahead and work with the natural numbers, taking PA as their definition. Proofs written in terms of PA will be a lot simpler and make a lot more sense than those written in terms of ZF, and the von Neumann numeral construction justifies our working at the high level rather than the low one.

John's point is a pretty good one. In fact, this bit

is very true. Mathematicians rarely use the Axiom of Choice directly these days. Instead they use some equivalent formulation that doesn't sound so bad (e.g. Zorn's Lemma). That is why things like the Banach-Tarski do not bother them.

Furthermore, I think there is another good point to the programming language comparison. ZFC is created to be a very powerful "language". However, it is not clear that mathematicians really need all that power. I don't know if you plan to go into the special classes like the definable sets (that would be a bit advanced), but the claim has been made that R(omega+omega) is enough to do the fast majority of mathematics. Similarly, almost every time we use Choice in an "acceptable way" we could use Countable Choice instead. Countable Choice is nice because then I could add really convenient axioms like "All sets are measurable".

However, while these restrictions would help deal with some of the pathologies Mark has pointed out, they make the axiomatization a lot messier. What do you want in a "math programming language"? A language that is easy to use but has weird effects on the fringes? Or a language that eliminates all bad properties but is difficult to master?

In Firefox I see "&empty" in your definition of the natural numbers - I take it that's a typo for ∅ ?

"Almost all" math can be done with PA and the rest is "research".

Reverse mathematics will eventually turn up what almost all means exactly.

In IE6 I see "&empty" as well under the definitions of 2 and 3 ({ â, {&empty}} and { â, {&empty}, {â, {â}}}; respectively).

Would you care to elaborate? We have a metamathematical notion of "finite cardinality", and the natural numbers N capture it. If we don't have that concept, then we can't even conceive of the set of sentences PA, because we don't know what a sentence or formula is. Among other things, a sentence is a sequence of symbols of finite length, or a tree of finite depth: but what do those mean?

In my opinion, your statement about getting a model Ï of PA (even second-order number theory) inside any model ZFC is correct, but if we accept the notion of a set-theoretical universe, we can also make a metamathematical statement that Ï in that universe is isomorphic to N. In fact, we'd probably say that N is a set which satisfies second-order number theory, in which case it's not difficult to prove that Ï and N are isomorphic.

Walker: Yeah, in many cases you can get away with countable choice. Unfortunately, when you start doing a lot of homological algebra you end up having to do even worse and use

classchoice. Some mathematicians have tried to ameliorate this with the notion of anafunctors (which also have nice lower-level uses), but still most people just say, "pick a projective resolution of each object" and move on.Chad: In practice I actually use a much more categorical definition of "natural numbers object", which captures (second-order) PA in a single universal property. That property can be stated (syntactically) inside any topos, though its semantic content may differ. Really, PA only defines the natural numbers up to isomorphism in our ambient category of sets, but once we know that a representative (along with "zero" and "successor" arrows) exists in we can just work with the semantics of those axioms.

To be a bit more explicit, I can define order and addition of natural numbers in terms of the zero and successor operations with no reference to the model. In fact, I did this here, and I make similar comments to these at the end of that post. The arithmetic statement a<b "compiles" to different set-theoretic statements depending on whether I'm using Church's or von Neumann's numerals, but the semantic content

withinarithmetic itself is the same. I can then talk about the ordered monoid structure of the natural numbers with no ambiguity, since I'm not trying to relate it back to set theory any more than a programmer cares which opcodes his compiler generates for a given line of Pascal code. I can then go on and use these structures to build models of the integers (say, as equivalence classes of pairs of natural numbers) and then usetheirsemantics without ever talking in terms of how I built a model for the integers again.Full disclosure: I tend to follow Lawvere's lead to found mathematics on functorial semantics rather than on set theory.

Chad Groft: I think what he meant was the thinking that leads to statements like, "I don't know what all this ∅ or {∅} stuff is, all I know is that it isn't number. I count 0, 1, 2, and so on. No squiggly lines anywhere in there."

Specifying that ZFC produces a model of the natural numbers which is equivalent to the model produces by PA which is equivalent to 0, 1, 2... makes it explicit that, yes, they all do the same thing in the end. It's not really necessary for people who are comfortable with differing models of things, but considering how many people want to state that 1/3 isn't a 'real' number because its decimal representation doesn't terminate, it's good to be specific.

I thought the programming analogy was quite apt, by the way. When you really get down to it you can do much fancier things if you directly manipulate assembly code, but you generally are okay with giving up that power in return for the ease of writing in a higher-level language. Same with the differences between ZFC (assembly), PA (Pascal), and 0, 1, 2... (Lisp, clearly ^_^).

Xanthir: In this analogy I'd say LISP is the theory of small cartesian closed categories :D

I liked the programming analogy too, since even if we don't need the assembly it is an illustrative way of thinking about the matter. It helped untangle some knotty commentaries here, for example.

I guess the above makes set semantics assembly for packaged Windows machines, while functorial semantics is assembly for open source Linux machines. :-)

Seems IE either provides the missing semicolon or disregards the standard (most likely). That may explain why there are so many of these mistakes here. [Seems the comment script also works without semicolon. I had to edit the quote a little.]

I'm not sure that strict adherence to standards helps. Who knew that <p>'s are part of blockquotes? (n-Category CafÃ© knows...)

Xanthir: Looks like you're right. I was extrapolating from John's statement:

There are a couple of points there. First, it's not clear what John means by PA; is it the first-order or second-order theory? If the first, then there are non-standard models of PA, even models of the theory PA + "PA is inconsistent" (this is just a rearrangement of Godel II applied to PA). If he means the second, then yes, there is a unique model up to isomorphism, and the "muddled thinking" disappears to some extent.

Even that isn't the whole story, though, since if we have a (set) model of ZF, we have a model of ZF + "ZF is inconsistent" (Godel II again). The statement "ZF is inconsistent" is implicitly a statement about Ï, and since the unquoted statement is false by assumption, I certainly wouldn't accept the local version of Ï as standard. I'm still convinced that there is a correct notion of "natural number", even if I can't completely grasp it (but then, nobody can), and that it doesn't have things like codes for proofs of contradictions from theories that are actually consistent.

In any case, I thought he was referring to the past confusion on the board between "true" and "provable from a theory", which he apparently was not.

John: I've seen your article on NNO's, and you're right, it's a very nice category-theoretic (and categorical!) "local" definition of the natural numbers. While I'm not married to any particular foundation for mathematics at the moment either, I would reject as such any topos in which an NNO either didn't exist or did patently stupid things, like model the statement "PA is inconsistent".

Walker, just noticed your post: I think you often need Dependent Choice even for "acceptable" uses of AC (you need it for "every infinite set has a countably infinite subset", for example). The main consistency statement I know along these lines is: (ZF + DC + "every set of reals is measurable (and has the Baire property)") is consistent iff (ZFC + "there is an inaccesible cardinal") is consistent. This is slightly stronger than what most mathematicians use, but most set theorists would grant it easily.

I could not remember if Solvay's result (which is what I am thinking of) requires inaccessibles. It has been forever since I have done any set theory. However, I just looked it up, and you are right.

Many readers (and maybe MarkCC himself) seem to be assuming that all proofs of statements about the natural numbers are done using the Peano axioms. But that isn't true; there are things that you can prove about the natural numbers if you have ZF at your disposal, but that you can't prove using just the Peano axioms. "The Peano axioms are consistent" is an example, thanks to Goedel, but there are less artificial ones. Here's one, due to a chap called Goodstein.

Consider the following procedure. Take any number. "Expand it using base 2", by which I mean write it as a sum of powers of 2, and then do the same thing recursively to all the exponents, so you end up with no numbers bigger than 2. Replace every 2 with a 3. Subtract one. Repeat with 2,3 replaced with 3,4; then with 4,5; and so on until you end up with 0. If you ever do.

Theorem (of ZF, but not provable with PA alone): whatever number you start with, the process eventually terminates.

If you think that's obviously true, try it with 3 and see where you get; does it still seem plausible?

So, here's "why" it's true: at each stage, imagine replacing your "base" with omega (the smallest infinite ordinal). Then each "subtract 1 and expand again" step decreases the ordinal you're working with, and each "add 1 to the base" step does nothing. So you get a descending chain of ordinals. There are no infinite descending chains of ordinals. We're done.

The proof that this is unprovable in PA is unfortunately too long to fit in this margin.

One other note: I think Mark fudged his explanation of why induction works a bit, and for good reason. Implementing the natural numbers in ZF gets you induction *for properties that can be expressed in ZF*, and only for those.

For whatever reason, your explanations of set theory make me happy.

You probably want to have an 8 instead of a 7 at the end of the third-last paragraph though. I mean, axiom 7 is quite satisfied, but he was satisfied in the previous paragraph.

g: Yes the Goodstein theorem has no counterexample in the natural numbers, and yes this fact is not provable within PA itself. That's not the sort of thing I'm asserting, though.

My point is just to provide the converse viewpoint on the von Neumann numerals to the one Mark stated at the end of the post. The view he stated is that if we take ZFC as foundational, the von Neumann numeral construction allows us to take anything we prove with PA and translate it to the bedrock of ZFC.

The view I'm promoting is that we can run this backwards to say that once have a "compiler" handy we (usually) don't have to write proofs in ZFC primitives. We can just take the Peano axioms at face value and work with them as if they are the logical primitives. And in practice this sort of thing is what mathematicians actually do.

There are several problems when we try to use ZFC as a background for doing math. For instance, we cannot prove that all naÃ¯vely total recursive functions (``naÃ¯vely total'' means: they are total in some model for ZFC with a standard arithmetic part, if such a model exists) are in fact total within ZFC.

Follows that we can explicitly construct a recursive family of time-polynomial Turing machines which are total, but such that we can neither prove that all machines in the given set are polynomial, or even that all machines in the set do always converge in polynomial time.

This is just a first example. General decision problems are also unsolvable in ZFC, for instance: extend ZFC so that one can write predicates in its language. Say, some P so that ZFC proves P(x) and ZFC proves not P(y), for some terms x â y. Then P is undecidable.

Adding large cardinals wont help, either.

"One of the things that we always say is that we can recreate all of mathematics using set theory as a basis. What does that mean? Basically, it means that given some other branch of math, which works with some class of objects O using some set of axioms A, we can define a set-based construction of the objects of S(O), and them prove the axioms A about S(O) using the axioms of ZFC."

Sure, people say that. But, I don't know why they say it anymore. One simply can't talk about fuzzy subsets using ZFC and its axioms alone. Consider the elementary statement that given a universe of discourse {b, c, d}, the subsets {b, 1} and {b, .8} do not equal each other. The first axiom of ZFC basically predicts or implies that we would have the same set since we have the same member b for each subset. However, since .8 does not equal 1 we do not have the same degree of membership and thus we don't have two equivalent subsets. I believe you can rather easily see how to modify the axiom of extension here, but you still need to modify it. And that means that there exist elementary mathematical statements not strictly derivable from ZFC.

If one intends the statement "we can recreate all of mathematics using set theory as a basis," as either true or false, then it qualifies as false.

"So using that, any proof about the natural numbers can be reduced to a proof in terms of the axioms of ZFC."

Proposition: The set of prime numbers less than 10, or P(10), in proportion to any finite list of the first 1,000,000n primes P(n10^6), where n equals any natural number equals a very small fraction. In other words P(10)/P(n10^6)=d where d indicates a small rational number.

Discussion of what a possible proof will necessarily involve: I would first have to define 'very small' here properly. I can't properly define 'very small' in ZFC since the quantifier 'very' has a degree of vagueness or fuzziness to it. Consequently, I can't prove this strictly from ZFC (or from any pure two-valued logic/logic-based system).

"Reverse mathematics will eventually turn up what almost all means exactly."

That's rich. I feel as sure of this as that whatever system you choose will eventually determine what "nearly equal to 2" means or what "very close to 0" or what "rather far away from 10^12" or "has a medium low probability." In other words, I enjoyed your joke, thanks!

I enjoyed the discussion about the Peano axioms.

One simply can't talk about fuzzy subsets using ZFC and its axioms alone.

Of course we can. You've simply chosen a poor implementation. We have the reals, we have functions, we have ordered pairs. So one implementation of a fuzzy set would be as an ordered pair: (X, f), where f is a function from X to [0,1].

Another would be to simply take f, since the X is redundant.

I would first have to define 'very small' here properly. I can't properly define 'very small' in ZFC since the quantifier 'very' has a degree of vagueness or fuzziness to it.

So you're complaining that ZFC can't prove a statement which is informal rather than mathematical?

[One simply can't talk about fuzzy subsets using ZFC and its axioms alone.

Of course we can. You've simply chosen a poor implementation. We have the reals, we have functions, we have ordered pairs. So one implementation of a fuzzy set would be as an ordered pair: (X, f), where f is a function from X to [0,1].]

I suppose one can implement fuzzy subsets according to your proposal in a certain sense. However, if we do this, then we'll have (b, 1) not equal to (b, .8) as we have different functions and we've basically defined our subsets in terms of elements and in terms of functions. We also have the axiom of extension implying that (b, 1) equals

(b, .8). Consequently, ZFC comes as inconsistent since we've derived that [(b, 1)=(b, .8)] and ~[(b, 1)=(b, .8)]. Maybe you or I don't have a problem with that, but the founders of crisp set theory would.

[I would first have to define 'very small' here properly. I can't properly define 'very small' in ZFC since the quantifier 'very' has a degree of vagueness or fuzziness to it.

So you're complaining that ZFC can't prove a statement which is informal rather than mathematical?]

I don't see why you want to have such a strong equivalence between the notions of mathematical and formal. I consider informal statements such as "pi approximately equals 3.14159" as mathematical. Most proofs done in mathematics texts and in mathematics classes qualify as informal rather than "mathematical". This says nothing of applied mathematics which uses informal statements extremely frequently. Nor does it say anything of classical mathematicians like Euler or Leibniz who used informal arguments almost all the time. Nor does it say anything of a supposedly formal mathematical book like Euclid's Elements which actually turned out as a book chock full of informal statements. There exist several other ways that people use informal mathematics a lot more than formal mathematics. In other words, I view most mathematics as informal to begin with, and consequently I don't recognize any sort of meaningful distinction at the level we've discussed.

[Another would be to simply take f, since the X is redundant.]

No, X doesn't necessarily work as redundant. We could have (c, .6) and (b, .6). If we took X as redundant we would have these two sets as equivalent. However, since we have two different elements or members we have two different sets.

We also have the axiom of extension implying that (b, 1) equals

(b, .8).

No, it doesn't. Recall how we implemented ordered pairs: (b,1) = {{b}, {b,1}}, and (b, .8) = {{b}, {b,.8}}. {b,1} != {b,.8}, and consequently {{b}, {b,1}} != {{b}, {b,.8}}.

We're implementing fuzzy sets as a higher order structure within the basic universe of set-theory, but that doesn't mean we need to pull all of basic ZFC into this implementation. To use the compiler analogy. If I have a C++ compiler, I can use it to create a Scheme compiler. Now I have both C++ and Scheme at my fingertips. The fact that C++ has goto statements and Scheme does not is not a contradiction.

Most proofs done in mathematics texts and in mathematics classes qualify as informal rather than "mathematical".

If you're speaking of low-level courses like freshmen calculus, sure. But if you mean a real math class, then that's not true at all. They omit steps which are tedious, unenlightening and obvious to trained mathematicians, but every statement made is formal and precise. For example, I can take the Mean Value Theorem all the way back to ZFC.

No, X doesn't necessarily work as redundant. We could have (c, .6) and (b, .6). If we took X as redundant we would have these two sets as equivalent.

That's not what I proposed. For the fuzzy set (c, .6), the first implementation I proposed was: ({c}, f), where f(c) = .6. Recall that a function is a set of ordered pairs, so this becomes ((c), (c, .6)). The second version would be to simply have ((c, .6)). The important point being that from a function, one can recover its domain.

On the consistency of PA and ZFC: there is a very simple computational proof of the Paris-Harrington theorem which was recently given by Kunen (1996 or so). And:

PA proves [Paris-Harrington] ---> [PA is consistent]

(I mean by [PA is consustent] the usual GÃ¶del sentence.)

Also, for ZFC, we can use a reasonable infinitary argument and prove its consistency. (Of course people may disagree about the qualification, ``reasonable''). The reason why these theories are consistent is simple: being a theorem is a rather rare event. So there aren't enough proofs, to run into a contradiction (I refer to a theorem by Cris Calude).

[We're implementing fuzzy sets as a higher order structure within the basic universe of set-theory, but that doesn't mean we need to pull all of basic ZFC into this implementation. To use the compiler analogy. If I have a C++ compiler, I can use it to create a Scheme compiler. Now I have both C++ and Scheme at my fingertips. The fact that C++ has goto statements and Scheme does not is not a contradiction.]

I think your analogy misleads us from the point (like most arguments by analogy). Look, here's the contradiction: The axiom of extension says that two sets equal each other if and only if their members equal each other. (b, .8) consists of the element b, and its membership function .8 which doesn't come as an element. If it did it would have gotten specified in our universe of discourse. It didn't. (b, 1) consists of the element b, and its membership function 1. Since we have the same elements the axiom of extension implies that (b, .8)=(b, 1). An implementation using both elements and membership functions implies

(b, .8) does not equal (b, 1).

In other words, if ZFC can imply fuzzy set theory (completeness), then it comes as inconsistent. The other Godelian idea holds also: if ZFC comes as consistent, then it can't imply fuzzy subset theory (incompleteness).

[If you're speaking of low-level courses like freshmen calculus, sure.]

Most math courses come either at or below this "low-level" if you think about it. I mean if you consider each algebra class in say high schools taught as just 1 course, then we have a greater number of "low-level" courses than upper level course. I didn't mean that though.

[But if you mean a real math class, then that's not true at all. They omit steps which are tedious, unenlightening and obvious to trained mathematicians, but every statement made is formal and precise.]

Omitting steps which THE AUTHOR (possibly also readers or listeners) subjectively finds "tedious" or "unenlightening" or that the author, the mathematical community, and the readers intersubjectively find "tedious" or "unenlightening" means we have informal statements. If we don't have every single step of the argument, we simply don't have a formal and precise argument since we can't check every single step according to the rules of classical logic. A formal, precise argument has to either appeal to axioms or derived theorems from axioms using classical logic and no more. If omitting steps did work as precise and formal, then we could have a formalism which didn't need to appeal to either its axioms or derived theorems. It could appeal to something nonformal IN ITS LOGICAL INFERENCES. It would have undefined inferences. But, a formalism appealing to undefined inferences simply consists of an informal formalism. In classical logic that comes as a contradiction, so there simply exist no omissions in a formal and precise argument.

To deny such means that an argument doesn't either work as formal and precise or not formal and precise, by which you've denied the excluded third proposition. In classical logic this also implies you've denied the contradiction proposition (by Demorgan's duality proposition). So, if you mean what you say, you've already rejected classical logic (to some extent greater than 0) implicitly in your argument.

[For example, I can take the Mean Value Theorem all the way back to ZFC.]

Sure, in principle you can, and maybe someone has done so precisely and formally in detail. But MVT happens in classical mathematics based on classical logic. I didn't say one couldn't get classical results like that from ZFC. I said that one couldn't get ALL of mathematics (and I didn't implicitly mean almost all, I meant exactly all).

[That's not what I proposed. For the fuzzy set (c, .6), the first implementation I proposed was: ({c}, f), where f(c) = .6. Recall that a function is a set of ordered pairs, so this becomes ((c), (c, .6)). The second version would be to simply have ((c, .6)). The important point being that from a function, one can recover its domain.]

Maybe I did misunderstand here, I don't know. It still remains though that if you introduce your function idea (which actually existed in a form before fuzzy set theory) you've modified the axiom of extension and use something other than ZFC. There also could exist another problem with your idea if you really wanted to base all of maths on it. We might expect that the membership functions equal other if they equal other in real space. For fuzzy subsets this will work. However, for neutrosophic set this simply won't work. Suppose x+ represents x plus a positive infinitesimal. Then two subsets like (b, .6) and (b, .6+) don't equal each other on the hyperreals, even though they equal each other on the reals. Similarly (b, .6+) equals (b, .6++) on the hyperreals, but not on the hyperhyperreals.

The axiom of extension says that two sets equal each other if and only if their members equal each other. (b, .8) consists of the element b, and its membership function .8 which doesn't come as an element.

Here's what you're not understanding: in the sense of ZFC, b is not an element of (b, .8). I went through this in the beginning of post 21, where I showed how ZFC can tell that (b,.8) and (b,1) are two different sets.

When we implement something within ZFC, we create new operations and relations. For example, when we made the naturals, we defined an operation "+". "+" is not part of the language of ZFC, and yet we've created it.

Similarly, when we implement fuzzy sets within ZFC, we create a new relation "â". This is not the same as ZFC's "â", although we denote them by the same symbol, which is probably where the confusion comes from. Within the world of fuzzy sets, b â (b, .8). However, as far as ZFC is concerned, the only elements of (b, .8) are {b} and {b, .8}.

So we have these two different relations. Extensionality only talks about the original â. It says nothing about how fuzzy sets are supposed to behave. Hence there is no contradiction.

Omitting steps which THE AUTHOR (possibly also readers or listeners) subjectively finds "tedious" or "unenlightening" or that the author, the mathematical community, and the readers intersubjectively find "tedious" or "unenlightening" means we have informal statements.

No, it means we have informal proofs. The statements are all quite formal. We have formal proofs, too; we just don't put them on the board. The purpose of the informal proof is to convey the formal proof without writing it out.

I said that one couldn't get ALL of mathematics (and I didn't implicitly mean almost all, I meant exactly all).

And I maintain that a "theorem" which has no formal statement is not a theorem of mathematics.

[Here's what you're not understanding: in the sense of ZFC, b is not an element of (b, .8). I went through this in the beginning of post 21, where I showed how ZFC can tell that (b,.8) and (b,1) are two different sets.]

In post 21 Antendren wrote "No, it doesn't. Recall how we implemented ordered pairs: (b,1) = {{b}, {b,1}}, and (b, .8) = {{b}, {b,.8}}. {b,1} != {b,.8}, and consequently {{b}, {b,1}} != {{b}, {b,.8}}."

So, in post 21 you've defined {b} as an element of

(b, .8), as well as {b, .8}. The element {b, .8} consists of an element of the reference set {b, c, d} and a function .8. {b, 1} has an element of the reference set {b, c, d} and a function 1. With respect to the reference set both {b, .8} and {b, 1} have the same members. Maybe your method avoids such a contradiction with ZFC, but I can still deduce a contradiction using ZFC.

[Similarly, when we implement fuzzy sets within ZFC, we create a new relation "â".]

I haven't seen anyone do this. I'd like to see such, if possible. I really don't see how one can do so since ZFC from the outset defines sets as having its members either belong (characteristic function of 1) to its sets or not (characteristic function of 0).

[However, as far as ZFC is concerned, the only elements of (b, .8) are {b} and {b, .8}.]

According to ZFC both {b} and {b, .8} have the same degree of membership, as elements either belong or don't in ZFC. In fuzzy set theory by writing {b, .8} people MEAN to say that b has .8 degree of membership in some understood reference set. One could even say that b has a .8 degree of "belonging" in our reference set, even though that terminology confuses many people. In other words we have partial membership. Where does ZFC allow for this at all?

[No, it means we have informal proofs.]

A proof itself consists of no more than statements and axioms. In other words, the proof itself consists of a statement (albeit longer than what we usually consider statements). How do we know this? All statements have a sort of "logical closure" to them. If we have a statement A, and a statement B, then any logical connective using ^, V, ~, ->, <-> also comes as a statement. A formal proof consists of a sequence of formulae such that either our formula comes as an axiom or a derived result (theorem) using a rule of inference. Since each rule of inference consists of a statement using just wffs and logical connectives, it also consists of a statement. So, a formal proof consists of an example of an universal instantiation of rule(s) of inference. Since the rules of inferences qualify as statements, so do formal proofs!

[The purpose of the informal proof is to convey the formal proof without writing it out.]

I don't argue that informal proofs do have a large value and utility. However, since informal proofs themselves do mean to convey formal ones, and formal proofs themselves do consist of statements, informal proofs also then qualify as informal statements.

Doug:

What you're missing is that just because we call something "member of", that doesn't mean that it's the *some* member-of primitive of ZFC. We can *represent* fuzzy sets using ZFC sets and functions. The fuzzy "member-of" isn't the same thing as ZFC-member of - it's a *function* in ZFC that operates over the representation of fuzzy sets in ZFC.

It's the same idea as how we get arithmetic in ZFC. ZFC doesn't have a numbers, or arithmetic operators like addition; it doesn't have numerical comparisons like less than. But we can *define* a representation of numbers using ZFC sets, and then define functions in ZFC for arithmetic operations and comparisons. The only reason that numbers seems less contradictory is because they don't overload the basic terms of ZFC.

Doug - I'm not completely sure, but it seems like you're saying that the only items that 'exist' are a, b, and c, and then complaining that when you create a set with items that don't exist (like 1 or .8) things don't work right.

That is, the only reason that (b 1) and (b .8) are the same is because you're claiming that 1 and .8 simply don't exist.

This isn't an argument against ZFC's ability to handle fuzzy sets, it's just a demonstration that anyone can derive a contradiction from a system, if they start by contradicting themselves.

ZFC doesn't handle fuzzy sets at the base level. Using the base axioms and nothing else, you won't get it to work. However, once you add in support for reals and functions and such (all of which are constructable in ZFC), then you can construct fuzzy sets without a problem.

It's like complaining that you can't use continuation-passing style when programming in assembly. Well, duh, the base instructions don't handle that sort of complex stuff. You have to build up more complex instructions from them before you have the necessary richness to adequately describe continuations.

So, in post 21 you've defined {b} as an element of

(b, .8), as well as {b, .8}.

I did nothing of the sort. {b} is not an element of {b, .8}. The elements of {b, .8} are b and the number (not function) .8. Similarly {b, 1}. {b, .8} and {b, 1} are not fuzzy sets, they're simply normal sets in ZFC.

I haven't seen anyone do this. I'd like to see such, if possible. I really don't see how one can do so since ZFC from the outset defines sets as having its members either belong (characteristic function of 1) to its sets or not (characteristic function of 0).

If A is a fuzzy set, (such as {(b, .8)} ), we say that x â A if there exists a y â A such that x is the first coordinate of y, and the second coordinate of y is not 0.

According to ZFC both {b} and {b, .8} have the same degree of membership, as elements either belong or don't in ZFC.

No, according to ZFC the only element of {b} is b, and the elements of {b, .8} are b and .8. .8 is a real number, and thus a set (since we've already implemented reals in ZFC).

In fuzzy set theory by writing {b, .8} people MEAN to say that b has .8 degree of membership in some understood reference set. One could even say that b has a .8 degree of "belonging" in our reference set, even though that terminology confuses many people. In other words we have partial membership. Where does ZFC allow for this at all?

By implementing fuzzy sets as a higher order construct. The fuzzy set {b, .8} is implemented as the ZFC set {(b, .8)}, which is equal to the ZFC set {{b}, {b, .8}}. If you give me an implementation of a fuzzy set, I can determine the reference set and the membership function.

Xanthir: In this analogy I'd say LISP is the theory of small cartesian closed categories :D

Wait, is this still an analogy, or is it in fact just literally accurate?

[If A is a fuzzy set, (such as {(b, .8)} ), we say that x â A if there exists a y â A such that x is the first coordinate of y, and the second coordinate of y is not 0.]

If you translate what you wrote into words you'd notice that you've said that "x is a member of A if there exists a y as a member of A..." I certainly don't see how this squares with the idea of a "membership function" which can range over [0, 1]. Buckley and Eslami in _An Introduction to Fuzzy Sets and Fuzzy Logic_ write "If A(x)=1 we say that x belongs to A, A(x)=0 means that x does not belong to A, and A(x)=.6 says x has membership value .6 in A."

[No, according to ZFC the only element of {b} is b, and the elements of {b, .8} are b and .8.]

Right, but that's exactly the problem. .8 does NOT come as an element. It comes as a membership function. In order for any ZFC scheme to work it would have to treat .8 as a member of some crisp set as you've done. In fuzzy set theory .8 tells us the degree of membership of b in some other set without such having to work as an element of a crisp set.

[The fuzzy set {b, .8} is implemented as the ZFC set {(b, .8)}, which is equal to the ZFC set {{b}, {b, .8}}.]

.8 doesn't work as a member of (b, .8), where b indicates the element or member, and .8 indicates the degree of membership of b in the reference set {b, c, d} in fuzzy set theory. .8 does not happen in the reference set {b, c, d}. Nor does the set {0, 1} happen in {b, c, d}. {0, 1} doesn't come as a problem for ZFC since the characteristic function notion corresponds to an output of either 0 or 1. But, I simply don't see where the membership function idea comes out of ZFC. At best I see a mimicry of it, which really doesn't get the idea here and ends up with difficulties. I guess you could say I don't see how you can seriously implement fuzzy set theory as a first-order construct. One simply won't end up with any quantifiers other than 'for all' and 'there exists' this way. Without those the approximate reasoning schematics simply don't come as possible.

[What you're missing is that just because we call something "member of", that doesn't mean that it's the *some* member-of primitive of ZFC. We can *represent* fuzzy sets using ZFC sets and functions. The fuzzy "member-of" isn't the same thing as ZFC-member of - it's a *function* in ZFC that operates over the representation of fuzzy sets in ZFC.]

I thought I had basically said something like this in my previous comment, except that I don't see how you can really represent fuzzy sets using ZFC since the "member-of" idea works very differently than in ZFC, and the "member-of" idea comes as an extremely important idea in fuzzy set theory. I guess I didn't speak clearly.

[That is, the only reason that (b 1) and (b .8) are the same is because you're claiming that 1 and .8 simply don't exist.]

I don't claim this. ZFC basically claims that .8 doesn't exist since members of sets either belong or don't.

[Using the base axioms and nothing else, you won't get it to work. However, once you add in support for reals and functions and such (all of which are constructable in ZFC), then you can construct fuzzy sets without a problem.]

I still don't see how one can really implement fuzzy set theory using ZFC or something similar. The proposal up here, once drawn out, really just looks like mimicry at best which doesn't provide anything substantial.

Perhaps a more cogent argument: ZFC has at its base a two-valued logic. Fuzzy set theories have at their bases at least a three-valued logic. So, ZFC doesn't provide a proper basis to derive a fuzzy set theory.

Returning to the original point I really don't see why so many people these days want to talk about ZFC as a foundation for all of mathematics, especially since Godel long ago showed this not so. I guess that such a theorem doesn't really mean that much though in people's minds at a preconscious level, and people would rather write as if Godel never wrote anything. Heck, most people today speak as if Newton, Copernicus, Kepler, etc. made any difference as we still speak of "sunrise" and "sunset." I suppose the phenomenon similar.

Doug, perhaps you should give it a rest for a while. Try coming back to this next week.

Can you see you have written nonsense? The number has nothing to do with fuzzy sets, it's just a number. If we write 0.8 as 4/5, then 0.8 is something like

({∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}, {∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}},{∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}}), along with it's operations.

So, 4/5 surely exists in ZFC, and so does 0.8.

The trick you seem to be missing, is that, if you say "x has membership value 0.8 in X", it translates to "(x, 0.8) ∈ X" this way:

x -> x

has -> ∈

membership value -> (.,.)

X -> X

Can you see where the "∈" comes from? It's from:

"It's 100% TRUE that x has membership value 0.8 in X", not from "x has membership value 0.8 in X".

Doug: You're really skipping over something quite basic here. Missing the forest for the atoms, as it were.

Here's another analogy. (Wee!) What is computer circuitry? Nothing more than true/false circuits and logical functions. We implement computer chips with an absolutely basic 2-value logic system.

And yet, somehow we're able to build from that and eventually represent fuzzy sets in computer programs. We go from just having 1 and 0, and using and, or, xor, and not, all the way to implementing graphical environments for evaluating fuzzy logic expressions.

I'm sure it sounds like I'm talking down to you, and I apologize. But the leap from circuitry to Windows is of the same kind as the leap from ZFC to fuzzy sets. There's really no difference in the fundamental nature of the constructions.

This is why I'm not seeing your confusion. If I can take a bunch of capacitors and string them together into Youtube, why couldn't I take ZFC and build it up into fuzzy sets? Assuming it has the necessary expressive power (which it does), the fact of it is straightforward, even if the actual construction may be a bit difficult.

[ZFC basically claims that .8 doesn't exist since members of sets either belong or don't.

Can you see you have written nonsense?]

In a superficial sense that does come as nonsense. Of course ZFC does allow for the rational number .8 to exist. But, it doesn't allow for an object like a to have a .8 degree of membership in a reference set. Here's the context "[That is, the only reason that (b 1) and (b .8) are the same is because you're claiming that 1 and .8 simply don't exist.]

I don't claim this. ZFC basically claims that .8 doesn't exist since members of sets either belong or don't."

In other words ZFC basically claims that .8 doesn't exist as a possible value for a membership function. Only 1 and 0 exist as possible values for membership functions, and thus such a function gets called a characteristic or indicator function in an attempt to indicate such.

["x has membership value 0.8 in X"]

["It's 100% TRUE that x has membership value 0.8 in X"]

I consider these as very, very different statements. Just because I say something has a membership value .8 or .7 does NOT mean that I mean to assert it 100% true that x has an exact membership value in X. I could say .8, but really mean about .8, in which case I might implicitly mean an interval-valued fuzzy set, or a type-2 fuzzy set. I might mean .8 plus or minus .0001, with .8 as the "best fitting" value.

So, basically I don't accept your "trick", because I don't try to assume that people make such binary statements so blithely. I could just translate your epsillon as an implicitly unstated "of belonging" as in "x has membership value .8 of belonging in X".

Again, here's the problem. Suppose we have a reference set {b, c, d}=A. We then know that b belongs to A, as do c, and d. Suppose we then have a subset {b}=B of A. b belongs to B , while c and d do not. Consequently, the indicator function for b equals 1, and those of c and d equal 0. With a fuzzy subset {(b, .8)}=C of A, where .8 indicates the degree of membership of b, we simply don't know if b either belongs to C or it doesn't belong to A. Consequently, the indicator function doesn't have an output for {(b, .8)}. The membership function of fuzzy set theory will say that b has a degree of membership of .8 in C.

Perhaps my tactic comes as rather poor. I suspect it works out much easier to understand these sorts of ideas if one first thinks of 2-valued logic, and even goes so far to think of set theory as a broad sort of 2-valued logic. Then one can extend 2-valued logic to n-valued, compare them, and then think of fuzzy set theories as broad sorts of n-valued logics. One simply can't derive n-valued logics from classical two-valued logic, so one can't derive fuzzy set theory from crisp set theory.

There's a deep, deep misunderstanding. You keep mixing the fuzzy ∈ and the crisp ∈.

The point you're missing is that fuzzy logic is not an extension of ZFC. Conceptually, yes. But not in it's implementation. You have to distinguish between the two, even if the membership value is 1.

Let me go through your post.

For crisp membership, that is. But 0.8 can exist as a number. And, given a suitable definition of operations, we can use numbers to simulate statements of fuzzy logic.

That's exactly the problem - you can't. The "membership value of belonging" phrase translates to the ordered pair (element, value). The "has" translates to the crisp ∈.

Well, you shouldn't. These are equivalent. Even in fuzzy logic, you still work with crisply true statements - about fuzzy sets.

You cannot do this. Either you're in fuzzy logic, then

{b1, c1, d1}=A,

{b0.8}=C subsetfuzzy of A,

and you can say ChiA(b)=1, and write this special case as b ∈fuzzy A.

Or, you're in crisp ZFC logic, and then

{(b, 1), (c, 1), (d, 1)}=A,

{(b, 0.8)}=C subsetfuzzy of A.

Again, you can say ChiA(b)=1, but you cannot say b ∈crisp A. You can say (b, 1) ∈crisp A.

You just need to distingush between the two logics, the primitive (ZFC) and the simulated (fuzzy).

Doug: I must ask, do you think that it is possible to write a computer program that implements fuzzy logic?

If so, then your basic premise (that no system based on binary truth can implement fuzzy truth) is obviously false, since computers are based on bitwise operations, which are merely binary logical functions.

If not, then I'd ask you to explain why such programs exist, if they're impossible. ^_^

[The point you're missing is that fuzzy logic is not an extension of ZFC.]

Many fuzzy set theorists claim fuzzy set theory as an extension of crisp set theory.

[You have to distinguish between the two, even if the membership value is 1.]

*laughs* Look, if you restrict a fuzzy set theory to

{0, 1} you get EXACTLY the results of crisp set theory. Let's say I have a fuzzy set theory with 'min' for 'and', 'max' for 'or', and '1-x' for 'not'. In such a case, the membership function of fuzzy set theory works exactly like the characteristic function of crisp set theory, and ALL the basic algebraic properties of crisp set theory come out. The principle of excluded middle holds for 'max' on {0, 1}, and the principle of contradiction holds for 'min' on

{0, 1}, and the rest of them hold as well. Consequently, I don't have to distinguish a crisp set theory from a fuzzy set theory (as in fuzzy set theory implies crisp set theory). In fact, people like Buckley and Eslami _explicitly_ define fuzzy set operations such that if we restrict them to {0, 1} we ALWAYS get crisp set theory. The same goes for fuzzy logic in the narrow sense. We may have to distinguish a fuzzy set theory from a crisp set theory (as in crisp set theory doesn't imply fuzzy set theory), as I can't get all the properties of fuzzy set theory from crisp theory.

[For crisp membership, that is. But 0.8 can exist as a number. And, given a suitable definition of operations, we can use numbers to simulate statements of fuzzy logic.]

Even numerical statements of fuzzy set theory say things like "a woman with height 5'11" has .8 degree of membership in the set of very tall women." How will you "simulate" that .8 degree of membership using crisp set theory? How will "simulate" the set "very tall women" using crisp sets, when we have a fuzzy quantifier? You might be able to do this actually if you restricted everything to convex fuzzy subsets, as done in fuzzy number theory. But, fuzzy set makes no such restrictions on fuzzy sets in general, and consequently one can respesent heights using non-convex fuzzy subsets. Also, how will "simulate" something having a dual membership in two fuzzy sets to two different degrees? How will you "simulate" x having a degree of membership .6 to a set of "tall people" and .4 to a set of "medium height people"?

[I could just translate your epsillon as an implicitly unstated "of belonging" as in "x has membership value .8 of belonging in X"

That's exactly the problem - you can't. The "membership value of belonging" phrase translates to the ordered pair (element, value). The "has" translates to the crisp â.]

You may translate it as such. I don't see any legal code of English that says I have to translate "has" a crisp term, do you? In fact, I can point out PRECEDENTS in the English language where "has" gets used otherwise. A 16-year old who who drive her parents car says things like "I have a car." Does she own the car? No. Does she still "have" it another sense? Yes, she uses the car and treats it as if she has property rights by caring for it and maintaining it and possibly paying insurace. Also, consider something like a public park. People share such property in common. "x has membership value .8 of belonging in X" I translate as (x, .8) in X.

[Well, you shouldn't. These are equivalent.]

I told you I do NOT consider them as equivalent. And honestly, I think you've missed a subtetly here.

[Even in fuzzy logic, you still work with crisply true statements - about fuzzy sets.]

Sure, you can. But, you can also work with fuzzy statements. You can work with BOTH fuzzy statements and crisp statements in fuzzy logic. You can't do both in crisp logic.

[Again, you can say ChiA(b)=1, but you cannot say b âcrisp A.]

I didn't claim this. I claimed "With a fuzzy subset {(b, .8)}=C of A, where .8 indicates the degree of membership of b, we simply don't know if b either belongs to C or it doesn't belong to A." If it were crisp, we would know whether it belonged or not.

[You just need to distingush between the two logics, the primitive (ZFC) and the simulated (fuzzy).]

All fuzzy logics when restricted to {0, 1} become crisp. So, one can distill all of crisp logic from a given fuzzy logic. But, one can't distill all of fuzzy logic from crisp logic, since a theorem of crisp logic (like the excluded middle) won't always work out as a theorem or fuzzy logic. In other words, we could recreate all of crisp set theory from fuzzy set theory. But, we couldn't recreate all of fuzzy set theory from crisp theory.

"You keep mixing the fuzzy ... and the crisp..."

Dang! I dropped my potato chips on the deep-pile carpet, and now they're all covered with dog hairs and fabric fuzz. I hate mixing the fuzzy and the crisp.

Sorry. Couldn't resist.

We now return you to an interesting thread. Fuzzy thread. Whatever.

Doug:

Let's look at real numbers. If I recall correctly, they are defined as limits of infinite sequences of rational numbers, who themselves are pairs of integers, who are signed naturals without -0.

The reals can be added and multiplied just as natural numbers can, giving the same results, if you use the right mapping between them.

But you cannot find the square root of the natural number 3. Does that mean there's no square root of 3? No. But first, you need to convert the natural 3 into the real 3.0, implemented as a sequence of rational numbers... etc. With that implementation, you can define and find the square root of 3.

Similarly, there's no partial membership in ZFC. But, you can convert a set into a fuzzy set, implemented as a set of ordered pairs of element and a number, which... etc. With the right definition of operations, the fuzzy set will behave as the original ZFC set, but it will NOT be the original set. With this implementation, you can define and work with partial membership.

If you still cannot see what I was talking about in previous posts, then I'm sorry: I cannot find more arguments than I've already given, so this is my last post on the subject. It is my hope that, sometime later, you will see where the misunderstanding was.

[Let's look at real numbers. If I recall correctly, they are defined as limits of infinite sequences of rational numbers, who themselves are pairs of integers, who are signed naturals without -0.]

Well, I don't know about what they actually "are" in a metaphysical sense. But, sure, you can define them that way, which if I recall correctly uses Cauchy sequences. But, you could also do so without limits. You can define the set of rationals from the natural numbers, use Dedekind partitions (or cuts) to get the set of irrationals, and then take the union of these two sets to get the set of _standard_ numbers. They have no more "reality" than any other numbers.

[But you cannot find the square root of the natural number 3.]

If by "find" you mean write an exact decimal representation sure. But, you can always write as close an approximation of sqrt(3), in whatever base system you have, as your computational power allows you to compute. You can also find as small an interval of rational numbers as you like (using the metric abs(l-u) where l means the lower approximation and u the upper approximation) which contains sqrt(3) as an interior point.

[Similarly, there's no partial membership in ZFC. But, you can convert a set into a fuzzy set, implemented as a set of ordered pairs of element and a number, which... etc.]

I see your analogy, but it doesn't work out as anologous as you might think. If you compare the irrationals with the rationals they both work as fields, and even ordered fields. But, the irrationals don't work as complete ordered fields. Still, they seem to have about the same algebraic properties. Their logical structure also works out the same, as we just need crisp two-valued logic for both of them.

Comparing fuzzy sets and crisp sets, well, let's say we have fuzzy sets based on t-norms and s-norms or 'normed fuzzy sets'. In general they don't have the same algebraic properties. Normed fuzzy sets will come as monotonic commutative monoids. Crisp sets do also, but fuzzy sets don't have other properties like distributivity, idempotency, involution, duality, etc. But, we could drop such and study fuzzy sets without properties like associativity, commutavity, an identity, and monotonicity. We can't do anything like this with crisp sets. More importantly, the logical structure works out differently with fuzzy sets in general than it does with crisp sets (infinite-valued or multi-valued logic vs. two-valued logic). This doesn't happen when you compare the set of rationals to the set of standard numbers.

I rather strongly think I see very, very clearly what you meant to say. It just works out much differently than you expect it would.

Simply put your implementation of crisp sets won't behave like fuzzy sets algebraically, nor will it behave like fuzzy sets logically. It also won't behave mathematically like fuzzy sets in a more general sense. Additionally, your implementation won't provide a way of developing a fuzzy arithemtic, fuzzy differential calculus, fuzzy trigonometry, fuzzy graph theory, fuzzy differential equations, fuzzy linear programming, fuzzy linear equations, fuzzy groups, fuzzy relational equations, etc. Nor will it suggest that you can find different ways of developing (some of) these ideas.

In ZFC there exists no real number x such that x={x}. However, in fuzzy set there do exist such crisp real numbers. So, suppose we have a set of axioms F for fuzzy set theory which allow for such crisp real numbers, where can define a set-based construction of the reals R, and them prove the axioms F of fuzzy set theory about S(R) using the axioms of ZFC. Then ZFC would imply there exists a real number x such that x={x}. But, there exists no such real number in ZFC. So, if ZFC can recreate fuzzy set theory via the proposed method, then ZFC contradicts itself. If ZFC can't recreate fuzzy set theory, such as instances where 1={1}, then there exist mathematical statements outside of ZFC, e. g. defuzzifications of fuzzy sets via the maximum member method where say you have {(1, .5), (2, 1), (3, .2)} defuzzified to (2, 1), which at least comes very close to having an equality.