Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Truth value of for all x in {} and there exist x in {}

  1. Sep 12, 2005 #1
    truth value of "for all x in {}" and "there exist x in {}"

    Suppose T is a true statement. Now, given a nonempty set A, both the statement

    for all x in A, T

    and

    there exist x in A, T

    are true. However, let E be the empty set. What is the truth value of

    for all x in E, T

    and

    there exist x in E, T

    ?

    In the second chapter of Paul R. Halmos' book "Naive Set Theory", he stated that if the variable x doesn't appear in sentence S, then the statements

    for all x, S

    and

    there exist x, S

    both reduce to S.

    Is that something that is just agreed upon? In that case, the statement

    for all x in E, T

    reduces to T which is true (eventhough there's nothing in E) and so does the statement

    there exist x in E, T (eventhough there exist nothing in E).

    I find that counterintuive although if it is indeed the agreed upon rule, I think I just have to get used to it (but any justification would greatly help :)). Your comments?

    Thanks,

    Agro
     
  2. jcsd
  3. Sep 12, 2005 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I would be inclined to phrase this as an implication: If x is in set A, then x is in set A is always true.

    In particular, if the hypothesis, "if x is in set A" is false the implication is trivially true. That would apply to the empty set but also to other sets.

    Suppose A= {x,y} and you assert "if x is in set A, then x is in set A". Could I point to "z" and say since z is not in A your statement is false? Of course not. Similarly with A= {}. The hypothesis "x is in set A" is false for all x so the implication is trivially true.
     
  4. Sep 12, 2005 #3

    honestrosewater

    User Avatar
    Gold Member

    If T is a true statement, then there exist x in A and for all x in A are already superfluous - no matter what A is. In

    For all x in A, Px

    Px alone cannot be assigned a truth-value; You need to add For all x in A in order to form a statement that can be assigned a truth-value. However,

    Pb

    where b is an individual, can be assigned a truth-value. So your example is just adding

    For all x in A

    to what is already a formula:

    For all x in A, Pb

    Adding for all x makes no difference - there's no x in Pb. Does that make sense?
     
  5. Sep 12, 2005 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    It seems to me that to say there exists x in A such that T is the case is to say that there exists x in A (and this x happens to satisfy some condition). But if A is empty, then there exists no x in A, so should the sentence be false? We could deduce that it is false, I think.

    [tex](\exists x)(x \in A\ \wedge \ T) \supset [(\exists x)(x \in A)\ \wedge \ (\exists x)T][/tex]

    [tex]\neg (\exists x)(x \in A)[/tex]

    Therefore:

    [tex]\neg [(\exists x)(x \in A)\ \wedge \ (\exists x)T][/tex]

    and hence

    [tex]\neg (\exists x)(x \in A\ \wedge \ T)[/tex]
     
  6. Sep 12, 2005 #5

    honestrosewater

    User Avatar
    Gold Member

    If a statement S can be assigned a truth-value, then S contains no free variables. If S contains no free variables, then adding a quantifier - any quantifier, ex. For all x in {} - to S has no effect, since the quantifier has no variables to bind.*

    For example, 0 = 0 contains no free variables - it contains no variables at all. It can be assigned a truth-value, say, true. For all x in {}, 0 = 0 is then still true, because there are no free variables in 0 = 0 for the quantifer to apply to.
    The OP said that T was a true statement. So T could be 0 = 0. You guys are saying that the truth of 0 = 0 depends on how some variable, say, x, is quanitified. But there is no x in 0 = 0, so this doesn't make sense. The rules make sense to me. Does anyone see what I'm saying here? There is no free variable in T.

    *As long as the added quantifier isn't positioned so as to change the scope of any other quantifiers in S. In every language that I've seen, adding a quantifier to the left of S, as in the OP's example, does not change the scope of any other quantifiers in S.
     
  7. Sep 12, 2005 #6

    honestrosewater

    User Avatar
    Gold Member

    I'm not familiar with the system allowing you to break up

    1) [tex]\exists x \in A[/tex]

    into

    2) [tex]\exists x (x \in A)[/tex]

    Is (2) a complete statement? Surely (1) isn't a complete statement?

    Anyway, notice the quote from the book in the OP:
    If S is

    [tex](x \in A\ \wedge \ T)[/tex]

    then x is a free variable in S, and I think the author's and my comments are still true.
     
    Last edited: Sep 12, 2005
  8. Sep 12, 2005 #7

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I am not questioning the truth of T, I am questioning the truth of (Ex)(x in A & T). And to say "Ex in A" is, I believe, short form for "(Ex)(x in A)".
    I'm not sure what you mean by this.

    Generally, the universe of discourse is non-empty. But if it is empty, then to say that 'there exists x such that S' obviously implies that 'there exists x', and if there does not exist any x, then there doesn't exist any x such that S.

    Also, note that there's a difference between saying (Ex)(S) and (Ex)(x in A & S).
     
  9. Sep 13, 2005 #8

    honestrosewater

    User Avatar
    Gold Member

    :rofl: Okay, I'm starting to understand the OP's confusion.

    1) If S contains no free variables, then [itex]\exists x (S)[/tex] is equivalent to S.

    Do you agree with (1)? That was my whole point. I thought it was a simple matter and was looking at [itex]\exists x \in S[/itex] as an 'indivisible unit', just as [itex]\exists x[/itex] is an indivisible unit. I'm not saying that I was right in considering [itex]\exists x \in S[/itex] to be indivisible - it just didn't cross my mind that it would be otherwise.
    Can they be assigned a truth-value?
    Sure, and the rules for empty universes are different (don't ask me how - I'm not very familiar with them - I think they're called free logics). But the OP didn't say anything about the universe. When you say 'there exists x such that S', it is implied that x varies over the universe, yes? But
    makes me think that A and E are subsets of the universe. Clearly if A is non-empty, whether it refers to the universe or a proper subset of it, the universe is non-empty, so I never even thought that the OP was asking about empty universes or using the rules for empty universes.

    Meh, I'm not disagreeing with you. :smile: I'm just trying to figure out what exactly [itex]\exists x \in A[/itex] means to you.
    What's the difference? S could be x in B & T. And if the x in Ex varies over the universe, wouldn't Ex(S) be short for Ex(x in U & S), where U is the universe?
     
  10. Sep 13, 2005 #9

    honestrosewater

    User Avatar
    Gold Member

    I am genuinely confused by part of this (hopefully, only for the moment), but I think

    1) If S contains no free variables, then [itex]\exists x(S)[/itex] is equivalent to S.

    is the key to clarifying things.
     
  11. Sep 14, 2005 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Normally I would, but if that sentence is to be read, "there exists x such that S" then there must exist x for the sentence to be true, and if the U.D. is empty, then no x exists and so the sentence in question is false. I hope that we can agree that if the U.D. is empty, the following is true:

    [tex](\forall x)(\neg S)[/tex]

    In fact, the following sentence would also be true:

    [tex](\forall x)(S)[/tex]

    but we need only focus on the first one. Now if you accept the truth of the sentence [itex](\forall x)(\neg S)[/itex] then you accept the truth of [itex]\neg (\exists x)(S)[/itex] and thus the falsehood of [itex](\exists x)(S)[/itex].
    Set membership is a two place predicate defined by [itex]\in xy[/itex] iff x is an element of y. Normally this predicate is written in infix notation so we write [itex]x \in y[/itex] as you know. We certainly need such a predicate, and we certainly need [itex](\exist x)[/itex] to be an indivisible unit of its own. Given that we can define [itex](\exists x \in A)(\dots )[/itex] in terms of just the existential quantifier and the set membership predicate, it doesn't make sense to add [itex](\exists x \in A)(\dots )[/itex] as its own new indivisible unit. I could be wrong, but to me, this seems most sensible. We would define them as follows:

    [tex](\exist x \in A)(\mathbf{P}) := (\exist x)((x\in A) \wedge \mathbf{P})[/tex]

    [tex](\forall x \in A)(\mathbf{P}) := (\forall x)((x \in A) \supset \mathbf{P})[/tex]
    Certainly, [itex](\exists x)(x \in A)[/itex] can be assigned a truth-value. Given the above, [itex](\exists x \in A)[/itex] alone cannot be assigned a truth-value. I see where you were confused. I wasn't being precise when I said that [itex](\exists x \in A)[/itex] can be replaced by [itex](\exists x)(x \in A)[/itex].
    Yes.
    If E is empty though, then the sentence:

    There exists x in E, T

    is the sentence:

    There exists an element x in E such that x satisfies the condition T

    but if there is no element in E satisfying the condition T, or any condition at all, since there is no element in E at all!
    Well the difference should be obvious (note that I mean S to refer to the same sentence in both expressions.
    Yeah, that seems right to me.
     
  12. Sep 14, 2005 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, there are good reasons to consider [itex](\exists x \in A)[/itex] an indivisible unit: a logic with unbounded quantifiers (like [itex](\exists x)[/itex]) is often more powerful than a logic without them, and there are circumstances where this extra power is undesirable.
     
  13. Sep 15, 2005 #12

    honestrosewater

    User Avatar
    Gold Member

    Okay, S containing no free variables was the important part. S contains only individuals or bound variables, so for example, S could be Pa or [itex]\exists x(Px)[/itex]. On one interpretation, [itex]\exists x(Pa)[/itex] and [itex]\exists x (\exists x(Px))[/itex] reduce to Pa and [itex]\exists x(Px)[/itex].

    IMO, this interpretation makes sense. [itex]\exists x[/itex] only acquires meaning when it quantifies whatever variables fall within its scope. If S doesn't have any free variables, then no variables fall within the scope of [itex]\exists x[/itex] - so [itex]\exists x[/itex] doesn't mean anything in that case; It's superfluous. In other words, [itex]\exists x (Px)[/itex] and [itex]\forall x (Px)[/itex] say different things because some variable falls within the scope of the quantifiers. But [itex]\exists x (Pa)[/itex] and [itex]\forall x (Pa)[/itex] say the same thing, Pa, because no variables fall within the scope of the quantifiers. But that's only one way of looking at it.

    You say that you read [itex]\exists x \in E (S)[/itex] as "There exists an element x in E such that x satisfies the condition S". But it seems like you are really reading it as "There exists an element x in E and that x satisfies the condition S". ?? Also, since S can be assigned a truth-value, I'm not sure how it is a 'condition'.

    The interesting thing is that [itex]\exists x(S)[/itex] seems to be equivalent to [itex]\exists x \in U (S)[/itex], which, by your definitions (which seem fine to me),

    [tex](\exists x \in A)(\mathbf{P}) := (\exists x)((x\in A) \wedge \mathbf{P})[/tex]

    [tex](\forall x \in A)(\mathbf{P}) := (\forall x)((x \in A) \supset \mathbf{P})[/tex]

    means that [itex]\exists x(S)[/itex] is equivalent to [itex]\exists x (x \in U \wedge S)[/itex]. If U is non-empty, [itex]\exists x (x \in U)[/itex] is always true, so this interpretation doesn't really change anything. But if U is empty, [itex]\exists x (x \in U)[/itex] is always false, so [itex]\exists x (x \in U \wedge S)[/itex] is always false. Er, I forgot what my point was. I think it was that this interpretation assigns a truth-value to [itex]\exists x[/itex]. Can you distribute the quantifier in [itex]\exists x (x \in U \wedge S)[/itex], getting [itex](\exists x (x \in U)) \wedge (...))[/itex]?
     
    Last edited: Sep 15, 2005
  14. Sep 15, 2005 #13

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Do you see a real difference?
    Why not?
     
  15. Sep 16, 2005 #14

    honestrosewater

    User Avatar
    Gold Member

    I agree with you and your source on this:
    [tex]\begin{array}{|c|c|c|c|c|c|}\hline 1&2&3&4&5&6 \\ \hline \forall x (Px)&\neg (\exists x (\neg Px))&T&T&F&F\\\hline \neg (\forall x (Px))& \exists x (\neg Px)&F&F&T&T\\\hline \forall x (\neg Px)& \neg (\exists x (Px))&T&F&T&F\\\hline
    \neg(\forall x (\neg Px))&\exists x (Px)&F&T&F&T\\\hline \end{array}[/tex]
    This table is from an old post of mine - I've not been disagreeing with you about this. Columns 1 and 2 are equivalent. Column 3 lists the truth-values for the empty universe. But notice both in my table and your source that the quantifiers bind a variable.
    [itex]\mathbf{P}[/itex] could be Qb, where b is an individual. If the universe is empty, there are no individuals, so Qb is false, i.e., [itex]\mathbf{P}[/itex] is false. [tex](\forall x \in \{\})(\mathbf{P})[/tex] should then also be false. If [itex]\mathbf{P}[/itex] was Qx, then [tex](\forall x \in \{\})(\mathbf{P})[/tex] should be true. That is what I'm saying. Do you see a difference between [itex]\mathbf{P}[/itex] containing free variables and not containing free variables?
     
  16. Sep 16, 2005 #15

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Yes, I see. But I still think that [itex](\exists x)(P)[/itex] means that there exists an x such that P, and if there exists no x, then there does not exist an x such that P, in fact there does not an exist such that ~P, or Qx, or anything else. To say that there exists an x such that P is to say that there is some x satisfying the condition that P is true, where P may or may not contain x. If no x exists, then no x exists to satisfy that condition, or any condition.
     
  17. Sep 16, 2005 #16

    honestrosewater

    User Avatar
    Gold Member

    Yeah, I see what you're saying. If it isn't the free variable thing, I guess you take Ex to mean more than I take it to mean. But it seems like we've covered all of the bases and haven't really gotten anywhere, so I don't know what else to say.
    But if P is already true or false, how does it still need to be satisfied?

    Er, I don't know, maybe it's time to let it be.
     
  18. Sep 16, 2005 #17

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, maybe. I see your point, and what I'm suggesting is just a matter of what I'm reading into the sentences, I'm not sure on the technical details. I'll go hunting around the net to see if there is an answer either way to this question.

    I think I found one here. Go the webpage and search for (hit Ctrl+F) "alternative approach". Points 3 and 4 under that heading, in conjunction with the definitions for truth and falsity which follow, seem to support my idea that a universally quantified sentence over an empty domain is always true, and an existentially quantified sentence over an empty domain is always false. If you scroll up to the first definition for truth in L2 (this "alternative approach" you will search for is the alternative approach - 'Tarski style' - for defining truth for L2), you'll see something said about the truth of quantified sentences over empty domains, but that approach seems like it would take some more study to understand, whereas the Tarski style approach seems to give a very clear answer. I'm not sure if the non-Tarski approach actually says something different about the truth of such sentences because, as I said, it is a little harder to understand, but the page in general seems interesting so check it out if you like.
     
  19. Sep 17, 2005 #18

    honestrosewater

    User Avatar
    Gold Member

    Eh, I didn't read the whole page, but if I understood things correctly, yes, what they call predicates include formulas with no free variables. You can make up whatever you rules you want, of course, I just don't understand how that approach works - it doesn't make sense to me. I'm getting Hodges' book when the next edition comes out. He allows for empty domains, so I'll see if what he does makes sense to me.

    I have two problems with this approach:
    1) It seems to treat [itex]\exists x[/itex] sort of like, say, P &, where P is a formula (formula being the only strings that can be assigned truth-values). [itex]\exists x[/itex] cannot be assigned a truth-value; It is incomplete in some way. P & also cannot be assigned a truth-value; it is incomplete in some way. The difference is that while part of P & is a formula, in my view, no part of [itex]\exists x[/itex] is a formula. That is, you seem to read [itex]\exists x[/itex] as if it has a subformula: "There exists an x & this x ...". You take "there exists an x" to be a formula - in that it can be either true or false. If the universe is non-empty, you take "there exists an x" to be true, so you read [itex]\exists x[/itex] as T &, where T is a true formula; If the universe is empty, you take "there exists an x" to be false, so you read [itex]\exists x[/itex] as F &, where F is a false formula. This is the only way that I can make sense of [itex]\exists x[/itex] being able to affect the truth-value of any formula to which it's attached. Do you see the connection I'm making? The truth-value of T & Q depends only on Q, while the truth-value of F & Q is always F. This is the same way you use [itex]\exists x[/itex]. Is that the way you see things?
    I suppose you should then treat [itex]\forall x[/itex] as P v (P or), since F v Q depends on Q and T v Q is always T. But that gets into the second problem.

    2) There doesn't seem to be an analogous way to treat [itex]\forall x[/itex]. "For all x & this x..." isn't a natural reading. If [itex]\exists x[/itex] is making a claim about existence (if it's actually claiming that something does exist), then [itex]\forall x[/itex] must also make some kind of claim about existence, since only one of the quantifiers is necessary ([itex]\exists x(P) \Leftrightarrow \neg(\forall x (\neg P))[/itex] and so on). The normal reading of [itex]\forall x[/itex], "for all x", doesn't seem to make any claim about the existence of anything.? And in keeping with the treatment of [itex]\exists x[/itex] as P &, you should treat [itex]\forall x[/itex] as P v (or whatever), but it doesn't make sense to me to treat [itex]\forall x[/itex] as containing a subformula - or, rather, it makes even less sense than treating [itex]\exists x[/itex] as containing a subformula, or it doesn't make sense in the same way.

    Bah, I don't know if any of these explanations are making sense. The clearest way I can put it is that I think quantifiers don't say anything in themselves; They only say something about the variables to which they apply. So if they don't apply to any variables, they just don't say anything at all.

    Again, when the quantifiers come into play, I think we agree on their effect. I think we only disagree about when the quantifiers come into play (and when they are superfluous).
     
    Last edited: Sep 17, 2005
  20. Sep 17, 2005 #19

    honestrosewater

    User Avatar
    Gold Member

    Oh, I should add that in my main logic book, only the universal quantifier is used (in the object language) and its valuation (the s* function in the link) is:

    [tex](\forall x \alpha)^{v} = \left\{\begin{array}{cl}T & \mbox{ if } \alpha^{v(x/u)} = T \mbox{ for every } u \in U, \\ F & \mbox{ otherwise} \end{array}\right.[/tex]

    Where x is a variable, v is a valuation, [itex]\alpha[/itex] is a formula, u is an individual in the universe U, and (x/u) means that every instance of x has been replaced with u (this is very similar to the language in your link, if not the same). If there are no instances of x in [itex]\alpha[/itex], then replacing them with u doesn't make a difference (if it even makes sense). And if [itex]\alpha[/itex] is itself a universal formula, then you're just repeating a process that's already been done, so it still makes no difference - if I understand everything anyway.

    I can't read half of what my book says because I've forgotten many of the definitions. But one of the problems is
    show that if x is not free in [itex]\alpha[/itex], then [tex]\forall x \alpha \leftrightarrow \alpha \leftrightarrow \exists x \alpha[/tex].​
    Of course, they assume that U is non-empty, so this doesn't really help us. I'm just saying that my interpretation does work in that case. :smile:
     
  21. Sep 17, 2005 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Sigh, it's always hard to chime in when it's hard to figure out just what people are asking!

    (I hope I don't mix up proposition and predicate in what follows -- I always forget which is which)

    Ex is, in fact, incomplete. In the specification of the language of formal logic, the only place such a thing appears is part of a string that looks like Ex:P or Ex in A:P.

    I think it's incorrect to say that the quantifiers act on the variables: each quantifier Ex is something that operates on a predicate to produce a predicate of one fewer variables.

    (we always infer that in Ex:P that x is a free variable in P, even if it doesn't explicitly appear. I think I'm talking semantics here, and not syntax)


    I rather like the geometric interpretation of formal logic, which I first saw in the context of real algebraic geometry. Any predicate in n free variables corresponds to a surface in R^n. For example, the predicate:

    x*x + y*y = 1

    corresponds to the unit circle in R^2. (Of course, we can also treat this as a predicate of 3 free variables, x, y and z, and say that this is a cylinder in R^3, et cetera)

    The existential quantifier is just projection. The predicate:

    Ex: x*x + y*y = 1

    has one free variable -- it corresponds to the interval [-1, 1] in R. The operation of Ex is to project points in R^2 onto their second coordinate.

    The universal quantifier has a similar (but not as nice) geometric interpretation.

    I don't remember why I thought this was relevant, though. :frown:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?