Frankl, My Dear • 3

Re: Dick Lipton & Ken Regan(1)(2)

Here’s a few pages on differential logic, whose ideas I’ll be trying out in the present setting:

I next need to look at the following “key lemma” from (2) and see if I can wrap my head, or at least my own formalism, around what it says.

Lemma.  Let {f(x_{1}, \dots, x_{n})} be a Boolean function and let {x_{i}} be fixed.  Then the Boolean inputs can be partitioned into six sets:

\displaystyle A_{0}, A_{1}, B_{0}, B_{1}, C_{0}, C_{1}.

These sets have the following properties:

  1. The variable {x_{i}} is equal to {0} on {A_{0} \cup B_{0} \cup C_{0}}.
  2. The variable {x_{i}} is equal to {1} on {A_{1} \cup B_{1} \cup C_{1}}.
  3. The union {A_{0} \cup A_{1}} is equal to {J_{i}}.
  4. The function is always {0} on {B_{0} \cup B_{1}}.
  5. The function is always {1} on {C_{0} \cup C_{1}}.
  6. Finally {|A_{0}| = |A_{1}|}  and  {|B_{0}| = |B_{1}|}  and  {|C_{0}| = |C_{1}|}.

This may take a while …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | 10 Comments

Consequences of Triadic Relation Irreducibility • 2

From time to time I come to the realization that there are ways of reading Peirce that make no sense to me.  When I stop to think about the potential sources of that evident divergence from common sense, the first thing that comes to mind is the fact that people come to reading Peirce with so many different aims, backgrounds, and collateral experiences with the objects that he wraps his signs and ideas around.

Thinking about that leads to all sorts of questions that I see no way of beginning to address with any sense of coherence.  All I can do is try to give a good account of what makes sense to me and why.  My experience with failures to communicate over many trials tells me that the biggest and most numerous rifts in our several understandings of Peirce all point back to the visions of relations, triadic relations, and triadic sign relations that dance in our various and sundry heads.

So that is what I’ll take up first …

Posted in C.S. Peirce, Logic, Logic of Relatives, Mathematics, Peirce, Peirce List, Philosophy, Pragmatism, Relation Theory, Semiotics, Sign Relations, Thirdness, Triadic Relations, Triadicity | Tagged , , , , , , , , , , , , , | Leave a comment

Consequences of Triadic Relation Irreducibility • 1

2014 Sep 10

I will have to be out of the loop for some days, but this post will give me a peg on which I can hang a few thoughts via mobile device that have been tugging at the edge of my mind for a while.

2014 Sep 13

I am still a bit loopy from jumping through a triple of orthogonal loops and it’s taking me longer to get back in the saddle than I thought it might, so let me just paste in a passel of links to a collection of background materials I’ve referenced before, a lot of it work-in-hopeful-progress, the rest of it more polished, published, and with luck less perishable.

Basic Concepts

Related Readings

Posted in C.S. Peirce, Logic, Logic of Relatives, Mathematics, Peirce, Philosophy, Pragmatism, Relation Theory, Semiotics, Sign Relations, Thirdness, Triadic Relations, Triadicity | Tagged , , , , , , , , , , , , | Leave a comment

Frankl, My Dear • 2

Re: Dick Lipton & Ken Regan(1)(2)

Supplied by the cache of definitions from Post 1, I can return to the passage from (2) that seemed to jog a bit of memory and see if what I imagined I saw there makes any sense.

Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}} — we are open to suggestions. Any?

I responded to their query about a better notation for {J_{i}} in a series of comments along the following lines:

I think {J_{i}(f)} is just the set of places where the partial differential of {f} with respect to {x_i} is {1}.

See Tables A9 and A10 in my article on Differential Logic and Dynamic Systems.

For example, look at {f_8 (x, y),} which is just the logical conjunction {xy}.

In this case, {\partial_x f = y}.

This means that crossing the boundary of {x} will change the value of {f} exactly in those places where {y} is true.

The See a Number, Make a Set principle leads to the following observation, that an arbitrary set of cells in a venn diagram or an arbitrary set of vertices in a {k}-cube is described by a proposition or a boolean function as its fiber of {1}, so the above types of differential operators take us from propositions to propositions, in other words, they stay within the same general datatype.

To be continued …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | 10 Comments

Frankl, My Dear • 1

Re: Dick Lipton and Ken Regan(1)(2)

I need to think a little about the context Lipton and Regan have wrapped around the Frankl Conjecture, if not exactly about the problem itself.  This will be a scratch-worky post-in-progress (PIP❢), or a series of posts, and I may even delete it down the road if it runs out of gas or turns into too much nonsense.

Just to get started, let me post the passage from the 2nd of the above articles where I thought I spied something familiar, though it was late, past my bedtime, and I was pondering weak and weary, etc.

Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}} — we are open to suggestions.  Any?

In order to understand the above formulas, we have to back up a little and pick up a couple of earlier definitions, rephrasing them slightly in the style of notation to which I would like you to become accustomed.

Let {\mathbb{B} = \{0,1\}} and let {f : \mathbb{B}^{n} \to \mathbb{B}} be a boolean function.  The influence of the {i}^\text{th} input of {f} is defined by

\displaystyle I_{i}(f) = \mathrm{Prob}_{x}[ f(x) \neq f(x^{i}) ],

where {x^{i}} is equal to

\displaystyle x_{1}, \dots, x_{i-1}, \neg x_{i}, x_{i+1}, \dots, x_{n}.

There is another way of expressing the bit flip operation {x \mapsto x^i} I like a bit better.  Here is the formal definition, using {j} instead of {i} as the index of the indicated variable.

Definition.  Let the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} be defined for each integer {j} in the interval {[1, k]} by the following equation:

{\lnot_j (x_1, \ldots, x_j, \ldots, x_k) ~=~ x_1 \land \ldots \land x_{j-1} \land \lnot x_j \land x_{j+1} \land \ldots \land x_k}.

It is conventional to write logical conjunction as multiplication, with or without a dot between conjuncts.  It is also convenient in many contexts to write logical negation {\lnot x_j} with a tilde as {\tilde{x}_j} or with distinctive parentheses as {\texttt{(} x_j \texttt{)}}.  Thus we may see the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} written in either of the following forms:

\begin{matrix}  \lnot_j (x_1, \ldots, x_j, \ldots, x_k)  & = &  x_1 x_2 \ldots x_{j-1} \tilde{x}_j x_{j+1} \ldots x_{k-1} x_k  \\[4pt]  & = &  x_1 x_2 \ldots x_{j-1} \texttt{(} x_j \texttt{)} x_{j+1} \ldots x_{k-1} x_k  \end{matrix}

Visually speaking, {\lnot_j (x_1, \ldots, x_k)} is a singular proposition which picks out a single cell {x} of the associated venn diagram, namely, the cell where {x_j} is false and all the rest of the {x_i} are true.  In other work, I used the above notations for {\lnot_j} in defining minimal negation operators, which may eventually find use in this discussion.

This looks like a good place to break and start a second post in the series.

To be continued …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | 11 Comments

Skiourosemiosis • 1

The resultant metaphysical problem now is this:
Does the man go round the squirrel or not?

— William James • Pragmatism

Differential Analysis of Propositions and Transformations

Posted in C.S. Peirce, Differential Logic, Inquiry, Inquiry Driven Systems, Logic, Peirce, Pragmatic Maxim, Pragmatism, Semiotics, Skiourosemiosis, William James | Tagged , , , , , , , , , , | 3 Comments

C.S. Peirce • Syllabus • Selection 1

Selection from C.S. Peirce, “A Syllabus of Certain Topics of Logic” (1903)

An Outline Classification of the Sciences

180.   This classification, which aims to base itself on the principal affinities of the objects classified, is concerned not with all possible sciences, nor with so many branches of knowledge, but with sciences in their present condition, as so many businesses of groups of living men.  It borrows its idea from Comte’s classification;  namely, the idea that one science depends upon another for fundamental principles, but does not furnish such principles to that other.  It turns out that in most cases the divisions are trichotomic;  the First of the three members relating to universal elements or laws, the Second arranging classes of forms and seeking to bring them under universal laws, the Third going into the utmost detail, describing individual phenomena and endeavoring to explain them.  But not all the divisions are of this character.

The classification has been carried into great detail;  but only its broader divisions are here given.

181.   All science is either,

  • A.  Science of Discovery;
  • B.  Science of Review;  or
  • C.  Practical Science.

182.   By “science of review” is meant the business of those who occupy themselves with arranging the results of discovery, beginning with digests, and going on to endeavor to form a philosophy of science.  Such is the nature of Humboldt’s Cosmos, of Comte’s Philosophie positive, and of Spencer’s Synthetic Philosophy.  The classification of the sciences belongs to this department.

183.   Science of Discovery is either,

  • I.  Mathematics;
  • II.  Philosophy;  or
  • III.  Idioscopy.

184.   Mathematics studies what is and what is not logically possible, without making itself responsible for its actual existence.  Philosophy is positive science, in the sense of discovering what really is true;  but it limits itself to so much of truth as can be inferred from common experience.  Idioscopy embraces all of the special sciences, which are principally occupied with the accumulation of new facts.

185.   Mathematics may be divided into

  • a.  the Mathematics of Logic;
  • b.  the Mathematics of Discrete Series;
  • c.  the Mathematics of Continua and Pseudo-continua.

I shall not carry this division further.  Branch b has recourse to branch a, and branch c to branch b.

186.   Philosophy is divided into

  • a.  Phenomenology;
  • b.  Normative Science;
  • c.  Metaphysics.

Phenomenology ascertains and studies the kinds of elements universally present in the phenomenon;  meaning by the phenomenon, whatever is present at any time to the mind in any way.

Normative science distinguishes what ought to be from what ought not to be, and makes many other divisions and arrangements subservient to its primary dualistic distinction.

Metaphysics seeks to give an account of the universe of mind and matter.

Normative science rests largely on phenomenology and on mathematics;  metaphysics on phenomenology and on normative science.

(Peirce, CP 1.180–186, EP 2.258–259, Online)

Notes

Collected Papers 1

  • Pp. 5–9 of A Syllabus of Certain Topics of Logic, 1903, Alfred Mudge & Son, Boston, bearing the following preface:  “This syllabus has for its object to supplement a course of eight lectures to be delivered at the Lowell Institute, by some statements for which there will not be time in the lectures, and by some others not easily carried away from one hearing.  It is to be a help to those who wish seriously to study the subject, and to show others what the style of thought is that is required in such study.  Like the lectures themselves, this syllabus is intended chiefly to convey results that have never appeared in print;  and much is omitted because it can be found elsewhere.”

Essential Peirce 2(a)(b)

References

  • Peirce, C.S., Collected Papers of Charles Sanders Peirce, vols. 1–6, Charles Hartshorne and Paul Weiss (eds.), vols. 7–8, Arthur W. Burks (ed.), Harvard University Press, Cambridge, MA, 1931–1935, 1958. Volume 1 : Principles of Philosophy, 1931.
  • Peirce Edition Project (eds., 1998), The Essential Peirce, Selected Philosophical Writings, Volume 2 (1893–1913), Indiana University Press, Bloomington and Indianapolis, IN.
Posted in C.S. Peirce, Classification, Foundations of Mathematics, Logic, Mathematics, Metaphysics, Normative Science, Peirce, Phenomenology, Philosophy, Philosophy of Mathematics, Philosophy of Science, References, Science, Sources | Tagged , , , , , , , , , , , , , , | 12 Comments

¿Shifting Paradigms? • 4

Re: Foundational Crisis?Harvey Friedman

2014 Aug 22

Shock and surprise are relative to a prior state of belief.  The belief that mathematics reduces to logic, and that of a purely deductive sort from given axioms, seems to be a fairly recent notion and never universally shared.  All of which brings us back to the question of locating mathematical inquiry in relation to inquiry in general.

Jon Awbrey

Posted in C.S. Peirce, Foundations of Mathematics, Inquiry, Logic, Mathematics, Model Theory, Paradigms, Peirce, Programming, Proof Theory | Tagged , , , , , , , , , | Leave a comment

¿Shifting Paradigms? • 3

Re: What Is Good Mathematics?Harvey Friedman

2014 Aug 17

Speaking of mathematics in the context of “general intellectual activity” brings to mind Raymond Wilder’s take on “mathematics as a cultural system”.

I would like to keep that in mind, if on a back burner, and focus on a more directed species of intellectual activity that goes under the name of inquiry, the flower of which species we know as scientific method, however much method or madcap various lights may see in it.  Whatever the case, that brings us to the task of placing mathematical inquiry within the sphere of inquiry in general.

Here I can do no better than recommend C.S. Peirce’s theory of inquiry as one of the best tacks we can take for approaching this task.

Jon Awbrey

Posted in C.S. Peirce, Foundations of Mathematics, Inquiry, Logic, Mathematics, Model Theory, Paradigms, Peirce, Programming, Proof Theory | Tagged , , , , , , , , , | Leave a comment

Forest Primeval → Riffs & Rotes

Re: Shifting Paradigms?(1)(2)(3)(4)(5)(6)

Prompted by the discussion of Catalan numbers on the Foundations Of Math List, I dug up a few pieces of early correspondence and later discussions bearing on the correspondences between graph theory and number theory which have occupied me these many years and I began putting reformatted transcripts at the following sites.

Posted in Algebra, Animata, Arithmetic, C.S. Peirce, Catalan Numbers, Combinatorics, Forest Primeval, Foundations of Mathematics, Gödel Numbers, Graph Theory, Group Theory, H.W. Gould, Integer Sequences, Logic, Martin Gardner, Mathematics, Neil Sloane, Number Theory, Paradigmata, Planted Plane Trees, Riffs and Rotes | Tagged , , , , , , , , , , , , , , , , , , , , | Leave a comment