How can Turing machines be used to model sets?

[phoenixthoth]

I have a set theory that I want to prove is consistent if ZFC is consistent.

I'm dimly aware of what to do or where to begin.

To keep the notation straight, A[0] is the set of axioms in ZFC. A[1] is the set of axioms in ZFA, antifoundation. I know that A[0] consistent implies A[1] consistent. Finally, A[2] is A[1] plus one more axiom.

From what little I understand, what I need to do is show that if (M,I) is a model for A[1] then there is a model (M',I') of A[2].

What is the proper way to show M' exists?

FYI, I'm working with wffs in a ternary logic. Russell-type paradoxes become Q <--> ~Q which is not always false: it can be neither true nor false. The one axiom I'm adding to A[1] is a universal set axiom E(x)A(Y)y&isin;x. For reference, denote this by U.

BTW: We would say (N,I)|=f, read "N satisfies f" if f is true when interpreted in N with I.

So I think that M'=M&cup;{U'} where U' is the symbol whose interpretation is U. Then, I'd like to show a map q exists from M to M' that preserves interpretations that is 1-1. So a,b in M (i.e., a, b are sets in ZFA) and a&isin;b iff q(a)&isin;q(b) (in A[2]). And since &isin; is the only nonconstant logical symbol, that would be all we need (?). I don't know if I'm on the right track at all. The thing is I am not seeing where I need ternary logic...

Thanks in advance for any feedback.

 

[Hurkyl]

This is generally a difficult field, I believe. This is compounded with the fact that, AFAIK, most of what is studied is about first-order (binary) logic... if you start up with a different logic, AFAIK you'd have to work from the ground up, or prove some cool theorems for transferring the theorems to work with your logic.

 

[phoenixthoth]

Check out this .

(It's a pdf)

See page 7, definition 4.1. It's a system for shaving fuzzy logic to make it binary, sort of.

One of those binary functions (I mean, having range in {F,T} not that there are two slots in input) would be the one I'd adopt for my theory.

For example, Russell's paradox boils down to a contradiction of the form Q <--> ~Q. Well, if I make a truth table with S∈S, S!∈S, and $$R^{+}\left( S\in S\leftrightarrow S\notin S\right)$$, then I get exactly one true possibility.

Now for another try, let's stick to well-founded sets. Let S=(0,1), the interval. Then $$R^{+}\left( x\in \left( 0,1\right) \leftrightarrow 0<x<1\right)$$ is true in all cases. Then we'd say that $$x\in \left( 0,1\right)$$ has the same truth value as $$0<x<1$$; when determing if x is in the set (0,1), it has the same truth value as 0<x<1.

So then we'd say, I think, binarily, that (A,I)|=f iff $$R^{+}\left( f\right)$$ is true in (A,I).

 

[phoenixthoth]

Maybe there is a nonstandard model of set theory with a universal set... Using compactness, I can get a set bigger than every set which is the powerset of a powerset of ... of the powerset of the set of natural numbers. But whether this would be a set that contains all sets...

Back to ternary logic...

I keep staring at the definition of what it means for a structure to be a model for a (set of) formula(s). For example, one would find something like this:
$$\left( A,R\right) \models \left( \phi \rightarrow \psi \right)$$ iff
if phi then psi.

If phi -> psi has the third truth value, then the statement (A,R) |= (phi -> psi) has the third truth value. That won't do.

When we write "iff" or "if phi then psi" in mathematical-english, I want things to be in binary logic. I want the formula phi itself to possibly be ternary but when we write about it in english, if phi then psi would have a different meaning than $$\phi \rightarrow \psi$$ in the following sense:
if phi then psi means if $$R^{+}\left( \phi \right)$$ is true then $$R^{+}\left( \psi \right)$$ is true. This is a binary logic reduction of ternary logic.

Then the definition of 'model' would include something like this:
$$\left( A,R\right) \models \left( \phi \rightarrow \psi \right)$$ iff
$$R^{+}\left( \phi \right) =T\rightarrow R^{+}\left( \psi \right) =T$$.

I'm trying to make it so that I don't have to reinvent model theory.

There is an article out there on model theory and many valued logic but it doesn't seem available on the net.

 

[Hurkyl]

Well, reinvinting model theory might net you a paper. (At least if 3-valued model theory hasn't yet been done)

A nonstandard model of ZFC won't give you a biggest set, though it will give you sets that are not well-founded, since there will exist infinite descending chains of the form ... in C in B in A.

 

[phoenixthoth]

As always, your feedback is appreciated. I think someone must have worked out the semantics for ternary model theory but I don't know who or where. I'd like to see it so I don't have to do it.

Nonwellfounded sets are something I need so that if there is a universal set U, then I'd want U&isin;U. So I'd start with a model for this and try to construct a model for the set theory I want.

I am just starting to work it out. If you come across any reference to nonclassical logics and model theory...

(I remember last time I gave this a go maybe a year and a half ago, I had a theorem that stated that by the foundation axiom, x&isin;x implies x=U. But my professor's counterexample was S={x:x!=Ø}.)

 

[phoenixthoth]

My journal is filled with T's, F's, and M's.

So I can have a model that makes sense in ternary logic, though my way is not unique. My way is so that the paradoxes will boil down to a statement whose truth value is neither true nor false, which, after that R upper plus function is applied to it, is true.

My first major goal is to prove that if PHI is a set of wffs in ternary logic that PHI is satisfiable iff PHI is consistent. So I'm going through the sequent calculus and checking that my system makes that work.

I've convinced myself that even though phi and not(phi) have the same truth value for phi neither true nor false, there won't be inconsistency; i.e., not(phi) is still not derivable from phi.

My next goal is to then build a model of my set theory...

 

[phoenixthoth]

I've convinced myself (hopefully rightly so) that a completness theorem (a set of formulas is consistent iff the set is satisfiable, i.e., there is a model for that set of formulas) is correct. I still have to work out the details fully. That will suffice to show relative consistency.

So let ((A,a),b) be an interpretation (in more modern texts, the assignment b is not specified and they deal with the structure (A,a)) which models ZFC set theory + AFA (antifoundation axiom). I want to build a larger interpretation ((A,a),b)* that models the above axioms plus the universal set axiom (and maybe an axiom about the uniqueness of the universal set to make other lose ends work out).

Does what I'm about to do sound right at all?

Enlarge A by adding one element that is not in A. Call this element U. Let A*=A∪{U}. To define a*(∈), we first note that a*(∈) is a subset of (A*)^2; we extend the binary relation a(∈) on A to one a*(∈) in a way that for all x, y in A: if x a(∈) y, then x a*(∈) y. Finally, this is critical: we further define a* so that for all x in A, x a*(∈) U is true.

I think that's my model that I'm looking for. Now I need to check that it satisfies all the axioms which is slightly tricky since x a*(∈) y can have 3 truth values.

Any feedback appreciated.

 

[phoenixthoth]

It's actually good no one replied. I figured it out for myself. :tongue2:

I had to scrap that A*=A∪{U} idea. (A*,a*) does not seem to model basically anything but the universal set axiom!

In the investigation, I found that given A (which is thought to be a domain for a model), there is a set containing A (as a subset) that is closed under pairing: for all x,y in the set, {x,y} is in the set. Call this F. Now I want F to satisfy extensionality but it doesn't clearly. Imagine I adjusted F. Then I'd lose the closed under pairing property. I figure that if I could do what I was trying to do, I'd have a model for set theory which doesn't exist (yet).

So now what I'm doing is letting U be an arbitary set in A that is nonempty. Then I define a relation, thinking of "is in", on A such that for all $$x,y\in A$$, $$x\in _{2}y$$ iff $$x\in _{3}y$$. Furthermore define $$\in _{3}$$so that for all $$x\in A$$, $$x\in _{3}U$$. Here, the 2 subscript refers to "is in" in standard set theory and the new 3 subscript denotes "is in" in the new theory.

This setup will clearly not model the foundation axiom as U∈U. Luckily, I dropped that in my theory.

Now I have to check that this models anything other than the universal set axiom!.

 

[Hurkyl]

If it helps, you can think of sets in terms of graph theory. (At least if you don't deny foundation) You can define a set to be a rigid, rooted tree.

Rooted means that you've selected a node of the tree to be the root. (So that the terms "parent" and "child" make sense)

Rigid means that the only automorphism is the identity. (As opposed to a floppy tree whose branches can flop around and give you the original tree) Less abstractly, this means that no node can have two identical children.


The membership operation, A in B, simply means that A occurs as a child of the root of B.


If you deny foundation, you could still probably salvage this picture.


The nifty thing is that if you have a universal set, you can describe the entire universe with a single tree! Then, the universality condition becomes that the sub-tree descending from any given node also appears as a child of the parent node.

 

[phoenixthoth]

That method does not seem to use three valued logic. Indeed, I'm not obviously using it yet but I'm only 1/3 way through proving the axioms are relatively consistent.

I dread some of them...

Thanks for your feedback. I've read some about non-well-founded sets and they're just graphs like yours but with cycles.

 

[Hurkyl]

I suppose you could color the edges of the tree, then.

 

[Hurkyl]

Hrm, does it matter to you which three-valued logic to use?

There's a three-valued logic with a really snazzy interpretation that I came across recently, where the third value was some sort of "I don't know" value.


But the interpretation seemed to relate to Turing machines. (I.E. programs) There are three kinds of behavior a Turing machine can exhibit on a given input: it can say "I accept this input", "I reject this input", and it can run forever. (Actually, Turing machines can also print an output too, so they can compute functions)


So, on a given input, you can ask a Turing machine M: "Do you accept this input?", and the result you get is either T (I accept), F (I reject), or U (runs forever).

Of course, you never actually get the "runs forever" result, but fortunately we're doing an external analysis and don't actually have to wait for it.


The nice thing about Turing machines is the fact that you can encode a Turing machine into a string, so Turing machines can take other Turing machines as inputs and simulate them. Additionally, Turing machines can obtain a string denoting themselves!


Now, we can think of a Turing machine as a "set", and the relation A in B simply means run the Turing machine B on the input A.


Now, Turing machines can be encoded into strings in a nice way. I assert that it's actually a Turing decidable language. (You can probably even make it context-free)

This means that there exists a Turing machine, I'll call it U, that runs the following program:

On input S:
If S represents a Turing machine, accept S.
If S does not represent a Turing machine, reject S.

So here's your universal "set" -- it accepts any Turing machine!

We also have a universal "set" that accepts all strings -- the Turing machine that accepts every input.


Now, we can try to write the Turing machine for Russel's paradox:

On input M:
If M does not denote a turing machine, reject M.
Simulate M with input M.
If M accepts M, I reject M.
If M rejects M, I accept M.

However, we run into the halting problem -- a Turing machine cannot tell if an arbitrary Turing machine will halt, so this Turing machine will often run forever, thus yielding the third truth value.


So let me try formalizing this a bit:

The three truth values are T, F, and X. (No particular reason for X)
The universe consists of all finite binary strings.
Binary strings that represent a Turing machine are called sets.

If B is a set, then the relation "A in B" simply means run the Turing machine B on the input A.

We can build logical operations too. For example, "A or B" is the following turing machine:
On input S:
Simultaneously simulate A and B on input S.
If A accepts, I accept.
If B accepts, I accept.
If A and B both reject, I reject.


And how about the union of all the elements of a set? Well, given a Turing machine M, the Turing machine Union(M) will, on input S, simply simulate all possible Turing machines until it finds a machine N such that N accepts S and M accepts N. Note that Union(M) will never reject any string!

I'm not sure what you can do with the power set operation.


Here's a Turing machine that contains itself and nothing else:

On input S:
Obtain a string T denoting myself.
If S and T are the same, accept S.
Otherwise, reject S.

I believe there are lots of different Turing machines that accept only themselves and nothing else.


And I'm sure there are other fun ways you can use these sorts of ideas. (Maybe use an enumerator instead of a Turing machine!)