Logic - 2018-03-16

user21820

01:11

@famesyasd Which derivative? We have 3 variables t,x,y, so you need to specify which of the 6 possible derivatives between them you are talking about.

Mar 11 at 12:53, by user21820

Take real parameter t. Let x = sin(t)^3 and y = cos(t)^3. (So x,y are variables that vary with t.) Then everywhere dx/dt = 3·sin(t)^2·cos(t) and dy/dt = −3·cos(t)^2·sin(t). In particular, if t is a multiple of π/2, then dx/dt = dy/dt = 0. This is probably what you were talking about. What does it mean? Well if t is time, then the point (x,y) always moves with a well-defined velocity, which is zero at each cusp (corner), meaning that it comes to a (momentary) stop at that point!

Mar 11 at 12:55, by user21820

You should also see that you are making a logical error when comparing to dy/dx. In this framework, the chain rule states: Take variables x,y,z varying with parameter t. Whenever dy/dx and dz/dy are both defined, dz/dx = dz/dy · dy/dx.

Mar 11 at 12:56, by user21820

You definitely cannot apply it here to get dy/dx, because dt/dx is certainly not defined since dx/dt = 0.

> It also turns out that when t = 0 we have dx/dy = 0. Proof: As t → 0 we have the following. x ∈ (t+o(t))^3 ⊆ t^3+o(t^3). y ∈ (1−t^2/2+o(t^2))^3 ⊆ 1−t^2·3/2+o(t^2). Thus Δx/Δy ∈ ( t^3+o(t^3) ) / ( −t^2·3/2+o(t^2) ) ∈ −3t/2+o(t) → 0.

> And similarly when t = π/2 we have dy/dx = 0.

As you can see, I showed that some of those 6 derivatives exist, but I didn't claim all 6 exist.

Secret

01:27

Claim that I have no idea whether there exists a foundation that can prove it:

in Mathematics, 4 mins ago, by Secret

Still, it seems that without any axioms of infinite objects, it seems to be impossible to distinguish between an unbounded collection vs an (actual) infinite object

I think I need something like a "foundation of all foundations", which is an inconsistent notion since different foundations can be incompatible with each other

Secret

01:45

personal.psu.edu/t20/papers/infinity.ps

> Now, an important discovery of reverse mathematics is that large parts of contemporary mathematics are formalizable in RCA∗0, RCA0, and WKL0. This seems to include the applicable parts of mathematics. See also my paper [5]. Combining all of the

> above considerations, we see the possible outline of an objective justification of much of modern mathematics, especially the applicable parts of it. However, the prospects for an objective justification of actual infinity remain much more doubtful. This is the background of my yes/no question.

https://www.scientificamerican.com/article/infinity-logic-law/
> Meanwhile, forcing axioms, which deem the continuum hypothesis false by adding a new size of infinity, would also extend the frontiers of mathematics in other directions. They are workhorses that regular mathematicians “can actually go out and use in the field, so to speak,” Moore said. “To me, this is ultimately what foundations [of mathematics] should be doing.”

Do forcing even exists or is necessary in predicative foundations ?

quantamagazine.org/…

> Simpson considers the colorable, divisible infinite sets in RT22 “convenient fictions” that can reveal new truths about concrete mathematics. But, one might wonder, can a fiction ever be so convenient that it can be thought of as a fact? Does finitistic reducibility lend any “reality” to infinite objects — to actual infinity? There is no consensus among the experts.

> Avigad is of two minds. Ultimately, he says, there is no need to decide. “There’s this ongoing tension between the idealization and the concrete realizations, and we want both,” he said. “I’m happy to take mathematics at face value and say, look, infinite sets exist insofar as we know how to reason about them. And they play an important role in our mathematics. But at the same time, I think it’s useful to think about, well, how exactly do they play a role? And what is the connection?”

It does seems if other infinite proofs can be reduced in terms of applications of $RT^2_2$ (I don't really know what that is yet), then perhaps, the embedding of actual infinity in our reality might be actually a bunch of objects interacting in some complicated manner

user21820

03:03

@Secret I don't know how much of forcing would go through. Certainly much of the set-theoretic stuff will not, but forcing has also been used in recursion theory and computability theory, and I think a lot of those will go through. In general, anything that only involves a countable recursion will probably go through.

@Secret RT[2,2] is a certain instance of Ramsey's theorem. You can look it up on wikipedia.

And all those stuff you saw about subsystems of second-order arithmetic (SOA) and RT[2,2] are concerning SOA, nowhere near set theory.

@Secret Foundation for all foundations is simply the meta-system MS. MS can correctly verify every proof over every practical formal system. This does not imply that MS can prove the consistency of every sound foundational system, because we do wish to believe that MS is itself sound, and so by the incompleteness theorem MS cannot prove itself sound.

Of course, we cannot combine alternative foundational systems, since as you know they can be incompatible.

Secret

Still, at least on top of my head, I cannot think of any foundation that allows the existence of an actual infinite object to be proven within the foundation itself, without first having an axiom that puts it in in the first place.

It seems that the notion of actual infinity is circular (to define it will need to reference to itself or other actual infinite objects) even in a formal sense, but I don't know how to prove/disprove that

user21820

03:19

@Secret Well, from a philosophical viewpoint it is obvious:

24

A: Does mathematics become circular at the bottom? What is at the bottom of mathematics?

Most set theories, such as ZFC, require an underlying knowledge of first-order logic formulas (as strings of symbols). This means that they require acceptance of facts of string manipulations (which is essentially equivalent to accepting arithmetic on natural numbers!) First-order logic does not ...

From a mathematical viewpoint, you can't actually 'prove' it because you need to work within an MS that already assumes or can prove the existence of a model of PA.

Secret

> So the issue dives straight into philosophy, because any proof in any formal system will already be a finite sequence of symbols from a finite alphabet of size at least two, so simply talking about a proof requires understanding finite sequences, which (almost) requires natural numbers to model.
This means that any meta system powerful enough to talk about proofs and 'useful' enough for us to prove meta theorems in it (If you are a Platonist, you could have a formal system that simply has all truths as axioms. It is completely useless.) will be able to do something equivalent to arithmeti…

If I understood this and what you just said above correctly, the existence of a model of PA cannot be proven without a notion of actual infinity?

because any finite statement can be modelled by the natural numbers (however unbounded but finite it is) and thus by the incompleteness theorem, they cannot prove a model of PA?

user21820

03:37

@Secret What does it mean by "they cannot prove"? The point is that any practical formal system you design will essentially be equivalent to a proof verifier program that must be run on an ideal computer (one with unbounded memory and time and so on).

Nobody has an ideal computer, so the very concept of "ideal computer" must necessarily be an abstract concept, which presupposes the existence of a collection of all finite strings and operations on them.

So it is clearly circular if you wish to use any formal system to prove that a model of PA exists.

Worse still, it also clearly shows that even to talk about the existence of a model of PA requires essentially assuming one exists!

Secret

@user21820 waaaahhhh, I did not expected that point....

user21820

This is what I meant by:

> simply talking about a proof requires understanding finite sequences, which (almost) requires natural numbers to model.

Secret

ah ok, I thought for that sentence we can get away with some unbounded but finite collection, hence a potential infinity (like arithmetical sets)

user21820

@Secret That notion seems contradictory. Every finite collection is bounded...

Potential infinity is not about being finite. It is about having a finite description that is 'constructive' in some sense.

Secret

So when we talk about an object having a finite but of unspecified (however large we want it to be) size, which notion of infinity are we using (cause that description appears in IST)?

user21820

03:47

@Secret You need to be careful with what you actually mean. Just because someone says that something in IST means "finite but unspecified size" does not imply that it is, nor that it makes sense to think that way. In fact, it is contradictory to think that way in IST.

Secret

I am trying to understand whether actual infinity is needed to talk about the existence of a model of PA, in order to understand why it is circular, but it seems I have been misunderstood about potential infinity the whole time, thus I think I need to revise everything and reformulate the question later.

From what we have discussed and I have comprehended so far, it seems potential infinity corresponds to an ideal computer thus even that is circular, let alone actual infinity

Sanity check: The natural numbers given by PA is a potential infinity right? since it has a finite description of "applying the successor function iteratively to 0"?

user539262

04:22

do you guys know when a set of boolean operators is complete vs. incomplete?

user21820

06:55

@Secret Sorry I was away. Yes, potential infinity corresponds to an ideal computer (of Turing's sort, namely not that we have an infinite tape but we have an indefinitely extensible tape).

@Secret No, because PA does not 'give' natural numbers. Nothing in PA says that the natural numbers are only those generated by the successor function.

@user539262 Yes. I see you have already asked on the main site and gotten a correct answer from xyzzyz. (By the way, xyzzyz could be said to be a neat representation of a fixed point combinator, but that's another topic haha..)

user539262

07:32

@user21820 I am trying to understand why Boolean functions have these specific 5 properties as outlined in the Post Completeness Theorem

0

Q: Why does Post's Completeness Theorem work?

My understanding is that a set of operators is complete if it fully describes any truth table you throw at it. If we have a function that accepts two Boolean inputs $p, q$ then there are $2 \cdot 2 = 4$ possible input combinations and therefore $4$ corresponding outputs. But depending on what is ...

user21820

@user539262 Yeap I saw that post of yours as well. Unfortunately, I have not looked at that theorem before, though I can see that the wikipedia article should actually tell you a lot about it, even if it will take some work for you to understand it.

And technically you cannot say that boolean functions have those 5 properties. What the theorem guarantees is that if you can represent one of each of the 5 classes then you can represent every possible boolean function.

user539262

right, I just don't know why that is the case

why those 5?

Are these 5 somehow the minimal number of "features" that completely describe a complete set of boolean operators? Where did these features come from / why these features?

Like two of them seem easy enough to see, I think:

If we need operators that describe all truth tables then at some point we're going to have something like f(0,0)=0 or g(0,0)=1

so if all our operators return 0 when you feed it all 0's, you can't have a complete set

likewise with something like f(1,1)=1 and g(1,1)=0

we need a function that will take in a bunch of 1's and possibly spit out a 0

but the others i don't quite understand

user21820

07:52

@user539262 As Henry stated in a comment, those 5 are simply the maximal classes of boolean functions that are closed under compositions and yet do not comprise the whole class.

user539262

I don't understand what that means

user21820

Given any set of boolean functions, you can close it under composition. Isn't that exactly what you are doing when you ask whether a set is functionally complete?

You take the set, you close under composition, and then you ask whether it is the whole class.

user539262

I'm not familiar with the jargon

the way I am thinking of it is that the set of operators can describe any truth table / boolean function

so if your function accepts n arguments there are 2^(2^n) boolean functions

the set of operators is complete if it can create an expression for all of them

user21820

"create an expression for f using boolean functions from S" is equivalent to "f is in the closure of S under composition".

Here is the more precise definition: You start with a collection S of boolean functions. Let S[0] = S. Then for each natural n let S[n+1] be the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in S[n].

user539262

S[0]=S?

user21820

07:59

Yes.

S[0] is the 0-th stage.

Then let S* = Union { S[n] : n in N }. S* is called the closure of S under composition. It is called a "closure" because if you form any composition of any boolean functions from S* it will still be in S*.

In other words, S* is closed under composition.

Do you get the definition of close/closure now?

So asking whether some boolean function f can be expressed using some collection S of boolean functions is the same as asking whether f is in the closure of S under composition, because any such expression is nothing more than some iterated composition.

@user539262: Makes sense so far?

user539262

Sorry, was writing a quick Python script to output all the DNFs

so for two functions accepting two inputs, would this be S?

Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 0, 0, 0] Function: NOT((not-p AND not-q) OR (not-p AND q) OR (p AND not-q) OR (p AND q))
Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 0, 0, 1] Function: (p AND q)
Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 0, 1, 0] Function: (p AND not-q)
Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 0, 1, 1] Function: (p AND not-q) OR (p AND q)
Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 1, 0, 0] Function: (not-p AND q)
Inputs: [(0, 0), (0, 1), (1, 0), (1, 1)] Outputs [0, 1, 0, 1] Function: (not-p AND q) OR (p AND q)

user21820

@user539262 What is S? I didn't specify it at all in anything I said.

user539262

"Then for each natural n let S[n+1] be the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in S[n]."

user21820

I wrote "S[n]" and "S[n+1]". I fail to see how that has anything to do with S.

user539262

nevermind'

user21820

08:13

If you want, use T[0] and T[n+1] and T[n] instead.

I used S for the sequence because people often do that. If it's confusing, I'll use T instead.

And then use U instead of S*.

@user539262: Do you understand what I wrote or not?

I can be more precise, but it will of course be at the cost of intuition, which apparently you were asking for.

user539262

No

i do not wish to be rude but I don't think this will be productive

we are talking past each other

but thanks anyway, i appreciate the time

user21820

If you do not understand this notion of closure, I'm afraid you will not be able to understand much of mathematics. It is in your best interest to learn what it is, rather than to avoid it and hope for an 'easier' route. Sorry but there's no easier route.

I have no problems spending as much time as you need to teach you, but you do need to try to put in the effort on your side.

In this particular case, if you do not understand closure, you will also not understand what the wikipedia article is talking about, nor how everything fits together.

@user539262: So why don't you try?

user539262

08:33

The problem is not my unwillingness to understand closure, I just don't think I am compatible with your particular method of explaining it

I already understand the general idea of what closure means, e.g. natural numbers are closed under addition, since you can add any two natural numbers and the output is also a natural number

but not closed under subtraction a-b when b > a since the result is negative, i.e. not a natural number anymore

but I don't really know what is meant by "closed under composition", does that mean feeding functions into each other?

like instead of f(x) we do f(g(x)), or instead of f(a,b) we do f(g(a), h(b)) or something, etc.

I also do not understand why you define things like S[0]=S (as a programmer this doesn't make sense to me), or then describe something like S[n+1] even though the following collection of functions doesn't seem to involve n at all

I don't know what your stages represent

that's why I output all 16 possible boolean functions for 2-arguments so there would be something concrete to work with

I also don't really know how composition is meant to be described when they accept multiple argumnts

user21820

08:56

@user539262 Composition indeed means something like what you are writing here.

Do you have mathematical background? I assumed (since you were asking about Post's completeness theorem) that you did.

But it seems you didn't, hence the mismatch in my level of explanation.

@user539262 Concerning this S[0] thing, it is common in mathematics to reuse variable names for different things. Since you don't like this, we can simply use different variable names for different things:

> Here is the more precise definition: You start with a collection S of boolean functions. Let T[0] = S. Then for each natural n let T[n+1] be the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in T[n].

> Then let U = Union { S[n] : n in N }. U is called the closure of S under composition. It is called a "closure" because if you form any composition of any boolean functions from U it will still be in U.

Better now?

But still, you should tell me your background otherwise I cannot tailor my explanation to you.

I am a programmer myself.

@user539262 More concretely, if T[n] has 3-input function f and 2-input functions g,h,i, then T[n+1] includes the function ( x,y,z ↦ f(g(x,y,z),h(x,y,z),i(x,y,z)) ).

Similarly for all other numbers of inputs.

user21820

09:16

Sorry, if T[n] has 3-input function f and 2-input functions g,h,i, then T[n+1] includes the function ( x,y ↦ f(g(x,y),h(x,y),i(x,y)) ).

user539262

I don't have a formal background no, just self-reading when I can

I think my problem with this is that it's a little too abstract up-front, it would help to see more concrete examples of what all this stuff represents

as of yet I don't have a good mental picture of what's going into all these various sets and functions and components, etc

user21820

Okay sure. Example 1: ( x,y ↦ ( x ) and ( x or y ) and ( x implies y ) ). This can be formed as a composition of f with g,h,i, where f = ( x,y,z ↦ x and y and z ) and g = ( x,y ↦ x ) and h = ( x,y ↦ x or y ) and g = ( x,y ↦ x implies y ).

Makes sense?

user539262

I also don't really understand the difference between S and U, since S was a collection that we are segmenting into various collections, i.e. S[n], but then we're unioning them all back together again in the end anyway but just labeling it U

user21820

@user539262 No we didn't segment it. I told you that we're defining a separate sequence. You were confused by the conventional reuse of variable names, so you should instead refer to the changed version:

30 mins ago, by user21820

> Here is the more precise definition: You start with a collection S of boolean functions. Let T[0] = S. Then for each natural n let T[n+1] be the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in T[n].

30 mins ago, by user21820

> Then let U = Union { S[n] : n in N }. U is called the closure of S under composition. It is called a "closure" because if you form any composition of any boolean functions from U it will still be in U.

user539262

(but maybe this last point I am making is a misunderstanding of what this is because I don't yet quite understand what this all looks like yet)

user21820

09:29

Ignore the original one I wrote; just refer to the one I just quoted.

user539262

I did

user21820

Argh...

Sorry..

> Then let U = Union { T[n] : n in N }. U is called the closure of S under composition. It is called a "closure" because if you form any composition of any boolean functions from U it will still be in U.

My careless mistake.

We start with S, define a sequence T[0],T[1],...

And then collect everything we get into U.

user539262

e.g. what does S look like? T[0]? T[1]? T[2]? U?

user21820

S is the original set of boolean operations. U is the closure of S under composition.

user539262

I know but I don't know what these are referring to / what this looks like

when you say boolean operations are you referring to $S = \{\land, \lnot\}$ for example?

what does S "look like" if you express it?

i don't know what boolean functions we're putting into this thing

or is it more like:

user21820

09:34

Let us go with an example first, but ultimately the point is that we are defining how to form the "closure under composition" of any given set of boolean functions.

user539262

ok

user21820

For example: Consider S = { ( x ↦ not x ) , ( x,y ↦ x and y ) } ⋃ PF, where PF is the collection of all projection functions, namely { ( x,y ↦ x ) , ( x,y ↦ y ) , ( x,y,z ↦ x ) , ( x,y,z ↦ y ) , ( x,y,z ↦ z ) , ... }.

user539262

ok

user21820

Then T[1] includes ( x,y ↦ x and ( not y ) ), because it is a composition of ( x ↦ not x ) and ( x,y ↦ x and y ).

user539262

why do we need to include all these "projection" functions?

user21820

09:39

Otherwise you can't construct all the possible boolean expressions. The projection functions allow you to 'forget' some inputs.

For example, if you want to construct a boolean expression with 3 inputs, you definitely cannot do it using just ( x ↦ not x ) and ( x,y ↦ x and y ).

Because none of them have 3 inputs.

Does that make sense?

user539262

yes but that's trying to synthesize something for 3 inputs when all the functions take 1 or 2, whereas the projections are taking in as many as 3 inputs and returning something smaller

doesn't that (somewhat) go against the original question of whether or not some set of operators is complete? are these projection functions "implicit" in that question?

like is a complete set really something like NAND + PF, or AND + NOT + PF, or OR + NOT + PF, etc

user21820

Yes indeed, the question "S is functionally complete" when expressed rigorously needs to involve "projection functions" in some way or another. Consider Example 1:

17 mins ago, by user21820

Okay sure. Example 1: ( x,y ↦ ( x ) and ( x or y ) and ( x implies y ) ). This can be formed as a composition of f with g,h,i, where f = ( x,y,z ↦ x and y and z ) and g = ( x,y ↦ x ) and h = ( x,y ↦ x or y ) and g = ( x,y ↦ x implies y ).

The final boolean expression has 3 pieces. Each piece may not involve all the inputs.

user539262

i can't tell what I need to be looking at there

user21820

( x ) and ( x or y ) and ( x implies y ) is the conjunction of 3 pieces.

The first piece does not depend on y.

It is in fact just the projection function ( x,y ↦ x ) applied to the inputs x,y.

user539262

I guess I am confused here since we're now talking about conjunction rather than composition

is there a simple example that shows why we need a projection?

like why we absolutely, positively need it and can't do without it?

user21820

09:53

If S = { ( x ↦ not x ) , ( x,y ↦ x and y ) } (meaning no projection functions) then U (the closure of S under composition) will not include the boolean function ( x,y ↦ x ).

user539262

Right now I'm assuming that we're just using them as intermediates to map outputs to inputs when we wish to "drop" some of the outputs so we can "pipe" the output to the input with perfect matching

user21820

@user539262 It is like that, and it is needed for the rigorous definition I gave.

I am not saying there is no other way. I am saying that the way I did it is the easiest and simplest way to define "functionally complete" rigorously. Incidentally, it is also the way taken by that wikipedia article.

user539262

Say we wanted to compose ( x ↦ not x ) and ( x,y ↦ x and y ) to make ( x,y ↦ x and ( not y ) ), are you saying that I need some additional function here in order to somehow take the "not x" from the first part and feed it into the y of the second part?

or is that not even what's happening when we are composing the two

user21820

@user539262 Sorry that example I gave is only in T[2], not T[1]. Let me do it explicitly.

T[0] = S includes f = ( x ↦ not x ) and g = ( x,y ↦ x and y ) and p = ( x,y ↦ x ) and q = ( x,y ↦ y ).

user539262

So what is 0 here representing?

Why these four in T[0]?

user21820

10:01

25 mins ago, by user21820

For example: Consider S = { ( x ↦ not x ) , ( x,y ↦ x and y ) } ⋃ PF, where PF is the collection of all projection functions, namely { ( x,y ↦ x ) , ( x,y ↦ y ) , ( x,y,z ↦ x ) , ( x,y,z ↦ y ) , ( x,y,z ↦ z ) , ... }.

This is the S I am referring to.

And in the construction of U, T[0] is defined as S.

user539262

ack, of course -- i need to sleep, 6 am without sleeping yet and my body is shutting down on me -- I will have to come back in a couple hours / re read everything here and see if it clicks better, I'm making dumb mistakes and forgetting stuff I just read seconds prior

thanks for being so patient with me so far, apologies for my ignorance and being dense, lol

user21820

Oh sure go and sleep. We will continue tomorrow. I will not be around in a couple hours, but I will finish the example in detail and then you can read it when you're next here.

See you!

user539262

okay -- thank you. g'night!

user21820

Good night!

For completeness, here is the whole thing from definition to example.

You start with a collection S of boolean functions. Let T[0] = S. Then for each natural n let T[n+1] be the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in T[n]. Then let U = Union { T[n] : n in N }. U is called the closure of S under composition. It is called a "closure" because if you form any composition of any boolean functions from U it will still be in U.

Example:

Let f = ( x ↦ not x ).
Let g = ( x,y ↦ x and y ).
Let p = ( x,y ↦ x ).
Let q = ( x,y ↦ y ).

Consider S = {f,g} ⋃ PF, where PF is the collection of all projection functions, namely { ( x,y ↦ x ) , ( x,y ↦ y ) , ( x,y,z ↦ x ) , ( x,y,z ↦ y ) , ( x,y,z ↦ z ) , ... }. In this example we will only need two projection functions, namely p,q.

Then construct T,U as in the definition of "closure of S under composition".
T[0] is just S, which includes f,g,p,q.
T[1] hence includes h = ( x,y ↦ f(q(x,y)) ) = ( x,y ↦ not y ).
T[2] hence includes i = ( x,y ↦ g(p(x,y),h(x,y)) ) = ( x,y ↦ x and ( not y ) ).
Thus i in U.

This is how the rigorous definition shows that i can be expressed in terms of "not" and "and".

I guess might as well just see one more in T[3].

T[3] includes j = ( x,y ↦ f(i(x,y)) ) = ( x,y ↦ not ( x and ( not y ) ) ).

Sorry I keep making mistakes myself... I probably need to do less multi-tasking... Definition should be:

> You start with a collection S of boolean functions. Let T[0] = S. Then for each natural n let T[n+1] be T[n] union the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in T[n]. Then let U = Union { T[n] : n in N }. U is called the closure of S under composition.

The definition didn't affect the example, but I realized the mistake later.

Anyway, once you understand closure, then the theorem in the wikipedia article on Post's lattice is claiming that for every collection S of boolean functions, the closure U of S⋃PF under composition must be either the collection of all boolean functions, or a subcollection of one of the 5 classes M, D, A, P0, P1.

Thus if S contains at least one boolean function outside each of those classes, then U cannot be a subcollection of any of those 5 classes, and hence U must be the collection of all boolean functions.

That is what Henry's comment on your question means.

famesyasd

14:00

:43436639

@user21820 I meant dx/dy = 0 at t = 0. Let f,g : R → R^2 be such that f(t) = sin(t)^3, g(t) = cos(t)^3, then we have a function L: $Im (g)$ → $Im (f)$ such that $L(y) = sin (acos (y)^1/3)^3$ (I expressed x as a function of y), now here dx/dy at t = 0 corresponds to dL/dy at y = 1 but dL/dy|(y := 1) does not exist, I think I got rid of t but do I still apply the same chain rule as here?

:43436639

"You definitely cannot apply it here to get dy/dx, because dt/dx is certainly not defined since dx/dt = 0."

user21820

14:44

@famesyasd Um your L does not make sense.

Please specify exactly its domain.

It will not trace the whole curve that the original parametric equation does. If your domain is [−1,1] then you get only the right-half, but flipped to the top.

famesyasd

L : [-1,1] -> [-1,1]

user21820

So okay I shouldn't say it does not makes sense, but it is not going to give you the same result that is obtained from my framework.

What did you get for dL/dy?

Your L is still problematic; you didn't solve properly for positive x in terms of y.

famesyasd

mm, yeah, I'm actually not sure if I did all that expressing and computing correctly

user21820

Note that I'm using standard precedence convention, namely that function application is higher than exponentiation. So sin(t)^3 = (sin(t))^3. I don't think that's your problem, though.

If y = cos(t)^3 then t = ?

famesyasd

.

user21820

14:53

So I guess my initial statement was right after all, since your wrong L actually caused the whole problem. =P

@famesyasd: Are you getting the right answer now?

famesyasd

@user21820 no, I'm confused :p

user21820

7 mins ago, by user21820

If y = cos(t)^3 then t = ?

famesyasd

t = acos (y^1/3), y \in [-1,1]

user21820

Yes compare that against what you wrote.

It makes a big difference!

famesyasd

do you mean L? L(y) = (sin acos (y^1/3))^3

I might have mistyped there but
I originally meant t = acos (y^1/3), y \in [-1,1] there, no, first of all, what caused my confusion was that like yesterday I computed a derivative and it didn't exist there, now I compute the derivative and it's equal to 0

user21820

15:07

Yeap it is indeed 0 so your answer tallies when we restrict attention to that half of the curve.

However, note that my derivation of that fact applies simultaneously to both halves.

And in some cases you will not be able to algebraically express one coordinate in terms of the others, and hence cannot use the 'standard' differentiate-a-function approach.

@famesyasd: In my profile you can see a link to the general differentiation post I showed you earlier, as well as a link to an example application of implicit differentiation:

3

A: Real life situation for an implicit function

A vast majority of scientific experiments can be considered to be collecting data that follows some implicit relation. What do I mean? In a typical scientific experiment, you wish to test or investigate an effect, and you have a number of parameters that you think can possibly determine some effe...

user21820

15:49

@MatheinBoulomenos @LeakyNun: If either of you are interested, here is the statement of wellordered recursion on separable types (separable means any two members of S are either equal or unequal). First, define a wellorder to be a linear order < on a separable type S such that there is no strictly <-decreasing sequence from S (function f from nat to S such that f(n+1)<f(n) for every n in nat).

For reference, a linear order is defined as a binary relation < on S (boolean function on S^2) such that < is irreflexive and transitive and satisfies trichotomy, which is more precisely, forall x,y,z in S ( not x<x and ( x<y<z implies x<z ) and ( x<y or y<x or x=y ) ).

user21820

16:03

Note that in ZFC every type is separable by fiat, so if you want the ZFC version you just ignore "separable".

user539262

@user21820 For something like

i = ( x,y ↦ g(p(x,y),h(x,y)) ) = ( x,y ↦ x and ( not y ) )

I guess I don't understand why the projection part is needed per se, i.e. what stops us from doing this:

i = ( x,y ↦ g(x,h(x,y)) ) = ( x,y ↦ x and ( not y ) )

user21820

@MatheinBoulomenos @LeakyNun: The general recursion theorem says: Given any wellorder [S,<] and separable type T, let cut(x) = { y in S : y<x }, then for every E in func( { [x,f] : x in S ?and f in func(cut(x),T) } , T ), there is some f in func(S,T) such that ( f(x) = E( [ x , f on cut(x) ] ) for every x in S ).

You can try proving this in ZFC first. There are multiple ways in ZFC, but there seems to be essentially only one way to do it in my type theory.

@user539262 Hello again! Now to answer your question. =)

Nothing stops you from doing that, but if we want to use my definition of closure under composition, we need it to be exactly of the form required by the definition.

6 hours ago, by user21820

> You start with a collection S of boolean functions. Let T[0] = S. Then for each natural n let T[n+1] be T[n] union the collection of all boolean functions ( x,...,y ↦ f(g(x,...,y),...,h(x,...,y)) ) for some functions f,g,...,h in T[n]. Then let U = Union { T[n] : n in N }. U is called the closure of S under composition.

In particular, since I require (as does Wikipedia if you refer there) that a composition must be exactly of a certain form, it excludes the form that you used to construct i.

user539262

Does closure by composition mean, technically, that when we are composing functions, we're composing all arguments?

(if that even makes sense to say)

user21820

Right right something like that. I'll draw a picture.

user539262

for instance why does "i = ( x,y ↦ g(x,h(x,y)) ) = ( x,y ↦ x and ( not y ) )" contradict this notion of closure under composition?

if we compose functions with arguments I assume by definition of composition it's filling the standalone "x" with a function and that's why we need a projection or something

user21820

16:17

No it doesn't contradict the intuitive notion, so if you like that notion very much you can of course feel free to define "composition" in a different manner than I and Wikipedia, but believe me it is more troublesome to write down rigorously. =)

user539262

but I'm not sure what that looks like (only ever done compositions with one variable)

user21820

But let me draw the picture I have in mind to explain why it's natural to consider the particular notion I defined.

user539262

I'm fine with including them, just trying to understand why that rigor is needed

*i.e. necessary for rigor, that is

ok

user21820

@user539262 It's in the description part. If you do your way you would have to specify clearly what exactly you can 'plug in' at each input. You can't 'hand-wave', and your (more intuitive) notion turns out to be more cumbersome to make rigorous.

x − g −
  /    \
:   : − f − f(g(x,...,y),...,h(x,...,y))
  \    /
y − h −

Heh ASCII art.

On the left are all the inputs.

They are fed into all the functions in the second column.

Then the outputs of those are fed into f.

This in some sense is the natural outcome of combining functions in neat layers.

Doing your way means a tree-like structure which may be easy to grasp intuitively but harder to express and reason about rigorously.

@user539262: Does this make (a bit) more sense? My definition is not the only correct way to do things. I simply selected one possible way that should give the easiest overall rigorous definition and proofs. I'm 'fortunate' that Wikipedia chose the same way, so that what I explain you can more or less directly see it in that Wikipedia article.

Over there, they said:

> A set of functions closed under composition, and containing all projections, is called a clone.

So given every set S of boolean functions, the closure of S⋃PF under composition would be a clone.

So basically you should now be able to understand the first few paragraphs of that article! =)

user539262

16:40

Ok I think I am with you on the closure-under-composition part more or less

What I don't quite understand still is how those 5 "properties of Boolean functions" arise from this closure under composition

I need to c/p your earlier comment for reference:

"Anyway, once you understand closure, then the theorem in the wikipedia article on Post's lattice is claiming that for every collection S of boolean functions, the closure U of S⋃PF under composition must be either the collection of all boolean functions, or a subcollection of one of the 5 classes M, D, A, P0, P1.

Thus if S contains at least one boolean function outside each of those classes, then U cannot be a subcollection of any of those 5 classes, and hence U must be the collection of all boolean functions."

so the "collection of all boolean functions" would be the 2^(2^n) functions we can enumerate (the thing I wrote my program earlier for)

I suppose technically we could extend this to all n too

what about this as a side question though -- consider a function f such that f(0,0) = f(0,1) = f(1,0) = f(1,1) = 0

i.e. the disjunctive normal form of this truth table is blank / empty / null, it's just "false" no matter what

is this basically the "projection" manifesting itself in a more direct way?

or is this a more f(x,y) = "false" = 0 thing explicitly

user21820

@user539262 This one is actually not a projection function; a projection function must choose one of the inputs, not ignore all of them.

Secret

16:55

> Parties are obliged to clearly convey, either verbally or non-verbally, their willingness to participate: lack of resistance, silence and non-protest do not signal consent.

One of the reasons why I like logic with more than two truth values. Us in ordinary life are way too used to the notion that not doing A, means not A is allowed, while reality is a lot more complicated

user21820

@Secret What what are you quoting?

user539262

@user21820 I updated my program for two inputs to make truth tables instead for clarity, where f(p,q) = r:

Truth Table #1
| p | q | | r |
________  _____
| 0 | 0 | | 0 |
| 0 | 1 | | 0 |
| 1 | 0 | | 0 |
| 1 | 1 | | 0 |
Function: (p,q ↦ ¬((¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ ¬q) ∨ (p ∧ q)))


Truth Table #2
| p | q | | r |
________  _____
| 0 | 0 | | 0 |
| 0 | 1 | | 0 |
| 1 | 0 | | 0 |
| 1 | 1 | | 1 |
Function: (p,q ↦ (p ∧ q))


Truth Table #3
| p | q | | r |
________  _____
| 0 | 0 | | 0 |
| 0 | 1 | | 0 |
| 1 | 0 | | 1 |
| 1 | 1 | | 0 |
Function: (p,q ↦ (p ∧ ¬q))


Truth Table #4
| p | q | | r |
________  _____

is this what the functions would "look like"?

Secret

Well, I was doing a uni program course that talks about affirmative consent, and one of the items it refer to is a newspaper smh.com.au/education/….

user539262

for the one that returns false I had it do not(result that returns true by disjunction)

Secret

My thoughts above is it just happens how the way people understood consent before taking such courses reminds me strongly how people like to guess someone is saying not A when they are not saying A, so to speak

e.g. if they are being asked about something, if the other party remain silent, then the person often assume it is either a yes or no depending on convention

user21820

16:59

@user539262 These are indeed all the possible boolean functions with two inputs.

user539262

For something like truth table #1 is this how we'd have to state it under closure?

i.e. we couldn't have something that just returns false?

Secret

While such cognitive shortcut is often useful, it sometimes does more harm than good in many social situation and lead to misconceptions and misunderstandings

Sha Vuklia

Guys, is it true that in a Boolean algebra $B$, for every $a\in B$ where $a>0$, we can find an atom $x$ such that $x\leq a$?

user21820

@user539262 Your expression would work if your starting set contains "not" and "and" and "or", meaning that you can easily translate that into a formal deduction showing that it is in T[something], but there is a simpler way.

( p,q ↦ ( p ) and ( not p ) ) is in T[2], just like my earlier example ( x,y ↦ x and ( not y ) ).

user539262

ah

Secret

17:02

a boolean algebra is a special case of a lattice, and if I recall, all lattice must have a minimum, thus there should be some $b \in B$ where there is no $x$ such that $x \leq b$?

user539262

assuming our starting set did include "or" as well, we're going to end up with a lot of duplicates of the same function just in different forms right?

user21820

@user539262 Indeed the constant 0 is not considered a projection function, which is why Wikipedia states {and,or} and {and,or,1} and {and,or,0} as generating different clones.

Sha Vuklia

yes, a Boolean algebra has a minimum @Secret and I need that there is no atom $x$ such that $x\leq b$ (or at least, I need to disprove that such $b$ exists)

user539262

like the one you just stated plus my more "convoluted" one, etc

would most people in practice use S = {and, or, not, 1, 0} union PF?

user21820

@user539262 Yes indeed! In fact, we have infinitely many stages, but only finitely many functions with two inputs, so we will certainly have infinitely many duplicates of some function. Moreover, we clearly can construct infinitely many duplicates of each function by say applying "not not" an arbitrary number of times.

user539262

17:05

right, makes sense

user21820

@user539262 I guess in standard logic most people use { not , and , or , implies , iff , 0 , 1 }.

And sometimes also xor.

Secret

if I recall correctly, the universal gate is xor which all other logic gates can be built from?

user21820

However, many logic textbooks purposely define everything in terms of just { and , not } or some other minimal set, so that it is easier to prove things about logic itself.

@Secret No you recall wrongly, and it would be a good exercise for you to prove that { xor } is not universal.

Nor even { xor , 0 , 1 , not }.

user539262

i think NAND and NOR are the universal gates?

unless I misrecall the definition

Secret

@user21820 I see, That will mean I should read up how "universal" is formulated. While from my physics courses in the past I have an intuitive idea on what it means, I never read about how it is formulated rigorously

user21820

17:08

@Secret And yes it is bad that many people like to assume that silence means consent, usually for their selfish benefit.

@user539262 Each of them is universal, yes.

Secret

That's the reason why I think introducing the concept of Null is so useful, so that out society will stop abusing silence and complacements

user21820

@Secret Intuitively, "universal" or "functionally complete" means that you can express every boolean function (no matter how many inputs) in terms of the set you're given, meaning some well-formed propositional formula with the inputs as propositional variables.

user539262

so if S is a "functionally complete" set iff we get the set of all boolean functions when we close S under composition?

Secret

@ShaVuklia yeah, and if you can prove that, then the original statement will be false because you found one such $a$ except itself which there are no atoms leq than it

user21820

Rigorously, I just did that for @user539262 here and we say that a set S is functionally complete iff the closure of S⋃PF is the set of all boolean functions.

user539262

17:11

if so this implies that the way for this to be false is if we do not get the set of all boolean functions under closure by composition, and somehow this would reduce to those 5 specific classes of functions?

user21820

→ 2 messages moved to trash

Secret

:43450870 that's a duplication glitch, it happens once a while, just trash the duplicate and you will be fine

user21820

@user539262 No it doesn't 'reduce to' those 5. The closure, if not the whole thing, must be a subcollection of one of those 5 classes, according to the Post's lattice article on wikipedia.

user539262

sorry, I did mean to say something like that

user21820

31 mins ago, by user539262

"Anyway, once you understand closure, then the theorem in the wikipedia article on Post's lattice is claiming that for every collection S of boolean functions, the closure U of S⋃PF under composition must be either the collection of all boolean functions, or a subcollection of one of the 5 classes M, D, A, P0, P1.

Thus if S contains at least one boolean function outside each of those classes, then U cannot be a subcollection of any of those 5 classes, and hence U must be the collection of all boolean functions."

Yeap yeap so any clone that 'sticks out' of each of those 5 classes must be the whole thing.

I'm afraid I just like to use such vague but intuitive words to convey how I actually think. At any point if you find something I say unclear, just ask and I'll make it precise. =)

user539262

17:16

so post's theorem says that for all 5 classes at least one of our functions of S must not belong to it. Then its negation would be there exists a class such that all our functions in S belong to it?

is that right?

(recently looked into negating logical statements so hopefully I did not mess that up)

I suppose it is possible for the closure to be a subcollection of one or more of those 5 classes?

user21820

Yes more or less. Post's theorem says that S is functionally complete iff ( for all 5 classes at least one function in S does not belong to it ). Hence S is functionally incomplete iff ( there exists a class (of the 5) such that every function in S belongs to it ).

user539262

how do these 5 classes arise? i.e. how do we know what they are?

user21820

@user539262 In particular, {}+PF would generate the smallest possible clone, which is in fact a subcollection of every one of those 5 classes.

@user539262 As I admitted earlier, I have not seen Post's theorem before, so I would have to actually think before I can answer your question about how we devise those classes.

user539262

NAND is not a member of any of those 5 either (since it is considered universal) so does that imply its negation, AND, is a member of all 5?

*the closure under composition of S = {and} + PF

user21820

@user539262 Um you're making a simple logical error here.

user539262

17:22

eep

user21820

Both 0 and 1 are in the class of constant functions.

Both 0 and 1 are linear.

user539262

that was the one I was never quite sure about

what it means for it to be linear

from what i understood it was like, "whenever the output is 1, the parity of the count of input 1's is constant"

user21820

But do you get why your argument about NAND doesn't work?

user539262

kinda-sorta

i think i negated the statement incorrectly so it didn't quite apply

user21820

@user539262 Linear is equivalent to being an integer linear combination of the inputs modulo 2.

Sorry.

A bit broader than that. An integer linear combination of the inputs and 1, modulo 2.

user539262

17:29

like for example I believe OR is not linear because when the output is 1, the inputs may be (1,0), (0,1), or (1,1) -- sometimes there is an even number of 1-inputs, sometimes there is an odd number of 1-inputs

user21820

But your description of "linear" is incorrect, because 0 and 1 are both linear.

user539262

so linear if sum(inputs) mod 2 is congruent to the output?

over all inputs?

e.g. (0+1) mod 2 = 1, (1+0) mod 2 = 1, (1+1) mod 2 = 0, not linear

whereas 1 mod 2 = 1 mod 2, same with 0 mod 2 = 0 mod 2

user21820

No it can be any integer linear combination. An integer linear combination of x[1..n] is c[1]x[1]+c[2]x[2]+...+c[n]x[n] where c[1..n] is a vector of integers.

( real x,y ↦ (2x+3y+4) ) would be an affine real function.

user539262

under what circumstance would our coefficients be outside of (0,1) though?

user21820

None.

I'm just explaining why people call it "affine".

user539262

17:32

affine real = integer coefficients, real x, y?

user21820

Similarly ( bool x,y ↦ (2x+3x+4)%2 ) would be an affine bool function.

@user539262 Oops sorry ambiguous. Affine real function can have real coefficients.

user539262

does "affine" here mean integer coefficients?

user21820

@user539262 "Affine" means "linear combination plus constant".

user539262

a sum of integer-multipliers applied to the inputs

ah

can a linear combination involve non-integer coefficients

user21820

Unfortunately some people use "linear" for "affine", which is why I got confused and gave the narrower definition at first until I checked with wikipedia.

Linear combination cannot plus constant.

user539262

17:34

so that's the only difference between affine and linear? affine permits the addition of a constant?

user21820

@user539262 The "integer" here is just because I didn't want to say "bool coefficients"...

@user539262 Yes. But unfortunately, you need to use the context to tell because too many people use "linear" for "affine".

user539262

so
( real x,y ↦ (2x+3y+4) ) would be a real affine, not a real linear combination
( real x,y ↦ (2x+3y) ) would be both a real affine, and a real linear combination

user21820

Yes.

user539262

( real x,y ↦ (1.5x+3y) ) would also be a real affine and a real linear combination?

user21820

Yes.

user539262

17:36

so the coefficients can themselves be real?

user21820

Yes a real function is linear iff its output is a real-weighted sum of its inputs.

user539262

So a linear boolean function does not involve the constant, but since we're talking "mod 2" I imagine this limits us to integer coefficients anyhow (unless we're allowed to take mod 2 of a non-integer in modular arithmetic)

so a linear bool function would be more like ( bool x,y ↦ (2x+3y)%2 )

but since any coefficient >= 2 gets reduced to 0,1 anyway we may as well use that

user21820

Right, except you probably meant (2x+3y).

user539262

oops, yes (edited, thanks)

user21820

And an affine bool function (which is what the class in question is really about) is something like ( bool x,y ↦ (2x+3y+4)%2 ), and the constant might as well be restricted to {0,1}.

user539262

17:40

wait the class among the 5 that we normally call linear bool is really more affine bool?

or am I misunderstanding the purpose of that distinction being brought up

user21820

Yes it's technically affine bool functions (so Wikipedia is the more accurate one).

But as I said, some people keep calling affine functions linear (see all your high-school textbooks calling affine real functions of 1 variable as linear functions).

Okay I need to go soon.

See you next time!

user539262

Ok, see you, and thanks for the helpful explanations

user21820

@user539262: As an exercise, you can prove one direction of the theorem: Show that each of the classes is not the whole thing. Namely, for each class there is a boolean function outside that class.

The other direction will need more work, that I haven't thought much about yet.

Okay I'm off! =)

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic