# What is the definition of a property?

I have seen 2 answers in stackoverflow:

My problem is: Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages).

Same as for: Saying that a property is trivial if it is does not contain any TM languages is not the same as saying that a property is trivial if it is empty.

• Have you read the comments under the second answer you link? You are right, it's not the same thing, and they don't claim that (but wrote the post in a potentially confusing way.)
– Raphael
Aug 31, 2017 at 18:16
• Then what is the currect definition? Aug 31, 2017 at 18:25
• I find the comments rather clear about that: the first. But that said, there are probably many equivalent definitions. Definitions are never "correct", there are only more or less useful.
– Raphael
Aug 31, 2017 at 18:25

## 1 Answer

We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies the property iff $L\in P$.

Rice theorem tells you that you can't, given a Turing machine $M$, check if $L(M)$ satisfies some non trivial property $P$, i.e. $P\neq \emptyset$, $P\nsupseteq RE$. Note that Shaull makes a distinction between semantic and syntactic properties in the comments. To the best of my knowledge, the standard definition of a property in the context of Rice's theorem is a set of languages.

• courses.engr.illinois.edu/cs373/sp2013/Lectures/lec25.pdf - Definition 3 - You are saying something complitly different. Aug 31, 2017 at 18:24
• FWIW, it's also common to express properties as predicates, i.e. boolean-valued functions (here of type $\Sigma^* \to \{0,1\}$). This is clearly equivalent, since subsets and indicator functions identify uniquely.
– Raphael
Aug 31, 2017 at 18:27
• @StavAlfi How so? I don't see it. (I think you need some time learning how to read mathematics. I can recommend the Book of Proof, which is available for free.)
– Raphael
Aug 31, 2017 at 18:28
• Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages)...... Aug 31, 2017 at 18:29
• Each TM has a corresponding language. So if it contains every TM, then it contains every language. Aug 31, 2017 at 18:33