I am having some trouble wrapping my head around the specific definitions of things when it comes to logic. This is my current understanding from my own note-taking, can anyone correct me?

Expressions: $2+2$, for example. Any sequence of mathematical symbols which produce some mathematical object like a number, matrix, function, set, etc.

Statements: Usually made up of expressions and must evaluate to either true or false. Statements must be well-formed. Not invoking undefined behavior like $0/0=1$ or bad syntax like $==3++-4=-$. So $2+2=4$ is a true statement, $2+2=5$ is a false statement. Statements are allowed to contain words and properties, e.g. "$30+7$ is prime".

Relations: Symbols like $=$, $<$, $\leq$, $\in$, $\subset$, etc, which provide some relationship between expressions to create a statement.

Properties: Is prime, is continuous, is invertible, etc.

Logical Connectives: And, or, not, if-then, implies, if-and-only-if, etc. These connect statements to create "compound statements" which are themselves still statements.

Compound Statement: For statements $P$ and $Q$, things like $P \land Q$, $P \lor Q$, $P \implies Q$, $P \iff Q$, etc.

Proposition: I don't really understand the difference between this and a statement but I am guessing $2+2=4$ is also a proposition, or something like "John has brown hair."

Predicate: Like a proposition but with variables, may be true or false depending on the value of the variable. For example $P(x) = x + 2 = 5$ is true when $x=3$ and false otherwise.

Quantifier: The universal quantifier $\forall$, or the existential quantifier $\exists$.

Universe: The relevant set of objects we draw from, referred to via quantifiers. For example $\forall x \in \mathbb{N}$ means "for all $x$ in the natural numbers", the natural numbers here would be the universe.

Is my understanding correct so far?


Pretty good. Personally, I would do 'predicates' a little different. The $P$ would be the predicate, while $P(x)$ would be a formula.

Also, you can regard properties as $1$-place predicates, and relations as $n$-place predicates. For example, $\le$ is a $2$-place predicate, and $\le(x,y)$ would be a formula using that predicate. ... though we will often use the infix notation $x \le y$ instead.

Indeed, the notion of a 'formula' is important but missing from your list. You can create Atomic formulas by giving an $n$-place predicate $n$ terms, which can either be constants (like $1$), variables (like $x$), or complex terms (like $x+1$). Atomic formulas can be combined using logical connectives into 'compound formulas', and formulas can be quantified.

Statements are formulas that do not have free (i.e. unquantified) variables).

  • $\begingroup$ If $P$ is a predicate but $P(x)$ is not then how would one even "state" or "frame" or "express" $P$ by itself? $\endgroup$ – user539262 Mar 11 '18 at 20:20
  • $\begingroup$ @user539262 You typically provide a little 'legend' .. saying that $P(x)$ means '$x$ has property ...' $\endgroup$ – Bram28 Mar 11 '18 at 20:26
  • $\begingroup$ Where do quantifiers fit in exactly? Do they transform things into a set? Are they an intrinsic part of predicates? Can they apply to statements or propositions? $\endgroup$ – user539262 Mar 11 '18 at 20:32
  • $\begingroup$ @user539262 Quantifiers do not transform things into sets, nor are they an inherent part of predicates. Syntactically, you put a quantifier in front of a formula, but what you quantify is of course some variable; that is, by putting $\forall x$ in front of a formula $\phi$, all free variables $x$ occurring in $\phi$ get quantified. The result of a quantification is always a new formula, but it could become a statement if thanks to the quantification there are no more free variables. $\endgroup$ – Bram28 Mar 11 '18 at 20:40
  • $\begingroup$ So would $P(x) = (\forall x \in \mathbb{R}) \land (x > 5)$ be a quantified predicate? Would $P(x) = (x > 5)$ be an unquantified predicate? $\endgroup$ – user539262 Mar 11 '18 at 20:58

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.