impossible in computer science. — alcontali

Then it's model theory. And your statement about it is plainly incorrect.

I only get to figure that out by actually doing it. If I don't do it, then I will never figure out where the problems are, not even the problems with the terminology. — alcontali

Your improvised public "figuring out", with confusions conflating terminology from two different areas of stusy, results in posts that are misinformation.

The term sentence in mathematical logic is probably the most closely related to "those strings for which some decision procedure produces the answer YES". — alcontali

That is very incorrect as far as mathematical logic is concerned.

A nonstandard model is created by throwing a symbol κ into the fray — alcontali

This is a notion of non-standard model not in model theory (in mathematical logic) but in computer science?

It is clearly not the notion in model theory.

if a first-order theory has a model of a given infinite cardinality, then it has models of every infinite cardinality. — Nagase

I'm not referring to the cardinality of the universe. I'm referring to the cardinality of each member of the universe.

In terms of computability, it is not incorrect. — alcontali

The headline reads onto itself and is incorrect. You do somewhat correct it in your post (though, even there, you mistate by saying "ZF minus infinity" rather than "ZF with infinity replaced by the axiom of infinity").

"The set theory" in my post is indeed "the theory of hereditarily finite sets". — alcontali

Then you're much better saying it rather than depending a very confused "context".

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. — alcontali

If your usage is is indeed standard computer science, then, yes, the terminology of computer science is radically different from basic mathematical logic. If you insist on using the terminology differently from the way it is used in ordinary discussions about hereditarily finite sets and PA, then you need to clearly state your system of terminology from your own basics rather than, without due specification, mixing it up with ordinary usage.

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"

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.

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.

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

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.

Saying that infinities have two aspects, cardinality and density, confounds me. — Gregory

As I mentioned before, the predicate 'is infinite' is defined as 'is not finite'. You then objected that that is "an illegal move". I explained that definitions are not "illegal moves" and I suggested a book that has an excellent discussion of the methods of mathematical definition. I don't know whether you understand now that definitions are not "illegal moves".

Meanwhile, 'is dense in the ordering' is a separate predicate.

I never have rearranged the odd numbers to biject them to the naturals — Gregory

There is no rearrangement in the proof.

As Tristan L has so generously and perspicaciously explained, the proof adduces a one-to-one function from the naturals onto the odds, and that is all that is needed.

Do you know the mathematical definitions of 'function', 'one-to-one', and 'onto'? Understanding those basic concepts, plus some grammar school arithmetic, leads to understanding the proof easily.

I'll look into Cantor proof more today. — Gregory

I suggest first establishing a firm understanding of the axioms and rules of inference of mathematical proof and definitions - whether in formal first order predicate logic or the informal techniques that are formalized by first order predicate logic. If one understands these conventions for mathematical proof, then one sees that the proofs of, for example, these theorems are incontestably correct:

the set of natural numbers is equinumerous with the set of odd numbers
the set of natural numbers is equinumerous with the set of rational numbers
the set of natural numbers is not equinumerous with the set of denumerable binary sequences
the set of natural numbers is not equinumerous with the set of real numbers
no set is equinumerous with its power set

Of course, one may choose to reject the axioms and rules of inference upon which the proofs depend. But it is incontestable that the theorems are entailed by those axioms and rules.

Below is a link to an article about HF. (They do call it ZF-Inf, contrary to some others, including me, who call it (ZF-Inf)+~Inf):

https://projecteuclid.org/download/pdfview_1/euclid.ndjfl/1193667707

[If the link doesn't work, do Internet search for 'richard kaye hereditarily finite' and it will be the first result.]

Note that the article warns against overlooking certain technicalities, as doing so leads to a merely "folktale" understanding. Indeed, the subject of interpretation of theories into another, and especially the exact sense of "equivalence", especially with PA and HF, is a lot of technical details that are doomed to be mangled in the confines of short posts.

ZF-inf says: There is no x such that all natural numbers are a member of x. — fishfry

That is not correct.

ZF-Inf is ZF but without the axiom of infinity. (The '-' here means 'without'; it doesn't mean 'the negation of'.)

(ZF-Inf)+~Inf is ZF but with the axiom of infinity replaced by the negation of the axiom of infinity.

the hereditarily finite sets. [...] I just thought they were the usual finite von Neumann ordinals, ie the natural numbers. — fishfry

No, the finite ordinals are a proper subset of the set hereditarily finite sets. For example, {0 2} is an hereditarily finite set but it's not an ordinal.

Is there something else special about them? — fishfry

They may be of interest for many reasons, but for starters, they are the usual universe for a model of "finite set theory" = (ZF-Inf)+~Inf = HF.

so interpretation is a technical term that I think I don't know. I know what it means to interpret an axiomatic theory, ie assigning meaning to the symbols or at least assigning elements of some model. — fishfry

This is a different sense of 'interpretation' (but closely related). Simplifying here: We interpret a theory T into a theory T' by defining the symbols of T in the language of T' so that every every theorem of T is a theorem of T' plus the added definitions. And we say the theories are equivalent when there is such an interpretation from T into T' and vice versa. (This deserves a sharper statement, but it's too many technical details for a post.)

How are HF and N different? — fishfry

HF is a theory. N is a set.

You're saying [in HF] I can't form the predicate that I think characterizes N. — fishfry

Defining a predicate symbol is not a problem. But there is no definition of a constant symbol (such as 'N') such that N = {y | y is a natural number}, since HF does not prove that there exists an object that has as members all the natural numbers.

In any language, in any theory, we can define whatever predicate symbols we want. It's only function symbols (including constant symbols, where a constant symbol is a 0-place function symbol) that require the supporting existence and uniqueness theorem

I can't form the collection of all numbers because I haven't got the language to do that. — fishfry

In HF, you have the language, but you don't have the existence theorem ExAy(y is a natural number -> y e x).

in any model of ZF-inf there is not a set of all natural numbers — fishfry

No, the sentence ExAy(y is a natural number -> y e x) is a theorem, but that doesn't preclude what the members of the universe for the model may be.

For every infinite cardinality, there is a model of ZF-Inf with a universe of that cardinality. And that universe can have as members any sets whatsoever. Same for (ZF-Inf)+~Inf. Same for PA.

For example, we can have a model of PA whose universe is {w, w+1, w+2} and each of those members of the universe is infinite.

But wait, (ZF-Inf)+~Inf has a theorem ~Ex Ix [where 'I' is a defined 1-place predicate symble we are read in English as "is infinite"], so how can the universe of a model have a member that is infinite? Well, because for such a model, the predicate symbol 'e' is interpreted not as the ordinary membership relation but rather as some other "bizarre" relation and so also my 'I' be interpreted differently from "is infinite". When we talk about models in general, we can't presume that any given model of a theory "captures" the way we ordinarily "read off" the theorems of the theory. If we want to narrow the discussion to only models that adhere to the way we "read off' the theorems, then we should confine to talking about standard models.

in ZF there is no such definition or thing as a proper class. — fishfry

In ZF, we may define:

x is a proper class <-> Ey y e x & ~Ez x e z

And we may prove:

~Ex x is a proper class.

When the Peano axioms say, "O is a number," — fishfry

First order PA doesn't have a primitive 'is a natural number'.

Peano's historical own formulation should not be conflated with first order PA.

the set of all sets is a proper class — fishfry

There is not a set of all sets, not even in class theory. There is the class of all sets, and it is a proper class. And I explained why referring to proper classes in discussion about set theory can be understood as an informal rendering for an actual formal notion in the background, but that is lacking here in saying N is a proper class in discussion about PA.

And N is a set, which is not needing exceptions in view of the fact that in PA there can be no definition N = {x | x is a natural number}. If one wishes to say "N is a proper class with respect to PA" but not formulate the exact mathematical meaning of "with respect to" or even to a clearly articulate an intuitive/heuristic notion that is still consistent with the ordinary mathematical result that N is a set, and hopefully has value as a metaphor rather than confusing the subject with impressionistic use of terms, then, of course, I cannot opine whether or not in one's own mind it somehow makes sense nevertheless. But I do say, and have explained, that it makes no sense to me.

The Dave Brubeck Quartet was unusual in its "whiteness" during its heyday in the 1960s. [...] something of a rarity. — Ciceronianus the White

Eugene Wright, the bass player with the Dave Brubeck quartet during the '60s, was not white.

Perhaps through at least the '60s, whites were somewhat a minority in jazz, but never rare. Since at least the 1920s, jazz has had many famous white musicians.

Perhaps one might get the notion of the universe for PA as "a proper class as far as PA is concerned" [or whatever paraphrase] from the notion regarding set theory that for every formula with n number of free variables there is the class of n-tuples for which that formula holds (where n =1, the class of individuals for which the formula holds).

That is okay as an understood informality when speaking of set theory. But it does not transfer to PA or HF in the same way. The reason is that PA and HF already have a meta-theory in which everything is a set. So saying "the proper class that is the extension of the predicate" (i.e. the predicate carved out by the formula) is a way of saying that there is no set of all things that have the predicate but for convenience, and recognizing this as merely informal, we can speak of the formula itself as if it specifies a "class". However in PA or HF, any formula specifies not a proper class but a set. Even the universal predicate specifies the set that is the universe of whatever given model for the theory.

Example:

With set theory, "the proper class of ordinals". This is an informal way of saying "those x such that 'x is an ordinal' holds". It is a breezy way of speaking, when more formally we would refer only to the formula 'x is an ordinal'. In other words, saying "If x is in the proper class of ordinals" is an informal locution for "If 'x is an ordinal' holds". Or for example, "relativize F(x) to the proper class of finite sets" is a locution for "Ax(x is finite -> F(x)).

With PA, "the proper class of natural numbers". No, doesn't work, because the usual meta-theory for PA is set theory where there is the SET of all natural numbers, which encompasses those x such x is a natural number.

I'm not advanced. But I do have a methodical understanding of some basics.

(1) There is a difference between ZF-Inf and (ZF-Inf)+~Inf. I'll call the later 'HF' (the theory of hereditarily finite sets).

The language of HF is the language of ZF (i.e. the language of set theory).

PA and HF can be interpreted in each other.

The usual universe for HF that we have in mind is the set of hereditarily finite sets. And of course N is also a universe for HF.

(2) Most textbooks take 'is a set' as informally primitive, but we can be precise in the language of set theory:

x is an urelement <-> (~ x=0 & ~Ey yex)

x is a class <-> ~ x is an urelement

x is a set <-> (x is a class & Ey xey)

x is a proper class <-> (x is a class & ~ x is a set)

In set theory, we can prove:

Ax x is a set (though, as mentioned, most textbooks don't bother with something so basic).

(3) The language of class theory (such as Bernays style class theory, which I'll call 'BC') has a primitive predicate 'is a set' (or a many-sorted language is used, which is essentially the same as using a primitive 1-place predicate), so in BC 'is a set' is not defined but instead certain axioms are relativized to sets.

In BC we prove:

Ex x is a proper class

(4) I explained why "N is a proper class in PA" [or whatever paraphrase] is, on its face, not coherent. But I allowed that one is welcome to adduce some particular mathematical statement instead. And I explained why it would not be a correct statement in set theory (and I would add, not even in BC). So maybe we turn to HF.

Since HF is in the language of set theory, in HF we can define any predicate of set theory, and we can define any operation of set theory for which we can prove existence and uniqueness in HF.

HF proves ~ExAy(y is a natural number -> y e x). So there is no definition of 'N' (in the sense of the set of natural numbers) in HF.

So, while HF can have predicates 'is a natural number', 'is a set', and 'is a proper class', still HF can't have the definition N = the set of natural numbers.

As far as I can tell, the best we could do in NF is this theorem:

If Ax(Ay(y is a natural number -> yex) -> x is a proper class). But that holds vacuously, since there we have ~ExAy(y is a natural number -> yex).

So, as far as I can tell, we are still thwarted from making sense of "N is a proper class in PA" or even "N is a proper class in HF".

And in set theory (and even in BC, if I'm not mistaken) the universe for a model is a set, not a proper class.

(5) Caicedo says, "in ZF without the axiom of infinity [...] you cannot prove that w is a set, but you can prove that as a (perhaps proper) class, it satisfies both first and second order PA."

I don't know why he says 'perhaps' there. And without more explanation, I don't understand what he's saying.

I do understand that, in ZF-Inf, there is not a proof that there is a set of which all natural numbers are a member (that's another way of affirming the independence of the axiom of infinity).

But when he says "you can prove", does he mean prove in ZF-Inf? Proof of satisfaction with models takes place in set theory, not in ZF-Inf nor in HF. And in set theory, universes of satisfaction are sets, not proper classes.

What is understandable to say is:

ZF-Inf does not prove there is an x such that all natural numbers are a member of x.

HF proves there is no x such that all natural numbers are a member of x.

PA and HF are mutually interpretable.

The set of natural numbers N is a universe for a model of ZF-Inf or of HF.

But saying "in Pa (or in HF), N is a proper class" makes no sense.

(6)

absent the axiom of infinity, w (or N) is a proper class. — fishfry

No, absent Inf, it is not a theorem that N is a proper class. Indeed, absent Inf, there is not even possible a definition N = the set of natural numbers. Rather, absent Inf, there is not a proof that there exists an x such that all natural numbers are in x, and there is not a proof that there is no x such that all the natural numbers are in x. In other words, "there is an x such that all natural numbers are in x" is independent of ZF-Inf. However, (ZF-Inf)+~Inf does prove "there is no x such at all natural numbers are in x", but still, it does not say anything about such a thing (which does not exist anyway in NF) being a proper class or not.

(7)

Yes, you can't define the ordinals in PA because you can't get to the first transfinite ordinal ω by successors. — fishfry

In HF, we can define the predicate 'is an ordinal' and for any finite ordinal, we can define a constant for it. But, as you mention, we can't define a set that has all the finite ordinals as members.

But even in set theory, there are specific ordinals that don't have a definition (there are more than countably many ordinals, but only countably many definitions we could form).

I guess you're referring to something you wrote previously in this thread. Whatever you have in mind, it does not contradict that definitions are not "illegal moves".

"It's legal for finite, not infinite" makes no sense. You can inform yourself about the subject with introductory textbooks.

It can't be an "illegal move" since it is merely a definition.

The best explantion (an exellent one) I have found of how mathematical definitions work is:

Introduction To Logic - Patrick Suppes

There are many senses in which mathematicians use the term 'infinity'. But when we get to formal definitions, we distinguish among those senses.

These are basic definitions :

w = the set of natural numbers

x is finite <-> there is a 1-1 correspondence between x and a natural number

x is infinite <-> x is not finite

x is denumerable <-> there is a 1-1 correspondence between x and w

x is countable <-> (x is finite or x is denumerable)

x is uncountable <-> x is not countable

More good understanding about this and related topics is available in any introductory textbook in set theory.

Maybe this will help:

PA is a certain set of sentences. There is no sentence in PA that one would ordinarily regard as saying "N is a proper class". There is a universal quantifier for PA, and with any model (formulated in set theory) for PA, the universal quantifier stands for the universe of the model. And that universe is always a set. In particular, with the standard model, the universe is N, which is a set.

I think maybe what you were driving at originally might be said this way:

The universe for the standard model of PA is N and has as its members all and only the natural numbers, so N itself is not a member of N. And with the standard model, PA itself does not assert the existence of a set that has all the natural numbers as members.

Couching that in terms of proper classes is off.

We can go further, it is not precluded that other models of PA do include all the members of N and N itself as a member of the universe for the model. Most simply, N+ (i.e. Nu{N}) is a denumerable universe for certain models of PA.

I paraphrased what you said:

"via the Peano axioms, in which N is a collection but not a set"

"in PA, the natural numbers are a proper class"

Those are not actual mathematical statements. Not even informally. First order PA (throughout, I will mean first order, which is what people usually mean in modern context unless said otherwise, and as your remark about set theory proving model existence also suggests you're not referring to higher order PA) does not speak of N (not as a formula "in" PA, but only by model interpretation in, say, set theory) nor of a distinction between sets and proper classes. And it would be quite remote, along with needing to work out needed details in execution, to justify those two quoted claims by the fact that PA can be viewed as (ZF-Inf)+~Inf.

In PA the extension of the unary predicate "n is a natural number" is the collection we call NN. — fishfry

No such thing takes place in PA there is no unary predicate 'is a natural number'. Usually the meta-theory for making statements about PA is set theory. And in set theory, the notion of an "extension of a predicate" is given by a model. The universe for the standard model is N, which is a set.

In other words PA is a model of ZF-infinity. — fishfry

PA is a theory, not a model. The correct statement is that PA and (ZF-Inf)+~Inf can be interpreted in each other. But that still doesn't make "N a proper class in PA" a coherent statement.

The only way to get a model of PA is to wave your hands and say the magic words, "Axiom of infinity!" — fishfry

Then one can say that any axiom of any theory is waving hands and saying magic words. But yes, a model of PA is proven to exist from the set theory axioms that include the axiom of infinity. Again, that does make "N a proper class in PA" a coherent statement.

/

Correct statements include these:

If PA is consistent, then PA does not prove that PA has a model.

Set theory proves that N, which is a set, is the universe for a model of PA.

And that does not involve proper classes.

No, by definition, x is uncountable if and only if x is not countable. That's simply a definition of 'uncountable'.

Then we prove that there do indeed exist sets that are uncountable. And we prove that, in particular, the set of real numbers is uncountable.

The diagonal proof does not assume what it proves. Rather, it assumes some quite basic axioms of set theory, then it proves from those axioms that the set of real numbers is not countable (i.e. that it is uncountable). One may wish not to accept the axioms used, but that is a different matter.

(1) I don't know in what exact mathematical formulation one says [paraphrasing] "N is a proper class as far as PA is concerned". First order (I'll mean first order throughout) PA is a theory, i.e. a set of sentences closed under deduction. A typical meta-theory for PA is set theory. In set theory we prove that PA has models. And the universes for these models are sets, not proper classes. And one of those universes is N, which is a set.

Indeed, every consistent theory has a model whose universe is a set. Moreover, every consistent theory that has a model with an infinite universe also has a model with a denumerable universe. Moreover, every consistent theory that has a model with an infinite universe also has a model whose universe is N.

Meanwhile in the standard interpretation of PA there is not even mention of sets, proper classes, or universes for models of PA. So, since the standard interpretation of PA doesn't mention it, and, in PA's ordinary meta-theory, universes are sets, not proper classes, I don't know where there would be an actual mathematical formulation of "N is a proper class as far as PA is concerned."

(2) Usual terms for inductive sets are 'inductive set' or 'closed under induction', The induction may pertain to a relation or operation. In the case of ordinals, we may consider the successor operation ( Sx = xu{x} ), and indeed, as mentioned, limit ordinals are closed under the successor operation.

(3) It is not necessary to use the axiom of regularity or unions to show that there is no set that has all the ordinals as members, as follows:

Lemma (easy to prove without using the axiom of regularity): No ordinal is a member of itself.

Now suppose there is a K such that every ordinal is a member of K. Then let L be the subset of K that has only ordinals as members. Then L itself is an ordinal (easy to prove). But then L is a member of itself. Contradiction.

(4) As mentioned, the notion of showing that two theories (even with completely different symbol sets) "say essentially the same thing" is rigorously captured by showing that there is an interpretation of one theory into the other and vice versa. The mathematical formulation of an interpretation of a theory into another is straightforward and not mysterious.

There are too many incorrect claims in this thread (and forum) to reply to them all. But I'll address one about the axiom of extensionality.

The axiom of extensionality is:

If for all z we have z is in x iff z is in y, then x = y.

That does not contradict the theorem:

There exists a unique x such that for all z we have that z is not in x

and then we have the definition:

the empty set = the x such that for all z we have that z is not in x

Assuming "countable" is what denumerably infinite means — tim wood

That's not what 'countable' means. Here are the definitions:


S is countable iff (S is 1-1 with a natural number or S is 1-1 with N)

S is denumerable iff S is 1-1 with N

S is countably infinite iff (S is countable and S is infinite)


So it's easy to prove that S is countably infinite iff S is denumerable.

So 'countable' does not mean "denumerably infinite", and "denumerably infinite" is redundant, and 'countably infinite' is equivalent to 'denumerable'.

.10101010..., how long is it? How many zeros and ones? As many as there are counting numbers? Or more? ℵo or ℵ1? — tim wood

In this context, for convenience, by 'string' we mean 'denumerable binary sequence'. That said, here we go:

The length of any string = card(N) = aleph_0.

I'm thinking the number of digits must be countable. And I'm thinking my listing, then, being ordered, is also countable. It's all countable. But clearly that's not correct. — tim wood

Each string in the list has denumerable length. And there are denumerable lists of such strings. But there is no denumerable list of strings such that the list has every possible string in the list.

if the list is denumerable and complete (just as N is denumerable and complete), then the diagonal argument seems not to work, because any new number generated by the diagonal process will already be somewhere on the list. — tim wood

IF the list includes every string, then the diagonal argument doesn't work. But that's not saying much, because we have not shown that there is a list that includes every string. Indeed the diagonal argument proves that there does not exist a list that includes every string. There is no force to an argument that says "If there is a complete list then there is a complete list".

Instead, you start with the question "Is there a complete list?" Then you prove that there is no complete list.


REVIEW of all this:

Each string has denumerable (i.e., countably infinite) length.

The question is "What is the cardinality of the set of all strings?"

If there is a denumerable list that has every string as an entry, then the cardinality of the set of all strings is card(N).

So is there a denumerable list that has every string as an entry? The diagonal argument proves that the answer is No.

And the notation 2^N stands for 'the set of functions from N into {0 1}", which is exactly the set of all strings.

We also prove that the card(2^N) = card(PN).

So the cardinality of the set of all strings = card(2^N) = card(PN).

And the cardinality of the set of all strings does NOT equal card(N).

Whether it's "true" in any meaningful sense is, frankly, doubtful. — fishfry

This is more a philosophical or psychological question than a purely mathematical one, but I don't have much problem understanding that the set of natural numbers and other infinite sets exist as abstract mathematical objects. And it's a pretty safe bet that mathematicians in general feel the same. Even as a child, I was introduced in a school textbook to the notions of the set of natural numbers, the set of rational numbers and the set of real numbers; and that did not seem problematic to me. And of course, as we know, whatever our feeling about the truth of real or abstract existence outside of the formal notion of existentially quantified theorems, no mathematical contradiction has been shown from ZFC.

As I understand, you're asking: What is cardinality of the set of finite sequences on a set of cardinality x?

I'm very rusty in math, so let me see if I remember correctly:

Let F(x) = the set of finite sequences on x.

Let w = the set of natural numbers.

If x is countable, then card(F(x)) = w. (That's for sure.)

If x is uncountable, then card(F(x)) = x? That follows by the absorption property of infinite cardinal arithmetic? (I'm almost sure that's right. But I'd have to check that I'm not overlooking a flaw in my premises.)

And card(PPR) = beth2.

The following set of sets is an element of the powerset of real numbers: — alcontali

No, that set is a member of the power set of the power set of the set of real numbers.

And I don't understand the rest of your post, starting with "any language expression that matches only this kind of stuff, would be the membership function for a set of which the cardinality would be the powerset of real numbers"

No, your argument is nothing like Cantor's argument.

Cantor proved that there does not exist a surjection from the one set onto the other, peforce that there is no bijection between them. (No surjection from N onto R, perforce no bijection between them).

Your argument just points out that one particular function is not a bijection from the one set onto the other (it's not a bijection from E onto N) The fact that one particular function is not a bijection from the one set onto the other does not prove that no other function that is a bijection from one set onto the other. And indeed we prove that there is a bijection from the one set onto the other.

Cantor proved that there is no surjection from N onto R.

But we also know that there is a bijection between N and E.

It is a clear logical fallacy to infer that because some particular function is not a bijection between N and E that therefore there is no function that is bijection between N and E.

I offered to recommend some starting books on this subject so that you can inform yourself to avoid the fallacies and confusions to which you are prone.

A very simple text. — TheMadFool

What is the name and author of the text?

Axiom of infinity? — TheMadFool

The axiom of infinity is not a mathematical object named 'infinity'.

Moreover, the axiom of infinity itself is a finite mathematical object, as it is a finite string of symbols in a formal language.

How is it "wordplay"? — TheMadFool

I explained explicitly in my post.

Oh I see now. They may not be the same thing but just two different objects that behave in the same way. — TheMadFool

No, you just made the same mistake I pointed out the first time.

what axioms would be necessary for the existence of natural numbers and the basic mathematical operations of + and ×? I begin from these — TheMadFool

There are lots of different axiom systems for such things. For example, set theory. The existence of natural numbers is proven in set theory (even without the axiom of infinity). The existence of the set of natural numbers is proven in set theory (with the axiom of infinity). The operations of addition and multiplication are also definable and proven to exist in set theory.

Set theory proceeds from formal axioms, formal definitions, and formal rules of inference. Your argument has no apparent basis in those axioms, definitions, and rules. So I ask you what, exactly, are your axioms, definitions, and rules. Without specifying them, your argument, using such verbiage as "this pattern suggests" and then the non sequitur "in other words there is a largest natural number" is nonsensical handwaving, also known as 'waffle'.

Moreover, not just axioms, but ordinary mathematical common sense endows us with the understanding that there is no greatest natural number. Suppose there were a greatest natural number n. Then n+1 is greater than n. So n is not, after all, a greatest natural number.

This post got out of sequence. I put the text in my next post.

I wrote "isomorphism" in scare quotes because I don't mean an actual function. I mean that tuples and sequences are "isomorphic" in that you can recover the order from one to the other and vice versa. This can be expressed exactly, but it's a lot of notation to put into posts such as these. Anyway, the general idea is obvious and used in mathematics extensively.

My math is at high school level so bear with me. — TheMadFool

If you like I can recommend a few textbooks in first order predicate logic and then set theory that would provide you with a self-course in this subject. Then you would not be prone to confusions about the subject.

In terms of cardinality or largeness or magnitude N = E. — TheMadFool

That's not how we say it. Rather, we say the cardinality of N equals the cardinality of E.

card(N) = card(E)

we pair the members of E with the even numbers in N. — TheMadFool

The even numbers in N are just the members of E. So your pairing is just pairing the members of
E with the members of E.

What now of the odd numbers in N? They have no matching counterpart in E.

Doesn't this mean N > E? — TheMadFool

No.

N > E

means

Both hold: (1) there is a pairing from E to a proper subset of N and (2) there is no pairing between N and E.

But there is a pairing between N and E, so it is not the case that N > E. The fact that there is a pairing from E to a proper subset of N (e.g. the pairing misses the odd numbers in N) does not contradict that still there is a pairing between N and E.

/

I recommend this terminology ('<->' means 'if and only if'):

f is an injection from S into T <-> (f is a one-to-one function & the domain of f is S & the range of S is a subset of T) [note: here the range of f might not be a proper subset of T since it is allowed that the range of f is T]

f is a surjection from S onto T <-> (f is a function & the domain of f is S & the range of S is T) [note: here f might not be a one-to-one function]

f is a bijection from S to T <-> (f is an injection from S into T & f is a surjection from S onto T)

S is equinumerous with T <-> there is a bijection from S to T

S is dominated by T <-> there is an injection from S into T

S is strictly dominated by T (i.e., S < T) <-> (there is an injection from S into T & there is no bijection from S to T)

This post by TheMadFool was supposed to rolled into this thread:

[start quote of post]

This is a question from an elementary math book:

u = u + 1.
(i) Find the value of u
(ii) What is the difference between nothing and zero?

If you try and solve u = u + 1 you'll get 0 = 1 (subtracting a from both sides)

0 = 1 is a contradiction. So u is nothing. u is NOT zero. u is nothing.

Why?

Take the equation below:

e + 1 = 1

Solving the equation for e gives us e = 0. The same cannot be said of u = u + 1 our first problem.

So given the above equations ( u = u + 1 AND e + 1 = 1) we have the following:

1) u is NOTHING. u is NOT zero
2) e = zero

What's the difference between NOTHING and zero?

My "explanation" is in terms of solution sets.

The solution set for u = u + 1 is the empty set { } with no members
The solution set for e + 1 = 1 is {0} with ONE member viz. zero.

There's another mathematical entity that can be used on the equation u = u + 1 and that is INFINITY.

INFINITY + 1 = INFINITY

So we have:

a) u is NOTHING
b) u is INFINITY

Therefore,

NOTHING = INFINITY

Where did I make a mistake?

Thank you.

[end quote of post]

(1) What math book is that? What is the context? What does the variable 'u' range over? What specific operation does '+' stand for?

(2) There is no mathematical object named 'infinity' (unless it's something like a point of infinity in the extended real system - and in a context like that, the operations of addition and subtraction have special modified formulations that avoid such contradictions). And if infinite sets are meant, then operations such as cardinal addition or ordinal definitions are formulated so that they may not be confused with the operations of addition on natural numbers or on real numbers.

(3) Your "nothing = infinity" is just wordplay. As mentioned, there is not an object named 'infinity'. And 'nothing' also is not the name of a mathematical object. To say something like "nothing is not equal to itself" is not saying that there is an object named 'nothing' that has the property of not being equal to itself. Rather, it means that there is no object that has the property of not being equal to itself. So then putting an equal sign between 'nothing' and 'infinity' is nonsense.

in Peano arithmetic, the collection of all the natural numbers is a proper class. — fishfry

I wouldn't state it that way. If we mean first order Peano arithmetic (PA), then there are not in PA definitions of 'set', 'class', and 'proper class'. Meanwhile, in set theory, the domain of the standard model of PA is a set.

There are two different domains of discussion: (1) mathematics itself and (2) philosophy of mathematics.

(1) MATHEMATICS ITSELF

(There are forms of mathematics other than classical set theoretic mathematics, but for brevity by 'mathematics' I mean ordinary classical set theoretic mathematics.)

In mathematics we don't ordinarily think in terms of a noun 'infinity' but instead of the adjective 'is infinite'. There is no object (abstract of otherwise) named by 'infinity' (setting aside in this context such things as points of infinity in the extended real system). Rather the adjective 'is infinite' holds for some sets and not for others.

Formal definitions of 'finite' and 'infinite':

A set S is finite if and only if S is in one-to-one correspondence with a natural number.

A set S is infinite if and only if S is not finite.

In mathematics itself there is not a formal set theoretic notion of 'potentially infinite'. Mathematics instead proceeds elegantly without undertaking the unnecessary complication of devising a formal definition of 'potentially infinite'.

(1) PHILOSOPHY OF MATHEMATICS

In the philosophy of mathematics, the distinction between actually infinite and potentially infinite might be described along these lines:

Actually Infinite. An actually infinite set is an object (presumably abstract) that has infinitely many members. The set of natural numbers is an actually infinite set.

Potentially Infinite. There are some philosophers or commenters on mathematics who do not accept that there are actually infinite sets. So for them there is no set whose members are all the natural numbers. Instead these commenters refer to processes that are always finite at any point in the execution of the process but that have no finite upper bound, so that for any step in the execution, there is always a next step available. For example, with counting of natural numbers, only finitely many natural numbers are counted at any given step, but there is always a next step allowed.

In constructive mathematics (not classical mathematics), perhaps, with research, one can find formal systems with a formal definition of 'potentially infinite'. But I would bet that any such system would be a lot more complicated and more difficult to work within than classical mathematics. This is the drawback of the notion of 'potentially infinite'. One can talk about it philosophically, but it takes a lot more work to devise a formal system in which 'potentially infinite' is given an exact, formal definition.

Looks like the difference between Platonism and Constructivism. — Marchesk

It is not necessary to adopt platonism to accept that there are infinite sets. One may regard infinite sets as abstract mathematically objects, while one does not claim that abstract mathematical objects exist independently of consciousness of them.

it should be #{1,2, 3,...} or card({1,2, 3,...}) or |{1,2, 3,...}| for actual infinity — alcontali

No, that is not required. (1) There are infinite sets that are not cardinals. (2) Let w (read as 'omega') be the set of natural numbers. So w = {x | x is a natural number}. That is what is meant by {0 1 2 ...} (I drop unnecessary commas). And w itself is a cardinal, and for any cardinal x, we have card(x) = x anyway.



Here is an explication of 'set', 'tuple', 'sequence', 'multiset' in (set theoretic) mathematics:

Everything is a set, including tuples, sequences, and multisets.

A tuple is an iterated ordered pair.

Definitions:

{p q} = {x | x = p or x = q}

{p} = {p p}

<p q> = {{p} {p q}}

Then also, for example, <p q r s t> = <<<p q> r> s> t>

S is a sequence if and only if S is a function whose domain is an ordinal.

S is a finite sequence if and only if the domain of S is a natural number. (There is an "isomorphism" between tuples and finite sequences. For example: The tuple <x y z> "encodes the same information" as the sequence {<0 x> <1 y> <2 z>}.)

S is a denumerable sequence if and only if the domain of S is w.

S is a multiset if and only if S is of the form <T f> where f is a function whose domain is T and every member of the range of f is a cardinal. (So f "codes" how many "occurences" there are of the members of T in the multiset.)

It is very difficult to define infinity using any concept other than infinity itself. Hence it is often circular, self referential. — Wittgenstein

There is no circularity in the set theoretic definition of 'is infinite'.

Without the axiom of infinity, a concept of actual infinity is not viable. — alcontali

Depends on what you mean by 'viable'. There is a set theoretic definition of 'is infinite' without the axiom of infinity. The axiom infinity implies that there exists a set that is infinite, but we don't need the axiom just to define 'is infinite'. I think you were pretty much saying that yourself, but I wish to add to it. Indeed, we agree that dropping the axiom of infinity makes an axiomatic treatment of mathematics extremely complicated.



Your claimed proof that there is no infinite set is not recognizable as a proper mathematical argument but instead proceeds by hand waving non sequitur.

The set of natural numbers does not have an upper bound, so it will always have a number that is smaller than another number. — Wittgenstein

No, there is no natural number smaller than the natural number 0. So maybe you meant that for any natural number n there is a natural number greater than n.

The problem with axiom of infinity is that it fails to fall in one of the two categories. Intension and extension.

"intensional definition gives the meaning of a term by specifying necessary and sufficient conditions for when the term should be used."

"This is the opposite approach to the extensional definition, which defines by listing everything that falls under that definition." — Wittgenstein

That is irrelevant because the axiom is not a definition and does not need to meet any standards of definitions. Also, we have to distinguish between two different notions of extensional/intensional. Aside from yours, there is the notion of extensionality that applies to set theory: Sets are extensional because they are determined solely by their members. That is, S = T if for all x, x is a member of S if and only if x is a member of T. And it doesn't matter whether a set is described by what you call 'intension' (such as {x | x has property P}) or, for finite sets, by finite listing in braces. For example, {x | x is a natural number less than 3} = {0 1 2}. Of course, infinite sets don't have listings such as {0 1 2}, but that does not vitiate that they exist.

Some logician view that infinite extensions are meaningless as extensions must be complete in order to be well defined, so infinity cannot be defined by extensions. ( They reject Cantors proof too )
The problem with definition using intention is that they are circular. — Wittgenstein

Maybe there are such logicians, but even constructivists accept the proof of Cantor's Theorem and Cantor's proof of the uncountability of the reals.

And there is no circularity in the definitions of set theory. Mathematical definitions are not circular (that is, if a purported definition is circular then somewhere in the formulation of the purported definition there is a violation of the formulaic rules for mathematical definition).