Re: 3 basic metalogic questions.
From: Jeffrey Ketland (ketland_at_ketland.fsnet.co.uk)
Date: 06/04/04
- Next message: |-|erc: "Re: resolving Will's misunderstanding"
- Previous message: Earle Jones: "Re: Deep Thoughts # 5: We Cannot Output Anything"
- In reply to: Yarden Katz: "3 basic metalogic questions."
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 4 Jun 2004 02:24:37 +0100
Yarden Katz wrote in message <86brk0p69b.fsf@umd.edu>...
>Hi,
>
> I have three quick questions on metalogic. First, my textbook asks to:
>
> 10.9 Show that if T U {~(B & C)} is satisfiable, then either T U
> {~B} is satisfiable or T U {~C} is satisfiable.
Suppose that T U {~(B & C)} is satisfiable. So, there is a model M of T U
{~(B & C)}. So, M satisfies T and M satisfies ~(B&C). So, M satisfies T and
satisfies ~Bv~C. So, M satisfies T and either satisfies ~B or ~C. So, either
M satisfies T U {~B} or M satisfies T U {~C}. So, either T U {~B} is
satisfiable or T U {~C} is satisfiable.
> It strikes me that the book's example proofs (which are usually 2-5
> sentences long) are really informal - maybe it's the text, or maybe
> that's just the way these type of things are proven. In any event, I
> did this exercise, but I can't help but feel as if I'm sort of
> "cheating" by kind of restating what I'm asked to prove. If the
> nature of these proofs as presented was more formal, I'd feel more
> confident. However, when I compare my proof to the other examples,
> I don't think that I'm any more informal. Here's my proof:
>
> For T U {~(B & C)} to be satisfiable, it cannot be that B(c) is
> true *and* C(c) is true, where c is the denotation of any element
> in our domain. In other words, it must be that:
What is B(c)? That doesn't make good sense here. Normally B(c) means the
result of substituting the constant c for any occurrence of a free variable
in B. But here B is a sentence, without any free variables.
> 1. ~(B(c) & C(c)) (again for c being the denotation of any and
> all elements in our domain)
>
> [note that when I say B(c) I really mean something like B^c or
> B^m, i.e., B in the interpretation c or in the interpretation m -
> I just thought the function notation is clearer (is it?)]
No. It's very unclear.
> From this it follows that,
>
> 2. ~(~B(c) v ~C(c))
>
> For (2) to be satisfiable, it must be that either T U {~B} or T U
> {~C}. Q.E.D.
>
> Is this correct? Is it necessary to get more
> formal about proofs like this, that clearly don't take a lot ingenuity
> or insight?
The proof I gave above is OK.
> A second problem was:
>
> 10.10(f) "Show that: If c does not occur in F(x) or G(x), and F(c) and
G(c)
> are equivalent, then AxF(x) and AxG(x) are equivalent,
> and similarly for E."
>
> What exactly do they mean by "if c does not occur in F(x) or G(x)"?
> Does it mean that c is not one of the terms in the actual sentence
> F(x)? Can someone give a hint about approaching this problem?
c is a constant (i.e., a name, like "Chumbawumba" or "Chomsky"). F(x) is a
formula which has at least the variable x free. The formula may in general
contain the constant c. For example, the formula F(x) might be Ay(R(c, y)
<-> ~R(x, y)), which contains c. However, in this case, you are told that
F(x) does not contain c.
You are told that F(c) is equivalent to G(c). Let M be an interpretation of
the language which does not specify an interpretation (denotation) of the
constant c. You are told that F(c) is equivalent to G(c). So, F(c) and G(c)
have the same truth value in M *no matter* how c is interpreted. Since c can
be taken to denote *any element* of the model M, it follows that the
formulas F(x) and G(x) are equivalent (technically, they define the same
subsets F^M and G^M of the model). So, Ax F(x) and Ax G(x) are equivalent
also.
> Finally, some of the exercises in my book, like this one:
>
> "Show that EyAxR(x, y) implies AxEy(x, y)"
You meant to say that EyAxR(x, y) implies AxEyR(x, y).
I call this the God argument:
"There is someone (e.g., God) who loves everyone"
implies
"Everyone is loved by someone"
> Are really so obvious/superficial that I am kind of at loss on how to
approach
> them in a proof. I think I could probably do the above indirectly
> to somehow get a contradiction, but if I were not allowed to do it
> indirectly I'd really have no idea where to start. Can someone shed
> some light of this?
Model-theoretically, you can do it like this (my notation may differ a bit
from BBJ):
Suppose you have an interpretation M of your language containing the
predicate R in which EyAxR(x, y) is true. So, there is an element m of
dom(M) such that AxR(x, y) is true in the assignment val, where val(y) = m.
So, for any element m', R(x, y) is true in the assignment val*, where
val*(x) = m' and val*(y) = m. But, in general, if R(x, y) is true in some
assignment v, then the formula EyR(x, y) is true in that assignment v too.
So, for any element m', EyR(x, y) is true in the assignment val*, where
val*(x) = m'. So, AxEyR(x,y) is true in M.
Since this works for any model M, we may conclude that EyAxR(x, y) implies
AxEyR(x, y)
Deductively you can do it like this, constructing a "tree":
1. EyAxR(x, y) premise
2. ~AxEyR(x, y) negated conclusion
|
3. AxR(x, a) instantiate (1) using new constant a
4. ExAy~R(x,y) convert negated quantifiers in (2)
5. Ay~R(b,y) instantiate (4) using new constant b
6. R(b,a) instantiate (3) using b
7. ~R(b,a) instantiate (5) using a
X (contradiction)
--- Jeff
- Next message: |-|erc: "Re: resolving Will's misunderstanding"
- Previous message: Earle Jones: "Re: Deep Thoughts # 5: We Cannot Output Anything"
- In reply to: Yarden Katz: "3 basic metalogic questions."
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
