[Math] Why and how is logic related to set theory

logicphilosophyproof-theorysoft-question

I am learning set theory on my own at the moment, and I realised I can't avoid not to learn logics. There is a strong connection between these two. such that, proofs for sets are based on logics.

I don't understand why and how these two fields are connected. For me, I reviewed them as separated fields. and from my past experience, one field is kind of self-contained, like axioms of Euclidean geometry are contained in geometry. axioms of real analysis are contained in real numbers.

With my limited knowledge about logic, It is based on statements, and a statement is either true or false. The rules of negations, contradictions etc completely make sense within the logic land!

However, in set theory. Objects are undefined, whatever objects which meet some conditions become sets. Sometimes we know what objects are, maybe even the exact and complete list of objects. Most of time we don’t.

Therefore, How can we apply logic rules to a set of undefined objects? (did I miss something very important here?)

Hence I am not convinced that 'if the rule is true in logic, then it is also true for sets'? for example, let A,B,C be sets, $if A \subseteq B, and B \subseteq C, then A \subseteq C$, due to Transitive Inference.

Many thanks!

Best Answer

There is a very close relation between a predicate $P(x)$ and the set $\{x: P(x)\}$ of all $x$ (in some universe) for which this predicate is true. The basic operations (not, and, or) of logic then correspond to the operations (complement, intersection, union) of set theory.

Related Solutions

Set Theory – Axioms of Set Theory and Logic

The usual approach is to define a concept of a first order language $\mathcal{L}$. They are usually specified by the nonlogical symbols. Well-formed formulas in the language $\mathfrak{L}$ are strings of symbols of $\mathfrak{L}$ along with the logical symbols such as $($, $)$, $\wedge$, $\neg$, variables etc. You can look up in a logic textbook the inductive definition of well-formed formulas, but something like $x \wedge y$ is a well-formed formula, but $(()\neg\wedge xy \neg$ is not a well-formed formula.

A first order theory $T$ in the language $\mathfrak{L}$ is then a collection of well-formed sentences (no free variable) in the language $\mathfrak{L}$. You would then define the deduce relation $T \vdash \varphi$ to mean that there exists a proof of $\varphi$ using $T$. A proof is just a string of of sentences $\phi_1, ..., \phi_n$ such that $\phi_n = \varphi$, each $\phi_i$ is in $T$, a logical axiom of first order logic, follows from modus ponen or generalization using previous $\phi_j$, where $j < i$.

So the above is the definition of a arbitrary first order theory in an arbitrary first order language $\mathfrak{L}$. Now let $\mathfrak{L} = \{\in\}$ a first order language consisting a single binary relation. $ZFC$ is then the first order theory in the language $\mathfrak{L}$ consisting of the "eight axioms" you mentioned above. (Note that ZFC has infinitely may axioms. For example, the axiom schema of specification is actually one axiom for each formula.)

The benefit of this approach where the general definition of first order logic is developed first is that you apply this to study first order logic in general and other first order theories such that the theory of groups, rings, vector space, random graphs, etc. Also first order logic is developed in the metatheory. That is for example, a theorem of ZFC (even if it is about infinite cardinals greater than $\aleph_1$) has a finite proof in the metatheory. However, within ZFC you can formalize first order logic. Then you can consider question about whether $ZFC$ can prove it own consistency.

By taking the approach of developing first order theories in general, you also gain a certain perspective. Some people think that ZFC is something special since it can serve as a foundation for much of mathematics. Through this approach, $ZFC$ is really just another first order theory in a very simple language consisting of a single non-logical symbol. People often have a hard time grasping the idea that $ZFC$ can have different models, for instance one where the continuum hypothesis holds and one where it does not. However, almost everyone would agree that that there exists more than one model of group theory (i.e. more than one group). Sometimes it is helpful to know that results about arbitrary first order theory still apply when one is working in ZFC set theory.

Why do we need/use proof theory

Your question makes sense to me, but it's a bit hard to answer concisely. The short answer is that for the most part, when mathematicians decide to accept anything as true, it is because it has been proven rigorously. And as you allude to, rigorous reasoning lends itself to an analysis where we convert the reasoning into a formal proof in some system (say PA, or ZFC). When you come up with a semantic proof for the truth of something by considering models (or truth tables for propositional logic), you are using reasoning that can be formalized in ZFC or in rare cases, some somewhat stronger system. In fact 'mathematically accepted fact' roughly correlates with 'has a proof formalizable in ZFC.' Thus, formal proofs are always there... it's really the only way we know to clearly establish mathematical truth.

Some of your thinking seems to stem from overgeneralizing from the example of propositional logic. Frankly, I'm a bit surprised your instinct was that formal proofs are the more convenient method here. A formal proof can be tedious to find, even in the case of propositional logic, especially if you're using an inconvenient Hilbert-style system. On the other hand, what could be easier than just plugging in some values to a truth table? (conceptually... computationally, the problem does not scale well).

However, this is an artifact of the fact that propositional logic is decidable. If we move on to first order logic, we're faced with difficulty: how do we decide if every $m\in M$ satisfies $\phi(m)$ for $M$ some structure and $\phi$ some formula of its language? We no longer necessarily have a decidible problem. The "brute force solution" would be checking $\phi(m)$ for every $m\in M,$ which cannot be done if $M$ is infinite (and who knows if $\phi(m)$ is decidible itself). It turns out that this basic difficulty is not surmountable in general, and Godel's theorem and the halting problem are ways of seeing this.

To show that a sentence is true in the structure $\mathbb N,$ we must have some way of proving things about $\mathbb N.$ Finding a proof formalizable in some system like PA or ZFC are the only accepted ways of doing so, although the incompleteness theorem tells us we can't decide every statement in some fixed system.

So what of these "true but unprovable" statements of Godel? How can we determine it's true if it isn't provable? Well, if we're considering the Godel sentence $G$ for PA, we haven't shown it isn't provable, only that it isn't provable in PA. The proof that the Godel sentence is true is done in a stronger system than PA. The basic argument is this: Recall that $G$ essentially says of itself that it is not provable in PA. Now, assuming PA only proves correct things (i.e. it is sound), we can see that it can't be provable in PA, and thus that it is true (since it says it is not provable in PA). It turns out the premise of soundness can be weakened to just consistency.

Godel's first theorem "if PA is consistent, then $G$ is not provable in PA" can be shown in a fairly weak system. The first step toward proving $G$ by the logic above is showing PA is consistent and a closer look reveals this must be the step at which PA fails (this is Godel's second theorem). However, you can prove PA is consistent in ZFC, and the easiest way to do this is to show that $\mathbb N$ is a model for PA. Then the rest of the reasoning falls into place, and proceed to prove $G$ is true. You believe this since your reasoning is formalizable in ZFC and you believe ZFC (or the fragment you used, anyway).

So semantics are not some black box that generates truths that you cannot get from formal proof. Philosophical worries notwithstanding, the truths are there, but there's no way to see what they are without proof. Instead, ZFC is a formal system that proves some things that you cannot prove in PA. And ZFC is also incomplete: in order to believe that its 'true but unprovable statements' (like its Godel sentence or Con(ZFC)) are in fact true, we need to believe assumptions beyond those made in ZFC.

Best Answer

Related Solutions

Set Theory – Axioms of Set Theory and Logic

Why do we need/use proof theory

Related Question