Graphs

So you can have vertex v3.4893594... and vertex v4354.45639045034985604... ? Fair enough then

So I guess in this case whether the set of graphs is countably infinite depends entirely on whether you let the vertex set be countably or uncountably infinite which makes the question kind of boring.

>the set of graphs
No such thing.

Why is there no such thing retard

>Proof by repeated assertion.

>Why is there no such thing retard
If the set of graphs existed, then there would be a set of all pairs (V,E) with vertex set V and edge set E. Forgetting E, there would be a set of all vertex sets V. But any set can be a vertex set, and so there would be a set of all sets, which is not such a thing.

There's no such thing as a set of all graphs you moron.
Holy SHIT study some set theory before spewing mindless bullshit

Sorry I'm legitimately retarded

That the fuck? you can have a set of all vertices because there isnt a one to one corresponding between the collection of sets and vertexes, all sets with the same cardinality corresponds to the same set of vertices. The 'set of all vertices' is the skeleton of the category of sets of vertices, which do form a set and is whos objects are equivalent to the category of ordinal numbers objects {0,1,2,3,...}, the objects of which form a set.

It would be helpful if you autists finally write down a definition of a graph, then you can spare yourself those back and forth.

But to be honest
>all sets with the same cardinality corresponds to the same set of vertices
is the more autistic claim, so I'm gonna go with the first poster on this one.

Of course, I see why you'd want that and it's somewhat clear that when people do graph theory 101, they kind of think that way (because they are not concerned with pathologies). But nobody actually defines sets of verices as cardinals (i.e. muh skeleton category) like you do here. That's too much baggage for page 1 of a graph theory book or paper.
(And if they are category theorist, they probably define graphs as the functors 2->Set, where 2 is two object category with two parallel errors)

>any set can be a vertex set
does graph theory allow uncountable or even infinite vertex sets?
i tried googling but all i got was a mathoverflow thread that was closed before it was answered

That's obviously just a matter of definition. Most books will not bother to say "countable" anywhere but when they write formulas where e.g. they consider the sum over all vertices, then it's clearly implied they are finite. So you can study anything you like. Mostly people will write down theorems assuming the vertex set is finite.

A graph is defined as a presheave where the tuple of the target and source map is a monomorphism. the functors 2->Set is a lot more general than just graphs.

I think 2->Set would be directed psudographs.

Suppose your verticies are labelled by a set X.
The choice of edges is the powerset of XC2 which is roughly 2^(X^2). There will be uncountably infinitly many graphs if there are countably infinite verticies.

If you consider the set of all labelled graphs with a finite number of verticies, there is a countably infinite number of them.
For graphs with 1 labelled vertex, there are 2^(1C2), for 2 verticies there are 2^(2C2), for 3 there are 2^(3C2), etc. It is easy to come up with a bijection as long as you have a systematic way of ordering the graphs on n verticies for any n.

wat

Am I wrong?

If were going by graph theory 101, then 2 graphs being the same means they are isomorphic to each other, thus have the same adjacency matrix modulo some transformations, that can only be the case if sets of vertices with the same caridnality are taken as being the same vertices.

The set of all finite graphs is countable:
Every graph on n vertices is isomorphic to a graph on vertex set [n]. For every graph G on the vertex set [n] there is a canonical bijection G -> [n]^(2) by identifying G with its set of edges. Now [n]^(2) \subset [n]^2, thus we can find an surjection from the set of all finite graphs to NxN. Since |NxN|=|N| and the set of all finite subsets of N is countable, the set of all finite graphs is countable.

Obviously there are more than countably many (countable) infinite graphs.

are you FUCKING kidding me I was thinking about the cardinatlity and definability of sets of graphs this morning aswell wtf. And Ive never heard much about the topic either.
What I was wondering is if the set of all graphs exists. The set of all finite graphs does have some clear cardinality (count possiblw adjacency matrices) but the set pf all graphs does not exist.
Every set surjectivrly induces a tree, so fromthe set of all trees you can construct a tree of all trees which then contains itself. I believe you can then contradict this just like with sets. As trees are subset of graphs the set of all graphs doesnt exist.
What do you think?

to expand, take any set and remove all the elements, leaving only the brackets. This structure is a tree.
And the tree of all trees containing itself means that from the root node there is an edge which leads to the whole tree again.
I dont remember proofs that a set containing itself is contradictiory but it goes something like "form the subset of all sets not containing themselves blabla contradiction" afaik. And I suspect this works for a tree containing itself as well but Im not sure.

well the set of finite graphs is just the union of the set of graphs with n vertices which is finite that's all

>does graph theory allow uncountable or even infinite vertex sets?
Yes.

I believe he is speaking of finite graphs

when considering "all" graphs, you usually do it up to isomorphism (so there is only one graph with one vertex and no edge, etc.)

>does graph theory allow uncountable or even infinite vertex sets?
Yes, and there is even an infinite graph that contains any finite or countably infinite graph as an induced subgraph.

en.wikipedia.org/wiki/Rado_graph