$\exists x \in \Sigma^* (t=sx)$

Have I interpreted the above into words correctly?:

"There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, where sigma contains string 't', which is a concatenation of string x and string s."

I'm not clear on how/whether t=xs is an alphabet.

Note: an earlier version of this question, with some errors, was posted at Math.SE.

  • $\begingroup$ Please don't post the same question to multiple Stack Exchange sites. It's against site rules because it fragments answers and wastes people's time when they put effort into answering questions that have already been answered elsewhere. $\endgroup$ – David Richerby Feb 13 '16 at 18:31

Since $t$ and $s$ aren't quantified, the expression $\exists x\in\Sigma^*\;(t=sx)$ is a predicate $P(s, t)$ in inputs $t$, and $s$. In other words, we could write $$ P(s, t)\stackrel{\text{def}}{\equiv}\exists x\in\Sigma^*\;(t=sx) $$ meaning "$P(s, t)$ is true if and only if there is a string $x$ over $\Sigma$ for which $t$ is the concatenation of $s$ and $x$". In answer to your question, $t=sx$ isn't an alphabet, but is a condition, namely that $t$ (a string) can be expressed as the string $s$ followed by the string $x$.

Look at some examples, with $\Sigma = \{a,b\}$,

  1. Is $P(a, abb)$ true? It is if we can find a string $x$ such that $abb=ax$. Obviously $x=bb$ works here, so $P(a, abb)$ is true.
  2. Is $P(ba, abb)$ true? It is if we can find a string $x$ such that $abb=bax$. There's no $x$ we can use here, so $P(ba, abb)$ is false.

In general, it's not hard to see that $P(s,t)$ can be interpreted as "$s$ is a prefix of $t$".

In a different universe of discourse, if $s, t, x$ were integers, can you see that $\exists x\in\mathbb{N}\;(t=sx)$ would mean that $s$ divides $t$?

  • $\begingroup$ Many thanks for this explanation. Can you recommend any good sources where I can read more about this? I have transferred to a course that assumes I know all this, but I've obviously got lots of gaps. For example, I'm not sure what 'quantified', 'predicate' mean in this context. By it not being quantified do you mean that it hasn't been assigned the function P(s,t)? My intepretation of your end note: There exists an x, in the set of real numbers, which is always a factor of t. Therefore 's divides t'? Would my reading of the notation be correct? The brackets kinda confuse me. $\endgroup$ – kjldfg Feb 13 '16 at 20:03
  • $\begingroup$ @kjldfg. What you're looking for is known as predicate logic. Any intro logic text will cover it. For your other questions, a predicate is a sentence which can be true or false depending on the values of its variables, like (in integers) "$x$ is a multiple of 3" or (in people) "$x$ and $y$ are related". A variable $x$ is said to be quantified if it is part of an expression and $\exists x$ or $\forall x$ appears in the expression. $\endgroup$ – Rick Decker Feb 13 '16 at 20:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.