« first day (512 days earlier)      last day (2600 days later) » 

03:36
@AlessandroCodenotti Yes. No need for second-order.
@AlessandroCodenotti No @LeakyNun is wrong about that, despite me telling him many times lol... PA2 with only the second-order induction axiom and without the first-order induction schema cannot prove anything that needs induction, simply because it does not have any set-existence axioms. That is why PA2 as originally specified by Peano is defective.
@AlessandroCodenotti Related to the above, PA2 has a unique full-semantics model up to isomorphism, and that is essentially an artifact of the notion of full semantics because it involves what the meta-system thinks are subsets of the domain. Notice that the uniqueness of model implies that PA2 with full semantics fails to be semantically-complete.
PA2 plus set-existence axioms with Henkin-semantics would essentially be some version of SOA (second-order arithmetic). Since the underlying second-order logic can be embedded into first-order logic with two sorts, which immediately implies semantic-completeness and a Henkin model, SOA will again have non-isomorphic models (if consistent).
@AlessandroCodenotti The easiest way to prove it is to first prove that RCF (theory of real-closed fields) has QE (quantifier elimination), which implies that RCF is syntactically-complete, and hence every model of RCF is also a model of Th(R), since R |= RCF. Then it remains to check each of the examples given by LeakyNun to see that they are models of RCF.
04:01
@user21820 I don't think the examiner expects him to write "actually, PA2 is trash because the induction cannot prove anything"
is this a common opinion in the logic field?
@LeakyNun It's not trash, but one must distinguish clearly between what PA2 proves and what are models of PA2. And what I'm saying is standard.
@user21820 could you give me any online reference?
Note that Peano was a very very early logician in the modern sense, so it's understandable that he didn't distinguish clearly between the meta-system and the formal system.
@LeakyNun I'll see if I can find some after I finish what I was saying.
@AlessandroCodenotti: Real algebraic numbers work, because every odd-degree polynomial over them has a real root that is algebraic by the tower law. Computable reals also work, because the intermediate value theorem guarantees that binary doubling followed by binary search yields a computable root of any odd-degree polynomial.
interesting. our course never talked about peano arithmetic
04:19
@LeakyNun It was surprisingly hard to find an explicit Math SE post regarding this:
9
A: Why is better to work with first-order Peano's axioms than with second-order Peano's axioms?

Carl MummertEach set of axioms has its own purposes, and neither is better than the other in all circumstances. It is true that, when they are interpreted in set theory, the second-order Peano axioms are categorical. They are useful for characterizing the natural numbers once we have a notion of "set" to ...

10 hours ago, by Alessandro Codenotti
So the big difference is that $\sf PA^2$ proves that every element is the successor of the successor of .... of the successor of $0$
> The issue in working "with" these axioms is that they don't tell you how to construct any set X to apply the third axiom. So, if you want to proceed on an axiomatic basis, you have to add additional axioms to allow for the construction of sets, before you can actually use the third axiom in any nontrivial way.
I think that depends on the interpretation of that particular statement
how do you interpret what he said?
@LeakyNun As I stated, PA2 as defined by Peano (and which Carl says is what most people think of) proves strictly less than PA.
But PA2 plus set-existence axioms will be able to prove more than PA, how much more depending on the set-existence axioms. In particular, if you stick to predicative specification axioms, then you get ACA0, which proves exactly the same arithmetical sentences as PA.
$$\bigcap \varnothing = V$$
04:24
@LeakyNun Har har.. you know that's not allowed in ZFC, right?
(By "strictly less" I actually meant "strictly fewer arithmetical sentences", and the only extra non-arithmetical sentences are basically tautological consequences of the second-order induction axiom because there is nothing to 'apply' it to.)
@user21820 sure
@LeakyNun That's why I like a universal type. We get a symmetry between nothing and everything. =)
@AlessandroCodenotti: Anyway after your exam you may be interested to read some half-mathematics and half-philosophy post about natural numbers:
16
A: How do we know what natural numbers are?

user21820 How do the mathematicians that write standard natural numbers have formal consensus on what they are talking about? Mathematicians work in a meta-system (which is usually ZFC unless otherwise stated). ZFC has a collection of natural numbers that is automagically provided for by the axiom of ...

I found it while searching for an answer to LeakyNun's question...
 
1 hour later…
05:40
12
A: Are sets and symbols the building blocks of mathematics?

user21820The things you actually write on the paper or some other medium are not definable as any kind of mathematical objects. Mathematical structures can at most be used to model (or approximate) the real world structures. For example we might say that we can have strings of symbols of arbitrary length,...

@LeakyNun: I just realized that in Henry Towsner's PDF on reverse mathematics, linked from the above post, says pretty much the same thing:
> In order to get any mileage out of the new content, though, we need axioms which state that there are any sets at all. We will only work in theories which have comprehension axioms, which typically have the form ∃X ∀x ( x∈X ↔ φ(x) ) where X does not appear free in the formula φ.
So Carl's statement is the clearest (least informal) so far I guess.
@user21820 guess what this is :P
Why is the axis so weird?
that's a clue :P
05:44
It looks like a fractal.
I probably can generate it.
But I have no idea why the axis does not make sense.
I messed up the axis. Now it's fixed.
@user21820 it's the graph of y=exp(x) in Z_2
@LeakyNun What? But it's just a fractal, with the unit being:
  *
   *
 *
*
Okay this ASCII art is getting nowhere.
well exp is a fractal in Z_2
Hmm I see.
06:50
Just read all your messages @user21820, that was very useful, thanks!
@AlessandroCodenotti You're welcome! Is your exam soon?
@AlessandroCodenotti is it mentioned in your class that PA2 is trash?
Yep, a little more than an hour
We didn't really talk about PA2 or second order anything, the professor just mentioned you can get a unique model if you go second order and I got curious
I see
you know that completeness and everything fails in second order right
07:01
so categoricity does not imply completeness
and definitely there is no upward lowenheim-skolem
@AlessandroCodenotti any last-minute questions?
Nah, I feel ready
@LeakyNun Yup. But ω-categoricity for first-order logic does imply syntactic completeness.
It's not so obvious, is it?
isn't that just an application of compactness and downward LS?
07:06
What do you mean with "syntactic completeness"?
@LeakyNun Yes. Note that language must be countable.
@AlessandroCodenotti It proves or disproves every sentence over the language.
Oh, we called that just completeness
@AlessandroCodenotti because there's also the completeness theorem
Semantic completeness means that every sentence that is true in every model is also provable.
that's semantic-completeness
07:08
I like to differentiate the two, and I see LeakyNun has also frequently differentiated them.
I like to integrate them
Har har...
Ah, I see, makes sense.
Lobesgic integral?
lol
$1 + p^n \Bbb Z_p$ and $1 + p^m \Bbb Z_p$ are isomorphic as groups
@user21820 first order Z_p?
07:11
@LeakyNun I don't know much about Z[p]...
curiously, it is an inverse limit of finite groups
can we have inverse limit of finite theories...
there can be a unique model if it is finite
What is an inverse limit?
lol
that's a category theory notion, which you don't like
I'm sure you can phrase it concretely.
so we have a sequence of groups and homomorphisms A1 -> A2 -> A3 -> ...
wrong direction
A1 <- A2 <- A3 <- ...
@AlessandroCodenotti sniped :P
then we consider sequences (a1, a2, a3, a4, ...)
in which f21(a2) = a1
f32(a3) = a2
etc
@user21820 ok?
07:18
Where the f's are homorphisms.
Might as well use f[n](a[n+1]) = a[n].
Next?
then the allowed sequences forms a group, which is the inverse limit of the groups
it's like taking the "limit" of the groups as they go larger
If $f_{ij}:A_i\to A_j$ you also need $f_{ik}\circ f_{kj}=f_{ij}$ to get an inverse system iirc?
@AlessandroCodenotti Doesn't that follow from the chain? It looks like LeakyNun is using a chain not an arbitrary poset.
but since I assumed that the indexing set is N, it suffices to have maps from the successor to itself
right
07:21
I get the construction, but will now have to think about it a while to get an intuition.
if you only allow length-n sequences, you essentially get An
so in a sense you're pretending that those are the objects of An
as n goes larger
21 secs ago, by Leaky Nun
if you only allow length-n sequences, you essentially get An
Oh, sure, I thoughy you were doing a more general version
since the first n-1 objects is uniquely determined by the last object by the maps
@AlessandroCodenotti he doesn't like category theory
so he wants things to be as concrete as possible
@user21820 but I should have used the poset setting, since you can obtain Z-hat as the inverse limit of Z/nZ with maps f[mn,n]:Z/mnZ->Z/nZ
That's fine; I understand the poset version as well; it's the obvious generalization.
Z_p is the inverse limit of Z/p^n Z with maps f[n]:Z/p^(n+1)Z -> Z/p^n Z
I like to think of Z-hat as a sequence of modulos (just like the construction)
so 7 generates the sequence (0,1,1,3,2,1,0,7,7,7,7,7,7,...)
because 7%1=0, 7%2=1, 7%3=1, 7%4=3, 7%5=2, ...
and then you just take "limit" of those sequences
07:28
What is Z^ used for?
Z-hat is the absolute Galois group of F_p
Lol this rabbit hole is getting deeper. This is the first time I've heard of the profinite completion and the absolute Galois group.
well extension of F_p of degree n has Galois group Z/nZ
so it arises as an inverse limit naturally
I see. What about the algebraic closure of F[p]?
you just adjoin elements of each degree lol
so it's basically U F[p^n]
it's enough to adjoin elements of each prime power degree, I think
oh and it's easy to see how pZ[p] = Z[p] if you view it as a limit
this gives the self-similarity of Z[p]
07:44
@LeakyNun Yes it's enough, and I know that fact, but was wondering whether it could be viewed as an inverse limit.
I don't think there's a map from F[p^2] to F[p]
I might be wrong
failed attempt:
1
Q: Direct and inverse limits of finite fields

Henrique Augusto SouzaLet $\left\{\mathbb{F}_{p^n}| n \in \mathbb{N}\right\}$ be a family of finite fields of characteristic $p$. Whenever $m$ divides $n$, we have the inclusion homomorphism $\mathbb{F}_{p^m} \to \mathbb{F}_{p^n}$. We also have the surjection $\mathbb{F}_{p^n} \to \mathbb{F}_{p^m}$ given by the norm m...

oh wait
D is actually the algebraic closure lol
so F[p]-bar is the direct limit of F[p^n]
with inclusions F[p^n] -> F[p^(mn)]
@LeakyNun You're right.
I wonder what you get if you take the direct limit of Z/p^n Z
Is the direct limit just the union?
right
07:54
Well Wikipedia says it's not just the union. It's the disjoint union and modulo some equivalence.
In mathematics, a direct limit (also called inductive limit) is a colimit of a "directed family of objects". == Formal definition == === Algebraic objects === In this section objects are understood to be sets with a given algebraic structure such as groups, rings, modules (over a fixed ring), algebras (over a fixed field), etc. With this in mind, homomorphisms are understood in the corresponding setting (group homomorphisms, etc.). Let ⟨ I , ≤ ⟩ {\displaystyle \langle I,\leq \rangle } be a directed set. Let ...
One of the examples in the linked section answers your question.
:o
that's very interesting
aha, it's a subgroup of the unit circle
 
6 hours later…
14:16
Here's something related to ordinals...
0
Q: What comes after (Primary,unary),(secondary,binary),(tertiary,ternary),...?

user21820I was curious to know what comes after: Primary, secondary, tertiary, ... This Oxford website says it is "quartenary, quinary, ..." But they are already taken! Unary, binary, ternary, quaternary, quinary, ... And according to this EL&U post deriving from the Latin originals should gi...

Lol...
 
2 hours later…
15:49
har har
@LeakyNun I see I've attracted more users here like @Zermelo's_Choice...
@Zermelo's_Choice: Welcome! What logic entails you to arrive here? =)
16:17
It said logic, and I've never seen the chat side of SE.

« first day (512 days earlier)      last day (2600 days later) »