I just had a weird thought [Logic]

Prev: Please, DO NOT forget the only thing that matters on this planet........................……..
Next: Topos theory: axiom of choice implies a topos is Boolean

From: Marshall on 17 May 2010 12:08

On May 15, 10:03 pm, herbzet <herb...(a)gmail.com> wrote:
> Marshall wrote:
> > herbzet wrote:
> > > Marshall wrote:
> > > > herbzet wrote:
>
> > > > > etc., etc.!
>
> > > > > Plus ça change, eh?
> > > > > (herbzet's axiom in French)
>
> > > > "The more things change, the less they stay the same."
>
> > > Bonsoir, Marshall -- nice to hear from you. Thanks for your reply!
>
> > C'est mon plaisir.
>
> > Glad to see you back, and I hope (for entirely selfish reasons) you
> > will again be a frequent contributor.
>
> My goodness, what an agreeable remark! I'm touched! (Perhaps it's
> best not to inquire into your "entirely selfish reasons"(!))

No need to make it complicated: I like you, and the stuff you write,
is what I'm saying. :-)

> Basically, I don't think I'm quite up to be a frequent contributor
> for awhile longer -- though I intend to come back more often in
> the not-to-distant future. I just wanted to direct people's attention
> to the startling fact of non-Boolean-algebra structures for which
> classical propositional logic is a complete theory. I was hoping
> for some discussion by the smart guys of this, but it may take some
> time for people to get used to the idea.
>
> On the subject of models of classical (propositional) logic:
> both Schroder and C.I.Lewis (inventor, with C.H.Langford, of the
> S1-5 modal logics) tried to get rid of the models of Boole's
> algebra that have more than two elements (and so make things
> nicer for true/false logic) by including the formula A = (A = 1)
> in their axiomizations for propositional logic -- an axiomization
> that is otherwise identical to that for their algebra of classes.
> Later workers have passed over this meaningless axiom in charitable
> silence.
>
> Indeed, I myself have occasionally wondered how to get rid of all
> the "extra" models ever since I started to learn about logic.

Me too!

> Letting
> '[=]' be ascii-speak for the triple bar symbol of logical equivalence,
> my latest effort was to add the formula
>
> (A[=]B) v (B[=]C) v (C[=]A)
>
> as an axiom. "Hah!" I thought. "Not elegant, but that oughta do it!"
> thinks I -- but alas: that formula turns out to denote the universal
> class (as does any tautology interpreted as a class) when A,B,C are
> any classes, 'v' is interpreted as class union, and '[=]' is inter-
> preted (as is usual) as the complement of the symmetric difference.

Oh, my. The formula I lately came up with was:

[1] (x = y) v (x = z) v (y = z)

Where '=' means "equals."

Do you recall from some time ago my amusing axiom "x = y"?
Note that we can imagine an axiom generator with the intent
of restricting the cardinality of the domain of any model.
To restrict the domain to n elements, use n+1 variables
in the form of a big disjunction of equalities of every pair
of variables. Thus "x=y" limits the domain to 1 element;
[1] to two elements, etc. It's a general approach.

I didn't delve too deeply into the idea; in fact the above
paragraph marks the first time I ever wrote it down. But
the obvious flaw in the idea is that boolean algebra is
supposed to be complete, yet it has models of cardinality
2, 4, 8, etc., but it certainly *seemed* to me that [1] above
was true in 2-valued boolean algebra, but not in 4, 8, etc.
If it was true it ought to be provable, but it couldn't be provable
if it wasn't true for 4, 8, etc. A very annoying internal
inconsistency in my thoughts which I didn't have time to
track down.

> Then the penny finally dropped: classical propositional logic is Post
> complete -- adding *any* formula as an axiom that is not already a
> theorem makes the logic inconsistent: every formula then becomes
> provable. The "extra" models cannot be gotten rid of by adding
> new axioms, except at the cost of inconsistency (and thus having
> no models at all).
>
> What an exciting life I lead!

This rather reminds me of the Lowenheim-Skolem theorem.
But it's not exactly the same, is it, because we're discussing
finite models.

[In another post, you wrote:]

> With a tautology, we can validly substitute any formula phi
> for any propositional variable w in the tautology, provided
> that we uniformly substitute phi for every occurrence of w
> in the tautology.

So at 4 AM this morning, it hit me: my idea for restricting
cardinalities with variables was based on the assumption
that those variables would be substituted only with single
valued terms. And in fact, [1] works exactly as designed
in many cases.

I'm not sure I've got this exactly right, but it seems like
if x, y, and z are replaced by terms with no variables in
them, or by terms with no more than 1 variable total, or
by terms with no variables in common, then it will work
as designed. These are the cases in which each line of
the truth table will have the property that the substituted
terms are sufficiently independent as to allow the intended
3-way exclusion to "work."

If not, then what is being substituted is not a plain value
from the domain, but rather a function of the assignment
to variables. So if our 3 terms are

x <- a and b
y <- a or b
z <- a xor b

it's as if we're substituting these 3 functions, and thus, even
though the underlying *domain* has cardinality 2, the set
of arity-2 functions over that cardinality-2 domain has cardinality
16. And [1] won't hold over a cardinality-16 domain.

That's not quite saying it right, either, because it doesn't
capture the dependence/independence of the variables
being substituted, but it's the best I can do on a morning
where I woke up at 4 AM.

Must run; hope you find this vaguely enjoyable.

Marshall

From: herbzet on 18 May 2010 04:58

Marshall wrote:
> herbzet wrote:

> > Indeed, I myself have occasionally wondered how to get rid of all
> > the "extra" models ever since I started to learn about logic.
>
> Me too!
>
> > Letting
> > '[=]' be ascii-speak for the triple bar symbol of logical equivalence,
> > my latest effort was to add the formula
> >
> > (A[=]B) v (B[=]C) v (C[=]A)
> >
> > as an axiom. "Hah!" I thought. "Not elegant, but that oughta do it!"
> > thinks I -- but alas: that formula turns out to denote the universal
> > class (as does any tautology interpreted as a class) when A,B,C are
> > any classes, 'v' is interpreted as class union, and '[=]' is inter-
> > preted (as is usual) as the complement of the symmetric difference.
>
> Oh, my. The formula I lately came up with was:
>
> [1] (x = y) v (x = z) v (y = z)
>
> Where '=' means "equals."

Again, great minds think alike.

I took the trouble in my previous post to use the triple bar symbol
of logical equivalence '[=]', which is identical in meaning to the
symbol for bi-implication: '<->'. Although the two symbols
are identical in meaning, sometimes one wishes to connote logical
equivalence more than mutual implication, as I wanted to above.

Standardly, /propositional logic/ does not even include
the symbol of mathematical identity '=' in its language,
although /Boolean algebra/, to which it is extremely similar,
is routinely presented as an equational system, and uses '='
like any other branch of mathematics.

For many purposes, the distinction doesn't matter; I
have posted many posts to sci.logic using '=' for '[=]'
(or for '<->') and it usually doesn't make any real
difference to the subject being discussed.

However, in a recent post of mine to sci.logic "Classical logic
is not distributive" news:4BEB8FDF.D134B296(a)gmail.com I reference
a paper by Pavicic and Megill which, in part, is precisely about
models of classical propositional logic and the fact that (surprisingly)
propositional logic has models that are *not* Boolean algebras.

And part of the reason for that appears to be, to my inexpert
eye, the fact that the system of Boolean algebra is an equational
system, and propositional logic is not.

So as we're talking in this thread about models of propositional
logic, I'm being newly careful to distinguish between '[=]' and
'='.

Let me be clear: the models of boolean algebra are, of course,
Boolean algebras. The models of classical propositional logic
include Boolean algebras but also, apparently, structures that
Pavicic and Megill call weakly distributive ortholattices.
I am unclear on whether these two types of structures exhaust
the models of classical propositional logic.

The axiom [1] you suggest is not statable in the standard language
of propositional logic, since that language lacks the symbol '='.
However, the axiom is statable in ordinary first-order logic
w/identity, and would work just as intended:

[2] AxAyAz [(x = y) v (x = z) v (y = z)]

This would force the domain of discourse to have no more than two members.

> Do you recall from some time ago my amusing axiom "x = y"?

Yes, in another debate with Nam.

> Note that we can imagine an axiom generator with the intent
> of restricting the cardinality of the domain of any model.
> To restrict the domain to n elements, use n+1 variables
> in the form of a big disjunction of equalities of every pair
> of variables. Thus "x=y" limits the domain to 1 element;
> [1] to two elements, etc. It's a general approach.

Right -- oughta work.

> I didn't delve too deeply into the idea; in fact the above
> paragraph marks the first time I ever wrote it down. But
> the obvious flaw in the idea is that boolean algebra is
> supposed to be complete,

Actually, I'm not sure whether /boolean algebra/ is complete --
I never thought about it. I know that /propositional logic/ is
complete in several distinct technical senses of the term "complete".

We're very used to thinking of boolean algebra and propositional logic
as "the same thing", more or less -- differing negligibly only in
notation. The paper by Pavicic and Megill suggests there is a subtle
but non-negligible difference.

> yet it has models of cardinality
> 2, 4, 8, etc., but it certainly *seemed* to me that [1] above
> was true in 2-valued boolean algebra, but not in 4, 8, etc.

If you changed '=' to '[=]' (or to '<->') you'd be wrong: thus
re-written, your axiom [1] would be true in all those models --
it would be a tautology of propositional logic.

> If it was true it ought to be provable, but it couldn't be provable
> if it wasn't true for 4, 8, etc. A very annoying internal
> inconsistency in my thoughts which I didn't have time to
> track down.

Yes, I see.

Here's a question for you: How are you intending your axiom to
be interpreted? In standard treatments of boolean algebra, the
join 'x v y' is a term, not a sentence, and would be used as a
noun in a sentence, like "(x v y) = (y v x)" with '=' as the verb.

(See, e.g., http://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29 )

Whereas in your axiom it appears that you want 'v' to be a
sentential connective, making a compound sentence out of three
sentences 'x=y','x=z','y=z'. This is not actually illegal, but
you wouldn't expect to see an axiom of this form in standard
presentations of boolean algebra -- 'v' would probably be used
to combine terms with terms to make compound terms, rather than
combining sentences with sentences to make compound sentences.

As I said above, it would be perfectly fine and meaningful in the
context of a first-order language, with 'v' taken as a sentential
connective. But here, your meaning is somewhat ambiguous to me.

> > Then the penny finally dropped: classical propositional logic is Post
> > complete -- adding *any* formula as an axiom that is not already a
> > theorem makes the logic inconsistent: every formula then becomes
> > provable. The "extra" models cannot be gotten rid of by adding
> > new axioms, except at the cost of inconsistency (and thus having
> > no models at all).
> >
> > What an exciting life I lead!
>
> This rather reminds me of the Lowenheim-Skolem theorem.
> But it's not exactly the same, is it, because we're discussing
> finite models.

No, not the same. But we're discussing an algebra with many
models, and it's of interest to find out whether some extension
of the algebra can be made categorical, i.e., having one model
"up to isomorphism", as the saying goes -- and if not, why not.

> [In another post, you wrote:]
>
> > With a tautology, we can validly substitute any formula phi
> > for any propositional variable w in the tautology, provided
> > that we uniformly substitute phi for every occurrence of w
> > in the tautology.
>
> So at 4 AM this morning, it hit me: my idea for restricting
> cardinalities with variables was based on the assumption
> that those variables would be substituted only with single
> valued terms.

Not sure what you mean by "single-valued terms", unless you
just mean "other variables".

The use of variables makes the value of a term systematically
ambiguous. Once values are assigned to the variables, the
term resolves to a single value.

The exceptions are tautologies and contradictions, which are
constant functions, and resolve to a single value regardless
of what values their arguments might take.

The rest of your post sort of confuses me -- I'm not
sure about whether we're "in" propositional logic,
first-order logic, or (boolean) algebra.

In any case, you got my point correctly: If we add a new "postulate"
to classical propositional logic, we cannot operate on it as we would
do with other axioms -- there must be some restrictions on the allowed
operations or the system blows up.

> And in fact, [1] works exactly as designed
> in many cases.
>
> I'm not sure I've got this exactly right, but it seems like
> if x, y, and z are replaced by terms with no variables in
> them, or by terms with no more than 1 variable total, or
> by terms with no variables in common, then it will work
> as designed. These are the cases in which each line of
> the truth table will have the property that the substituted
> terms are sufficiently independent as to allow the intended
> 3-way exclusion to "work."
>
> If not, then what is being substituted is not a plain value
> from the domain, but rather a function of the assignment
> to variables. So if our 3 terms are
>
> x <- a and b
> y <- a or b
> z <- a xor b
>
> it's as if we're substituting these 3 functions, and thus, even
> though the underlying *domain* has cardinality 2, the set
> of arity-2 functions over that cardinality-2 domain has cardinality
> 16. And [1] won't hold over a cardinality-16 domain.
>
> That's not quite saying it right, either, because it doesn't
> capture the dependence/independence of the variables
> being substituted, but it's the best I can do on a morning
> where I woke up at 4 AM.

Not bad for the middle of the night.

> Must run; hope you find this vaguely enjoyable.

Sure -- I think we're on slightly different pages, though.

--
hz

From: George Greene on 19 May 2010 22:06

On May 11, 9:07 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote:
> Sure. But why should you think it a physical matter?
> It's a mathematical triviality.

This from the person who taught me that "finitude is not first-order
definable"
??

From: Aatu Koskensilta on 20 May 2010 18:01

George Greene <greeneg(a)email.unc.edu> writes:

> On May 11, 9:07�am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote:
>> Sure. But why should you think it a physical matter? It's a
>> mathematical triviality.
>
> This from the person who taught me that "finitude is not first-order
> definable"
> ??

Yes? I'm afraid I don't quite see the connection.

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

From: Ross A. Finlayson on 20 May 2010 23:12

First | Prev | Next | Last
Pages: 1 2 3 4 5 6 7 8 9 10 11
Prev: Please, DO NOT forget the only thing that matters on this planet........................……..
Next: Topos theory: axiom of choice implies a topos is Boolean