Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The logical operations $\Rightarrow$ and $\Leftrightarrow$ correspond to relations on sets. What are these two relations? Is there anything in logic that could not be expressed in terms of set theory and vice versa?

share|improve this question

2 Answers 2

To say that $P(x)\Rightarrow Q(x)$ is to say that if $x$ satisfies property $P$ then it satisfies property $Q$.

One can see this as $x\in P\Rightarrow x\in Q$, or in a compact notation: $P\subseteq Q$.

From this you can infer that $P\Leftrightarrow Q$ corresponds to $P\subseteq Q\land Q\subseteq P$, which essentially to say $P=Q$.


Similarly, if we think of $P(x)$ as $x\in P$, we have that $P(x)\land Q(x)$ is the same as to say $x\in P$ and $x\in Q$, or $x\in P\cap Q$; the $\lor$ corresponds the same way with $P\cup Q$; and lastly $\lnot P(x)$ is to say that $x\notin P$.

share|improve this answer
    
"$P\cap Q$" and "$P\cup Q$" are sets, but "$x\not\in P$", "$P\subseteq Q$", and "$P=Q$" are logical formulas, so in the last three cases you haven't actually expressed the original formula as a set, just as a different formula. –  Henning Makholm Dec 16 '11 at 13:28

I will make a short story.... very long. I hope you will find it interesting/illuminating, but if you cannot really bear it, jump right to the last few lines for a summary.

I think one should have clear in mind the distinction between logic and ...anything else. Logic comes first. Logic is the science of reasoning and as such it can be applied to anything that requires reasoning. Set theory and mathematics (which is based on set theory) are just sample applications. You (can/should) use logic in physics, law, politics, biology, criminal investigations, love matters, ect We can say: mathematics is the language of nature, but logic is the language of mathematics therefore - not surprisingly - logic is the language of nature. It may also be used as the language of imagination (as in model theory, in a sense). To create a logical theory of something, just decide what are your axioms and anything else will follow "logically". The problem consists in creating the axioms for a specific application. Unfortunately in the world education systems logic is taught after law, biology, mathematics,...if ever, under the assumption that people can instinctively reason clearly and correctly. This is often true...and often not. Now, "set theory". There are several set theories, some are even incompatible with each other. The first was even inconsistent (naive set theory), that is, it led to contradictory statements. How do all these theories look like? well, nothing special in a sense: they are just a bunch of axioms with variables x,y,z... They differ from one another in the specific bunch of axioms. (Notice that I avoid saying "set" of axioms). You can see ZFC or NBG or Grothendieck-Tarski set theories formally described in Wikipedia. Nowhere it is written that the variables are called "sets". You just call them that way for lack of a better term. Actually in NBG they are supposedly called classes. You look at these axioms and see ⇒ and ⇔ and affirm that they "correspond" to relations on sets. That is not really correct. All you can/should say is that the particular set theory that you are looking at uses the logical connectives ⇒ and ⇔ in its axioms. But that is hardly surprising is it? It also uses "and" and "or" connectives for that matter. So what? Set theories are logical theories so they use logical connectives such as ⇒ and ⇔ and quantifiers. That's all. Now we come to your question. Is there something in logic which is not a set? Of course! Some examples: Take ZFC as your set theory and ask the theory if the collection of sets equal to themselves exists. More specifically: does an y exists such that all members x of y satisfy the relation x=x ? Well, following logic rules from the axioms, the answer is no. So here we have an example of relation (x=x) which does not "correspond" to a "set". Ok, we can change set theory to suit our needs. Take NBG theory. Here the y exists and it is modestly called "the universe" U. It is a class, a proper class. So NBG allows "bigger" collections of things than NFC and you may feel that NBG is all you need, but wait. Consider the collection made of just one element U. That is {U}. Simple collection apparently. Just one thing inside. Yet this collection does not exists in NBG! That’s because U is a proper class, which means it cannot be a member af another class. So the collection {U} cannot be a class. Ok, we can change set theory again to suit our needs. We use Grothendieck-Tarski (GT) theory. Now we can talk of many universes and collections of universes. The nice thing is that now everything is a "set" in some universe. it is a little bit like saying :"you can be anything you want in your imaginary parallel universe". Now it seems at last that GT has a set for everything you might consider in logic, but wait...read the small print on the label: "Only works with pure sets". Pure sets are sets built on…the empty set. Oh dear! After all this chat you discover that all “sets and classes and…” described in these grand theories are just built on …nothing really. The empty set. This miracle of imagination. Much ado about nothing. The only constant symbol present in any set theory is the empty set. So , for example elementary particles do not exist even in GT (even if you define an elementary particle as a quantum field, you need to add the axioms of quantum field theory to “recover” the elementary particle). GT alone is not enough to describe everyday things like electrons or people. So you take a relation or a predicate in logic – for example Human(x) (meaning x is a human) and you think it describes a collection of all objects which are humans and ask yourself: is this a set in GT? The answer is no, because it is a collection of objects (people) which are not sets, so it cannot be a set. All you can say is that relations or predicate in logic describe “collections” (All x such that….) but that these collections in general do not follow the axioms of any “set theory”. We may further say that GT and friends describe the axioms of collections of the membership relation which is thereby defined. These collections are called “sets” or “classes” and are built out of just one constant called “the empty set”.

To summarize: Logic is the science of reasoning and is used everywhere reason is used. You create axioms, put them together in theories and deduce some conclusions from them. You can create collections in logic (All x such that….). These collections should not in general be called anything else than “collections”. This is because there are certain theories called “ xyz set theory” which have given the word “set” a specific technical meaning, so they have “robbed” us of the term “set”. These theories describe very special collections ultimately made of just one collection which has no members.

share|improve this answer
    
What the heck does this have to with anything let alone this answer?? –  Asaf Karagila Dec 17 '11 at 15:35
    
Also, what about ZFA which allows the existence of non-set objects? How are these objects "collections made of the empty set"? How is the collection of those object is a collection "made of just one collection which has no members"? What about infinitary logic? –  Asaf Karagila Dec 17 '11 at 15:38
    
it has to do with the question. The OP asked if there are anything in logic that cannot be expressed as sets. It is a broad question with a broad answer, to be intelligible –  magma Dec 17 '11 at 15:51
    
@asaf there are set theories that use urelementen (that is non sets). But this is beside the question of the OP. What i wanted to stress is that "set" has nowadays a technical meaning. A "set" is supposed to obey to some axiomatic set theory. But in general logic you may have collections that do not obey any (well-known) set theory. Or if it satisfies one theory, it may not satisfy another one. –  magma Dec 17 '11 at 15:58
    
So is your entire speech. –  Asaf Karagila Dec 17 '11 at 16:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.