I would like to discuss this because it is absolutely not self-evident to me that two sets of different rules, i.e. PA versus ZF minus infinity, would be completely equivalent. The rules do not even look like each other. Just look at the axioms. They are simply different. Still, if their equivalence is provable, then I would consider that to be an amazing result. — alcontali
The technical condition is that PA and ZF-infinity (read "ZF minus infinity") are
bi-interpretable. Here's one link I found:
https://math.stackexchange.com/questions/315399/how-does-zfc-infinitythere-is-no-infinite-set-compare-with-pa
Also see:
https://mathoverflow.net/questions/551/does-finite-mathematics-need-the-axiom-of-infinity
In fact, in that case, it should be possible to take the axioms of PA, push them through some kind of algebraic transformation process, and then end up with ZF minus infinity. I cannot imagine what this transformation process could look like. — alcontali
Andrés E. Caicedo's checked answer in the Stackexchange thread outlines the procedure.
The axiom of infinity allows us to take the "output of the completed induction,"
— fishfry
That is exactly what I mean by "materializing". — alcontali
I'm not convinced. The completed set of natural numbers is posited, or brought into set-theoretic existence, by the axiom of infinity. If you want to call that materialized, well ok I guess ... but ... Is the powerset of
materialized by the powerset axioms? If I have two sets
and
, is their union materialized by the
axiom of union?
There doesn't see to be much depth to your definition of materialization. It just seems to mean, "brought into existence by a given axiom." In which the entire universe of propositions is materialized by the axiom 0 = 1. Is this what you mean?
The reason why I used this term, is because this is the term used when you fully calculate and store the output of a view formula in relational databases, instead of keeping it around as a merely virtual construct. So, taking the "output of the completed induction" is called "materializing" in that context. — alcontali
Oh I see. I understand the example but it's a bit of a stretch as an analogy for the set of natural numbers being given by the axiom of infinity. But if it works for you I do sort of see what you mean.
I just accidentally used a term (materialized view) en provenance from another domain. — alcontali
It's not really analogous to an axiomatic system IMO but sort of works as a vague metaphor.
In fact, it is not a completely different domain, because relational algebra is a downstream domain from ZF set theory. It completely rests on standard set theory. It is only much closer to practical applications:
Relational algebra, first created by Edgar F. Codd while at IBM, is a family of algebras with a well-founded semantics used for modelling the data stored in relational databases, and defining queries on it.
— Wikipedia on relational algebra — alcontali
Yes, perfectly well aware. But that doesn't make your vague analogy any sharper IMO. But this is not an important matter. Everyone is entitled to their own visualizations, intuitions, and conceptual ideas. Whatever works to understand the material.
Your use of complete is nonstandard and I don't know what you mean.
— fishfry
I wasn't aware of the fact that the notation, N = { 0, 1, 2, ... }, is considered complete in set theory (through the axiom of infinity). — alcontali
It surely isn't. There is no such term of art in set theory. Of course the natural numbers with the usual metric (absolute arithmetic difference) is Cauchy-complete. (Tricky. Why?) It's because every Cauchy sequence of natural numbers is eventually constant. But of course this is not what you meant.
What do you mean? There is no such technical term as saying that
is "completed" by the axiom of infinity. You just said it was materialized. I'd almost buy the latter, because even though it doesn't mean much, at least it's not a totally nonstandard use of the word complete, which has many other meanings in math but none in this context.
(It is obviously not considered complete in PA.) — alcontali
Oh, complete as in a completed infinity. Yes well the problem here is that "actual and potential infinity" are terms of art in philosophy, not math.
You seem to be trying to make something out of not much. If what you're saying is that you weren't formerly aware that it's the axiom of infinity that bestows set-hood on
, ok now you know. But you can see from statement of the axiom of infinity that this is exactly what it does. It says that there is a set that contains the empty set and, whenever it contains a set
, it also contains the successor
.
The negation of the axiom of infinity says there's no such set; and since
is such a set, the negation of the axiom of infinity outlaws its existence.
So, yes, my use of the term "complete" is not standard in set builder notation in reference to ZF (but not in reference to ZF minus infinity). — alcontali
You're just making stuff up here. I'm trying to figure out why you're meandering down this road. PA is perfectly "complete" in your sense, it contains the conclusions of all its axioms. Or something. Neither PA nor ZF are more or less "complete" than the other. They each contain all and exactly those objects that are permitted by their respective axioms. Yes?
These things are extremely subtle. — alcontali
You're reading in subtleties where there are none. From where I sit you are taking a simple fact and tring to give it great significance. PA has all the natural numbers, and ZF via the axiom of infinity has a completed set of them. But if you took ZF minus powerset, then you wouldn't have full powersets. Does the powerset axiom complete ZF with respect to powersets? There's nothing interesting about this, you are seeing complications and subtleties where truly, I say to you as clearly as I can, there are none.
It depends on whether the theory in the context of which it is used, has an axiom that can "take the output of the completed induction", i.e. "materialize" it in relational-algebra lingo. — alcontali
Or make a full powerset. Or a union. So is materializing the same as completing? Why go on about this? Without the axiom of pairing, X and Y could be sets but there's no set {X,Y}. Does the pairing axiom complete, or materialize, pairs of sets? Can you see that you're imagining subtlety where there isn't any?
It is also very related to the concept of list comprehension where a similar problem occurs. You can create the list of natural numbers as a virtual construct, but you cannot "materialize" it, because that will cause your system to run out of memory. — alcontali
In Python there's something called a generator. The idea is that I want to iterate through a list but I don't want to pre-create the full list ahead of time. I just supply the algorithm. This I assume is exactly what you mean. I understand the example, I just don't think it's very interesting or meaningful.
Here, the list [0..] represents ℕN , x^2>3 represents the predicate, and 2*x represents the output expression. List comprehensions give results in a defined order (unlike the members of sets); and list comprehensions may generate the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list.
— Wikipedia about using virtual constructs that represent the infinite list of natural numbers — alcontali
Sure whatever.
So Burali-Forti is a theorem that follows from the axioms of ZF: that the class of ordinals can not be a set. — alcontali
We've already been through the proof. It's straightforward. First you prove that the union of ordinals is an ordinal, therefore if the class of ordinals is a set so is its union, which violates regularity. Ok done. This is not worth starting a religion over. It doesn't mean anything as significant as what you're trying to read into it.
And non well-founded set theory is a thing, but an obscure thing. These two ideas are NOT at some opposite ends of a pendulum or related to one another at all. You are wrong about any important connection or insight here.
— fishfry
if Ω is the set of ordinals but Ω is also itself an ordinal, then this situation will result in Ω being a set that contains itself, and therefore, result in a set that is not well-founded. — alcontali
Yes, and ...?
There are no infinite downward chains of membership.
— fishfry
Yes, but that is exactly what would happen if Ω is the set of ordinals but Ω is also itself an ordinal. That is in my impression another reason why Ω cannot be termed a set but must be considered a proper class. — alcontali
Yes, that's what regularity prevents. Again, so what? I find myself frustrated. You're trying to convince me that something deep is going on, and there isn't. If your private intuitions help you, all the good. But you haven't written anything of interest; least of all with your materialize and complete terminology. ZF is not complete, you know, at least if it's consistent. You can't say the axiom of infinity completed it using your made-up definition, when it's NOT complete by everyone's standard definition. There's nothing complete about it. It just has more sets than PA because you added another axiom of set existence.
Here's another link that might be of interest, the
hereditarily finite sets. This is the class of objects that's described by PA and by ZF-infinity. It's perfectly "complete." It has all the sets and only those sets that it's supposed to as given by the rules of its construction.
To sum up, all I can see is that you're saying that PA is complete with respect to the axioms of PA, and ZF is complete with respect to the axioms of ZF, and ZFC is complete wrt the axioms of ZFC, and so forth. But then ZF is missing some choice functions so it is "incomplete" with respect to the axiom of choice. And ZFC is complete with respect to the axiom of infinity and the axiom of powersets and the axiom of union and the axiom of pairing, but not with respect to the Continuum hypothesis.
There's nothing of interest to this observation; and worse, it's bad terminology because it conflicts with the standard meaning of completeness in an axiomatic system.
This is what I got from your post.