1
$\begingroup$

Background

Definition: A ring $R$ is said to satisfy the ascending chain condition (ACC) for left (right) ideals if for each sequence of left (right) ideals $A_1,A_2,\ldots$ of $R$ with $A_1\subseteq A_2\subseteq\cdots,$ there exists a positive integer $n$ (depending on the sequence) such that $A_n=A_{n+1}=\dots$.

Questions

If I want to translate the portion where it says: "if for each sequence of left (right) ideals $A_1,A_2,\ldots$ of $R$ with $A_1\subseteq A_2\subseteq\cdots,$ there exists a positive integer $n$ (depending on the sequence) such that $A_n=A_{n+1}=\dots$" in the above Definition, does it go as follow:

$$(\exists n\in \Bbb{N})(\forall i>n )(\forall \{A_i\}_{i\in \Bbb{N}}\subset R)(A_1\subseteq A_2\subseteq\cdots \Rightarrow A_n=A_{n+1}=\dots)$$

If so, I don't think the translation is complete, since I am not sure how to capture the $\ldots$ notation in symbolic logic notation.

$\endgroup$
3
  • $\begingroup$ Though the question arose for ideals, it makes sense for any (po)set so I removed those tags. $\endgroup$
    – Bill Dubuque
    Commented Jun 14 at 19:43
  • $\begingroup$ @BillDubuque thank you for the editing help. I was not sure at first what the appropiate tags should be. $\endgroup$
    – Seth
    Commented Jun 15 at 0:51
  • $\begingroup$ @ryang I just voted for the answer. Sorry for the delay. I also have a minor question for my post on superset notation where you posted an answer. $\endgroup$
    – Seth
    Commented Jun 19 at 18:14

3 Answers 3

Reset to default
3
$\begingroup$

I don't think the translation $$(\exists n\in \Bbb{N})(\forall i>n )(\forall \{A_i\}_{i\in \Bbb{N}}\subset R)(A_1\subseteq A_2\subseteq\cdots \Rightarrow A_n=A_{n+1}=\dots)$$ is correct. It seems to say that you can find an $n\in\mathbb N$ such that any chain $A_1\subseteq A_2\subseteq \dots$ stabilizes with the same $n$. To capture $n$'s dependence on the chain of ideals, the quantifier $(\forall\{A_i\}_{i\in\mathbb N})$ should appear before the others, i.e. a better translation is $$\left(\forall \{A_i\}_{i\in\mathbb N}\subseteq R\right)\left[{\color{blue}{\left(\forall k\in\mathbb{N}\right)\left(A_k\subseteq A_{k+1}\right)}}\rightarrow{\color{green}{\left(\exists n\in\mathbb N\right)\left(\forall i\geq n, A_i=A_{i+1}\right)}}\right]$$ The blue part of the if-then checks if your collection of ideals is ascending, and the green part says that the chain stabilizes.

$\endgroup$
10
  • $\begingroup$ thank you for the correction. I thought I can just simply pull out $\exists n\in \Bbb{N}$ to the beginning of the statement when translating. $\endgroup$
    – Seth
    Commented Jun 14 at 6:01
  • $\begingroup$ @Seth you can't do this in general. For example, the statement $(\forall n\in\mathbb N)[(\exists k\in \mathbb N)(n=k)]$ does not say the same thing as $(\exists k\in \mathbb N)[(\forall n\in\mathbb N)(n=k)]$. The first says that for each $n\in\mathbb N$, we can find a $k\in\mathbb N$ that equals $n$ — a true statement — but the second says we can find a single $k\in\mathbb N$ such that every $n\in\mathbb N$ is equal to $k$. $\endgroup$
    – Alann Rosas
    Commented Jun 14 at 6:08
  • $\begingroup$ when doing these translation, is it better to stick close to the english as far as when the quantifier sign posts appear. Also, sometimes when i see statement: "$A_1,A_2,\ldots$ of $R$ with $A_1\subseteq A_2\subseteq\cdots,$ there exists", do I translate the "with" as "and" and $A_2\subseteq\cdots,$ there exists$, the missing 'then", I have to read it a few times to see if the "then" is inferred or not. How did you get so good at these translation exercsies. $\endgroup$
    – Seth
    Commented Jun 14 at 6:17
  • 1
    $\begingroup$ @Seth: You should beware that natural language sentences very often mangle the position of quantifier sign posts, so you need to think carefully when doing these translations. It is not always better to stick close to the english. For instance, consider this English sentence: "$x < \epsilon$ for all $\epsilon > 0$". When properly translated into prenex normal form it becomes "$\forall \epsilon > 0, x < \epsilon$". $\endgroup$
    – Lee Mosher
    Commented Jun 14 at 13:43
  • 1
    $\begingroup$ When making the translations, you should look at each quantifier and carefully identify which portion of the statement serves as the scope of that quantifier. Then, when translating into prenex normal form, you should pull the quantifier to the front of its own scope and no more than its own scope. $\endgroup$
    – Lee Mosher
    Commented Jun 14 at 13:47
2
$\begingroup$

For the first $\ldots$, you could write $\forall j \in \mathbb{N}, A_j \subseteq A_{j+1}$, and similarly for the second.

I think you have the order of things a bit mixed up in your translation though. The $A_1 \subseteq A_2 \subseteq \ldots$ should go on the outside, before the $\exists (n \in \mathbb{N})$, like in the original statement.

$\endgroup$
2
  • $\begingroup$ I thought I can have $\exists (n\in \Bbb{N}$ pull out to the beginning. $\endgroup$
    – Seth
    Commented Jun 14 at 6:00
  • 1
    $\begingroup$ No, if you put $\exists(n \in \mathbb{N})$ at the beginning, you are saying that there is a single value of $n$ that works for all choices of $A_i$. That is not true. $\endgroup$
    – Ted
    Commented Jun 14 at 14:42
1
$\begingroup$

To make Alann's answer—which I agree with—really succinct (though not necessarily advocating for this level of pithiness): $$\forall \{A_i\}_{i\in\mathbb N}{\subseteq} R \:\: \exists k{,}n{\in}\mathbb N \:\: \forall i \; \Big(A_k\subseteq A_{k+1} \;\text{and}\; i\geq n \implies A_i=A_{i+1}\Big).$$

for each sequence of left ideals $A_1,A_2,\ldots$ of $R$ with $A_1\subseteq A_2\subseteq\cdots,$ there exists a positive integer $n$ (depending on the sequence) such that $A_n=A_{n+1}=\dots$.

I thought I can just simply pull out $∃n∈\mathbb N$ to the beginning of the statement when translating

No: as the boldfaced parenthetical portion of the theorem helpfully reminds you, $n$ depends on $A_1,A_2,A_3,\ldots;$ this means that the quantification $\forall \{A_i\}_{i\in\mathbb N}{\subseteq} R$ must precede the quantification $\exists n{\in}\mathbb N.$ In fact, that reminder is technically redundant, since in general $$\forall y \exists xP(x,y)\kern.6em\not\kern-.6em\implies \exists x \forall y P(x,y).$$ On the other hand, $$\exists x \forall y P(x,y)\implies \forall y \exists xP(x,y).$$

$\endgroup$
3
  • 1
    $\begingroup$ Why does the $k$ have an existential quantifier? We need the collection to ascend at least eventually, i.e. $A_k\subseteq A_{k+1}$ for all sufficiently large $k$, but this seems to say that the collection stabilizes as soon as we find a single containment $A_k \subseteq A_{k+1}$. Maybe I'm misunderstanding something? $\endgroup$
    – Alann Rosas
    Commented Jun 14 at 18:03
  • 1
    $\begingroup$ @AlannRosas, $\Big((\forall x\,Px){\implies} Q\Big)\equiv\Big(\exists x\;(Px{\implies} Q)\Big),$ as proved in the appendix of this post. The logic statement that I wrote is the Prenex form of yours, which, again, I'm not asking the OP to translate that ascending-chain-condition definition into. $\endgroup$
    – ryang
    Commented Jun 14 at 19:09
  • 1
    $\begingroup$ I just read your proof; it makes much more sense now. Thank you! $\endgroup$
    – Alann Rosas
    Commented Jun 14 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .