The Empty Set (or lack thereof)

[Jake]

I picked up Introductory Discrete Mathematics by V.K. Balakrishnan this week, because I'm interested in Set Theory. I was surprised to read that the empty set (Ø) is purportedly a subset of every set. The book's logic goes like this:

A set P is a subset of Q if every element of P is an element of Q.

...

A set is empty if it has no elements.

...

The fact that the empty set is a subset of any set is established by "vacuous reasoning": If it were not a subset of a given set S, there should be at least one element in the empty set which is not in S.

I wiki'ed set theory, empty set, and vacuous truth. I have found nothing that disagrees with this logic. I don't think the empty set strictly matches the definition of subset. The words "every element" assume there is at least one element. Furthermore, I find vacuous "truths" to be incompatible with Objectivism. As far as I can tell, the essence of vacuous truths lies in binary logic. The argument is that every statement must be true or false, but this omits the "not even wrong" case. 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).

Here's the subset definition reworded: A set P is a subset of Q if every x in P is also in Q.

I believe it's wrong to say any statement "every x in P is ..." is true (or false), if there are no x in P on which to test the statement (i.e. P = Ø).

One of the pages I found used the following example of a vacuous truth: "All seven-legged alligators are pink." This statement is meaningless, unless there are seven-legged alligators running around somewhere. (If so, then the statement could be determined to be true or false). The contradiction is quickly apparent if you also state that "All seven-legged alligators are blue."

If you have anything valuable to add to my thoughts on the empty set (or vacuous truths), it'd be much appreciated.

[Pokarrin]

I fall more into the category of inclined than adept, but I'll take a stab at this. Could it be that the book's logic was simply badly stated? What if it were changed to the following:

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

It's kind of a subtle difference, and I think it boils down to the purpose of the empty set. Does it later become important, in order to maintain logical consistency, for the empty set to be included in every other set (perhaps in relating Set Theory to classical mathematics)? It's been awhile since I took calculus, but I vaguely remember that every power of your variables held a place, even if the coefficient was 0 (or an empty set of that power of the variable).

[Seeker]

If I have anything valuable to add, then you have discovered the mathematical root of humor. Ha-ha.

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." Thus, since there are no seven-legged alligators, I am making no claim about them all being pink. And, since no element belongs to an empty set, I am making no claim about all of its elements belonging to every set. Yet, that is what my Discrete Mathematics textbook (like yours) essentially does. So in the end I agree, but perhaps this is a matter best left to the mathematicians.

Edited August 13, 2008 by Seeker

[John McVey]

I don't think the empty set strictly matches the definition of subset. The words "every element" assume there is at least one element.

I mostly agree with Pokarrin that there's a problem with the definition of subset and that the change suggested is much better, though I think there's more that needs the attention of a rational expert before settling on that definition. What I do strongly believe, however, is that Balakrishnan's "vacuous reasoning" is blatant context-dropping.

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. It is not just that P must have at least one element, but that element must be chosen for a particular reason or serve some analytical purpose that the superset was also capable of serving: there is the question of how P came to be so constituted as well as what P contains to consider (ditto for Q). Without this attention to the how there is no foundation to give any meaning to an empty set when it arises. Consider the statement "I don't have any candy in my pocket." The reaction that this statement would get is entirely dependent on context: if the context is clear from the situation at hand (eg a boy walked up to his mother and said it) then the reaction will be understandable, whereas if it is said out of the blue (eg if I said it to the maintenance supervisor at work) the reaction is apt to be strange. Context provides meaning to a negative statement. For that reason, I wouldn't dismiss Balakrishnan's "vacuous reasoning" merely because it raises the concept of the empty set as I have heard of being done elsewhere.

Under normal circumstances I'd agree with the charge of 'reification of the zero' in relation to things like this, but on a related note I know of three particular cases of equations with division by zero or infinity are not automatically nonsensical. There is a thing called L'hopital's Rule (is this what you have in mind, Pokarrin?). This rule says that when one has an equation that works out under some circumstance to be zero divided by zero, zero multiplied by infinity, or infinity multiplied by infinity, there could be (though there might still not be) a meaningful answer when the equation elements giving the zeroes or infinities are taken to their first derivatives under the use of limits and then divided or multiplied. Whether a comparable methodology might exist in the use of sets I am not knowledgeable enough to say, but, a), it gives at least one line of inquiry to pursue (consider the possibility that some answer is dependent on the number of instances of set P that are in set Q, where the two sets' contents are variable - one could potentially have a case in a relation of set P to set Q where set P turns out to be the empty set under certain conditions and so Q has an infinite number of instances of P in it), and b ), places emphasis on the context in which any particular instance of the empty set arises if there is to be any basis for meaningfulness.

If reasoning along those lines is fruitful then one can say, in some well-defined circumstances, that the empty set turns out to be a subset of another set, and thence to make a definite inference from this conclusion. If that is the case, then Pokarrin's definition is too restrictive and what is required is a qualification of some kind of Balakrishnan's. If not, well, what Seeker said.

I think it boils down to the purpose of the empty set.

I'd say so, too.

I find vacuous "truths" to be incompatible with Objectivism. As far as I can tell, the essence of vacuous truths lies in binary logic. The argument is that every statement must be true or false, but this omits the "not even wrong" case. 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).

Vacuous, meaning empty like a vacuum, lacking meaningful content. I am no expert in epistemology, but off the top of my head the notion of "vacuously true" sounds like the analytic side of the analytic-synthetic dichotomy - rationalistic deduction devoid of any connection to observation from which to obtain premises to deduce with.

JJM

Edited August 13, 2008 by John McVey

[DavidOdden]

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", I don't know that there is a sensible way to solve the problem. Now a bit of commentary.

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

That would be ordinary language usage, which is derived from how quantifiers relate to concepts. In mathspeak, a universally quantified proposition doesn't entail an existential, so ∀x P(x) does not entail ∃x P(x).

Starting with the definition "A set P is a subset of Q if every element of P is an element of Q," say that Q is {1,2,4,5,6} and P is {1,4}. Every element (1,4) which is in P is also in Q. The definition doesn't say that P must be an element of Q (which would be so if Q were {1,2,4,5,6,{1,4}}). By further definition, "A set is empty if it has no elements". Thus {} is_def the empty set. To belabor the obvious, we can conclude that for all x, it is not the case that there exists an element x such that x is an element of the set.

Since subset is defined in terms of the elements of one set being in another set, and since Ø is not an element, then Ø is also not an element of a set P (for any set P). Remember also that subset is defined in terms of the presence of the elements of a set, so we're looking for the non-element >< (the thing between the arrows) in {....}. We are not looking for {}, just as we are looking for 1, 2 and not {1}, {2}.

Thus you find the reification of nonexistence to be a fundamental requirement of this proof that the empty set is part of every set, and this is part of the reified set notion of set which leads to completely arbitrary sets, where {1} is different from 1 and {{1}} etc. where sets simply "are", and don't have anything in common.

[Jake]

Thus you find the reification of nonexistence to be a fundamental requirement of this proof that the empty set is part of every set, and this is part of the reified set notion of set which leads to completely arbitrary sets, where {1} is different from 1 and {{1}} etc. where sets simply "are", and don't have anything in common.

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.

[DavidOdden]

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.

I have the idea that there is a divide, at least historically, between people who thought of sets as arbitrary collections, versus those who thought of them as being a natural kind, thus I think Cantor was inclined towards the intensional, "well-defined" view of sets. I think the root problem is the current impossibility of an ideal, natural descriptive calculus whereby the set of dogs are well-defined.

[Capitalism Forever]

I find vacuous "truths" to be incompatible with Objectivism. As far as I can tell, the essence of vacuous truths lies in binary logic. The argument is that every statement must be true or false, but this omits the "not even wrong" case. 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).

Your last sentence is correct; however, the important thing to realize is that if a statement IS related to reality (i.e. it does meaningfully propose that a certain fact is part of reality) then it IS either true or false. This is what the Law of the Excluded Middle states.

If the concept "subset" were restricted to non-empty sets, then the statement "{} is a subset of {1,2,3}" would be meaningless (because an invalid application of the word "subset") and therefore neither true nor false. But mathematicians have seen no reason to restrict the use of the word "subset" in this way--and indeed, why should they?--so the sentence "{} is a subset of {1,2,3}" is valid and meaningful, and the Law of the Excluded Middle does apply to it. The fact of reality it proposes is a certain relationship between {} and {1,2,3}. The relationship proposed can be reduced to concretes as follows: you can go from the "{" to the "}" of the left-hand set so that, whenever you encounter a number, you will also find that number in the right-hand set. Can you do that? Yes, you can; you will never encounter a number, so the second clause will never actually be invoked--but it is still a perfectly meaningful clause, just like the "self-defense" in "I have a gun for self-defense" is meaningful even if you never actually end up needing to use the gun. So the proposition is true, and we may further explain why it is true by pointing out that the "whenever" never happened, so there was nothing to prevent us from getting from the "{" to the "}"--which is what the phrase vacuously true refers to.

As another example, think of a railroad that advertises itself as giving all passengers under 21 a discount. Now suppose that on August 12, 2008 the railroad happened to have no passengers under 21. Does that mean that its advertisement was meaningless on that day? After all, "all our passengers under 21" had no referents in reality. But I think all rational linguists, logicians, legal experts, railroad managers, and passengers will agree that the statement was meaningful--and also true.

[Capitalism Forever]

whereby the set of dogs are well-defined.

Now that is meaningless, strictly speaking, although the mind of the experienced reader will nearly automatically make the required substitution of "is" for "are" !

[punk]

You need to say the empty set is a subset of every set for consistency's sake.

Now given two sets A,B take the union and call it C = A u B, so A is a subset of C and B is a subset of C.

Let's use 0 for the empty set then C = A u 0 and A is a subset of C and 0 is a subset of C.

But in this case C = A (as C and A have exactly the same elements), so A = A u 0.

So the empty set must be a subset of A.

[DavidOdden]

Now given two sets A,B take the union and call it C = A u B, so A is a subset of C and B is a subset of C.

Here's a more formal way of saying that: the union C is the set which contains all elements that are in A and all elements that are in B. Since Ø is not an element, it is not in A or B, so it is not in C either. Thus for any set C which is the union of two sets A, B, the empty set is not in C.

Let's use 0 for the empty set then C = A u 0 and A is a subset of C and 0 is a subset of C.

Except that since 0 i.e. {} has no elements, and since C is all of the elements of the two component sets, then C does not contain Ø.

I think you've given us a nice example of why people rightly mistrust informal "formal" proofs, i.e. derivations that do not procede by listing the axioms and giving a symbol-replacive axiomatic proof (as one finds in Kleene's textbook).

[punk]

Here's a more formal way of saying that: the union C is the set which contains all elements that are in A and all elements that are in B. Since Ø is not an element, it is not in A or B, so it is not in C either. Thus for any set C which is the union of two sets A, B, the empty set is not in C.Except that since 0 i.e. {} has no elements, and since C is all of the elements of the two component sets, then C does not contain Ø.

On the contrary, I said what I said. That if you want to say that adding the empty set to a given set and get the original set back then you have to say that the empty set is a subset of the original set. Otherwise you will have a contradiction.

I think you've given us a nice example of why people rightly mistrust informal "formal" proofs, i.e. derivations that do not procede by listing the axioms and giving a symbol-replacive axiomatic proof (as one finds in Kleene's textbook).

I think you have given us a nice example of why people who don't understand what formal proofs are trying to achieve for the system taken as whole mistrust what they fail to understand.

The point is to make sure that the entire system is consistent.

The whole notion of the "empty set" is something that only makes sense within a formal system, and it only has meaning by virtue of that system.

The fact is if you want to have a consistent system which also says that the union of any set with the empty set is the original set itself you are also going to have to say that the empty set is the subset of any set.

Either one is going to imply the other.

If you want to say that 0 is not a subset of any other set, then you have to say that A u 0 = A1 which is distinct from A, which goes against the entire notion of the empty set. If you say this you are saying that adding nothing to a given set somehow generates some member which isn't nothing.

What you are proposing will lead to contradictions within the system.

The fact is the statement that every set has the empty set as a subset is effectively a dual to the statement that the union of any set with the empty set yields the original set.

...

Anyway this is all necessary if you want to work in some Boolean topos like Set (i.e. set theory). If you don't like it, you can always move to some non-Boolean topos that makes you happier, of course then you'll have to work with Heyting Algebras and Intuitionist logic.

This will mean dropping the Law of the Excluded Middle though.

Edited August 13, 2008 by punk

[DavidOdden]

On the contrary, I said what I said.

I know you said what you said, but what you said is false, as I showed. As a starting point, are you aware that {1,2,3} is not the same as {1,2,{3}}?

If you would give us a formal proof of your claim, we could check it for errors. Otherwise, I don't know how we can help you. There is no formal proof of the claim that the empty set is in every set (or whatever one might think the claim is) under discussion here: the discussion is about an informal talk-"proof". If you want, you could look for an actual (complete) proof and then translate it into English for us. I'm just saying that your attempt missed the mark.

Edited August 13, 2008 by DavidOdden

[punk]

I know you said what you said, but what you said is false, as I showed. As a starting point, are you aware that {1,2,3} is not the same as {1,2,{3}}?

I'm fully aware of that.

If you would give us a formal proof of your claim, we could check it for errors. Otherwise, I don't know how we can help you. There is no formal proof of the claim that the empty set is in every set (or whatever one might think the claim is) under discussion here: the discussion is about an informal talk-"proof". If you want, you could look for an actual (complete) proof and then translate it into English for us. I'm just saying that your attempt missed the mark.

Given a set A we define a subset B of A by the usual convention as:

B is a subset of A if and only if for every x in B x is in A.

Suppose 0 is not a subset of A, then there exists an x such that x is in 0 but x is not in A.

However by definition 0 has no members thus there is a contradiction.

So 0 is a subset of A.

[DavidOdden]

Given a set A we define a subset B of A by the usual convention as:

Since you upped the ante by talking of formal proofs, I want to see your formal proof. Don't leave home without it.

[punk]

Since you upped the ante by talking of formal proofs, I want to see your formal proof. Don't leave home without it.

What I gave was a formal proof, schoolteacher.

That was the typical sort of proof a working mathematican gives. Every word corresponds to an obvious symbol (assuming one has experience in higher mathematics that is).

Do you want to argue about the issue at hand or do you want to play petty games?

If there is a part of it you find unclear, then please specify which part that is.

...

Well I had time so here is something more formal:

using Ax for "for all x" Ex for "there exists x", and S(x) for "x is an element of S" -

1. We define a set S' to be a subset of a set S iff Ax S'(x) -> S(x)

2. So a set S'' is not a subset of S iff Ex ~(S''(x) -> S(x))

3. That is S'' is not a subset of S iff Ex S''(x) & ~ S(x)

4. We define the empty set 0 to be the set with no elements, ie Ax ~0(x)

5. Suppose 0 is not a subset of a nonempty set S

6. Then Ex 0(x) & ~S(x), call this x 'y'

7. So 0(y)

8. But by 4 we have ~0(y)

9. =><=

10. Therefore 0 is a subset of S

Edited August 13, 2008 by punk

[DavidOdden]

B is a subset of A if and only if for every x in B x is in A.

Letters changed to overcome stupid emoticons. Subset(D,A) ≡ ∀x((x∈D)(x∈A))

Suppose 0

Who? What? Okay, define 0 to be {}, a set which contains no elements. Thus the intension of 0 is a set s.t. ∀x(x∉0).

is not a subset of A

Example: A ={1,2,3}. {} is not an element of A: ∃x(x∉A) when x={}. Inter alios.

then there exists an x such that x is in 0

I have no idea where you got that from. We have a set, A, which does not contain 0. How do you get to the conclusion that ∃x(x∈0)&∀x(x∉0)? Here's where I'd like to see you reduce this to an actual Kleene-style axiomatic proof. You know Kleene's Mathematical Logic I assume. In other words, you can assume an empty set (it's a silly notion but whatever), and yet you have not given the proof that the empty set is in every set.

Being generous, I will point out that your problem lies in saying forgetting that you admitted that {1,2,3} is not the same as {1,2,{3}}, thus if 2 is an element of a set, {2} is not automatically so. Let us define the symbol <د> "duh" to be the content of {}, i.e. not the empty set but the extension of the empty set -- nothing. We may be able to demonstrate that <د> can be unified with any set, but it cannot be shown to exist in any set (since it doesn't exist) and at any rate it isn't the empty set. If you want to try again, feel free.

[DavidOdden]

Well I had time so here is something more formal:

Leaving aside the reprehensible practice of editing a post after the fact just a second before I responded, this suggests to be that you have a very informal notion of "formal proof". Hence I retract my unfounded statement about assuming familiarity with Kleene 1967.

[punk]

Letters changed to overcome stupid emoticons. Subset(D,A) ≡ ∀x((x∈D)(x∈A))Who? What? Okay, define 0 to be {}, a set which contains no elements. Thus the intension of 0 is a set s.t. ∀x(x∉0).Example: A ={1,2,3}. {} is not an element of A: ∃x(x∉A) when x={}. Inter alios.I have no idea where you got that from. We have a set, A, which does not contain 0. How do you get to the conclusion that ∃x(x∈0)&∀x(x∉0)? Here's where I'd like to see you reduce this to an actual Kleene-style axiomatic proof. You know Kleene's Mathematical Logic I assume. In other words, you can assume an empty set (it's a silly notion but whatever), and yet you have not given the proof that the empty set is in every set.

We used Enderton for mathematical logic, Devlin for set theory, Boolos and Jeffrey for computation theory, and probably a lot of things I've long since forgotten about. I rather like Goldblatt for topos theory as it comes from a logician's view rather than that of an algebraic topologist.

But I'm more the mathematician type and mathematicians assume a knowledgeable audience that can fill in the obvious blanks (it makes papers and books much easier to read).

Anyway as you seem to be having problems with undergraduate logic:

~(Ax P1x -> P2x)

Ex ~(P1x -> P2x) (i.e. ~Ax Px <=> Ex ~Px)

Ex ~(~(P1x & ~P2x)) (i.e. ( a -> B ) <=> (~( a & ~B )))

Ex P1x & ~P2x (i.e. ~~a <=> a)

This struck me as obvious.

Being generous, I will point out that your problem lies in saying forgetting that you admitted that {1,2,3} is not the same as {1,2,{3}}, thus if 2 is an element of a set, {2} is not automatically so. Let us define the symbol <د> "duh" to be the content of {}, i.e. not the empty set but the extension of the empty set -- nothing. We may be able to demonstrate that <د> can be unified with any set, but it cannot be shown to exist in any set (since it doesn't exist) and at any rate it isn't the empty set. If you want to try again, feel free.

Well, being generous, you aren't as familiar with this all as you suppose, even if you can name drop Kleene.

As I stated in my second proof the empty set is simply the set for which nothing is a member

Ax ~0(x)

I think you are confused by the straight set theoretic notation. It isn't too amenable to usage when nothing is denoted by a blank.

Let us denote nothing by @ for lack of a better symbol.

Then we can say {1} is equivalent to {1 @}.

I mean after all just writing down a symbol for nothing doesn't do much of anything. However it is obvious that from {1 @} we can get subsets {1} and {@}. I mean formally {1}u{@} is just {1 @}. So {@} is a subset (that is {} is a subset).

But this is confusing.

It is better to go the way I did in my second proof and define the empty set by:

Ax ~0(x)

So it is just the set for which the statement "x is a member of 0" is always false.

Leaving aside the reprehensible practice of editing a post after the fact just a second before I responded, this suggests to be that you have a very informal notion of "formal proof". Hence I retract my unfounded statement about assuming familiarity with Kleene 1967.

I'll use my psychic powers better next time around.

And as indicated above, while I haven't read Kleene, I've read newer and better books.

Edited August 14, 2008 by punk

[Jake]

Let us denote nothing by @ for lack of a better symbol.

Then we can say {1} is equivalent to {1 @}.

If you have an empty sack, it may be grammatically correct to say: "The sack is filled with nothing.", but nothing is a metaphysical absence. In reality, there is no thing in the sack. It seems to me that there's a bit of a word trick going on, when one defines a set as "a collection of objects", then says a metaphysical absence is an element of all sets (as if an element can be a non-object). If a set is a collection of objects, and a set is composed of only those things which are its elements, then its elements must be objects.

{} or Ø, like 0, is not an object, it's a notation representing said metaphysical absence.

And as indicated above, while I haven't read Kleene, I've read newer and better books.

The newer books are better than what? I'm wondering: if you haven't read Kleene, how you can determine the relative worth of the newer books to Kleene?

[punk]

If you have an empty sack, it may be grammatically correct to say: "The sack is filled with nothing.", but nothing is a metaphysical absence. In reality, there is no thing in the sack. It seems to me that there's a bit of a word trick going on, when one defines a set as "a collection of objects", then says a metaphysical absence is an element of all sets (as if an element can be a non-object). If a set is a collection of objects, and a set is composed of only those things which are its elements, then its elements must be objects.

{} or Ø, like 0, is not an object, it's a notation representing said metaphysical absence.

Like I said, one really shouldn't use that notation for this sort of thing. It is too prone to misleading the user. It is better to go with a more typical formal notation like:

Ax ~0(x)

for the empty set.

The real thing to use for a subset is what I gave:

S' is a subset of S just in case Ax S'(x) -> S(x)

That isn't exactly an easy sort of thing to express purely in the other notation.

I guess in the other notation you'd have to say:

given a set {x1,x2,x3,...} another set {y1,y2,y3,...} is a subset of the first just in case for every yn in the second there exists and xn in the first such that yn = xn. so if the second is not a subset of the first then there exists an yn, call it y, such that there is no xn such that y = xn. Now take the first and {}, then {} is not a subset of the first just in case there exists an element in {} which is not in the first. However there is no element in the {} that is not in the first (by virtue of the fact that there is no element in {}), so {} is a subset of the first.

It really gets back to how a subset is defined.

If one doesn't like that {} is the subset of any other set then one needs to redefine the notion of subset somehow.

The result really follows from the definition.

Hey, as long as we are at it, I could use an even simpler (and equivalent) definition of subset:

B is a subset of A just in case A u B = A (think about it)

So since we all agree A u 0 = A, then 0 is a subset of A. I thought this begged the result too much though.

Unfortunately all the nonsense that has gone on has distracted from this simple (and interesting) fact.

The question is can one come up with another definition of subset which doesn't lead to other (worse) problems than saying that {} is a subset of every set.

I suspect that any other definition of subset is going to force one to have to give up the Law of the Excluded Middle.

So you have a choice, the Law of the Excluded Middle or {} is a subset of every set.

The newer books are better than what? I'm wondering: if you haven't read Kleene, how you can determine the relative worth of the newer books to Kleene?

I needed it for a reference on a particular topic once.

I only really used that one section though. It was for a graduate seminar on logic a decade ago, and I remember it had something to do with some result about some kind of "tree". I was probably using it to try to figure out something that wasn't clear in the assigned course readings.

I remember finding it an awful reference though.

Edited August 14, 2008 by punk

[Jake]

Like I said, one really shouldn't use that notation for this sort of thing. It is too prone to misleading the user. It is better to go with a more typical formal notation like: Ax ~0(x)

1) David / punk: can either (or both) of you recommend a book describing this notation. If it is more precise and less prone to confusion, I'd like to learn it. Unfortunately, I find Wikipedia and Mathworld are a bit too reference-y and scattered to learn things from scratch.

2) Is "just in case" equivalent to "if and only if"?

I guess in the other notation you'd have to say:

given a set {x1,x2,x3,...} another set {y1,y2,y3,...} is a subset of the first just in case for every yn in the second there exists an xn in the first such that yn = xn. so if the second is not a subset of the first then there exists a yn, call it y, such that there is no xn such that y = xn. Now take the first and {}, then {} is not a subset of the first just in case there exists an element in {} which is not in the first.

bold mine

Similar to a statement I made in my OP, I hold that to state "for every yn" you must have at least one yn, otherwise it is vacuous reasoning.

However there is no element in the {} that is not in the first by virtue of the fact that there is no element in {}), so {} is a subset of the first.

italics mine

Why couldn't one also say, "there is no element in the {} that is in the first, by virtue of the fact that there is no element in {}?

I still think that you can't determine anything about the properties or truth relations of a non-existence, because it has none, because it doesn't exist.

If one doesn't like that {} is the subset of any other set then one needs to redefine the notion of subset somehow. The result really follows from the definition.

It only follows by vacuous reasoning. I think the error is clearer if you replace the arbitrary set in the definition with the empty set:

Ø is a subset of Q, because every element of Ø is an element of Q.

If there are no elements in Ø, the phrase "every element of Ø" makes no sense. "Every" and "for all" assume "at least one".

So you have a choice, the Law of the Excluded Middle or {} is a subset of every set.

I don't think the Law of Excluded Middle requires every statement to be either true or false. The ability to determine if a statement is true or false is predicated on the statement's relation to reality (or lack thereof). True/False determinability is therefore a property of a statement, subject to the Law of Excluded Middle.

So, you first ask: "Is this statement related to reality (does it have a truth value)?"

Yes => you can then ask: "Is it true or false?"

No => it has no true/false property.

The Law of Excluded Middle is used in both steps, a statement's truth value cannot be both determinable and indeterminable; if it is determinable, the statement cannot be both true and false. There is no semi-determinable or semi-true.

As a concrete example: 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? Which is the case? Are all the non-existent lights in the hallway on or off? I hold that the answer is that the original statement is neither true nor false, not because it is between true and false, but because it is before true and false.

Isn't the Law of Excluded Middle just a restatement of the Law of Identity? A thing cannot simultaneously have and not have a given property.

Edit: between/before sentence added.

Edited August 14, 2008 by Jake

[DavidOdden]

1) David / punk: can either (or both) of you recommend a book describing this notation.

There are numerous books which present some notation, for example Richard Jeffry Formal Logic: Its Scope and Limits, which is a useable textbook. Apparently it's not at home so I can't check this, but I think he mentions the different notational conventions for FOP logic, except of course the internet non-standard (i.e. where you use 0 for Ø, A for ∀ etc), tailored to the problem of easily inserting funny characters. There may be other reference-card type guides that lay out the different notations.

If it is more precise and less prone to confusion, I'd like to learn it.

The notation itself isn't necessarily "more precise" in the sense of a determinate mapping between representation and referent, but on average, symbolic notation has less variation in form-meaning relationship compared to natural language. For example, the universal quantifier ∀ has one formal referent, and it isn't exactly the same as how "all" is used in natural language.

2) Is "just in case" equivalent to "if and only if"?

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.

[TuringAI]

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? Most people say it's a result of the Axiom of Choice, but I think, more fundamentally, it is the consequence of the requirement of strict heiarchy that exists as one of the axioms in typical set theory. Is there any proof of this, either positive or negative?

[punk]

1) David / punk: can either (or both) of you recommend a book describing this notation. If it is more precise and less prone to confusion, I'd like to learn it. Unfortunately, I find Wikipedia and Mathworld are a bit too reference-y and scattered to learn things from scratch.

2) Is "just in case" equivalent to "if and only if"?

I'm sorry, It has been ages since I've done this stuff at an introductory or intermediate level.

Yes, "just in case" is the same as "if and only if".

bold mine

Similar to a statement I made in my OP, I hold that to state "for every yn" you must have at least one yn, otherwise it is vacuous reasoning.

Not really. If I say that every egg in an empty basket is red, that is a true statement. All of the eggs (of which there are none) are read. It gets at the way this is written formally:

Ax (E(x)&B(x)) -> R(x) ('every egg in the basket is red')

So what is being said is that for any x (which can be anything in the universe, say the star alpha proxima) you ask is it an egg? (no), is it in the basket (no), then it would be red if it were an egg and in the basket. If there were anything in the universe that were an egg and in the basket and were not red then you'd have a problem.

Effectively all the expressions are defined in such away that you can test every object in the universe to see if it holds.

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.

The alternative is to say "well no object in the universe makes it false, so it isn't false, but yet no object in the universe satisfies it, so it must be neither true nor false". But the minute you start doing this you have given up the Law of the Excluded Middle (which requires every expression be either true or false).

italics mine

Why couldn't one also say, "there is no element in the {} that is in the first, by virtue of the fact that there is no element in {}?

I still think that you can't determine anything about the properties or truth relations of a non-existence, because it has none, because it doesn't exist.

No, as above, if we require the Law of the Excluded Middle then every expression must be either true or false. You are saying that since the empty set is empty we can't ascribe properties to it. So for a given set A it is neither true that the empty set is a subset of A nor false that the empty set is a subset of A (as there are no properties to make the comparison).

Again, you've denied the Law of the Excluded Middle.

It only follows by vacuous reasoning. I think the error is clearer if you replace the arbitrary set in the definition with the empty set:

Ø is a subset of Q, because every element of Ø is an element of Q.

If there are no elements in Ø, the phrase "every element of Ø" makes no sense. "Every" and "for all" assume "at least one".

No, you really need some way of reasoning with the empty set per what I said above, or else you drop the Law of the Excluded Middle.

Which is fine, there is a logic without that Law, namely Intuitionistic logic.

But I don't think you really want to go there.

I don't think the Law of Excluded Middle requires every statement to be either true or false. The ability to determine if a statement is true or false is predicated on the statement's relation to reality (or lack thereof). True/False determinability is therefore a property of a statement, subject to the Law of Excluded Middle.

For any expression A the Law of the Excluded Middle states A v ~A. So every expression must be true or false. Otherwise you must assign some other truth value (neither true nor false) to some expressions (such as those involving the empty set, since every expression should be able to have some assignment, you could call the third state "vacuous"), 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.

So, you first ask: "Is this statement related to reality (does it have a truth value)?"

Yes => you can then ask: "Is it true or false?"

No => it has no true/false property.

The Law of Excluded Middle is used in both steps, a statement's truth value cannot be both determinable and indeterminable; if it is determinable, the statement cannot be both true and false. There is no semi-determinable or semi-true.

The Law of the Excluded Middle requires a truth value be assigned to every expression in itself. This is how deduction works. If I give you the expression "{} is a subset of A", the Law of the Excluded Middle says I can say "either {} is a subset of A or {} is not a subset of A" and that this statement is true. But with a third truth value (vacuous) it isn't true any longer.

The point of deductive logic is to create a system where every expression is either true or false and that there are methods of deduction that always reason from true expressions to true expressions.

But, again, you are proposing a non-Boolean system.

You can do it if you want to, but you are no longer doing classical logic.

As a concrete example: 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? Which is the case? Are all the non-existent lights in the hallway on or off? I hold that the answer is that the original statement is neither true nor false, not because it is between true and false, but because it is before true and false.

Okay you have the expression "either the light is on or the light is off", but there is no light. If you are in a Boolean system with the Law of the Excluded Middle, then the expression must be either true or false. If you don't want to work in a Boolean system with the Law of the Excluded Middle you can get the result you want.

Again, you are proposing using a non-classical logic.

Isn't the Law of Excluded Middle just a restatement of the Law of Identity? A thing cannot simultaneously have and not have a given property.

Edit: between/before sentence added.

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.

The expression you gave would be derivable from the Law of the Excluded Middle in a Boolean system.