I Do you believe that continuum is Aleph-2, not Aleph-1?

[stevendaryl]

How many variables do you typically have?

If you're saying that you need to already have an informal notion of a collection in order to make sense of logic, that's probably true. But you certainly don't need any set theory. Set theory is a theory of sets. I wouldn't say that any time someone mentions a collection, they are using set theory.

 

[stevendaryl]

Indeed, it doesn't matter so much. However, in my point of view, I reject any use of infinite sets in Set1 including the axiom of choice which is a statement about infinite sets. I am prepared to accept potential infinity. If we do this, then we cannot develop the completeness theorem or Löwenheim-Skolem theorem in Log2 unless you already developed Set2.

The Lowenheim-Skolem theorem is a theorem ABOUT first-order logic. That doesn't mean that you need it to do first-order logic. Set theory is required to prove facts about the natural numbers, but children learn to use natural numbers before they learn set theory.

You do not need set theory in order to use first-order logic, even if set theory is used to study first-order logic.

 

[micromass]

If you're saying that you need to already have an informal notion of a collection in order to make sense of logic, that's probably true. But you certainly don't need any set theory. Set theory is a theory of sets. I wouldn't say that any time someone mentions a collection, they are using set theory.

In usual definitions of first order logic they set a countable collection of variables. Furthermore, there is an infinite collection of ZFC axioms. Countable and infinite do not make sense outside of an axiomatic set theory.

 

[micromass]

but children learn to use natural numbers before they learn set theory.

That is irrelevant. If you take the natural numbers as a priori knowledge that is god given, then so be it. But you need to be specific about it. In the same way, you need a set theory in order to define first order logic.

 

[micromass]

The Lowenheim-Skolem theorem is a theorem ABOUT first-order logic.

And uh, in what system are you proving things about first order logic?

 

[stevendaryl]

That is irrelevant.

No, it's not. It's clearly true that you don't need set theory in order to do arithmetic. You don't need set theory in order to do first-order logic. If it is possible to do X without knowing anything about Y, then I would say that X does not need Y.

In the same way, you need a set theory in order to define first order logic.

I would say "In the same way, you DON'T need set theory in order to define first order logic".

I certainly learned first-order logic before I learned set theory, and it was invented before set theory was invented, so what exactly do you mean by saying that you "need" set theory? I can teach someone how to do proofs in first-order logic without ever mentioning sets, so how, exactly, do I "need" set theory? I really don't understand what you're talking about.

 

[stevendaryl]

And uh, in what system are you proving things about first order logic?

That doesn't matter, but I assume it is in an informal system of first-order logic plus set theory. There is a distinction between doing first-order logic and proving things about first-order logic. Set theory typically is needed for the second, but not for the first.

 

[stevendaryl]

In usual definitions of first order logic they set a countable collection of variables. Furthermore, there is an infinite collection of ZFC axioms. Countable and infinite do not make sense outside of an axiomatic set theory.

Once again, you're confusing (1) proving things about first order logic with (2) using first order logic. You need set theory (or something similar) to do (1), but not (2). You can prove, using set theory, that there are an infinite number of axioms of ZFC. But that doesn't mean that you need set theory in order to say what the axioms of ZFC are. ZFC is specified using axiom schemas. That means that you give a pattern for an axiom, and any first-order logic sentence that matches that pattern is an axiom. You can certainly prove using set theory that there are infinitely many axioms matching the schema, but such a proof is not needed to do set theory.

 

[micromass]

No, it's not. It's clearly true that you don't need set theory in order to do arithmetic. You don't need set theory in order to do first-order logic. If it is possible to do X without knowing anything about Y, then I would say that X does not need Y.
I would say "In the same way, you DON'T need set theory in order to define first order logic".

I certainly learned first-order logic before I learned set theory, and it was invented before set theory was invented, so what exactly do you mean by saying that you "need" set theory? I can teach someone how to do proofs in first-order logic without ever mentioning sets, so how, exactly, do I "need" set theory? I really don't understand what you're talking about.

Why does it matter what you can teach? This is s a discussion on how to formalize mathematics, not on how to teach it. I can very easily teach calculus without limits, does that mean that it's not necessary.

 

[micromass]

Once again, you're confusing (1) proving things about first order logic with (2) using first order logic. You need set theory (or something similar) to do (1), but not (2). You can prove, using set theory, that there are an infinite number of axioms of ZFC. But that doesn't mean that you need set theory in order to say what the axioms of ZFC are. ZFC is specified using axiom schemas. That means that you give a pattern for an axiom, and any first-order logic sentence that matches that pattern is an axiom. You can certainly prove using set theory that there are infinitely many axioms matching the schema, but such a proof is not needed to do set theory.

I see you conveniently ignored the necessity of countably many variables.

And now you talk about axiom schema's. I thought you said first-order theories required axioms? What's an axiom schema then?

 

[micromass]

That doesn't matter, but I assume it is in an informal system of first-order logic plus set theory. There is a distinction between doing first-order logic and proving things about first-order logic. Set theory typically is needed for the second, but not for the first.

Well, it shouldn't be difficult for you to give a reference where first-order logic is done without mentioning infinity, countability or sets then?

 

[micromass]

That doesn't matter, but I assume it is in an informal system of first-order logic plus set theory. There is a distinction between doing first-order logic and proving things about first-order logic. Set theory typically is needed for the second, but not for the first.

An informal system? You are aware that there are theorems and proofs out there which say that "compactness theorem" is equivalent to "ultrafilter lemma" in ZF. Where are we proving this result? In your informal system?

 

[stevendaryl]

An informal system? You are aware that there are theorems and proofs out there which say that "compactness theorem" is equivalent to "ultrafilter lemma" in ZF. Where are we proving this result? In your informal system?

I would say yes, most mathematics is done using an informal system of set theory and first-order logic. It could be formalized within ZF, but that's a ton of work that most mathematicians wouldn't actually bother with.

But my point is that it is irrelevant what system you use to prove facts about ZF. There is a distinction between proving facts about ZF and proving theorems using ZF.

 

[stevendaryl]

Well, it shouldn't be difficult for you to give a reference where first-order logic is done without mentioning infinity, countability or sets then?

Are you saying that if an author mentions sets, then that proves that first-order logic requires sets? I doubt if anything written in mathematics or logic today would fail to mention sets, because the reader is most likely familiar with sets and using sets greatly clarifies material.

Anyway, I really don't know what you are talking about when you say that first order logic needs set theory. What does that claim mean to you?

 

[stevendaryl]

I see you conveniently ignored the necessity of countably many variables.

I wasn't ignoring that. You can specify what you mean by a variable without the notion of infinity. For example,

x is a variable
If V is a variable, then V' is a variable.

These two rules imply that we have variables x, x', x'', x''', etc. There are obviously infinitely many variables according to this specification, but you don't need to formalize the statement "There are infinitely many variables" in order to use variables.

What's an axiom schema then?

I thought I said what an axiom schema was. An axiom schema is a pattern such that an axiom is an instance of that pattern. For example, in the rules for propositional logic, there is an axiom schema for implies:

A implies (B implies A)

That isn't an axiom, but if you substitute sentences for A and B, then you get an axiom.

 

[micromass]

OK, I see you are completely missing my point. I'm not really all that interested in this discussion, so I'm leaving. If anybody wants more information on my point of view, they can read Paul Cohen's "Set Theory and the Continuum Hypothesis".

 

[Demystifier]

@stevendaryl , micromass is saying that in order to axiomatize logic, you first need some intuitive (informal, naive) understanding of sets. And I see nothing controversial about that.

 

[Demystifier]

but children learn to use natural numbers before they learn set theory.

To teach a kid to count 3 apples, you first need to convey the idea that those apples constitute a kind of single entity (that is, a set). That's why you teach the kid to count apples in a basket, or to count the fingers at the hand, but not to count apples and fingers together, because it's much harder for a kid to get the idea that fingers and apples may constitute a single entity. If you ask a 5 year old kid how many apples and fingers together do we have, it's very likely that you will confuse him. The confusion stems from the fact that the concept of set is needed for counting, and this particular set is too abstract for him to do the counting.

In fact, in the first grade of elementary school, they taught us sets before teaching us counting.

 

[stevendaryl]

To teach a kid to count 3 apples, you first need to convey the idea that those apples constitute a kind of single entity (that is, a set). That's why you teach the kid to count apples in a basket, or to count the fingers at the hand, but not to count apples and fingers together, because it's much harder for a kid to get the idea that fingers and apples may constitute a single entity. If you ask a 5 year old kid how many apples and fingers together do we have, it's very likely that you will confuse him. The confusion stems from the fact that the concept of set is needed for counting, and this particular set is too abstract for him to do the counting.

In fact, in the first grade of elementary school, they taught us sets before teaching us counting.

Well, I think there is a distinction between understanding and performance. You can learn to do arithmetic (or prove theorems in first-order logic) without knowing anything about sets. I think that micromass is right that understanding probably requires some kind of spiral approach, where you learn some topics in a superficial way, then use your superficial understanding of those topics to develop a deeper understanding of advanced topics, which can lead to a deeper understanding of the original topics. So you learn a little bit of arithmetic, a little bit of logic, a little bit about sets, and then use that knowledge to get a deeper understanding of arithmetic, logic and sets, rather than learning one completely and then going on to the others.

 

[tzimie]

I think naive logic is solid foundation contrary to naive set theory which is inconsistent. But even that inconsistency comes from the axiom of unrestricted comprehension, which is a "reflection" of boolean algebra into sets(so we can take any boolean predicate and form a set based on it). In some sense, naive logic is killing naive set theory, so logic comes first )