Exploring Structures: Reconciling Concepts and Questions in Logic

[sponsoredwalk]

Every so often I return to the idea of structures as used in logic & clean up my ideas
about them, here is my latest attempt, four questions based on the short summary
below, would really appreciate any help from you guys.

A structure is a triple of the form = (F, σ, I).
F is a set of objects.
σ is the signature, a set of function &/or relation symbols with no meaning ascribed to them.
I is an interpretation "function" that takes elements of the signature & gives them meaning.
If σ = {+,•,0,1} then:
I(+) : F × F → F | (a,b) ↦ +(a,b) = (a + b);
I(•) : F × F → F | (a,b) ↦ •(a,b) = (a • b);
I(0) ∊ F;
I(1) ∊ F.
That is my summary of the wiki page on structures.

I'm trying to reconcile this material with the following:

1: Ebbinghaus in Mathematical Logic describes a structure as something of the form
= (F,+,•,0,1)
I can see that = (F, σ, I) is like a shorthand for Ebbinghaus' explicit way of
showing what's in the structure but there is no interpretation function in Ebbinghaus,
what's going on there?


2: If we're working with = (F, σ, I) what happens to all of the definitions of
relations & structures that are commonly found in most textbooks?
For example, A (binary) relation is defined also as a triple of the form (A,B,G)
where G ⊆ A × B. This triple is nothing like (F, σ, I)! The question here is not
about the apparent contradiction between = (F, σ, I) & (A,B,G) [check next question],
I am asking about the way something like (A,B,G) fits into = (F, σ, I). So on the
one hand σ = {+,•,0,1} is described as a set of function symbols lacking meaning but
on the other hand things like + & • are described as sets. (A,A,+) describes
(A,A, + ⊆ A × A), so + is a graph.

3: What about the apparent contradiction in notation, here is a triple rigorously
founded in logic, = (F, σ, I), and here is a triple given with no justification
(A,B,G), I'm assuming that (A,B,G) is really some kind of (F, σ, I) in disguise?

4: Why are 0 & 1 in the signature? Surely 0 & 1 are in all sets you commonly work with
regardless? My question might be clearer by asking about symbols such as ℕ ℤ ℙ ℚ ℝ etc...
Is ℕ = (N, σ, I) or N = (ℕ, σ, I)? Think about that, if ℕ = (N, σ, I) then I can see that
the set N of objects does not contain 0 or 1 & you need some function to put them in there
but if N = (ℕ, σ, I) then 0 & 1 are already in the set of objects ℕ & the structure N has
some extra 0 & 1. I don't really understand what's going on here.


(5: Do you have, or can you find, a boldface F, i.e. , that doesn't create massive
spaces between lines? :tongue2: Preferably an alphabet of html-friendly boldface letters!).

 

[Fredrik]

Instead of answering your questions one at a time, I will say something that I think can help you find the answers to all of them. Consider the following two definitions:

A pair $(G,\star)$ is said to be a group if $\star$ is a binary operation on G (notation: $x\star y=xy$), and for all x,y,z in G,

(1) $(xy)z=x(yz)$,
(2) There's an element e in G such that $xe=ex=x$,
(3) For each x in G, there's a y in G such that $xy=yx=e$.A 4-tuple $(G,\star,e,i)$ is said to be a group if $\star$ is a binary operation on G (notation: $x\star y=xy$), $i$ is a unary operation on G (notation: $i(x)=x^{-1}$), $e\in G$, and for all x,y,z in G,

(1) $(xy)z=x(yz)$,
(2) $xe=ex=x$,
(3) $x^{-1}x=xx^{-1}=e$.These definitions associate the term "group" with two different things, but it's not hard to see that it makes no difference which of these definitions we choose to use. A group of the first kind corresponds in an obvious way to a group of the second kind, and vice versa. If two groups of the first kind are isomorphic, the corresponding groups of the second kind are isomorphic too, and vice versa.

What's going on here? I would say that these are two different ways to make the same idea mathematically precise. I think this is the concept you need to answer the questions you asked. Are there other equally useful ways to make the idea of a group mathematically precise? Yes, there is. This is one of them:

A structure $\mathbb G=(G,\sigma,I)$ with $\sigma=(\star,e,i)$ is said to be a group if $I\star$ is a binary operation on G (notation: $I\star(x,y)=xy$), $Ii$ is a unary operation on G (notation: $Ii(x)=x^{-1}$), $Ie$ is a member of G (notation: Ie=e), and for all x,y,z in G,

(1) $(xy)z=x(yz)$,
(2) $xe=ex=x$,
(3) $x^{-1}x=xx^{-1}=e$.

The reason why we might prefer this last definition is that it makes it explicit that groups are structures. The detail that seems to have caused you some confusion is that groups (as defined by either of the first two definitions in this post) don't satisfy the definition of "structure". That doesn't matter. It's standard to say that groups are structures because there's a category of structures that captures the idea of a group just as well as the "standard" definition.

 

[Fredrik]

Did that help?

 

[sponsoredwalk]

I don't really agree with the point you're making about the distinction between structures
& your other definitions but I'd rather not get into an argument about that. I understand
how to construct a group it's just that I don't understand the 4 points I made above,
from the point of view of structures grounded in first-order logic I'd like to know how to
answer the questions above without committing any logical leaps of imagination.

As a side question I don't understand the justification for putting your i or e outside
of the set G:

Lets take (G,*), this is also (G,*) = (G,(GxG,G,%)) = (G,(GxG,G,(GxG)')).
Here % = (GxG)' is the graph of the binary relation *.
Lets take (G,*,e,i), what's going on here? Now, you've called i an
unary relation so I'd assume we can write:
(G,*,i,e) = (G,(GxG,G,%),(G,G,&),e) = (G,(GxG,G,(GxG)'),(G,G,(£)),e)
where £ is the unary "graph" of i.
Still, I don't understand the reasoning because the set G contains
elements that are inverses of the elements.

Clearly * operating on G just makes no sense as a statement if you think of sets in
terms of set theory, I mean we know what it means intuitively & it gets the point
across but if you think any deeper into that statement it's nonsense, you have to
think in terms of subsets & rules defining those subsets & have to interrelate everything
somehow & organize arity & interpretation etc... I see no reason to choose intuition that
makes no sense when you pry deeper into it over an idea that really, really packs a
punch in terms of sense.

If anybody has anything to say about my four questions please let me know, considering
the fact that there are many ways to look at these ideas it's only a good thing if
someone posts even with a tiny bit of insight, tough subject

 

[Fredrik]

As a side question I don't understand the justification for putting your i or e outside
of the set G:

Lets take (G,*), this is also (G,*) = (G,(GxG,G,%)) = (G,(GxG,G,(GxG)')).
Here % = (GxG)' is the graph of the binary relation *.
Lets take (G,*,e,i), what's going on here? Now, you've called i an
unary relation so I'd assume we can write:
(G,*,i,e) = (G,(GxG,G,%),(G,G,&),e) = (G,(GxG,G,(GxG)'),(G,G,(£)),e)
where £ is the unary "graph" of i.
Still, I don't understand the reasoning because the set G contains
elements that are inverses of the elements.

I don't see what you're trying to say here. Is your point that the pair (G,*) can't possibly be equal to the 4-tuple (G,*,i,e)? That's what I said, so I don't know what you're objecting to.

I don't understand the last sentence at all. First of all, if (G,*) is a group, then all elements of G are inverses of elements of G. Second, it doesn't really make sense to talk about "inverses" until we have established that (G,*) satisfies the definition of a group.

If anybody has anything to say about my four questions please let me know, considering
the fact that there are many ways to look at these ideas it's only a good thing if
someone posts even with a tiny bit of insight, tough subject

I gave you a lot more than that, so why are you asking for a tiny bit of insight? What I told you answers all of your questions.

Edit: It answers 1 and 4 at least. In 2 and 3, you seem to be trying to see how relations and functions satisfy the definition of "structure". The simple answer is that they don't.

 

[sponsoredwalk]

I gave you a lot more than that, so why are you asking for a tiny bit of insight? What I told you answers all of your questions.

I should have been clearer, I'm asking how it's justifiable within the context of logic,
the logic that develops structures according to the specific rules necessary for
their construction, to in one context include the interpretation function (wiki page) &
enclose everything inside a signature etc... while in another (the Ebbinghaus book) it's
okay to list everything in the structure and omit the interpretation function. I need a
specific response particularly because when constructing two-sorted, or many-sorted,
structures I want to know what I'm actually doing. I have no interest in doing this
any other way, of just defining (G,*) & defining axioms I want to do it in the context
of structures properly so you didn't answer my question you basically just told me that
it's okay to do it the way the books normally do.

My 2nd/3rd questions are also very specific because I'm asking how you turn 3-tuples or
4-tuples or whatever into a statement in terms of the structures I've mentioned. Again
I'm not interested in doing it any other way. Also it's very important because I'm asking
whether the function & relation symbols in a structure are defined in terms of sets the
way these things are defined in set theory. I was just asking what the contradiction in
notation was because I want to find out how functions and relations - as described in
set theory as subsets of sets and graphs in triples - relate to a logical structure. I
don't know how they all connect. I thought that through a structure you could create
things as though they are defined in the regular way - in terms of sets - but I may be
wrong but I don't know, I'm tying to figure it all out.

Also you didn't explain to me why 0 or 1 are in the signature, you just told me they
are without any explanation & in your latest response, I wasn't saying anything like
(G,*) is/isn't equal to (G,*,i,e), I was asking for you to explain why i & e, the inverse
& identity elements, are not in the set G in one definition while in another they are.
Notice that this is me asking you why one of your definitions chooses that approach, this
has nothing to do with why it's done in structures (ergo a side question).

Based on your response I just made explicit, in terms of sets, the notation for functions
& relations & to show what happens when you put functions like "i" in there, it creates
this extra stuff & I'm wondering about it, also I don't even know what happens to "e" in
your construction.

In (G,*), * is a binary relation. The definition of a binary relation on wiki says its a
triple (G,G,*). Now, I've posted on this forum before & had it explained to me that
this isn't really correct, that it should be (GxG,G,&) where & is the graph. This makes
more sense because it's a binary relation. Now, if you're creating (G,*,i,e) you have
(G,*,i,e) = (G,(GxG,G,%),(G,G,&),e) = (G,(GxG,G,(GxG)'),(G,G,(£)),e)
according to this viewpoint when you make things explicit. I'm wondering how all of
this relates to each other, why in one context the inverses are in a separate triple
while in your other definition the inverses are just in the set G. Like ⅓ & 3 are
both in G so I don't understand why i : G → G | (3) ↦ i(3) = ⅓ exists?
* : G x G → G | (3,⅓) ↦ *(3,⅓) = (3*⅓) = e = (3*⅓) = (⅓,3) = (3,⅓) ↦ *(3,⅓)
where ⅓ ∊ G. I don't understand the need.

So that's why I wrote that blue text because your response just opened up side
questions it didn't answer my original ones, they were specific to structures and
the topics mentioned & I should have emphasized further that I'm hoping for a
response that points in that direction.

What I'm ultimately trying to get at is how structures with functions/relations etc...
relate to functions & relations as defined in terms of sets & I'd like to be able to
put everything I can in terms of structures & be able to translate back and forth,
the books contain so much material though & it requires a hell of a lot of focus which
I can't do right now so I'm just hoping for some specific insight.

 

[Fredrik]

I should have been clearer, I'm asking how it's justifiable within the context of logic,
the logic that develops structures according to the specific rules necessary for
their construction, to in one context include the interpretation function (wiki page) &
enclose everything inside a signature etc... while in another (the Ebbinghaus book) it's
okay to list everything in the structure and omit the interpretation function.

I just had a look inside "Mathematical Logic", 2nd edition, by Ebbinghaus, Flum & Thomas, and it doesn't define "structure" the way you say it does. They define it essentially the same way you did it. The only difference is that they don't explicitly include the signature in the tuple. Instead of saying that a structure is a triple (F, σ, I) such that blah-blah, they're saying that a σ-structure is a pair (F,I) such that blah-blah. This difference in terminology is obviously irrelevant.

In your question, you claimed that Ebbinghaus defined structures as tuples like (F,+,•,0,1), with no mention of a signature or a function that assigns functions, relations and elements of F to members of the signature. So naturally, I thought you wanted to know why it's OK to do it this way. I answered that question in detail, using groups as an example. Are you telling me that this isn't what you wanted to know? If that's the case, i still don't know what you're asking.

Also you didn't explain to me why 0 or 1 are in the signature, you just told me they
are without any explanation

That's not true. I did explain that. I just called the constant e, because that's what it's usually called in the context of groups.

& in your latest response, I wasn't saying anything like
(G,*) is/isn't equal to (G,*,i,e), I was asking for you to explain why i & e, the inverse
& identity elements, are not in the set G in one definition while in another they are.

You mean "in the tuple (G,...)", right? Not "in the set G"? I still don't understand what you're asking. If I had included i and e in both definitions (or omitted them from both), then they would have been two equivalent (if not identical) definitions. The point I wanted to get across is that these are two inequivalent ways to make the same idea mathematically precise. Both kinds of "groups" are equally useful.

If (G,*) is a group according to the first definition, then you can define i as the unary operation that takes an element of G to its inverse. Now (G,*,i,e) satisfies the axioms of the second definition.

If (G,*,i,e) is a group according to the second definition, then you can define $x^{-1}$ by $x^{-1}=i(x)$ for all x in G. Now (G,*) satisfies the axioms of the first definition.

The definition of a binary relation on wiki says its a
triple (G,G,*). Now, I've posted on this forum before & had it explained to me that
this isn't really correct, that it should be (GxG,G,&) where & is the graph.

This is just another example of how there can be several different ways to make the same idea mathematically precise. You can define a binary relation on G as any of the following:

a) a triple (G,G,E) where E is a subset of G×G,
b) a triple (G×G,G,E) where E is a subset of G×G
c) a subset E of G×G.

I think this concept is easier to understand if we talk about functions instead. Suppose that X and Y are sets. We would like to make the idea of "a rule that assigns exactly one member of Y to each member of X" mathematically precise. What this means is that we want to find a set that's a suitable representation of the idea of a function, and can be shown to exist using the ZFC axioms. There are at least two standard ways to do this, and lots of non-standard ways. These are the two standard ways:

Definition 1: A triple f=(X,Y,G) is said to be a function from X into Y, if G is a subset of X×Y, and

a) If x is in X, there's a y in Y such that (x,y) is in G.
b) $(x,y)\in G\ \land\ (x,y')\in G\ \Rightarrow y=y'$

People who choose to use definition 1 use the notation y=f(x) to say that (x,y) is in G.Definition 2: A subset f of X×Y is said to be a function from X into Y, if

a) If x is in X, there's a y in Y such that (x,y) is in f.
b) $(x,y)\in f\ \land\ (x,y')\in f\ \Rightarrow y=y'$

People who choose to use definition 2 use the notation y=f(x) to say that (x,y) is in f.These definitions capture the idea of a function equally well. It can be a little annoying that the second kind of function has infinitely many codomains, but the worst problem this causes is that it makes the phrase "f:X→Y is surjective" ambiguous, so that it needs to be replaced by "f:X→Y is surjective onto Y".

Now, if you're creating (G,*,i,e) you have
(G,*,i,e) = (G,(GxG,G,%),(G,G,&),e) = (G,(GxG,G,(GxG)'),(G,G,(£)),e)
according to this viewpoint when you make things explicit. I'm wondering how all of
this relates to each other, why in one context the inverses are in a separate triple
while in your other definition the inverses are just in the set G. Like ⅓ & 3 are
both in G so I don't understand why i : G → G | (3) ↦ i(3) = ⅓ exists?
* : G x G → G | (3,⅓) ↦ *(3,⅓) = (3*⅓) = e = (3*⅓) = (⅓,3) = (3,⅓) ↦ *(3,⅓)
where ⅓ ∊ G. I don't understand the need.

There's no need. If there had been, my second definition would have been the only meaningful definition of the term "group". But the first one is just as useful. The point is that we can include i and e in the tuple if we want to (or just one of them), and get an equally useful concept. At least they're equally useful in abstract algebra. In mathematical logic, it's customary to include all the function, relation and constant symbols in the signature. I don't think it's absolutely necessary to do it this way. The only advantage I can see right now is the one you can see if you look at the first two definitions of "group" that I posted. By including i and e, I eliminated the need for "there exists" and "for all" statements in the axioms.

 

[sponsoredwalk]

Thanks for the response Fredrik , I'll give this some serious consideration & get back
to you in a while, I'm trying to get to grips with a lot of stuff & this isn't at the top of my
list right now but you've given me stuff to look out for. I'll get back to you with a more
detailed response when I can devote some proper time to this issue as I feel a bit uneasy
but can't really articulate why, take it easy.