You can do with numbers everything that you can do with sets, and the other way around

alcontali

When I first ran into a remark at math-exchange that mentioned that set theory (ZF minus infinity) is bi-interpretable with number theory (PA), I thought that this result is quite amazing, because the axioms of set theory do not look at all like the axioms of number theory. In fact, at first glance, these two different theories have absolutely nothing to see with each other.

The Wikipedia page for bi-interpretability does not mention this example of bi-interpretability (it does not mention any other examples either.)

Set theory can do everything that number theory can do, because it is possible to represent numbers as sets and do arithmetic using set operations such as the set union and the set intersection. We can represent numbers as sets e.g. by using Von Neumann ordinals:

0 = { }, 1 = { { } }, 2 = { { }, { { } } }, ...

Just like in number theory, we only need to be able to add one to a number, because that will allow us to define all other arithmetic operators, i.e. addition, substraction, multiplication, and division. The generalized successor operation (="add one") is relatively simple. If we want to add one to a set, we just add the set to itself. For example:

{ a, b } ⊕ 1
= { a, b } ⋃ { { a, b } }
= { a, b, { a, b } }

If the set represents a number, then the result will be the number is exactly one larger, i.e. its successor. If we want to add two, we just repeat the operation. For example, in Von Neumann ordinal arithmetic, 1+2 looks like:

{ { } } + { { }, { { } } }
= ( { { } } ⋃ { { { } } } ) + { { } }
= { { }, { { } } } + { { } }
= { { }, { { } } } ⋃ { { { }, { { } } } }
= { { }, { { } }, { { }, { { } } } }

Expressions in this model of arithmetic interpretation leave a bit of a brainfuck impression, but it certainly works fine. So, the Von Neumann ordinals, $\Bbb{N}^{VN}$ along with arithmetic operators defined in term of set operations (+,-,x,/) λ(⋃,⋂) properly interpret number theory (PA):

PA ⊨ $\Bbb{N}^{VN}$ (+,-,x,/) λ(⋃,⋂)

The Von Neumann ordinals are as much a legitimate model for PA as the standard model of natural numbers:

PA ⊨ $\Bbb{N}$ (+,-,x,/)

The other way around works as well. Number theory can do everything set theory can do. According to the Wikipedia page on arithmetic sets, we can represent sets as number-theoretical predicates:

An arithmetical set is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic ... by using Gödel numbers to represent elements of the set and declaring a subset of A to be arithmetical if the set of corresponding Gödel numbers is arithmetical. — Wikipedia on arithmetical sets

Defining the union and intersection of arithmetical sets is actually the easy part. If the predicate $φ_1(x)$ represents a first set and $φ_2(x)$ a second one, then the union of both is $φ_1(x) \vee φ_2(x)$ while the intersection will be $φ_1(x) \wedge φ_2(x)$ . It is the translation from standard set-builder notation to arithmetic-set notation that is not as simple. As expected, the Wikipedia page on arithmetic sets does not even show one example of what arithmetic-set notation could look like.

For example, what does the set { 1, 5, "hello" } look like in arithmetic-set notation?

$φ(x) := (x=\ulcorner 1\urcorner) \vee (x=\ulcorner 5\urcorner) \vee (x=\ulcorner hello \urcorner)$

With $\ulcorner x\urcorner$ the Gödel encoding for x.

would be a good start, but it does not look much like standard PA arithmetic. We can make use, however, from the following considerations:

x $\vee$ y = x + y - xy
x $\wedge$ = xy

We can also consider that x=5 is equivalent to 1 - sgn(x-5)². Hence, after applying these considerations, the set-theoretical set { 1, 5, "hello" } can be represented as the following arithmetic set:

$φ(x) := 1 - sgn( ( x - \ulcorner 1 \urcorner) ( x - \ulcorner 5 \urcorner) ( x - \ulcorner hello \urcorner) )²$

In the end, I struggled the most with representing embedded set expressions in set builder notation, such as { 1, 6, { 4, 3} , 8 } in arithmetic-set notation. The outer set looks like:

$φ(x) := 1 - sgn( ( x - \ulcorner 1 \urcorner) ( x - \ulcorner 6 \urcorner) ( x - \ulcorner ??? \urcorner) ( x - \ulcorner 8 \urcorner) )²$

While the embedded set expression would look like:

$φ(x) := 1 - sgn( ( x - \ulcorner 4 \urcorner) ( x - \ulcorner 3 \urcorner) )²$

The solution to combine both into one expression may look simple, but it took me forever to realize that the solution had to be:

$φ(x) := 1 - sgn( ( x - \ulcorner 1 \urcorner) ( x - \ulcorner 6 \urcorner) ( x - \ulcorner 1 - sgn( ( y - \ulcorner 4 \urcorner) ( y - \ulcorner 3 \urcorner) )² \urcorner) ( x - \ulcorner 8 \urcorner) )²$

Hence, since it is possible to translate all (finite) set-theoretical expressions in set-builder notation into arithmetic-set notation, as well as reimplement all set operators as arithmetic operators, i.e. (⋃,⋂)λ(+,-,x,/) , we can conclude that the arithmetic sets $S_{AR}$ interpret ZF-∞ in an equivalent way as its standard model S with (⋃,⋂):

ZF-∞ ⊨ $S_{AR}$ (⋃,⋂)λ(+,-,x,/)
ZF-∞ ⊨ S (⋃,⋂)

Hence, the bi-interpretability of number theory and set theory can be expressed as the following four statements:

ZF-∞ ⊨ S (⋃,⋂)
ZF-∞ ⊨ $S_{AR}$ (⋃,⋂)λ(+,-,x,/)
PA ⊨ $\Bbb{N}$ (+,-,x,/)
PA ⊨ $\Bbb{N}^{VN}$ (+,-,x,/) λ(⋃,⋂)

If you prefer a formal proof -- necessarily burdened by a larger bureaucracy of formalisms -- instead of the proof sketch/strategy laid out above, you can find it in the 2006 paper "On interpretations of arithmetic and set theory" by Richard Kaye and Tin Lok Wong.

Gregory

Truth has no essence, so you confound yourself ontically with what covers numbers and what is it and if it covers itself. There is no way to explain how the infinite instantiates into finite objects. Can there be an infinitely large cell phone?

Gregory

And more, I can prove no God exists alpowerful by the existence of colors and math. If God threw a box across space and it split into infinite descending fractions into the alleys of the infinitesimal, and then applied colors to each fraction, I ask what would be the color at the end of the series when God puts the box together..?

tim wood

↪alcontali

You may recognize I'm no idle flatterer, but you have presented this in a masterful way that is a delight to read (even if I don't completely get it). Very nice!

alcontali

ou may recognize I'm no idle flatterer, but you have presented this in a masterful way that is a delight to read (even if I don't completely get it). Very nice! — tim wood

Thanks!

Gregory

The term "set" and "number" are unclear though. We are free to think of 1 as finite or an infinite collection of fractions. Are sets when separated from their members something truly mathematical? What existence do they have? Are they finite, transfinite, or infinite?

Gregory

↪tim wood

ye he is very astute

Gregory

If one contains all its fractions then it is a set too. It's a set that contains itself, which would mean it's solidity as a single number

Nagase

↪alcontali

A couple of observations:

(1) I think the notion of a theory interpreting another can be made more intuitive by considering the relations between algebra and geometry. As is known at least since Descartes, there is a natural translation of basic algebraic operations (sum, product, subtraction, division, and extraction of roots) into geometric constructions involving ruler and compass, and vice-versa. At first, it may seem exotic that a discipline that is overtly about operations between numbers has anything to do with constructible figures and vice-versa, but once you study in detail the translation between these theories, they become more natural. In fact, the algebraic theory of field extensions even proved to be the natural setting for solving long-standing problems in geometry, such as the trisection of the angle, etc. The general notion of interpretation is basically a generalization of this idea.

(2) I think you are confused about "arithmetical sets". As the wikipedia page explains, arithmetical sets are not sets which are coded by numbers, rather, they are sets of numbers definable in PA. For example, the set of the squares (i.e. the set {0, 1, 4, 9, 16, ... } is definable by the formula Ex(x * x = y), and hence is an arithmetical set. Similarly, every singleton of a natural number is also an arithmetical set. So considering the arithmetical sets will not give you an interpretation of ZF-Inf into PA. In order to achieve the latter, you need some way of coding the relation "x belongs to y" using only arithmetical predicates. As Kaye and Wong explain the paper you linked (p. 3), this is usually done by way of the Ackermann interpretation, namely "x belongs to y" is defined as "the xth digit of the binary expansion of y is 1". One then shows that, given this interpretation of "x belongs to y", all the axioms of ZF-Inf are satisfied. For instance, extensionality is trivially satisfied, since if w and z have the same binary expansion, they are the same number; the empty set is represented by the number 0; the set {a, b} is coded by 2^a + 2^b, etc. A more or less detailed (and tedious) proof that various set-theoretical concepts can be defined using this interpretation is given in section 1.(b) of this chapter (which is mentioned by K&W).

(3) Notice that bi-interpretability between two theories, T and T', is a stronger notion than mutual interpretability between T and T'. The latter only requires that there be an interpretation of T into T' and vice-versa, whereas the former requires that each interpretation be the inverse of the other.

(4) Incidentally, note also that our usual set theory, ZFC, goes far beyond first-order PA! So it's not exactly true that we can do with numbers everything we can do with sets. Rather, we can do with numbers everything we can do with the hereditarily finite sets!

alcontali

this is usually done by way of the Ackermann interpretation, namely "x belongs to y" is defined as "the xth digit of the binary expansion of y is 1". — Nagase

So, in a universe with just 7 numbers, { 0, 1, 2, 3, 4, 5, 6 }, the subset { 2, 4 } is represented as 0010100. So, the binary representation is as long as the largest number in the subset. I don't see, however, how to represent { 2, { 3, 5} } in that scheme.

One model of the natural numbers are the string symbols that satisfy the regular language:

L = 0 | [1-9][0-9]*

We can pick any arbitrary number of symbols of at least two symbols, $\{ α_0, α_1 , α_2, ..., α_n\}$ , and represent natural numbers as:

L = $α_0$ | [ $α_1$ - $α_n$ ] [ $α_0$ - $α_n$ ]*

L is a model of PA:

PA $\models$ ( $α_0$ | [ $α_1$ - $α_n$ ] [ $α_0$ - $α_n$ ]* ) { +, -, x , / }

We can also capture the Von Neumann ordinals and the constant expressions representing heriditarily finite sets as languages with (non-context free) grammars. In this approach, the Von Neumann ordinals interprete PA, simply because they are isomorphic under arithmetic with the language L mentioned above.

I think that the simplest way to argue that there is a language, i.e. a model, representing number-theoretical predicates that interprete ZF-∞ is to just create one, and then to argue that this language is isomorphic under arithmetic with the standard set-builder notation for set literals.

Kaye and Wong did it in another way, but I think that their approach is more complicated and less intuitive than an approach in which we treat models as formal languages.

christian2017

↪alcontali

Are you an engineer or a math major? You can actually discover alot of stuff about mathematical principles by studying how 3d engines are made such as Blender. A relationship can be made between any two objects/ideas if you attach a complex (or simple sometimes) equation to it. (one to one, linear, exponential, inverse exponential, logarithmic) and ofcourse you have your coefficients and constants in the equation which add even more depth to the relationship. Reality is similar to a 3d topographical map except reality is like hundreds of these 3d topographical maps all intertwined at the same time.

christian2017

↪alcontali

Most of the discussions on this forum are fairly banal and then you jump to something that can actually be proven and also at the same time has alot of depth.

alcontali

Are you an engineer or a math major? — christian2017

A software engineer. Math is more of a hobby, actually. I would never have studied it at uni. Math is fun, intriguing, and surprising but not vocational enough as a profession.

You can actually discover alot of stuff about mathematical principles by studying how 3d engines are made such as Blender. — christian2017

I am impossibly lousy at visual mathematics, especially, at the visual puzzling of classical Euclidean geometry ("Elements"). I can only do algebraic geometry, to a better extent, but I don't like it all that much either. I prefer symbol manipulation only. So, I pretty much never choose a math topic that is fundamentally visual. It reminds me too much of technical drawings we had to do at high school. I could never "see" the thing ...

christian2017

Are you an engineer or a math major?
— christian2017

A software engineer. Math is more of a hobby, actually. I would never have studied it at uni. Math is fun, intriguing, and surprising but not vocational enough as a profession.

You can actually discover alot of stuff about mathematical principles by studying how 3d engines are made such as Blender.
— christian2017

I am impossibly lousy at visual mathematics, especially, at the visual puzzling of classical Euclidean geometry ("Elements"). I can only do algebraic geometry, to a better extent, but I don't like it all that much either. I prefer symbol manipulation only. So, I pretty much never choose a math topic that is fundamentally visual. It reminds me too much of technical drawings we had to do at high school. I could never "see" the thing ... — alcontali

Cool! You ever use Spring (a java technology)? I have to head out now. ttyl

alcontali

You ever use Spring (a java technology)? — christian2017

I very rarely use Java, C# or C++, even though I should probably be more open concerning Java in Android development. I tend to use a combo of scripting languages along with C for native libraries.

Nagase

↪alcontali

I think you're losing sight of what it is we're after. We want an interpretation of ZF-Inf, not just any way to code random finite sets. I mention this because, given this goal, we should bear some things in mind:

(1) The universes of ZF-Inf are composed of sets, not random objects (that is, there are no urelements). So every object in the universe is built out of the empty set in a structured way. So your set {2, 4}, for example, is actually the set { { {}, {{}} }, { { }, { { } }, { { }, { { } } }, { {}, {{}}, { {}, {{}} } } (I may have missed some brackets there). This is important because our coding scheme will use this to its advantage.

(2) The universes of ZF-Inf are all infinite. This is clear from the fact that ZF-Inf has the power set axiom, so that there's no bound for the size of its sets.

(3) The interpretation is actually coding sets as numbers, so that to say that 3 belongs to 5 (say) is actually to say that the set coded by 3 belongs to the set coded by 5.

With this in mind, note that, under Ackermann's interpretation, the empty set is coded by 0, the singleton of the empty set (i.e. {{}}) is coded by 1, the number two is coded by 11 (i.e. by 3), the number three, by 111 (i.e. by 7), and so on and so forth for every von Neumann ordinal (note that I'm considering the leftmost digit as the 0th digit, the second leftmost digit as the 1st digit, etc.). On the other hand, the set {{{}}} is coded by 10, since it does not contain the empty set, but it does contain the singleton of the empty set.

Note that simply having a coding scheme is not nearly enough for an interpretation (let alone bi-interpretation). You also need to show that (i) the elements in this coding scheme are all definable in the theory that is doing the interpretation and that (ii) all the axioms of the target theory are provable under this coding scheme. These are not trivial matters and some ingenuity is required to see that everything works smoothly (see the chapter by Hájek and Pudlák that I linked in the previous chapter to see how it is done).

Qwex

You can do with shapes anything you can do with sets.

A shape is a powerful set.

Otherwise you're literally barking at space.

I know the route of all base 4 mathematics, by it's shape.

alcontali

So every object in the universe is built out of the empty set in a structured way. So your set {2, 4}, for example, is actually the set { { {}, {{}} }, { { }, { { } }, { { }, { { } } }, { {}, {{}}, { {}, {{}} } } — Nagase

That is the standard model and therefore the standard formal language of ZF-∞, essentially unique only up to isomorphism. Therefore, { 2, 4 } is a legitimate expression in an alternative model and formal language that is isomorphic under set calculus to the standard model.

As a side note, given the bi-interpretability with PA, ZF-∞ is subject to Löwenheim-Skolem, and is therefore not categorical.

The BNF grammar of the standard model would be:

set = "{" "}" |
       "{" set "}" |
     "{" set "," tail_of_sets "}"
tail_of_sets = set |
                    set "," tail_of_sets

The BNF grammar is not sufficient to entirely validate set expressions because it is not capable of expressing that the set cannot contain duplicates. Hence, the formal language of the standard set model is not context-free. So, there is also need for a function that would be able to do the following:

remove_duplicates({ a, a, b, b }) = { a, b }

(2) The universes of ZF-Inf are all infinite. This is clear from the fact that ZF-Inf has the power set axiom, so that there's no bound for the size of its sets. — Nagase

Agreed.

It is just that it does not contain induction-completed cardinals ω of infinity.

With this in mind, note that, under Ackermann's interpretation, the empty set is coded by 0, the singleton of the empty set (i.e. {{}}) is coded by 1, the number two is coded by 11 (i.e. by 3), the number three, by 111 (i.e. by 7), and so on and so forth for every von Neumann ordinal (note that I'm considering the leftmost digit as the 0th digit, the second leftmost digit as the 1st digit, etc.). On the other hand, the set {{{}}} is coded by 10, since it does not contain the empty set, but it does contain the singleton of the empty set.

Note that simply having a coding scheme is not nearly enough for an interpretation (let alone bi-interpretation). You also need to show that (i) the elements in this coding scheme are all definable in the theory that is doing the interpretation and that (ii) all the axioms of the target theory are provable under this coding scheme. These are not trivial matters and some ingenuity is required to see that everything works smoothly (see the chapter by Hájek and Pudlák that I linked in the previous chapter to see how it is done). — Nagase

It is obvious that the strategy that you prefer, works absolutely fine. It has been the general idea to work like that since the nineties anyway.

However, that does not mean that my strategy would not work too.

I just designed a formal language that produces legitimate number-theoretical predicates and that is isomorphic with the standard ZF-∞ language/model under the standard set operations (⋃,⋂). I like my own approach much better than the standard approach, if only, because it is much simpler.

Nagase

↪alcontali

You say:

I just designed a formal language that produces legitimate number-theoretical predicates and that is isomorphic with the standard ZF-∞ language under the standard set operations (⋃,⋂). I like my own approach much better than the standard approach, if only, because it is much simpler.

First, it's not clear what is for languages to be isomorphic. A model M is isomorphic to a model N iff there is a bijection between their respective domains that respects the interpretation of the non-logical symbols. What does it mean for languages to be isomorphic? Second, it's not clear what is the "standard ZF-∞ language under the standard set operations (⋃,⋂)". The "standard ZF-∞ language" is the language whose only non-logical symbol is the set membership symbol, "∈". What does it mean for this language to be "under the standard set operations (⋃,⋂)"?

More importantly, you claimed in your first post that your procedure was meant to express the bi-interpretability of PA and ZF-Inf. What I'm saying is that this is very far from the truth. You have not shown how to define the relevant notions in PA (i.e. you have not shown that PA proves that your definitions are well-defined). You have not shown that, using your definitions, we can prove the axioms of ZF-Inf. And finally, you have also not shown that your "interpretations" are inverses, which is crucial for bi-interpretability.

Finally, I'm confused by your use of the sign function. For any x, sgn(x) is either 1, 0, or -1, corresponding to the cases x>0, x=0, x<-1. So there are only three possible values for 1-sgn(x), namely 0, 1, 2. Hence this term can only code at best three possible objects.

alcontali

First, it's not clear what is for languages to be isomorphic. A model M is isomorphic to a model N iff there is a bijection between their respective domains that respects the interpretation of the non-logical symbols. What does it mean for languages to be isomorphic? — Nagase

A formal language is a class of sentences, just like a model-theoretical model is. Such classes can be isomorphic. This is very possible.

For example, the class of decimal representations of natural numbers is isomorphic under arithmetic to the class of binary representations of natural numbers. The translation function τ is definable and even trivially computable. Example:

$τ(4) = 100$

$τ^{-1}(100) = 4$

I also tend to believe that a model-theoretical model is a formal language, and that a formal language is a model-theoretical model (of sorts). It is a similar view as expressed by the Curry-Howard correspondence (CHC): "A proof is a program, and a program is a proof (of sorts)." Still, the bureaucracy of formalisms to actually prove the CHC is daunting and full of subtleties. I would certainly not be able to do it alone.

As I remarked previously, the standard model of natural numbers can be completely captured by a really simple regular expression (=a regular language), one example being (=decimal):

$\Bbb{N}$ = 0 | [1-9][0-9]*

There really is a bijection between $\Bbb{N}$ and the Von Neumann ordinals $\Bbb{N}^{VN}$ , while arithmetic clearly is homomorphic in both directions. That is the reason why $\Bbb{N}^{VN}$ interpretes PA using arithmetic expressed in terms of set operations; simply because $\Bbb{N}$ already does. Given the isomorphism with the standard model $\Bbb{N}$ , there is no need to further prove that $\Bbb{N}^{VN}$ truly interpretes PA.

The bijection really exists, because the translation function τ can be defined and is even trivially computable:

$\forall k \in \Bbb{N}^{VN}, \exists j \in \Bbb{N} : j = τ(k)$

$\forall j \in \Bbb{N}, \exists k \in \Bbb{N}^{VN} : k = τ^{-1}(j)$

In the expressions above, $\Bbb{N}^{VN}$ and $\Bbb{N}$ are collections of strings. So, 9 is represented by the string "9" in $\Bbb{N}$ or by the binary string "1001" in base 2 (or by other strings in other bases, depending on the choice of base).

More importantly, you claimed in your first post that your procedure was meant to express the bi-interpretability of PA and ZF-Inf. What I'm saying is that this is very far from the truth. You have not shown how to define the relevant notions in PA (i.e. you have not shown that PA proves that your definitions are well-defined). You have not shown that, using your definitions, we can prove the axioms of ZF-Inf. And finally, you have also not shown that your "interpretations" are inverses, which is crucial for bi-interpretability. — Nagase

The proof sketch in my OP is obviously not a complete formal proof.

Still, if two models are essentially the same up to isomorphism, you can reuse the proof that the definitions for the first model are well-defined to argue that the ones for second model are too, since both models are isomorphic.

Finally, I'm confused by your use of the sign function. For any x, sgn(x) is either 1, 0, or -1, corresponding to the cases x>0, x=0, x<-1. So there are only three possible values for 1-sgn(x), namely 0, 1, 2. Hence this term can only code at best three possible objects. — Nagase

The predicate φ(x) only defines a set membership function. For example:

φ(x) := 1 - sgn( (x-4)(x-9)(x-12) )²

φ(x)=1 for { 4,9,2 } but not for any other value. For example, 8 is not a member of the set:

φ(8) = 1 - sgn( (8-4)(8-9)(8-12) )²
= 1 - sgn( (4)(-1)(-4) )²
= 1 - sgn(16)²
= 1 - 1²
=0

You can try for any value k not in { 4,9,2 } and you will find that φ(k) = 0, simply because the sgn(...)² subexpression will in that case always evaluate to 1, leading to a result that is 1 - 1 = 0.

Hence, the number-theoretical predicate function φ(x) is capable of returning 1 when the x is in the set, and 0 when it is not. This means that φ(x) effectively represents a set within arithmetic. Since set arithmetic (⋃,⋂) can be implemented in terms of ( $\vee , \wedge$ ) on these predicates, it is always a model for some set theory.

Given its bijection with the standard set-builder notation capable of representing sets in ZF-∞, it is isomorphic with the standard model for ZF-∞ under set arithmetic, and therefore a model for ZF-∞.

SophistiCat

↪Nagase

Oh hey! I didn't realize that you have joined this form. You've been missed :)

GrandMinnow

alcontali: You are egregiously posting a lot of misinformation

set theory (ZF minus infinity) is bi-interpretable with number theory (PA) — alcontali

Whatever you read on a forum, it's not ZF minus infinity that is, in a certain sense (a qualification I'll leave tacit henceforth), equivalent with first order (a qualification I'll leave tacit henceforth) PA. Rather it is ZF minus infinity plus the negation of infinity that is equivalent with PA.

Just like in number theory, we only need to be able to add one to a number, because that will allow us to define all other arithmetic operators, i.e. addition, substraction, multiplication, and division. — alcontali

No, PA has successor (adding one), addition, and multiplication as primitive.

If we want to add one to a set, we just add the set to itself. — alcontali

We take the union of the set with the singleton of the set.

The Von Neumann ordinals are as much a legitimate model for PA as the standard model of natural numbers: — alcontali

The finite (Von Neumann) ordinals ARE the universe for the standard model of PA.

Number theory can do everything set theory can do. — alcontali

That seems to be your main point. And it is wildly and clearly incorrect. PA cannot prove the existence of an infinite set; and, crucially for mathematics, PA does not provide for the construction of real numbers.

we can represent sets as number-theoretical predicates — alcontali

The quote you adduced says 'arithmetical sets' can be represented that way. Not sets in general.

the bi-interpretability of number theory and set theory — alcontali

No, the equivalence of PA and FINITE set theory, aka known as the theory of hereditarily finite sets.

A formal language is a class of sentences, just like a model-theoretical model is. — alcontali

Not if you're talking about basic mathematical logic. A language is not a set of sentences. A language is a set of symbols and arity functions. A theory is a set of sentences closed under deduction. A model is not a set of sentences. A model is a certain kind function on the set of symbols of a language.

GrandMinnow

ZF-Inf — Nagase

Some authors use 'ZF-Inf' to really mean ZF with infinity replaced by the negation of infinity. But better practice is to notate as '(ZF-Inf)+~Inf' to ward against confusions such as this by another poster:

"

(ZF minus infinity) is bi-interpretable with number theory (PA) — alcontali

'ZF minus Inf' there is incorrect and seems to come from 'ZF-Inf', when it should be 'ZF minus infinity plus the negation of infinity' or 'ZF with infinity replaced by the negation of infinity'.

GrandMinnow

The universes of ZF-Inf are all infinite. This is clear from the fact that ZF-Inf has the power set axiom, so that there's no bound for the size of its sets. — Nagase

Unless I'm overlooking something, for any theory, and for any cardinality, there is a model of the theory such that the universe of the model has a member of that cardinality.

alcontali

Whatever you read on a forum, it's not ZF minus infinity that is, in a certain sense (a qualification I'll leave tacit henceforth), equivalent with first order (a qualification I'll leave tacit henceforth) PA. Rather it is ZF minus infinity plus the negation of infinity that is equivalent with PA. — GrandMinnow

The original paper by Richard Kaye and Tin Lok Wong says:

Folklore Result.The first-order theories Peano arithmetic and ZF set theory with the axiom of infinity negated are equivalent, in the sense that each is interpretable in the other and the interpretations are inverse to each other.
...
the notion of ‘ZF set theory with the axiom of infinity negated’ turns out to be ...
...
For example, Chang and Keisler [5,§A.31] specify one particular choice of axiomatisation of ZF; for this axiomatisation a weak form of interpretation-equivalence of ‘ZF with infinity negated’ and PA can be proved, but for stronger notions of interpretation-equivalence a different axiomatisation of ZF seems to be required.
...
By ZF−inf we mean the theory in the first-order language L∈o f set theory with all the usual axioms of ZF except infinity, which is negated.
...
It was observed in 1937 by Wilhelm Ackermann [1] that N with the membership relation defined by n ∈ m iff the nth digit in the binary representation of m is 1 satisfies ZF−inf. — On interpretations of arithmetic and set theory

In my impression, it means that the induction-complete notion of infinity ("axiom of infinity") is not part of the ZF−inf theory. The idea to call it "ZF−inf" is apparently even older than this particular paper.

No, PA has successor (adding one), addition, and multiplication as primitive. — GrandMinnow

Addition and multiplication are defined in terms of the successor function:

The Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. The respective functions and relations are constructed in set theory or second-order logic, and can be shown to be unique using the Peano axioms. — Wikipedia on Peano's axioms

In my impression, addition and multiplication (and their inverses) are not counted as being part of Peano's axioms.

That seems to be your main point. And it is wildly and clearly incorrect. PA cannot prove the existence of an infinite set — GrandMinnow

ZF−inf can't either.

No, the equivalence of PA and FINITE set theory, aka known as the theory of hereditarily finite sets. — GrandMinnow

Yes, but that should have been clear from the context. The set theory at hand is ZF−inf and not ZFC.

Not if you're talking about basic mathematical logic. A language is not a set of sentences. A language is a set of symbols with arity functions. — GrandMinnow

I was talking about languages as seen through the lens of computer science, i.e. regular languages, context-free languages, and so on. They are not exactly the same as what is meant by language in mathematical logic. Still, they are covered by the same term, i.e. "language". For example, the natural numbers as a model can be characterized by a simple regular language.

model is not a set of sentences. A model is a certain kind function from the symbols of a language. — GrandMinnow

A model is a set of sentences in a particular "language" (as defined by computer science). For example, the natural numbers are the set of sentences characterized by a class of isomorphic regular expressions.

GrandMinnow

The original paper by Richard Kaye and Tin Lok Wong — alcontali

Yes, it exactly supports what I said. The theory in question is not ZF minus Inf; rather it is ZF minus infinity plus the negation of infinity.

Addition and multiplication are defined in terms of the successor function: — alcontali

In second order PA. But in first order PA, addition and multiplication are primitive. And in this context of equivalence with (ZF-Inf)+Inf, we're talking about first order PA.

In my impression, addition and multiplication (and their inverses) are not counted as being part of Peano's axioms. — alcontali

Your impression stems from your lack of distinguishing first order from second order.

clear from context [...] The set theory at hand is ZF−inf and not ZFC. — alcontali

Your usage and understanding of the concepts all around is so abysmally sloppy that context does not excuse you. When you write "set theory" but mean "the theory of herditarily finite sets" then you need to write "the theory of hereditarily finite sets" and not "set theory".

I was talking about languages as seen through the lens of computer science — alcontali

You said "model theoretic" in the exact passage. Granted, you did go into other areas in the discussion, so you might think again that context justifies, but your posting in all this is so jumbled that no one can be expected to sort through your widely misleading terminological departures. Unless you stipulate clearly that you have something very different in mind, you should stay consistent with the terminology of model theory, especially when you call it 'model theoretic'.

A model is a set of sentences in a particular "language". — alcontali

There might be such a notion in another branch of study, but not in ordinary mathematical discussion. By glibly throwing around terminology the way you do, it is, extraordinarily difficult to take your posts in a way that is not confusing let alone terribly misleading.

GrandMinnow

Even the title of the thread you posted is wildly, clearly and egregiously incorrect:

"You can do with numbers everything that you can do with sets, and the other way around"

alcontali

When you write "set theory" but mean "the theory of herditarily finite sets" then you need to write "the theory of hereditaraily finite sets" and not "set theory". — GrandMinnow

I thought that this was clear by clearly mentioning what set theory it is about. "The set theory" in my post is indeed "the theory of hereditarily finite sets".

There might be such a notion in a branch of study, but not in ordinary mathematical discussion. — GrandMinnow

I was not aware of the fact that the meaning of the terms "language" and "sentence" in computer science would be so out of place in mathematical logic. I am quite surprised by that, but I can see that it is probably true. It is mostly a question of properly qualifying these terms.

As I see it, a model-theoretical model is a grammar (as understood in computer science) along with a set of operators that interprets a theory which is a set axioms (written in again another grammar). I find it a lot easier to understand the concept in these terms.

In fact, I find it quite amazing that the collection of sentences (not logic ones but computer-science ones) constrained by a particular grammar can interpret a set of axioms. You get two unrelated formalisms that are to an important extent equivalent. I find that surprising and intriguing.

That does not mean that I would be interested in everything that ever gets investigated in model theory, such as, for example, the model for the real numbers and so on. I cannot do anything with real numbers, because they are generally not computable.

So, my post was about my understanding about the subject. It was not meant to be a particularly standard take on the matter, or an elaboration on the numerous formalisms and subtleties involved in the formal proof. For that purpose, the reader should rather use the original paper by Richard Kaye and Tin Lok Wong.

alcontali

Even the title of the thread you posted is wildly, clearly and egregiously incorrect:

"You can do with numbers everything that you can do with sets, and the other way around" — GrandMinnow

In terms of computability, it is not incorrect. Computability cannot handle full ZFC. In computability, everything is fundamentally just a natural number; even its pseudo-real numbers. Hence, in all practical terms, you cannot even do anything with what ZFC can do more than ZF-inf, because computers cannot handle that.

Nagase

↪alcontali

Again, a couple of observations:

(1) If the objective was to just express the finite arithmetical sets, and not interpret ZF-Inf, I don't understand why you don't simply use the first idea that came to your mind. That is, if the set is, say, {2, 3, 4}, then we can express that using the PA formula x=SS0 v x=SSS0 v x=SSSS0. No need to use a sgn function.

(2) In any case, again, note that being able to express a finite set is not the same as being able to interpret ZF-Inf. In particular, expressing a set is achieved by finding a suitable formula that is true only of the members of the set, whereas interpreting ZF-Inf requires one to find terms to stand for sets, and a suitable relation between such terms that captures the notion of belonging. For example, under the Ackermann interpretation, we can name the set {} by 0, the set {{}} by 1, and then we can say that "{ } belongs to {{}}" by way of "the 0th digit of 1 is 1". On the other hand, your supposed interpretation cannot say "the set {} belongs to the set {{}}", because you have neither provided a name for the relevant sets nor provided a suitable relation that captures the set membership relation.

(3) I'm not particularly convinced that a model is a "set of sentences". Consider any non-standard model of PA. How can we capture this non-standard model in a set of sentences? Certainly it is not by taking the set of all sentences true in it, because it is easy to show that there are non-isomorphic, elementarily equivalent non-standard models of PA. So the model outstrips our (first-order) expressive resources.

Nagase

↪SophistiCat

I joined when the other forum went down, but I haven't been much active. I generally post only when I have some spare time from university work...

You can do with numbers everything that you can do with sets, and the other way around

Welcome to The Philosophy Forum!

Categories

More Discussions