The Empty Set (or lack thereof)

[eriatarka]

I know this is off topic, but exactly which combination of premises make it so that you cannot have a universal set, IE a set for which every possible set is a subset?

Because if you call that set S then the power-set of S is also a possible set, and by definition must be a subset of S. But the power-set of any given set X has a strictly greater cardinality than X and hence cant be a subset, so you have a contradiction.

(This has nothing to do with the axiom of choice)

[punk]

For example, the universal quantifier ∀ has one formal referent, and it isn't exactly the same as how "all" is used in natural language.That would be an example of the problem. One approach that logicians follow is to create their own special meanings to ordinary language so that they deem that "just in case" and ≡ are interchangeable. This doesn't conform to ordinary language use, so consider the perfectly sensible statement "You should take an umbrella, just in case it rains". The statement "You should take an umbrella if and only if it rains" is ridiculous, this "if and only if" is not equivalent to "just in case". Your point about universal quantifiers and existentials is another example: in the real world, an all-proposition entails and existential one, but only in the real world. This is not unaddressable in formal logic, it just isn't a fundamental fact about the universal quantifier.

Yes, formally one typically takes Ex ('there exists') as a basic thing from which Ax ('for all') is defined by:

Ax := ~Ex~ ('it is not the case that there exists something such that not...').

Again this is going to come up if one wants the system to be Boolean.

[DavidOdden]

By the Law of Excluded Middle, the following is a true statement: "The lights in the hallway are either on or off." What if there are no lights in the hallway?

Under the standard formalization, the statement is false. The definite article asserts existence and uniqueness w.r.t. a set, and the existential part is false. An indefinite article similarly has an existential assertion, so if there is no light, the statement is false. The focus of the sentence seems to be the mutual-exclusiveness of on/off, but it carries a presupposition which coupled with your factual claim about no light makes the statement a contradiction (specifically, "The lights in the hallway are either on or off and there are no lights in the hallway" is a contradiction). You can avoid the contradiction by saying "If there are lights in the hallway they are are either on or off and there are no lights in the hallway", which is simply stupid, not contradictory.

[Jake]

The fact that no object in the universe satisfies the expression isn't a problem, the statement is still true by virtue of the fact that no object in the universe makes it false.

This assumes that the statement is falsifiable. If the statement is not anchored to reality, it is not falsifiable, and in the words of Wolfgang Pauli, it is "not even wrong."

...but now you have three truth values (true, false, vacuous) and you've dropped the law of Excluded Middle since vacuous expressions don't satisfy A v ~A.

It's not a third truth value, but an absence of a truth value.

This doesn't express the Law of the Excluded Middle. The Law of the Excluded Middle states that for any given property and any given object either the object has the property OR it doesn't have the property.

Exactly, any given statement either:

_1) has the property of relating to reality, its truth value is determinable, and it therefore also either:

__a. has the property of being true, or

__b. has the property of being false,

OR

_2) doesn't have the property of relating to reality, its truth value is indeterminable, and it doesn't have the property of being true or the property of being false.

As formally as I know how to type it:

D ≡ the property of being related to reality (or the property of truth determinability)

T ≡ the property of being true

F ≡ the property of being false

then for any statement x,

( Dx ( Tx Fx ) ) ( ¬Dx ¬Tx ¬Fx )

I agree that: Tx → ¬Fx and Fx → ¬Tx, which can just be stated as ¬( Tx Fx )

My point is that: ¬Tx ~→ Fx, and ¬Fx ~→ Tx, because ¬Dx → ¬Tx and ¬Dx → ¬Fx.

(My advance apologies for making up a "doesn't imply" symbol)

Like I said, I agree that there can be nothing between true and false. What I disagree with is the notion that every statement has a true/false property.

Aristotle's assertion that "...it will not be possible to be and not to be the same thing", which would be written in propositional logic as ¬ (P ∧ ¬P), is not the statement a modern logician would call the law of excluded middle (P ∨ ¬P). The former claims that no statement is both true and false; the latter requires that no statement is neither true nor false.

If this is the case, I deny the validity of the modern logician's Law of Excluded Middle.

To go back to something you said earlier: I've been thinking that A U Ø = A, not because Ø is a subset of A, but because when you "add nothing", you are really not adding any thing. U (or +) is a binary operator requiring two inputs. I don't know I'd go so far as to say that A U Ø is poorly constructed, but I'm planning on thinking about it more, and seeing where it takes me (i.e. what the mathematical results are).

[DavidOdden]

It's not a third truth value, but an absence of a truth value.

An obvious example of that kind would be: ≡Ax∀¬xD). Truth being the product of a consciousness grasping reality "true" is correspondence between reality and proposition, when a proposition has no relation to reality -- neither direct nor inverse -- then we usually say that the proposition is meaningless and has no interpertation of truth value, as in the above formula.

[eriatarka]

Under the standard formalization, the statement is false

There is no 'standard formalization'. Set theory doesnt deal with the translation of English statements into formal notation. I think youre confusing the formal mathematics of set theory with the philosophical program undertaken by people like Frege/Russell/Strawson which aimed at constructing a formal calculus for dealing with natural language statements. But even within this kind of analytic philosophy, there is no 'standard' way of dealing with statements like the one mentioned, and different people would deal with them differently. For instance, the Russellian approach of assigning a truth value to every proposition is different from Strawson's approach which refuses to assign truth values to statements which deal with non-existent objects (the classic example here is the statement "the king of France is bald", which Russell would claim is false, while Strawson would say it has no truth value).

But none of this is directly related to ZFC (or mathematical set theory in general), since this isnt intended to be a theory of natural language.

Edited August 14, 2008 by eriatarka

[Jake]

But none of this is directly related to ZFC (or mathematical set theory in general), since this isnt intended to be a theory of natural language.

I don't think any of us implied that about set theory. The issue, to me, is that set theory depends upon a certain kind of logic to 'prove' that the empty set is a subset of all sets. I have a problem with that kind of logic, namely, its artificial necessity for everything to have a truth value.

[eriatarka]

I don't think any of us implied that about set theory. The issue, to me, is that set theory depends upon a certain kind of logic to 'prove' that the empty set is a subset of all sets. I have a problem with that kind of logic, namely, its artificial necessity for everything to have a truth value.

Who said it was necessary for everything to have a truth value?

Within a formal system, all that matters is whether a certain statement (or its negation) is provable from the axioms of that system. And the choice of axioms isnt forced on us by reality, but is rather determined by pragmatic and aesthetic concerns. Its like asking why the product of two negative numbers has to be positive - theres no deep metaphysical reason why (-1) * (-1) has to equal 1, but we choose to define multiplication of negative numbers in this way because its desirable for the group of integers under multiplication to have certain properties, which wouldnt hold if we defined it to be anything else. Similarly, if you dont accept that the empty set is a subset of every set then certain properties of set unions fails to hold and your system starts to become ugly and needs more special cases, which can be avoided. (see punk's first post in this thread for an example of what I mean).

If you want a set theory where the empty set isnt the subset of every set then youre perfectly free to make one. The only question is whether itll be as elegant and easy to work with as ZFC.

Edited August 14, 2008 by eriatarka

[Seeker]

Similarly, if you dont accept that the empty set is a subset of every set then certain properties of set unions fails to hold and your system starts to become ugly and needs more special cases, which can be avoided.

I daresay that if the authors of textbooks on Discrete Mathematics would just admit this outright, instead of hiding behind the notion of vacuous proofs as their justification, then this entire conversation would have been unnecessary.

[eriatarka]

I daresay that if the authors of textbooks on Discrete Mathematics would just admit this outright, instead of hiding behind the notion of vacuous proofs as their justification, then this entire conversation would have been unnecessary.

But given the axioms of the system, the proofs are perfectly valid. Thats how axiom systems are often constructed - we start out with a set of properties which we want to hold, and then we choose a set of axioms which is strong enough to prove them, and 'weak' enough to not prove a lot of things which we dont want.

When we define set union, it seems intuitively obvious that if C = A u B, then both A and B should be subsets of C. And if you want this property to hold universally, then you need to accept that the empty set is a subset of every set, otherwise C = A u {} would be a counter-example.

Similarly, if you want it to be true that for all numbers x, x/x = 1 then this determines how you define the multiplication of negative numberes, since if you want x/x = 1 to hold universally then it must be the case that -1/-1 = 1, so that -1 * 1 = -1, and so on.

Edited August 14, 2008 by eriatarka

[DavidOdden]

There is no 'standard formalization'. Set theory doesnt deal with the translation of English statements into formal notation.

That is what formal semantics is all about. Your objection would be valid if I had said "using only concepts of set theory", but I didn't and I wouldn't have aven marginally had such a thought.

For instance, the Russellian approach of assigning a truth value to every proposition is different from Strawson's approach which refuses to assign truth values to statements which dealt with non-existent objects (the classic statement here is "the king of France is bald", which Russell would claim is false, while Strawson would say it has no truth value).

Do you think Strawson would attempt to express such a sentence in formal logic? I'm inclined to think he would rather poke out his eye. Any formalization of the definite article that I've heard of does attribute to it a non-conditional existential formalization. BTW I do think it's cognitively an error to put the apparent assertion of a sentence and the presuppositions on an equal footing, so it's not that I think that "the present king of France is bald" is the same as saying "George W. Bush is bald". They cash out to the same T-value, namely F.

But none of this has anything to do with ZFC (or mathematical set theory in general), since this isnt intended to be a theory of natural language.

No, but the ostensibly set-theoretic "proofs" are being carried out in natural language, not symbolic logic, so it is important to be clear on the point that for example ≡ is not the same as "just in case", or that natural language "all" is not the same as ∀.

[Hodge'sPodges]

I find vacuous "truths" to be incompatible with Objectivism.

One might or might not find the principle of vacuous truth to be incompatible with Objectivism, but it is a principle used in mathematics. And as you are interested in set theory, you will find argument by the principle of vacuous truth to be common.

One may object (on whatever different grounds) to the following, but this does happen to be the way what is called 'classical mathematics' works:

The principle of vacuous truth stems from the interpretation of the '->' symbol for what is called 'material implication'. The deductive system of the classical first order predicate calculus (taken to be the presumed deductive system for classical mathematics) is designed to fit that interpretation of '->'.

Specifically, the interepretation of material implication is:

For any formulas (by which I mean well formed formulas) P and Q:

If P is true and Q is false, then P -> Q is true.

If P is true and Q is false, then P -> Q is false.

If P is false and Q is true, then P -> Q is true.

If P is false and Q is false, then P -> Q is true.

So the principle of vacuous truth applies where P is false. The principle of vacuous truth is that if P is false then P -> Q is true.

One may object to that principle on grounds of Objectivism or other grounds, but it does happen to be the way classical mathematics works.

One explanation (which you may or may not accept) for the principle is this:

By saying "If P then Q", we are saying it is not the case that P is true while Q is false. So the NEGATION of P -> Q should be equivalent to P & ~Q (that reads, "P is true and Q is false"). But the table for P & ~Q is:

If P is true and Q is true, then P & ~Q is false.

If P is true and Q is false, then P & ~Q is true.

If P is false and Q is true, then P & ~Q is false.

If P is fasle and Q is false, then P & ~Q is false.

And that should make sense to one, given the meanings of '&' as "and" and of '~' as "not".

But the above is as the NEGATION of P -> Q, so the table for P -> Q gives the opposite result from the above table. The result is the table I first mentioned:

If P is true and Q is false, then P -> Q is true.

If P is true and Q is false, then P -> Q is false.

If P is false and Q is true, then P -> Q is true.

If P is false and Q is false, then P -> Q is true.

Thus, if P is false, then P -> Q is true, irrespective of whether Q is true or false.

And that is the principle of vacuous truth.

Now, moving to the empty set.

I'll use 'A' to stand for "for all", 'E' to stand for "there exists at least one", 'E!' to stand for "there exists exactly one", '<-> to stand for "if and only if", and 'e' to stand for "is a member of".

First, either by axiom or by theoremhood (depending on the exact formulation of the set theory), we have:

E!xAy ~yex

That is, "There exists a unique object that has no members."

And since, in set theory, all objects are sets, we have:

There exists a unique set that has no members.

That permits a definition:

Ax(x=0 <-> Ay ~yex)

That is, "For all x, x equals the empty set iff for all y, we have y not a member of x).

Or, more casually put:

0 is the set that has no members.

Now, subset is defined:

Axy(x subset of y <-> Az(zex -> zey))

That is, "For all x and for all y, we have x is a subset of y iff for all z, if z is a member of x then z is a member of y".

Or, more casually put ('iff' stands for 'if and only if'):

x is a subset of y iff every member of x is a member of y.

Now, to prove that the empty set is a subset of every set (any arbitrary y):

0 subset of y <-> Az(ze0 -> zey) ... from the definition of 'subset of'.

But for any z, we have ze0 -> zey, since we have ~ze0 from the definition of '0'.

So we have 0 subset of y.

Again, one may object to this on various grounds, but it is basic classical mathematics, and since classical mathematics is about 95% of advanced mathematics you'll encounter, we might as well say it is basic mathematics (and, by the way, vacuous reasoning works for intuitionistic mathematics also, except the truth table explanation is not available since intuitionistic logic cannot be formulated in truth tables, so the explanation in intutionistic logic is somewhat more complicated.)

[DavidOdden]

Within a formal system, all that matters is whether a certain statement (or its negation) is provable....

Here's a good starting point. Define "statement".

[eriatarka]

Here's a good starting point. Define "statement".

In this context, a statement is any combination of symbols which is consistent with the syntax of the formal system youre working in. In general though, I'd say that a statement/proposition is a sentence which admits a truth value (which is what distinguishes statements from questions, commands, etc).

BTW I do think it's cognitively an error to put the apparent assertion of a sentence and the presuppositions on an equal footing, so it's not that I think that "the present king of France is bald" is the same as saying "George W. Bush is bald". They cash out to the same T-value, namely F.

I think the more important question is: what hinges on this? If you want to say that "The king of France is bald" is false, whereas I say its indeterminate, then what practical difference does this make to anything? To me, it seems like a purely methodological point and it makes no difference whatsoever which one you go with, as long as youre consistent.

[Hodge'sPodges]

The words "every element" assume there is at least one element.

You have to be careful to distinguish the exact context of the word 'every'. And in all my remarks I'm taking the context of ordinary mathematics.

In Ax(Px -> Qx) ("Every x that has property P has property Q"), it is not the case that we can infer ExPx ("there exists an x such that x has property P).

However, from just plain AxPx, we can infer ExPx. For that matter, from Ax(Px -> Qz) we can infer Ex(Px -> Qx), which is just equivalent to Ex~(Px & ~Qx), which is equivalent to Ex(~Px or Qx), which you can see does not entail that there is an x such that Px.

If true means a non-contradictory relation to reality, and false means a contradictory relation to reality, then something which is not related to reality would be neither true nor false (it would arbitrary or maybe incorrectly constructed).

In classical mathematics, the truth values 'true' and 'false' apply, per an interpretation of the language, to any SENTENCE of the language. If a string of symbols is not a sentence, then neither 'true' nor 'false' is given as a value for that string. Formulas that are well formed but not sentences are given a value of 'satisfied' or 'not satisfied' by an interpretation and an assignment for the variables. And strings that aren't even formulas (by which I mean well formed formulas) are not given any value of this kind at all.

"A set P is a subset of Q if no element of P is an element not of Q"

That is equivalent with the ordinary definition of 'subset of'.

P subset of Q <-> ~Ex(xeP & ~xeQ) is equivalent to the ordinary definition:

P subset of Q <-> Ax(xeP -> xeQ)

And this does not alter that for any set Q, we have 0 subset of Q.

Edited August 14, 2008 by Hodge'sPodges

[eriatarka]

.

I think the main problem here is that we are coming at this from different backgrounds, with different concerns. I'm primarilly interested in mathematics (and I assume this applies to punk also), so I tend to see set theory as being purely a language for descrbing mathematical objects/proofs, and I judge it solely on that. However I understand that youre a linguist and I know that formal systems play a different role there. I'm not sure what your standpoint is, but I personally think the idea of applying formal logic to natural language semantics has been a horrible mistake from Frege/Russell right down to its more modern incarnations, and have very little time for any of it (I have no opinion on the Chomskian approach to use formal systems to study syntax/gramm rather than semantics though).

But anyway, because I have no interest in the application of set theory to natural language semantics (since I think the whole project is misguided and couldnt possibly tell us anything useful), I tend to think that all questions regarding set theory should be decided purely on their usefulness to mathematical practice. Asking 'should the empty set be a subset of all sets?' is like asking 'would it be nice if all the verbs in a human language were regular?' - theres no absolute truth here, all that matters are the pragmatic issues. Regular verbs are a nice thing and if I were designing an artificial language from scratch then I would make it very regular, Esperanto-style. And similarly, having operations like set union obey simple properties (while minimising the number of pathological cases) is highly desirable so its a good idea to treat the empty set as being a subset of every set.

This doesnt mean that theres some kind of metaphysically existing 'empty set' living in a Platonic netherworld which we are proving things about, and it isnt intended to be a statement which has direct application to reality. When we decide that the empty set is a subset of all sets, we arent learning anything new about what happens inside empty desk drawers. To put it in more Objectivist terms, what we're dealing with here are concepts of method.

Edited August 14, 2008 by eriatarka

[Hodge'sPodges]

My Artificial Intelligence textbook suggests that "P=>Q" makes sense (i.e. relates to reality) if you think of it as saying, "if P is true then I am claiming that Q is true. Otherwise I am making no claim."

That is not at all material implication ('material implication' more commonly known as 'conditional statement') ordinarily used by mathematicians and logicians. A conditional statement still makes an assertion when its antecedent (in this case 'P') is false. Edited August 14, 2008 by Hodge'sPodges

[Hodge'sPodges]

I mostly agree with Pokarrin that there's a problem with the definition of subset and that the change suggested is much better

The change he suggested is equivalent to the ordinary definition.

If P is a subset of Q then this implies that there is a concretely identifiable commonality between the two sets that goes beyond the fact that P contains at least some of what Q does.

(1) The definition of 'P subset of Q' does not require that P have some of what Q has. (2) You may have philosophical reasons for opposing the ordinary definition of 'subset', but we should at least be clear that the actual definition used in mathematics is as has been stated:

P is a subset of Q iff every member of P is a member of Q

and that is in a context in mathematics in which 'every' does not entail that P has members.

Edited August 14, 2008 by Hodge'sPodges

[Hodge'sPodges]

There are many flaws is that talk-argument about subsets and empty sets, but it may be an inept way of conveying a formal symbolical derivation. Since IMO the root of the problem (if not the root of all evil) is the concept "set",

The concept of 'set' doesn't even have to enter in, since the principle of vacuous truth is at work even for theories that are not set theories. Vacuous truth comes from the interpretation (and thus the corresponding logiccal calculus) for the '->' symbol as representing material implication: P -> Q false iff P true and Q false.

mathspeak, a universally quantified proposition doesn't entail an existential, so Ax P(x) does not entail Ex P(x).

That is incorrect. For any formula F, we have the theorem AxF -> ExF.

[eriatarka]

That is incorrect. For any formula F, we have the theorem AxF -> ExF.

No, generally we have the theorem ∀x(Fx) -> ~∃x(~Fx) ('there is no x for which Fx fails to hold'), which doesnt imply ∃x(Fx) ('there exists an x such that Fx holds'). If what you were saying were true, then the empty set wouldnt be a subset of every set if we were using the normal definition of subset (that A is a subset of B iff every element of A is an element of .

But of course, theres nothing stopping you making a logic in which ∀x(Fx) -> ∃x(Fx), it would just have different properties from standard predicate calculus.

Edited August 14, 2008 by eriatarka

[Jake]

I forgot that mathematicians are not necessarily trying to describe reality in their pursuits, but I'll have to admit I'm a bit disappointed by that. That's probably part of the reason I left Math for Engineering, that and the fact that I got to build a rocket...

There are some questions I still have:

Why is it important that if C = A u B, that A and B should be subsets of C?

Why isn't it important that they both be proper subsets of C?

What useful higher-level aspects of set theory are lost if {} isn't a subset of every set? Does the theory become inconsistent?

Thanks for all of the replies thus far.

[eriatarka]

I forgot that mathematicians are not necessarily trying to describe reality in their pursuits, but I'll have to admit I'm a bit disappointed by that.

Whether this is true or not (and its not as simple as you imply, since many would disagree [including me]), its not directly relevant to set theory. Set theory is a language for describing mathematics. Whether mathematics describes reality is a separate question.

I think that the relationship of set theory to mathematics is similar to the relationship that a written language has with its spoken equivalent. But many mathemaicians (and even more logicians) would probably disagree with this.

Edited August 14, 2008 by eriatarka

[DavidOdden]

In this context, a statement is any combination of symbols which is consistent with the syntax of the formal system youre working in.

Alright; now, that virtually smacks of the notion "well-formed formula". Here is a question: is the combination (AףD) consistent with the syntax of the system? (This could be a problem if your computer is uncooperative w.r.t. the thing between A and D). The answer is, it depends on whether it is a defined symbol in the system, and follows the rules of combination. Now, here is the connection between existence and syntax. For a symbol to be defined, it must have a referent (take it or leave it); if a symbol is undefined, a formula using it is not well-defined and not well-formed, thus violates the syntax of the system.

Therefore, all statements have a truth value.

In general though, I'd say that a statement/proposition is a sentence which admits a truth value (which is what distinguishes statements from questions, commands, etc).

Maybe we also need to clear up the distinction between true and T. You are aware that they are not the same, I hope. T is a formal relational symbol, true is a particular correspondence between mind and fact.

If you want to say that "The king of France is bald" is false, whereas I say its indeterminate, then what practical difference does this make to anything?

First, one of us has to be wrong, because there is only one reality and it is non-contradictory. Second, words have meaning and are not just pointless emotional grunts that we utter in the hopes of a handout from the state. Third, man is not born with full awareness of the nature of the world or of the proper method of acquiring such knowledge -- he must discover those means. There are a number of other important things I could mention, but these are the three main reasons why I maintain that it really does matter.

To me, it seems like a purely methodological point and it makes no difference whatsoever which one you go with, as long as youre consistent.

Do you want me to bitch-slap you for devaluing proper methods of reasoning? It's what I do.

[Hodge'sPodges]

Do you know if there are any set theories that avoid this? I definitely have a problem with considering a collection of nothing to actually be a collection.

There might be such a set theory without an empty set, but it is not common to find. If the notion of a collection containing nothing is not acceptable to you, then (I'm being serious, not facetious) you can think of all occurrences of the words 'collection' and 'set' to be crossed out and replaced by 'object'. Then consider that the primitive of set theory is 'is a member of'. So set theory talks about objects in terms of their membership or lack of membership in one another. Then consider the empty "set" as an object that has no members. Whether it needs to be called a "set" or "collection" is not very crucial to the role of set theory in mathematics.

[DavidOdden]

For any formula F, we have the theorem AxF -> ExF.

News to me. Can you reproduce the proof or at least direct me to where it was published? It's an accurate description of the meaning of "all", but not the properties definitionally attributed to ∀.