2
$\begingroup$

I've recently been delving into axiomatic set theories for the first time, and I've been troubled by the construction of natural numbers with the Peano axioms under ZFC. What I don't understand is how equality can be closed under the natural numbers, when the natural numbers are just an arbitrary encoding.

In other words, if I take the encoding of natural numbers to be $0=\{\}, 1=\{0\}, 2=\{0,1\}, ...$, then why could I not define some other concepts on ZFC as well, say primary colors as $red=\{\{\},\{\}\}, green=\{\{\},\{\{\}\}\}, blue=\{\{\{\}\},\{\{\}\}\}$ in which case $2=\{\{\},\{\{\}\}\}=green$, but green is not a natural number which seems to violate closure on equality. (i.e. $\forall x,y :(x \in \mathbb{N}) \wedge (x=y) \Rightarrow y \in \mathbb{N}$)

Edit: Even though the question is answered, some people still seem to be wondering why this issue was troubling to me so I'll eplain for clarity. In practical use, colors and natural numbers are probably not concepts that would be mixed. However, perhaps a better example would have been $\mathbb N$ and functions $\mathbb N \to \mathbb N$. Now if natural numbers are encoded in the traditional way as listed above and functions encoded in the traditional way, as sets of tuples, then the set {} denotes both the natural number 0 and a function that maps nothing to nothing. Thus any proof using ZFC that used both the notion of natural numbers and functions over natural numbers would violate the peano axioms for natural numbers. Now if you can use a different encoding for either functions or natural numbers that are completely disjoint, then this is not a problem which as @Henning Makholm noted, is always possible. However, without that being always possible any proof under ZFC using both natural numbers and functions would be invalid and since that fact was not obvious to me, I found it troubling.

$\endgroup$
  • 4
    $\begingroup$ What? If you're defining green that way, then it is a natural number! You can't just invoke the common definition of the English word "green" and contrast it to how you just so happen to be using the symbol \right now\. $\endgroup$ – Jonathan Hebert Jun 6 '15 at 2:10
  • $\begingroup$ my point was that two concepts encoded two different ways may construct some of the same sets (either intentionally or unintentionally) $\endgroup$ – S E Jun 6 '15 at 2:18
  • 2
    $\begingroup$ That is true, but is it a problem? $\endgroup$ – Ross Millikan Jun 6 '15 at 3:35
  • $\begingroup$ it is if you are doing proofs incorporating 2 independent concepts if you could not define encodings that were disjoint, hence my follow up question in the accepted answer $\endgroup$ – S E Jun 6 '15 at 3:38
  • $\begingroup$ @Jonathan Hebert see edit. $\endgroup$ – S E Jun 6 '15 at 6:18
6
$\begingroup$

If you define "$\mathit{green}$" as an alternative name for the set you've already decided to represent the concept of $2$ with, then naturally "green" is a member of $\mathbb N$. This may be a bit confusing, but there's nothing technically wrong with it. It's mathemathics; you're allowed to define names to mean whatever you want.

More to the point, perhaps, if the reasoning you aim to formalize using ZFC depends on $\mathbb N$ and the set of primary colors being disjoint, then it is your responsibility to choose representatives for those concepts that are in fact disjoint.

However, it is more common in everyday mathematics to treat numbers and colors as entirely different kinds of things that never belong in the same set. If the arguments you want to formalize in ZFC follow that convention, then it is not a problem to use the same object to represents concepts of two different kinds. Again it will be up to you to make sure that when you're formalizing something about numbers you're not conflating them with colors and vice versa.


The underlying important point here is that axiomatic set theory (in general and ZFC in particular) is a tool that you can use to formalize everyday prose mathematical arguments if you so choose. And it's up to you how you use the tool.

It is quite common for students to get an impression that ZFC is supposed to be "what mathematics really is", and that everything else you've ever learned is just lazy approximations to the "true ZFC reality". This is not a useful viewpoint, and it's not actually shared by many set theorists. In particular, it doesn't tell you anything interesting about ordinary mathematics outside set theory, and doesn't tell you anything interesting about set theory itself either. It's best just to get rid of it as soon as you can.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it always possible then when requiring the use of two concepts such as natural numbers and colors to define encodings which are disjoint? $\endgroup$ – S E Jun 6 '15 at 2:13
  • 2
    $\begingroup$ @SE: Sure -- if you have a set $X$ of encodings for colors that happen to overlap with the set-theoretic $\mathbb N$, just use the set $\{\langle x,\mathbb N\rangle\mid x\in X\}$ as encodings instead. That's guaranteed to be disjoint from $\mathbb N$. $\endgroup$ – hmakholm left over Monica Jun 6 '15 at 2:18
  • $\begingroup$ @SE Do you know anything about category theory? It is very much interested in respecting the semantics of objects, and tends to completely "forget" underlying structures - so numbers and colors are treated as incomparable parts of wholly different structures, and are given meaning only by their properties as numbers or as colors respectively. $\endgroup$ – Milo Brandt Jun 6 '15 at 2:21
  • $\begingroup$ @Meelo no but I will look into it, it may make more sense to me coming from a strong computer science background $\endgroup$ – S E Jun 6 '15 at 2:25
  • 3
    $\begingroup$ @SE: From a CS perspective, it's useful to think of ZFC as an "untyped assembly language" for mathematics, which we may, but don't have to translate everyday arguments into. A difference from CS is that in mathematics we don't need to "run" our arguments on a concrete machine, so it's perfectly valid to consider an argument that nobody's ever going to translate to ZFC in practice, even though we all agree that we could do it if we wanted to. In this view, your 2/green argument is no stranger than the fact that 01000001 is both the number sixty-five and the letter A, and it's up ... $\endgroup$ – hmakholm left over Monica Jun 6 '15 at 3:01
3
$\begingroup$

$\{\{\},\{\{\}\}\}$ is a natural number, regardless of whether you call it "green" or "2". When you work from this foundation, you are defining arithmetic on this underlying set structure, not on the labels, like $1$, $2$ and $3$, which we use for them. It's almost as if you set variables red=1 and green=2 and said red+red=green - which is totally okay.

You might regard that set theory doesn't come built in with any kind of "type safety". Everything's just data, encoded as sets - and, simply inspecting this data doesn't tell you whether its meant to encode a number, a string, or a color.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Given your definitions, the statement that $green \not \in \Bbb N$ is false. Both $green$ and $\Bbb N$ are objects in ZFC that we have given names to. We need to expand the names to the formal objects to check the truth of the statement $green \not \in \Bbb N$. In a similar perverse manner, I could define $0=\{\}, 2=\{0\}, 1=\{0,2\}$ and using my definitions and the usual definition of ordinal addition $1+1=2$ is false.

As your activity indicates substantial computer interest, think about a word in memory. We can interpret it as an unsigned int, an int, a float, some characters, some pixels of a picture, or other ways. Similarly we can give various names to the same set. The only problem comes when we assume that different names refer to the same set. If the word is 32 bits, the bit pattern of $-1$ as a(twos complement) int is the same as the bit pattern of $2^{32}-1$ as an unsigned int.

Even in math, we allow multiple names for the same object. If I write $\forall x \forall y$ (something) it is not guaranteed that $ x \neq y$

The simple answer is that equality is not closed on the naturals. $0,1,2,green$ are names for sets. The names are not formally part of ZFC. I can give a name to any ZFC set I want, and I can give multiple names to the same set. When I write a proof in ZFC I often use abbreviations, like names for sets, that are not part of the formal language. I need to convince the readers that if the argument were expanded into formal ZFC it would hold, or my proof will be rejected. That convincing is not formal mathematics, it is informal. Someone may claim that "You call this $x$ and that $y$. If they are the same object, your proof fails." In the computer arena, this is an argument for strong typing-every variable should come with a prefix that says what type it is and the compiler should reject references that are not of the proper type. This would make the attacks you describe more difficult. I suspect we can prove that it is not sufficient, that the halting theorem says you can get around this.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thinking along those lines is what made me come up with the question in the first place. In computer science, operations defined on encodings depend entirely on the context of the encoding. And exploiting this can lead to mainy types of attacks which break the assumptions of another context. One such example is the PS3 Jailbreak hack which tricks the code that processes a USB descriptor into processing something that is not a USB descriptor as if it were. $\endgroup$ – S E Jun 6 '15 at 3:00
  • $\begingroup$ Actually, this type of attack is typically easier in strongly typed languages than weakly typed ones for the simple fact that weakly typed languages do type checking at runtime while strongly typed languages only do so at compile time. $\endgroup$ – S E Jun 6 '15 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.