Hey @MikeMiller maybe you could help with my question

If there is anyone that can help me, the problem that I'm doing is that I need to figure if it is possible to find a path from X1 that traverses the whole graph. There are four vertices(X1, X2, X3, X4) and this is how they are connected. X1: X3 X4 X2, X2: X1 X3 X4 , X3: X1 X2 X4, X4: X1 X2 X3

So each vertex has a degree of 3

Remind me, path = "no repeated vertices", or "no repeated edges", @Deathslice?

Note: we defined a path in class to be connected by a sequence of vertices which are all distinct from one another

OK, and have you learned about Euler paths/circuits? There's a theorem that applies, but if you haven't learned it, it's off the table

Yes

just today

Hmm... well, I'd say check your notes to see if you have an "if and only if" theorem about Euler paths/circuits that involves the degrees of the vertices.

I think this particular sentences is what you're saying. If a graph has more than 2 vertices of odd degree, then it CANNOT have an EULER PATH.

Bingo, that's the one! (And in fact, it has to have exactly two vertices of odd degree for a non-closed path, but that statement is enough here)

I'm not sure if using that theorem would work.

consider this

Suppose we reduce X4 and X2 to have a degree of 2.

Thus we would have exactly to odd degrees.

OK, so now you've got a square with a single diagonal, I believe

Now this would be a euler path

but it is not a path

remember that a euler path never visits a edge more than once.

while a path never visits a vertex more than once.

I think there's some terminological confusion happening here. Vertices should be allowed to be repeated, when we're talking Euler Paths/Trails

correct

but we are talking about a path

not a euler path

Remember what the question said

"Is it possible to find a path"

no mention of a euler path.

OK, then what does it mean for a path to "traverse the whole graph"? I'd assumed it was talking about an Euler Path, but I quite likely was mistaken.

Ok

Traverses the whole graph means

uses all the edges of the graph

Starting at X1

OK, then there's no possible way a graph with more than one cycle could be "traversed" in a path, I suspect

It's going to boil down to the definitions we're using here (I'm quite rusty on graph-theory definitions, and for that, I apologize)

Well we are not really talking about cycles here

just paths :)

Once again. here are the vertices that connected to their corresponding vertex X1: X3 X4 X2, X2: X1 X3 X4 , X3: X1 X2 X4, X4: X1 X2 X3

I know, but think about it: suppose we have a triangle and attach an extra edge. Then entering/leaving the triangle, we have to visit that vertex twice. I should say "any graph that contains a cycle as a proper subgraph can't be "traversed" by a path"

It's the complete graph $K_4$

So, that's my intuition: The kind of "traversal" you're talking about is incredibly restrictive; almost no graphs could be "traversed"; we can't visit all edges and vertices exactly once, except in very rare situations

Actually you're right it is K4 now that I'm looking at it. Also the shape that I have is a triangular prism.

Yep, it's the skeleton of a tetrahedron as well

There are two main kinds of "traversals" in graph theory: The Euler ones, that visit each edge (and are allowed to repeat vertices) and the Hamilton ones, that visit each vertex exactly once (and don't necessarily, and probably in general can't, cross each edge). I just suspect the kind of traversal you're thinking of is way too restrictive for that to be the actual intended meaning

So if we're sure of the definitions involved, I'm alright at graph theory :) But I don't want to mislead you, if we're not thinking of the same things

I'd really appreciate it if someone could help me with the question I posted here: math.stackexchange.com/questions/1377454/…

ff topic - Rational Canonical Forms. Given an n×n matrix A, are there situations in which one would find the rational canonical form of $A$ by finding a matrix $P$ such that $P^{-1}AP$ is the rational canonical form of $A$? If so, when should this technique be applied?

@anon I have edited my answer to add some motivation :-)

that's essentially equivalent to what lhf says, except it checked the system for consistency and reduced the congruence. lhf's still probably more straightforward for a noob. (dunno what OP was wanting for in the earlier thread - commented as such). but checking for consistency is important, reducing numbers when possible is important, and being able to potentially generalize to multiple equations and variables is also good.

I found a weird injection from real numbers to countable order types (that is, order relations on the integers modded out by order isomorphism.)

Oh, turns out there's a much easier one.

@anon I am writing a program so I am trying to understand how to actually implement something that matches the results.

@columbus8myhw oh?

@anon Fix $r\in\mathbb R$. Let $\zeta$ be the order type of $\mathbb Z$, and let $(a_n)$ be the binary expansion of $r$. We have $a_n\in\{0,1\}$ for all $n$. The order type corresponding to $r$ is $a_0+\zeta+a_1+\zeta+a_2+\zeta+\dotsb$. This is much easier than what I originally had in mind.

I think you mean $0\le r\le 1$. anyway, where do 0.011111... and 0.10000... go? :-)

@anon Or at least $0\le r$, though that's not too hard to fix. And let's say that we'll go with the one ending in all $0$s... it's an arbitrary choice, after all.

(Let $s(r)=\begin{cases}0&r\le0\\1&r>0\end{cases}$, and put $s(r)+\zeta+$ in front of what I had before.

can you prove all reals have 1 or 2 binary expansions, and the only reals with 2 binary expansions are ones that have a finite binary expansion in which one can then replace the last 1 with 0111... ?

btw, what is $a_0$ if not the first digit after the decimal binary point?

Derp. It's the number before it... $a_0\in\{0,1,2,\dots\}$, I guess.

And of course all reals have $1$ or $2$ binary expansions. Just think of them as the completion of the rationals.

In any case, save for some details, that's an injection from $\mathbb R$ to countable linear order types.

yes, it is. I know about binary expansions, wondered if you knew why the facts are the facts though.

Here's a nice puzzle for you:

(equivalently, if one disallows expansions ending in repeating 1s, then expansions are unique)

Find an increasing bijection $f:\mathbb Q\setminus\{0\}\mapsto\mathbb Q$.

That is, show they have the same order type.

(There's a chance you've seen this before, though...)

heh. I think you gave away the game when you replaced R by Q editing. :-)

With $\mathbb R$ it's impossible, and it's not too hard to show that... :)

Is there a detailed and easy to understand guide anywhere that explains the application of the extended gcd algorithm for solving systems of congruences?

@user2597879 do you just mean 2x2 systems or more?

I've literally been at this for two weeks now and the lack of online resources is shocking to me

anon: I imagine if the system works for 2 equations you can just iteratively apply it to several

that would work, might not be very efficient

I can't think of any alternative at this point because of the lack of online resources

Sometimes when solving the CRT, you end up with non-coprime elements

good luck finding efficient materials online for that

i couldn't find a single one

as robjohn does in his answer, the first thing you want to check is consistency

is that the "gcd check"?

yes

usually my dog scratches the front door when he wants in. apparently a bug has learned to simulate this sound effect by running into it. :/

How on earth does vector [1,0] + vector [0,1] give vector [1,2]?

it doesn't

I really appreciate this answer but I'm finding the multitude of skipped steps frustrating

it doesn't but robjohn says it does?

robjohn did not add [1,0] and [0,1] together

robjohn very clearly states "add 1 times (5) to 2 times (6)"

yes but I am asking for a systematic way to approach that step

It's not always going to be the case that you do 1 times (5) to 2 times (6)

indeed, robjohn doesn't explain what system he is using

I pointed out that issue in my first comment to him

lhf's answer should be pretty straightforward for you though

it was insufficient

I have a perfectly good egcd implementation

I'm just trying to get this whole thing to spit out 50 mod 105

when feeding it values [5, 8] with moduli [15, 21]

I don't see anything insufficient about lhf's answer. It should be readily understood what the general procedure is.

Like I understand that combining the congruences gives 15a - 21b = 3

but again I am talking systematic

like if I have [5, 8] with moduli [15, 21], does this mean I run egcd(modulus1, modulus2)?

given x=u (N), x=v (M) [consistent], write x=u+aN=v+bM, yielding aN-bM=v-u. now solve for a,b via algorithm.

When I do I get (g,a,b) = (3, 3, -2)

[consistent]?

the system must be consistent

meaning u=v mod gcd(N,M)

Do you mean ensuring that if g = gcd(modulus1,modulus2), then value1 % g = value2 % g?

@anon Huge hint if you give up i.imgur.com/4YYNbFE.gif

ok so I am fine with the consistency part

but now once I get g,a,b = (3,3,-2) from the egcd algorithm

My question is how to take that and get it to spit out 50 mod 105

@columbus8myhw yes I was thinking about dedekind cuts. that's why I said you gave away the game visibly replacing R with Q

I assume the 105 modulus is simply lcm(15,21)

unless there is a more efficient way to arrive at that I'll stick with it for now

@anon Pretend that by $[a,b)$ I meant $\mathbb Q\cap[a,b)$ by the way

@user2597879 to solve 15a-21b=3 you should be able to plug those numbers into the extended euclidean algorithm and get (a,b)=(3,2). and lcm of the modulis is 105.

but the extended algorithm gives 3,-2

@user2597879 what did you plug into it?

The moduli, 15 and 21

(15)a+(-21)b=(3), notice the -21 is negative

But how can I know that from a systematic point of view?

Do I just treat that as negative all the time?

read it

(N)a+(-M)b=(v-u), you can see the inputs for the extended euclidean algorithm in parentheses.

that will give you a and b

then x=u+aN (also =v+bM) mod lcm(N,M) is the solution

ok but then if I do the egcd algorithm on 5a + (-7)b = 1, in other words egcd(5,-7), I get (g,a,b) = (-1,-3,-2)

first of all, (-3,-2) is not a solution to 5a+(-7)b=1. it's a solution to 5a+(-7)b=-1.

second of all, why is it saying g=-1? shouldn't standard choice of gcd be positive?

notice how your issues seem to have nothing to do with solving congruences, and everything to do with correctly implementing the extended euclidean algorithm, and putting in the correct input

That's why I made the questions about the egcd (but yes in terms of solving congruences)

And I don't know, this is a standard implementation of the algorithm found on the net

well, get a better implementation that isn't funky with negative signs, chooses a positive gcd, and gets an actual solution to the linear diophantine equation ax+by=c. or get a programmer to help you understand what's going on with the code.

I found a different one, returns (3,3,2)

Finally got it outputting the right numbers

good

However now what if we have: x = 50 mod 105 with x = 15 mod 35

note that both of your questions insinuate you are fine with the EEA, and are only concerned with using it to solve the congruences

I was fine with it because I had a working implementation of the algorithm

but kept running into problems with non-coprime moduli

so I need a different implementation for my CRT

@user2597879 they are not consistent

but there is a solution as per Robert Israel's answer

oh nvm they are

they're consistent but now the algorithm gives different results for x

give more detail

vals = [50, 15], mods = [105, 35]

so u=50, v=15, N=105, M=35

as per your notation correct?

g = gcd(105, 35) = 35

u % v = v % g = 15 so that's fine

pay attention to the signs

x=50+105a=15+35b implies 105a-35b=-35

egcd(105, -35) = (g,a,b) = (35, 0, -1)

mod still 105, but now (u+aN) mod 105 = 50 whereas (v+bM) % 105 = 85

if your egcd has two inputs, then you need to get your equation into the form ax+by=1

so, 105a-35b=-35 divided by -35 gives -3a+b=1

or with u,v if we want better letters, w/e

off topic algebra. Can one always find the rational canonical form by using the minimal and characteristic polynomials, or is there ever a case in which one needs to find a matrix $P$ so that the canonical form is $P^{-1}AP$?

when dividing by the gcd do you also divide the moduli?

or just the coefficients of things

you divide the equation

the coefficients that appear on the LHS of the equation happen to have been the original moduli, of course

(with one sign difference)

okay so now I have reduced it to -3a + 1b = 1

g,a,b = (-1 0 -1)

@TheSubstitute one doesn't need to find the matrix P to know the canonical form. one finds the char poly, factors into irreducible factors over your field, then finds the companion matrices to the powers of irreducible factors appearing in this factorization. one uses these companion matrices as diagonal blocks in the canonical form.

all of this is essentially applying the fundamental theorem of finitely-generated modules over Euclidean domains (one can do PIDs too but EDs are easier IIRC). one lets V be a space over F, and A a linear map, and considers V as a F[A]-module.

but see now at this point it seems lost again, because now it seems impossible to ake those tiny results and somehow get 50 mod 105 from it

so i am not sure reducing helped

@anon is there ever a case, outside of RCF, (say for a graduate algebra class) that one needs to find such a $P$ other than if instructed to?

@user2597879 why is your g coming out negative again? the solution to -3a+1b=1 is (a,b)=(0,1) or (1,2) or somesuch.

you need to figure out how to use the egcd more consistently

This is the implementation that gave the correct result in the previous problem

find an implementation that does what we want

I'm just going to force it to multiply everything by -1 if g is negative

yeah, if you want, you can add on some code to negate everything and make g positive if need be

okay, now (g,a,b) = 1 0 1

anyway, given a=0,b=1 recall we said x=50+105a=15+35b. that gives x=50. the lcm(105,35)=105, so we have x=50 mod 105. done.

is that gcd check the only necessary part to ensure a solution exists?

yes

going to try to tie this all together and see if it works

eeeeeee

so, to summarize. given x=u (N) and x=v (M), check for consistency by checking that u=v mod gcd(N,M). saying x=u+Na=v+Mb yields Na-Mb=v-u. divide this equation by gcd(N,M,v-u) to get Ta-Rb=w. input (T,-R) into the EEA and make sure the g it returns has the same sign as w (if not, negate the output to ensure it does). this yields a and b, which you can plug back into x=u+Na or v+Mb. this solution for x is correct mod lcm(N,M).

@TheSubstitute probably

@anon thanks :)

5a + (-7)b = 1, egcd giving (1 -2 -3)

something messed up again i think

need to sleep... thanks anon for your patience and help

mmhmm

@robjohn This is downright ambiguous! Unforgivable!

@MickLH what is ambiguous? Oh, that :-)

If I am to have the self respect to try and form a consistent set of rules to parse this, it's a double integral

@MickLH It is indeed intended as a double integral. It is just not easy to parse it.

@MickLH Though, it could be a product of two integrals with a free $x$

I just let out a sigh of relief to see that one is dt and it actually does make sense

What do you call someone who is good at word problems and bad at math and bad at arithmetic?

What types of problems are allowed on this website???

@VictorB. math.stackexchange.com/help/on-topic

hi @KarlKronenfeld

hello @Balarka

i went ahead and read up the proof that $\mathsf{PA}$ is $\omega$-consisten implies it's incomplete after the discussion we had.

don't know why i did it, but the proof's amazing.

I still don't understand it at a "deep enough" level, if you get what I am saying.

I see that it's related to the liar paradox style synopsis that I gave, but the precise manner in which he does it is a bit sophisticated

as far as I understand it, the general idea is to construct a Tarski schema assuming $\mathsf{PA}$ is $\omega$-consistent, and then apply Tarski's theorem than $\mathsf{PA}$ extended with a schema is always inconsistent.

he constructs the Tarski schema by defining the formula $F(\bar n, \lceil \varphi \rceil)$ for a statement $\varphi$ and a numeral $n$, which satisfies $\vdash F(\bar n, \lceil \varphi \rceil)$ iff $n$ is the Godel code for some proof of $\varphi$.

then it's easy to check that $T(\lceil - \rceil) := \exists x F(x, \lceil \varphi \rceil)$ is a schema.

is there anything else to it, @KarlKronenfeld?

ok and what is a tarski schema

the formula has to be recursive, for one, but that is easy to show by constructoin

@KarlKronenfeld a tarski schema $T$ is just a predicate $T$ such that for all scentences $\varphi$, $T(\lceil \varphi \rceil) \leftrightarrow \varphi$.

god, the hardest thing about logic is that you don't know what the latex symbols for these are.

you can think of a schema as a scentence of self-reference, which says, say, "$\varphi$ is true". of course, if $\varphi$ is true, this scentence must also be true and vice versa.

Looks like the work has been shifted to Tarski's theorem in that outline, in fact.

yep.

The precise construction is what I am having trouble comprehending atm

Got the whole $F$ causes problems thing

the precise construction of what?

oh, the tarski schema?

of the statement that kinda sorta claims its own unprovability. You can't just encode that.

yeah, i don't get what you said about encoding that statement. i don't see it being done in the proof I read.

is that what godel does in his original proof?

presumably equivalent work is being done in a proof of tarski's theorem

tarski's theorem is an easy corollary of diagonal lemma

diagonal lemma says that in $\mathsf{PA}$, for every formula $\psi(x)$, there is a statement $\varphi$ such that $\psi(\lceil \varphi \rceil) \leftrightarrow \varphi$.

a lot of godel's time is spent on ensuring the definition of (the negation of) F is recursive, so that its truth corresponds with its provability within the system. then some constructions are made that I don't fully understand. then you get the unprovability of one of them

now consider a schema $T$. in $\mathsf{PA} + T$, you can apply diagonal lemma to obtain a statement $\varphi$ such that $\varphi \leftrightarrow (\lnot T)(\lceil \varphi \rceil) \leftrightarrow \varphi$. however, $T(\lceil \varphi \rceil) \leftrightarrow \varphi$ by definition of $T$. then that's a contradiction to consistency.

@KarlKronenfeld hm, why do you need the recursive thing anyway?

"to correspond truth with provability within the system"

@BalarkaSen We can keep on digging, until you reach an actual construction. :)

isn't [something] is true implies [that something] is provable assumed in the ambient deductive logic of the theory?

nah

that's equivalent to completeness

yes. we're assuming that $\mathsf{PA}$ is $\omega$-consistent and complete, and then reaching a contradiction

ah, but not in the proof sketch I gave

oh.

only $\omega$-consistency is assumed

@KarlKronenfeld right, i should point out here that i don't know how to prove the diagonal lemma. :P

i figure an equally technical construction is in there somewhere

hi

hey, bananas.

one more week until my oral algebraic topology exam

i'm excited and simultaneously terrified :P

good luck! i think you'll do fine, you know a lot of topology by now.

i'm reviewing the proof of van kampen's theorem right now

trying to extract the gist of it

i never digested the kernel computation. ugh.

yeah that's where im stuck

the proof of surjectivity reminded me of barycentric subdivision

i know the proof of $H_i(X\times S^n) \approx H_i(X) \oplus H_{i-n}(X)$ by heart now, so i hope i'm asked to compute the homology of a space $X\times S^n$ lol

probably you can use it in some other question

keep tools at the back of the head, to be used whenever needed

for sure

@Karl you've heard of type theory, by any chance?

nope, it can be connected to programming, right? (which I have experience in)

it is, but it's of some theoretical interest too

surely

in a sense, types generalize set theory. the usual set theory has two layers, one the ambient deductive logic behind and two, the axiomatic system

type theory somehow puts the two in an equal footing.

hm.. well, sets can simply be viewed as certain predicates anyway

in other words idgi @ the equal footing bit

instead of sets, there are things called "types". elements of sets, $a \in A$ are replaced by "terms in types" $a : A$. there are things called function types $A \to B$ defined between any two type $A, B$. but the most interesting thing of all is the identity type $\mathsf{Id}_A(a, b)$, terms of which you can think of as "proofs" that $a = b$. these are equivalently like paths, and indeed you can give them an $\infty$-groupoid structure to incorporate homotopy theory in it.

this thing is called "homotopy type theory", and Voevodsky claims that it may be a unifying theory of foundations of mathematics. it can interpret a lot of topological/homotopy theoretic notions formally, for one.

ok now I "know" what homotopy type theory is, and I do "get" what you mean by paths so that is pretty cool

apparently, i don't understand what's going on in there.

don't understand the unify all of mathematics part though

i don't mean "unifying all of mathematics". i mean people thinks it can be used to formally interpret all of mathematics. like, ZFC can be used to formally interpret set theory, and category theory can be used to formally intepret algebra/topology/whatever.

maybe "universal construction" on the part of category theory. I see what you mean.

in a vague sort of way, there have been two schools trying to formalize mathematics : category theorists and logists. type theory lies somewhat in the middle of category theory and logic. a further amalgation with the notion of homotopy should give rise to something very powerful which will formalize a lot of math. at least, that's the logic of HoTT-ists.

pretty weird.

doesn't motivate me to read about it just yet, but yeah it will be interesting to see if they have any major successes

yes, i guess.

@BalarkaSen how would you compute the fundamental group of $S^1\times [0,1]/\sim$ where we make the identifications $(z,1)\sim (z e^{2\pi i/n},1)$ and $(z,0)\sim (z e^{2\pi i/m},0)$ ?

@iwriteonbananas So essentially, you're taking a cylinder, identifying points on the top which are obtained from rotating by angle a multiple of $2\pi i/n$ and the same thing done with the bottom with $2\pi i/m$ instead.

why don't you do van kampen? cut out the cylinder from the middle, $\epsilon$-thicken both pieces to get an open cover $\{U, V\}$ where $U$ and $V$ are both homotopy equivalent to $S^1$.

the maps $\pi_1(U \cap V) \to \pi_1(U)$ and $\pi_1(U \cap V) \to \pi_1(V)$ are just multiplication by $m$ and $n$ respectively, right? so there you go.

Hello @BalarkaSen what kind of maths have you been thinking today?

nothing interesting, mostly reading bits of this and bits of that about logic.

Logic ... You mean Gödel and stuff?

yes.

I always wanted to know what Gödel talks about .

But it us better I leave it for some other day

It says that any mathematical theory (something with a few axioms, and with an ambient logical system) extending Peano arithmetic (i.e., where you can do arithmetic) can't be both consistent (both $A$ and $\lnot A$ can't be true) and complete (there is no statement which can neither be proved nor disproved).

Seems weird ...

It feels like it gives you a huge weapon using which you can criticize statements

Most of the people who tries to criticize mathematics using G\"odel doesn't understand G\"odel. The incompleteness theorem just says that Hilbert's program can't be finished. Of course, that's a very interesting fact, but it by no means implies that mathematics (even axiomatization of mathematics) is pointless.

I think you are also thinking something along the lines. If you're not, give me an example.

@Balarka Sorry I don't understand about Godel .. I did not want to criticize any statement with Godel .. I was just thinking what it might do and whatever I said is wrong because I don't understand anything about logic :)

Well I disagree that mathematics is pointless

Mathematics is full of fruits which for me are just too high to reach now

@BalarkaSen, do you read under Mahan Mj?

Anyways @Balarka I will talk about Godel again only when I have knowledge about it