0
$\begingroup$

I'm trying to express the closure under countable union by using formal language, as I'm praticing the language. The following is the statement that I found on proofwiki. $$\forall x_n\in\Sigma:n=1,2,\cdots:\bigcup_{n=1}^{\infty}x_n\in\Sigma$$ It seems that it's written in formal language, but strictly speaking, the sentence has some grammatical errors, somewhat informal and implicit (e.g., an alphabet after a quantifier must be a variable, but $x_n$ is implicitly given as a function, and dots in $n=1,2,\cdots$ is not an alphabet of formal language.)

I think the sentence should be in $L^{\mathrm{II}}$, which means it's second-order logic. What I've done is the following but am not sure. $$\forall x:((\exists f:f:S\leftrightarrow\mathbb{N}\wedge Sx\wedge \Sigma x)\implies \Sigma\bigcup S)$$ ($f:S\leftrightarrow\mathbb{N}$ means a bijection from a set $S$ to the set of natural numbers $\mathbb N$, $S$ and $\Sigma$ are unary relations.)

$\endgroup$
  • $\begingroup$ If by "closure under countable union" you mean under all countable unions, then shouldn't you have $\forall f$ rather than $\exists f$ ? $\endgroup$ – DanielWainfleet Sep 30 '15 at 7:03
  • $\begingroup$ @user254665 Umm, I don't think so. Since a set $S$ is free variable, it can be any set that satisfies the statement. $\endgroup$ – Shin Kim Sep 30 '15 at 7:24
  • $\begingroup$ You don’t want $f$ to be a bijection, since countable includes finite. And I frankly think that even with that corrected, your style obfuscates the definition. I would simply define cardinality (or at least countable cardinality) first and write $$\forall S\subseteq\Sigma\left(|S|\le\omega\to\bigcup S\in\Sigma\right)\;.$$ $\endgroup$ – Brian M. Scott Sep 30 '15 at 15:58
  • $\begingroup$ I was going to ask about the notation of the Q. I didn't know whether it was just a standard that I'm not familiar with so I waited for someone else to comment on it. $\endgroup$ – DanielWainfleet Sep 30 '15 at 16:04
  • $\begingroup$ @BrianM.Scott Ah, it makes everything clear. Yeah, after that I formulated another one, $\forall S((S\subseteq \Sigma \wedge \exists f f:S\hookrightarrow \mathbb N)\rightarrow\Sigma\bigcup S)$, but I prefer Your formula way more than mine. Really appreciated. $\endgroup$ – Shin Kim Oct 1 '15 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.