How do I prove that finite Stars are not defined in First Order Logic Consider $ D $ as Set and $v \notin D$. A Star is a graph G with a set of nodes $B \cup \{v\}$ with a set of edges defined as $\{\{v,d\}| d\in D\}$
Show that the class of finite stars is not defined in First Order Logic.
I have two questions regarding that, why would that not be defined in First Order Logic?
Because something like
$$
\exists v \forall b  E(v,b)
$$
Wouldn't that be a class that is defined in first order Logic? And has the same attributes as a class?
 A: I will assume, alhough you should probably make this clearer in your question, that you are quantifying over nodes and you have a binary predicate $E$ stating that two nodes are connected by an edge.
Your formula $\exists v\forall b E(v,b)$ just says that there exists an element (let us call it center) which connects to every other element, but it doesn't state that two elements that are not the center can not be connected, what is necessary in a star graph. Of course, you could describe star graphs by the more complicated
$$\exists v\forall a\forall b E(v,a)\wedge \Big(E(a,b)\rightarrow (a=v\vee b=v)\Big),$$
but nothing is said about their cardinalities... And that is where you find your problem. Assume $T$ is an axiomatization of the theory of finite star graphs: if you consider the formula
$$\varphi_{n}=\exists a_{1}\cdots\exists a_{n} \bigwedge_{i=1}^{n}\bigwedge_{j\neq i}\neg(a_{i}=a_{j}),$$
any model satisfying $\varphi_{n}$ has at least $n$ elements. Consider then the theory $T\cup\{\varphi_{n} : n\in\mathbb{N}\}$. It has a model from the compactness theorem, since, for any finite subset $T_{0}\cup F_{0}$ of $T\cup\{\varphi_{n}:n\in\mathbb{N}\}$, with $T_{0}\subseteq T$ and $F_{0}\subseteq \{\varphi_{n} : n\in\mathbb{N}\}$, there exists $N=\max\{n\in\mathbb{N} : \varphi_{n}\in F_{0}\}$, and so a star graph with $N+1$ elements is a model of $T_{0}\cup F_{0}$: since any finite subset of $T\cup\{\varphi_{n} : n\in\mathbb{N}\}$ has a model, the whole thing must have a model as well.
But what is a model of $T\cup\{\varphi_{n}:n\in\mathbb{N}\}$? Is a model of $T$, that is, a finite star graph, which is also a model of $\{\varphi_{n} : n\in\mathbb{N}\}$, meaning that it is infinite. A contradiction, hence there is no axiomatization of finite star graphs.
