how to prove this?

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?

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.

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?

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.

flying2000

Anyway, thanks a lot to all guys!

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.

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.

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.

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.

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?

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.

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.

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)

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?

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.

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.

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.