Jump to content
Objectivism Online Forum

The Empty Set (or lack thereof)

Rate this topic


Jake

Recommended Posts

  • Replies 104
  • Created
  • Last Reply

Top Posters In This Topic

QUOTE (Hodge'sPodges @ Aug 14 2008, 06:03 PM)

Words

(1) I didn't write such as could be quoted. (2) I've written quite a bit here, but none of it is exceptionally wordy. I've covered a lot of ground and I've done it with deliberate detail. That does not deserve your smart-alecky reply. (3) So, I hope your joke is an exception to your ordinary manner, since the bit is quite cheap and insinuates falsely. Or perhaps, I took it wrong, and you didn't mean anything snarky by it, in which case, please disregard this paragraph.

Thanks for the book advice. Luckily, I have a solid undergraduate Math background to work from, including a year-long Analysis course. Unfortunately, I learned most of it 12-13 years ago, so I'm pretty rusty. My recently obtained Engineering B.S. didn't involve any upper-level math courses.
That's good. It will serve you well. And it is a lot of fun getting back into math! Anyway, as you expressed an interest in going in to set theory, I really do highly recommend first mastering the Kalish/Montague/Mar text on first order logic, which is the logic of set theory and of classical mathematics in general.

Are any of the more frequently applied aspects of Calculus, Linear Algebra, or Differential Equations dependent upon vacuous reasoning?
No immediate examples come directly to my mind, though I wouldn't say that I couldn't dig up an example. I think it might be fair to say that vacuous case arguments come up more in foundational contexts than in applied math? However, even in such ordinary contexts as mathematical induction, we may find vacuous case arguments. Usually, it amounts to dispensing the base case as, in these instances, the base case holds vacuously.

Then you didn't mean "sentence", since only natural languages have sentences. Formal languages have formulae.
No, the word 'sentence' is used quite commonly in mathematical logic and is defined as 'a well formed formula with no free variables'. And that is why I specifically said that sentences (not just expressions, and even just well formed formulas) are what receive truth values. Edited by Hodge'sPodges
Link to comment
Share on other sites

Well, finally, some progress. Notice that ¬,A,0f2c04f82a1eb8e3e371366214579f5b.png,B,≡,∨,P are not allowed symbols, so your logic doesn't allow you to say anything in set theory, or anything else of interest. Just XY*
Yes of course, its an extremely basic example. But formal set theory is essentially the same, just more complex - you have an alphabet of allowed symbols, and a system of rules for producing well-formed combinations of these symbols.

Do you have a shred of evidence that, aside from order, there is a valid distinction between syntax and semantics?
Semantics is the study of interpretations (''meanings') of the symbols. In the formal system I gave, we can only talk about the provability of strings (ie their derivation from the axioms) rather than their truth values, since there isnt yet a theory of semantics defined - the symbols do not yet 'mean' anything. Truth arises at the semantic level once we start creating models of the system, not the syntatic one.

But the point is that the axioms and combination rules fully determines which strings are valid and provable within the system. You dont need any meanings or referents for this. Thats why its a formal system.

I'm wondering whether you're conflating with a different matter. It is true that

Ax(Fx -> Gx) -> ExFx is NOT a theorem of the predicate calculus.

That is, from "Everything that is an F is a G" does not entail that there is something that is an F, but AxFx -> ExFx is a theorem of the first order predicate calculus.

That is "If everything is an F, then there exists something that is an F".

That is correct, since the standard first order predicate calculus requires that any domain of discourse be non-empty, so if everything in a NON-empty domain has a certain property, then there is at least one thing that has that property (since the domain has at least one thing in it). And thus the rules of inference permit inferring ExFx from AxFx.

Oh ok, I think I misinterpreted you then, I thought you were claiming the former.

Edited by eriatarka
Link to comment
Share on other sites

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?

Because it doesn't follow from the definitions.

A subset of AuB

and

B subset of AuB

are theorems

But neither

A proper subset of AuB

nor

B proper subset of AuB

are theorems.

For counterexamples:

A is not a proper subset of AuA.

B is not a proper subset of BuB.

A is not a proper subset of Au0.

B is not a proper subset of 0uB.

It may be that in certain instances (depending on what A and B are) that A is a proper subset of AuB, but it is not a theorem that for every A and every B we have A is a proper subset of AuB, etc.

What useful higher-level aspects of set theory are lost if {} isn't a subset of every set? Does the theory become inconsistent?
I don't think it's a matter of gaining or losing higher level aspects. But rather that it is very useful in set theory to define '0' and 'is a subset of' as we do; then, from those definitions, it simply follows that 0 is a subset of every set.

And yes, it would contradict set theory to assert that 0 is not a subset of every set.

Since Ay 0 subset of y

is a theorem, it is a contradiction in set theory to assert

~Ay 0 subset of y.

Link to comment
Share on other sites

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)

Why should the power set of any given set X have a strictly greater cardinality? Is that a rule that applies to all known cardinalities or is there a point of logic that would make it apply to arbitrarily large cardinalities?

Link to comment
Share on other sites

Why should the power set of any given set X have a strictly greater cardinality? Is that a rule that applies to all known cardinalities or is there a point of logic that would make it apply to arbitrarily large cardinalities?

Its a theorem which follows from the definition of cardinality and power sets. It applies to all cardinalities - different infinite sets can have different cardinalities and theres a hierarchy of transfinite cardinal numbers. The set of real numbers has a greater cardinality than the set of integers for example (there are 'more' real numbers than there are integers, in a sense).

http://en.wikipedia.org/wiki/Cantor's_theorem

Edited by eriatarka
Link to comment
Share on other sites

Why should the power set of any given set X have a strictly greater cardinality? Is that a rule that applies to all known cardinalities or is there a point of logic that would make it apply to arbitrarily large cardinalities?
It's a theorem. From the axioms and definitions, one can prove that for any X, the cardinality of the power set of X is greater than the cardinaility of X.

And, actually, more basically, even without the notion of cardinality defined, we have the theorem:

For any X, there is no function from X onto the power set of X.

So, once we do move on to defining 'cardinality', it will follow that the cardinality of the power set of X is greater than the cardinality of X.

Of course, I haven't given you here the proofs, but they're not difficult.

Edited by Hodge'sPodges
Link to comment
Share on other sites

It's a theorem. From the axioms and definitions, one can prove that for any X, the cardinality of the power set of X is greater than the cardinaility of X.

And, actually, more basically, even without the notion of cardinality defined, we have the theorem:

For any X, there is no function from X onto the power set of X.

So, once we do move on to defining 'cardinality', it will follow that the cardinality of the power set of X is greater than the cardinality of X.

Of course, I haven't given you here the proofs, but they're not difficult.

Which 'axioms and definitions' prohibit the existence of a universal set? I'd like to see the proofs so that I can deconstruct them, because it makes no sense that a universe can exist without a universal set.

Link to comment
Share on other sites

But the point is that the axioms and combination rules fully determines which strings are valid and provable within the system. You dont need any meanings or referents for this. Thats why its a formal system.
The point is that truth and validity do not exist except in relation to existence, and you do not need a syntax for this. Furthermore you can't prove anything without a semantics. Reference is all you need.
Link to comment
Share on other sites

Which 'axioms and definitions' prohibit the existence of a universal set? I'd like to see the proofs so that I can deconstruct them, because it makes no sense that a universe can exist without a universal set.

I think this is the wrong way to look at it. Noone is prohibiting you from doing anything - you can go away and create any set of axioms that you like. But once youve came up with some axioms, you have to accept what follows from them, and if the axioms lead to a contradiction then you have to change them.

In this case, one of the problems with a universal set is that you cant define the notion of 'cardinality' in the intuitive way we would want to, because it immediately creates a contradiction as explained above (there are other problems with it too but I think this one is the easiest to explain). There cant be a universal set because the power set of the universal set will always be bigger than it, and hence cant be a subset. So the assumption of a universal set leads to a paradox.

Set theory has been rife with these paradoxes ever since its creation - early set theories which allowed people to create arbitrary sets (such as Frege's) were shown to lead to contradictions. Russell's paradox ( http://en.wikipedia.org/wiki/Russell's_paradox ) is the most notorious example of this. The reason why modern ZFC set theory is more complex than this sort of naive set theory is because it was created in a way which avoids these paradoxes. Things like the assumption of universal sets seem innocuous but they can be shown to lead to contradictions. These problems were studied intensively during the first half of the 20th century and various solutions were proposed. ZFC is the solution that most modern mathematicians and logicians have adopted.

edit: I want to be clear about what a universal set is here. Lets say you have a universe containing the objects 'a', 'b', and 'c'. Now, theres nothing stopping you making a set containing all these objects, say S = {a,b,c}. And the set S2 = {a} will then be a subset of S. But we can also create another set S3 = {{a}} which isnt a subset of S, since '{a}' is not an element of S (although 'a' is).

The power set of S here is then {0,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}. And this obviously isnt a subset of S (and note that it has cardinality 8 whereas S only has cardinality 3). You cant have a set which has every set as its subset because the powerset of that set wont be a subset.

Edited by eriatarka
Link to comment
Share on other sites

Which 'axioms and definitions' prohibit the existence of a universal set? I'd like to see the proofs so that I can deconstruct them, because it makes no sense that a universe can exist without a universal set.
I don't know what you mean by 'deconstruct' in this context. I don't doubt that you may find some natural language or philosophical basis on which to object to a set theory proof, but that is a separate matter from two separate questions: (1) Whether there exists a sequence of formulas that is a formal proof in the formal system of Z set theory such that the last formula in that sequence is ~ExAy yex, and (2) Whether there is a sequence of formulas such that the last formula in that sequence is the negation of of a formula that is the last formula in a sequence that is a proof in the system of formal Z set theory (i.e. whether Z set theory formally proves a contradiction, i.e., whether Z set theory is inconsistent (in the mathematical sense of 'inconsistent').

As to universes and universal sets, given an intrepretation of set theory (say, Z set theory, just to be specific), there is a universe. However that universe is not a member of itself. Also, please keep in mind that the word 'universe' here is in a specific mathematical sense that does not necessarily correspond to everyday senses or even certain philosophical, ontological, or metaphysical senses of the word 'universe'.

Anyway, I already outlined a proof. The only set theoretic (i.e., non-logical) axiom I used is an instance of the axiom schema of separation:

For any formula F in which z does not occur free, all closures of

EzAy(yez <-> (yex & F))

are axioms.

I'll give a relaxed version of the reasoning, from which one can see easily that it is formalizable into a sequence of formulas that is a proof in the first order predicate calculus:

Theorem: ~ExAy yex

Proof:

Suppose, toward a contradiction, ExAy yex.

Let Ay yex.

From the axiom schema of separation, we have:

EzAy(yez <-> (yex & ~yey)).

Let Ay(yez <-> (yex & ~yey)).

So, since we have Ay yex, we have Ay(yez <-> ~yey)

so zez <-> ~zez, a contradiction.

So ~ExAy yex.

You won't find anything there that is not first order predicate logic applied to an instance of the axiom schema of separation. Nor is there any realistic hope that you could prove the negation of a theorem of Z set theory, from only the axioms of set theory, and using only first order predicate logic (especially not from just the axiom schema of separation and first order logic).

However, you may have any number of philosophical objections. That is not in question, and also they don't bear upon the mere matters (1) and (2) I mentioned earlier.

Link to comment
Share on other sites

The point is that truth and validity do not exist except in relation to existence, and you do not need a syntax for this. Furthermore you can't prove anything without a semantics. Reference is all you need.
One may have a view of proof that requires that the utterances in the proof have meaning, and probably that is the sense of 'proof' that most people have. However, there is a special mathematical definition of 'proof' such that it is not required that the formulas in a proof have meaning. The first order predicate calculus is such that proofs can be given irrespective of any meaning or without even consideration of whether the formulas have meaning; however, with the calculus we also have its sidekick - the semantics. And the semantics do provide a very certain kind of mathematical meaning. Then, of course, the central result (the soundness and completeness meta-theorems) is that the calculus and the system of meaning do perfectly work together (in the exact sense as in the said meta-theorems). Still, even as we prove that the proof syntax and the semantics perfectly mesh, we also understand that they are separable in the sense that one may, if one wishes, work with either of them alone; also that one can fully specify the proof syntax without ever mentioning the semantics; and one could fully specify the semantics without mentioning the proof syntax. Indeed, many (most?) books do that. They first develop one or the other alone, then the other, and then show how they mesh. Edited by Hodge'sPodges
Link to comment
Share on other sites

Or perhaps, I took it wrong, and you didn't mean anything snarky by it, in which case, please disregard this paragraph.

Replacing an author's words with "words" is a habit I picked up from another forum. It's used when one wants to use the quote feature of the forum to reply to something the author said, or in this case to specify whom I was thanking for the book advice. It's just a means of using the quote function without needlessly filling the page. There was no snarky intent. I suppose I could have just said, "Hodge'sPodges, thanks for the book advice."

Link to comment
Share on other sites

According to which axioms? Furthermore, how do you prove the axiom once you've identified it?
There are different axiomatizations of Z set theory. Personally, I like to work in Z set theory but without the axiom of regularity (only because the axiom of regularity is not needed for most math; so I can transfer to fuller theories, adding or dropping regularity, schema of replacement, or choice principles, as dictated by the nature of the project).

Here's an axiomatization of Z set theory:

Z set theory is an extension of identity theory in classical first order logic.

The set theoretic axioms are:

extensionality

schema of separation

pairing

union

power set

infinity

regularity

I'll write out the formulas with English "translation" if you like.

As to proving axioms, the axioms are not first proven.

Also, in general, keep in mind that the sense of the 'word' axiom in mathematical logic is somewhat different (and in some cases, greatly different) from other senses of that word that are found in ordinary speech, even in certain other mathematics, or in certain philosophies.

As to proving that every set has cardinality less than the cardinality of its power set, we ordinarily would say that the power set axiom is used, even if just to prove that every set has a power set. However, the gist of the theorem and proof can be stated hypothetically ("IF k is the cardinality of x and there is a set y whose members are all and only the subsets of x, and j is the cardinality of y, then k is less than j"); and we could even dispense with 'cardinality' and reduce the matter to the bare bones question of whether, for any given set x, there exists a surjection from x onto any set y that has as members all the subsets of x. And for that purpose, all we need (I would doublecheck myself though if my life depended on it) is the axiom schema of separation.

Would you like to see the proof?

Link to comment
Share on other sites

As to proving that every set has cardinality less than the cardinality of its power set, we ordinarily would say that the power set axiom is used, even if just to prove that every set has a power set. However, the gist of the theorem and proof can be stated hypothetically ("IF k is the cardinality of x and there is a set y whose members are all and only the subsets of x, and j is the cardinality of y, then k is less than j"); and we could even dispense with 'cardinality' and reduce the matter to the bare bones question of whether, for any given set x, there exists a surjection from x onto any set y that has as members all the subsets of x. And for that purpose, all we need (I would doublecheck myself though if my life depended on it) is the axiom schema of separation.

Would you like to see the proof?

Most definitely.

I hypothesize that I will see other axioms in place, but until I do I will withhold judgment.

Link to comment
Share on other sites

I hypothesize that I will see other axioms in place, but until I do I will withhold judgment.
Definition: Px = y <-> Az(zey <-> z subset of x)

Theorem: ~Ef(f is a function from x onto Px)

Proof:

1. Suppose f is a function from x to Px.

2. Let d = {b | bex & ~b e f(B)} ... from axiom schema of separation

3. d subset of x ... from 2 and by definition of 'subset of'

4. Suppose Eb(bex & d=f(B))

5. b e f(B) <-> ~b e f(B) ... from 2 and 4 by identity

6. ~Eb(bex & d=f(B)) ... from 4, 5, by contradiction

Notes: (1) The definition of 'P' is properly enabled courtesy the power set axiom. But, as I mentioned previously, we could still obtain the gist of the theorem without the power set axiom. (2) In the proof, the only set theoretic axiom used is an instance of the axiom schema of separation. The only logic used is intuitionisic logic (even weaker than classical logic); and, if I'm not mistaken, only minimal logic (a system even weaker than intuitionistic logic) is used.

Edited by Hodge'sPodges
Link to comment
Share on other sites

The diagonal argument is much more intuitive than a formal logic proof imo, you should look at the proof in the link I posted above if you want to see why the power set thing has to be true. Proofs directly from set theory axioms are useful iff you want to do computer proof checking but they often tend to hide the conceptual content of whats being said.

Edited by eriatarka
Link to comment
Share on other sites

The diagonal argument is much more intuitive than a formal logic proof imo, you should look at the proof in the link I posted above if you want to see why the power set thing has to be true. Proofs directly from set theory axioms are useful iff you want to do computer proof checking but they often tend to hide the conceptual content of whats being said.
What I just gave is the diagonal argument. I gave it semi-formally, since that seemed to be the context of the discussion at the time. And the poster wanted to see exactly what axioms are used. Also, I want to impress the fact that there is a proof that is indeed a formal mathematical object, so that 'proof' is taken in that context and not necessarily in certain other senses of the word. The semi-formal proof I gave is sufficient to see that there is a formal mathematical proof of the statement.

For just a relaxed natural language rendering:

Theorem: There is no function from x onto Px.

Proof: Suppose f is a function from x to Px.

Let d be the set of b such that b in x and b not in f(B).

d is a subset of x.

Suppose for some b, we have d is f(B).

So b in f(B) iff b not in f(B), which is a contradiction.

So, for no b do we have that d is f(B).

So d is not in the range of f.

Edited by Hodge'sPodges
Link to comment
Share on other sites

What I just gave is the diagonal argument. I gave it semi-formally, since that seemed to be the context of the discussion at the time. And the poster wanted to see exactly what axioms are used. Also, I want to impress the fact that there is a proof that is indeed a formal mathematical object, so that 'proof' is taken in that context and not necessarily in certain other senses of the word. The semi-formal proof I gave is sufficient to see that there is a formal mathematical proof of the statement.

For just a relaxed natural language rendering:

Theorem: There is no function from x onto Px.

Proof: Suppose f is a function from x to Px.

Let d be the set of b such that b in x and b not in f(:P.

d is a subset of x.

Suppose for some b, we have d is f(B).

So b in f(B) iff b not in f(B), which is a contradiction.

So, for no b do we have that d is f(B).

So d is not in the range of f.

So the argument goes, essentially, that because you can put x in one to one correspondence with a subset of P(x), that subset being simply the sets containing only one element, you cannot find room for the ones containing more than one element. So you cannot shift the elements around to make room? After contemplating the argument given, I think there is a lot still left to be explained, and a few more axioms that are implied.

Link to comment
Share on other sites

So the argument goes, essentially, that because you can put x in one to one correspondence with a subset of P(x), that subset being simply the sets containing only one element, you cannot find room for the ones containing more than one element. So you cannot shift the elements around to make room?
No, that's not the argument.

However, just the first part, that we can put x 1-1 with a subset of Px is correct (and in the manner you described), and is one half of showing that Px strictly dominates x. And that does use the pairing axiom and the axiom of extensionality (to prove the existence of singletons), also (unless there's a way I'm not thinking of), we need the union axiom and the power set axiom to get a Cartesian product from which to use the axiom schema of separation to form the injection.

What I showed was that there is no surjection from x onto Px. Therefore, there is no 1-1 between x and Px.

Now, that result and also taking the result you just mentioned, that there is an injection from x into Px, we get that Px strictly dominates x.

After contemplating the argument given, I think there is a lot still left to be explained, and a few more axioms that are implied.
At what exact step in the proof do you think there are other set theoretical axioms used merely to show that there is no surjection from x onto Px?

/

Note: I turned off icons (smilely faces) for my proof, but smiley faces are showing up in your quote of my proof.

Edited by Hodge'sPodges
Link to comment
Share on other sites

So the argument goes, essentially, that because you can put x in one to one correspondence with a subset of P(x), that subset being simply the sets containing only one element, you cannot find room for the ones containing more than one element. So you cannot shift the elements around to make room?

First, make sure you understand what it means for a function to be surjective and injective.

http://en.wikipedia.org/wiki/Injective_function

http://en.wikipedia.org/wiki/Surjective

Now, given any 2 sets (say X and Y), X and Y have equal cardinality if there is a surjective+injective function between the two sets. X has a greater cardinality than Y if you can find a injective function from Y to X, but there is no such function from X to Y.

Intuitively, what this means is that 2 sets have the same cardinality if you can put them side by side and pair up every object in one with an element of the other. And one set is bigger than another if you 'run out' of elements in the smaller set when you try to do this.

What the diagonal argument shows is that there is no injective function which can map every element of X onto the power set of X. This implies that X has a lesser cardinality than its power-set - if you start trying to pair up every element of X with an element in its power-set, then you eventually 'run out' of elements of X (even if there are infinitely many). The point of the diagonal argument is that if assume that you have a mapping which associates every element of X with an element of its power-set, then its possible to find an element of the power-set which has no element of X corresponding to it (ie youve 'ran out' of elements of X, but there are still elements of the power-set which havent been paired up). This is true no matter what you take the mapping to be, so no such mapping can exist.

Edited by eriatarka
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.

×
×
  • Create New...