# How to prove this?

1. Mar 20, 2005

### flying2000

{<->, ~} is not a complete set of connectives..
It seems that we can't use Propostions P is all true and thus lead to contradition since ~ can make it false.

Any suggestion?

2. Mar 21, 2005

### Owen Holden

1. {nor}
2. {nand}
3. {<-, True}
4. {->, False}
5. {~, v}
6. {~, &}
7. {~, ->}
8. {~, <-}

These sets of connectives are complete in the sense that all of the other propositional connectives can be defined by them.

{~, <->} and {~, xor} are not complete.

3. Mar 21, 2005

### honestrosewater

This is very sad because- if I have a specialty- it's finding things, and I can't find a decent definition of what it means for a set of connectives to be functionally complete. Does "functionally" refer to truth-functions? Does anyone have a definition to begin the proof with?

4. Mar 21, 2005

### BicycleTree

I did a Google search: http://www.cs.toronto.edu/~yilan/TA/236/note
"A 'complete' set of connectives is one which
can be used to build a formula equivalent to any given formula."

I looked some more on Google for ways to prove this type of thing, and although I have no experience, here is a way I think you could approach it: in some multivariate logical formulas, you can reverse the truth value of all variables and that will reverse the truth value of the formula. But with only ~ and <->, reversing the truth value of all variables must leave the truth value of the formula unchanged if the formula is multivariate.

5. Mar 21, 2005

### flying2000

Thanks!

Anyway, thanks a lot to all guys!

6. Mar 22, 2005

### honestrosewater

Well, every formula is equivalent to itself and there isn't any formula that is equivalent to every other formula. I think the author meant that, for each formula that can be written using connectives from a complete set of connectives, like {~, &, v, ->, <->}, you can write an equivalent formula using only connectives from a different set of connectives (the set you're trying to prove is complete). This isn't a good definition because it contains the term it's trying to define; How do you know the original set of connectives is complete? It only tells you something about relationships between complete sets of connectives.

7. Mar 22, 2005

### BicycleTree

Yes, that's what the author's sentence means (I don't think anyone was confused over that). It is not circular because it doesn't say "a formula equivalent to any given formula that can be written using a complete set of connectives." It says "equivalent to any given formula." The term "formula" has a clear definition, generally in terms of {~, &, v, ->, <->}, and without reference to completeness.

Your argument--as I interpret it--about whether formulas can represent all possible situations (i.e. whether they are intuitively "complete") just isn't relevant because the technical definition of a complete set of connectives doesn't have to comply with the intuitive idea of it.

Last edited: Mar 22, 2005
8. Mar 22, 2005

### honestrosewater

But "formula" occurs twice in the definition. Do both occurences have the same referent? You've just agreed that they don't. The first occurence refers to formulas of the set whose completeness is in question; The second occurence must refer to formulas of a set already known to be complete. If the second occurence doesn't refer to formulas of a set already known to be complete, the definition is wrong, since the second occurence could refer to formulas of an incomplete set of connectives.
I didn't mean the definition was circular. I suppose you could call the definition inductive; It says x is complete, and all sets bearing such and such relation to x are also complete. In that way, I guess it is close to a denotative definition. The problem I have with the definition is that it doesn't tell us what properties of x make x complete. I have seen a few connotative definitions of completeness, but they included terms I didn't know. Anyway, there is a connotative definition of completeness, and such a definition is preferable to a denotative one.
I didn't mean to make any such argument.

9. Mar 22, 2005

### BicycleTree

The definition does not state that the second use of the word "formula" must refer only to formulas in a complete set. (Also, completeness here is defined with respect to sets of connectives, not sets of formulas)

A stipulative definition can't be wrong unless it's paradoxical, and there isn't any immediately apparent paradox.

10. Mar 22, 2005

### honestrosewater

Then "formula" can refer to formulas of an incomplete set of connectives, making the definition wrong.
Where did I say otherwise?
This is clearly not a stipulative definition but a lexical one. If the context doesn't make it clear enough, the author says:
How could a stipulative definition already be known by other names?

11. Mar 22, 2005

### BicycleTree

All mathematical definitions are stipulative. A mathematical definition is not intended to explain common usage, but to precisely define the term as it will be used. The other names are simply where he refers to a stipulative term which he had not yet defined for his students. It doesn't mean that the forthcoming definition was based on common usage.

Yes, the word "formula" could indeed refer to formulas of an incomplete set of connectives. And this would be fine for the definition and not make it wrong.

However, it's easy to prove that {v, &, ~, -->, <-->} is a complete set of connectives. You start with the definition of a formula. I'll state it here, as best I remember it: if P is an atomic statement, then P is a formula. If R is a formula, then ~R is a formula. If R and S are formulas, then (R v S) is a formula, (R & S) is a formula, (R --> S) is a formula, and (R <--> S) is a formula, and anything that cannot be said to be a formula by these implications is not a formula. Call the set of all formulas F.

Now, given the set of connectives {v, &, ~, -->, <-->}, any atomic statement P can be built. If R can be built, then ~R can be built. If R and S can be built, then (R v S) can be built, (R & S) can be built, (R --> S) can be built, and (R <--> S) can be built, and anything that cannot be built by these implications cannot be built. Call the set of all formulas that can be built with {v, &, ~, -->, <-->} B. So B = F, so F is a subset of B, so any formula can be built with {v, &, ~, -->, <-->}, so {v, &, ~, -->, <-->} is a complete set of connectives.

12. Mar 22, 2005

### honestrosewater

What about this makes you think it was not intended to agree with the way the term is commonly used in logic? If you thought the definition wasn't meant to agree with common usage, then why did you post it without saying so?
It could also refer to formulas of all sets of connectives, both complete and incomplete.
You haven't defined what it means for a set of connectives to be complete so you haven't proven any set of connectives is complete.

13. Mar 22, 2005

### BicycleTree

I was going solely by the definition from the site: "A "complete" set of connectives is one which can be used to build a formula equivalent to any given formula." No further definition was needed for the proof.

If you believe there is a "common usage" of the word "complete" as it applies to a set of connectives which differs from that given definition, then what is it? (though I don't think it could properly be referred to as common usage, but rather as something like "common stipulation," since the meaning of mathematical terms is not defined by the way they are used)

14. Mar 22, 2005

### honestrosewater

But to what set of connectives was the second "formula" referring? If it was refering to {v, &, ~, -->, <-->}, what have you proved? Your definition?
I don't think it differs from the common definition- that's what I've been saying; It was meant to agree with common usage. The definition given, if you fill in the gaps and don't take it at face value, amounts to the same thing as other definitions. The definition given is still bad because you can't take it at face value, there are gaps to fill in, and it doesn't tell you what properties make a set of connectives complete.
Logic and math aren't exempt from lexical definitions. I doubt they could manage without them.
Can you answer my other questions?

15. Mar 23, 2005

### BicycleTree

The second use of the word "formula" was not referring to any set of connectives. It was referring to the already clearly (and arbitrarily) defined term "formula."

Logic and math depend entirely on stipulative definitions. There is no definition in math that is not stipulative.

I think I've indirectly answered all of your previous questions. If you think I haven't then please restate the question.

16. Mar 23, 2005

### honestrosewater

A set of formulas is defined using a set of connectives. If it refers to a set of formulas, it refers to the set of connectives used to define them. In fact, this is why the two occurences of "formula" can have different referents.
Mathematicians use terms, and I can give lexical definitions of the terms mathematicians use.
Nevermind, I think I'm about done arguing over this.

17. Mar 23, 2005

### Owen Holden

A set of connectives is truth functionally complete if any formula can be expressed using only the set of connectives. (given p, q, r, etc.)

For example:

{nor} is complete.

~p =df (p nor p)
p v q =df ~(p nor q)
p -> q =df ~p v q
p & q =df ~(~p v ~q)
(p nand q) =df ~(p & q)
p <-> q =df (p -> q) & (q -> p)
(p xor q) =df ~(p <-> q)

Any formula of propositional logic, can be expressed by using 'nor' alone.

..and so on.

18. Mar 23, 2005

### BicycleTree

Owen, that's the definition honestrosewater won't accept.

Honestrosewater, "formula" is defined in an absolute sense. Once you define a formula with {&, v, -->, ~, <-->}, then that set of connectives is not "just one way of looking at it." Once you've so defined it, that is the definition of a formula, and all further usage of the term "formula" refers back to that.

From a logical standpoint there is no reason why this definition--now from two sources, wherever Owen Holden got his--doesn't work. It does.

19. Mar 24, 2005

### honestrosewater

No, "formula" can be, and usually is, defined relative to some language containing some set of connectives.
But your definition contains two occurences of "formula" each with a different referent. Otherwise, it states that there is only one complete set of connectives. BTW, that is another problem with the definition.
"A 'complete' set of connectives is one which can be used to build a formula equivalent to any given formula." There is no formula that is equivalent to any given formula. The definition is indefensible if taken at face-value. Even after you fix it, it is still not a connotative definition, and I've already said that is my main complaint. I also already said the definition would work after it was fixed.
I gather the definition I am looking for will be stated in terms of truth-functions. I didn't know it would be such a big deal, so nevermind; I will try to find it myself.

20. Mar 24, 2005

### Bartholomew

I guess you're right, the word "formula" is used in two different senses. The second sense is according to the original formal definition of "formula," and the first sense is according to an analogous idea of formula for the set of connectives in question.

I looked on mathworld.wolfram.com for "formula" and (going to the "sentential formula" link) there is a more general definition of "formula." That may be what he is using.

"A 'complete' set of connectives is one which can be used to build a formula equivalent to any given formula"

To use more precise language, it obviously means, "A 'complete' set of connectives is one where, for any given formula, the set of connectives can be used to build a formula equivalent to it." The definition is unflawed and does not need to be fixed.

Represent your statement, "there is no formula that is equivalent to any given formula," using logic, with Fx means x is a formula. ~Ex(Ey(Fx & Fy & x = y))

This is obviously false. What you had meant to say was, "there is no formula that is equivalent to _every_ given formula." But "any" does not mean "every." If it did, then the statement "I don't have any apples" with Px meaning x is an apple and Hx = I have x, would be represented as ~(Ax(Px --> Hx)), which does not conflict with the statement "I have three apples."