3
$\begingroup$

Continuation of Free and bound variables in "if" statements

definitions:

A number is even if it is divisible by $2$.

The number is even if it is divisible by $2$.

Is the usage of the and a different in mathematical definitions(sorry for the poor example above, if you have any better example that would be appreciated). Also aren't mathematical definitions assertions ?

A number $n$ is even if it is divisible by $2$.

Every number $n$ is even if it is divisible by $2$.

I know that a definition is NOT an assertion and thus cannot be true or false(Right ?). The definition just describes a property(ies) of some mathematical object.

Now for the above two definitons is $n$ a free variable in the first but bound variable in the second ? Also the second definition can be expressed as $\forall n (n\ is\ even\ \leftrightarrow n\ is\ divisible\ by\ 2)$. Doesn't that mean that a definition in a sense is true or false since it can be expressed by a logical symbols ?

Another definition:

Suppose $n$ is an integer. Then $n$ is even if it is divisible by $2$.

Where is the location of Suppose $n$ is an integer(a precondition) in the logical structure of a definition(after or before the biarrow) ? $\forall n (n\ is\ an\ integer \rightarrow n\ is\ even\ \leftrightarrow n\ is\ divisible\ by\ 2)$ or $\forall n (n\ is\ an\ integer \land n\ is\ even\ \leftrightarrow n\ is\ divisible\ by\ 2)$ or $\forall n ( n\ is\ even\ \leftrightarrow n\ is\ an\ integer \land n\ is\ divisible\ by\ 2)$

Also when trying to prove "$x$ is even" what exactly should I do ?

Another definition:

Suppose $R$ is a partial order on a set $A$, $B ⊆ A$, and $ b ∈ B$. Then $ b$ is called an $R$-smallest element of B (or just a smallest element if $R$ is clear from the context) if $∀x ∈ B(bRx)$.

How do I express this definiton in logical symbols(are $A$,$b$,$B$, $R$ free or bound?)?What should I do if I want to prove that $z$ is a $H$ smallest element of $M$ ?

Suppose $f : A → B$ and $C ⊆ A$. The set $f ∩ (C × B)$, which is a relation from $C$ to $B$, is called the restriction of f to C, and is sometimes denoted $f|C$. In other words, $f|C = f∩(C × B)$.

What is the location of $f|C$ in the logical structure ?

Also, it would be great to give a list of books that could clarify misconceptions of these type.

$\endgroup$
4
$\begingroup$

Some theory

See George Tourlakis, Lectures in Logic and Set Theory. Volume 1 : Mathematical Logic (2003), I.7. Defined Symbols, page 112-on :

We start with a theory $\Gamma$, spoken in some basic formal language $L$. As the development of $\Gamma$ proceeds, gradually and continuously we extend $L$ into languages $L_n$, for $n ≥ 0$ (we have set $L_0 = L$). The theory itself is being extended by stages, as a sequence $\Gamma_n$, $n ≥ 0$. [...] At that same stage we also add to $\Gamma_n$ the defining nonlogical axiom of the new symbol in question.

Specifically, if $\varphi(x_1, ..., x_n)$ is some formula, we then can introduce a new predicate symbol “$P$” that stands for $\varphi$.

This entails adding $P$ to $L_k$ as a newn-ary predicate symbol, and adding

$P(x_1, ... x_n) ↔ \varphi(x_1, ..., x_n)$

to $\Gamma_k$ as the defining axiom for $P$.

Thus, we can start with the formula $\varphi(n) := \exists y(n = 2 \times y)$ and extend the "basic" language with the new predicate $Even(n)$ and the theory with the defining axiom :

$Even(n) \leftrightarrow \exists y(n = 2 \times y)$.

This is "implicitly" universally quantified, i.e. : $\forall n [Even(n) \leftrightarrow \exists y(n = 2 \times y) ]$.


Comment

About the natural language, my "feeling" is that :

a number $n$ is even if it is divisible by $2$

is a "correct" form for a definition; "a number $n$" must be interpreted as "a number $n$ whatver" i.e. as having $n$ universally quantified.

I would prefer to "read" :

every number $n$ is even if it is divisible by $2$

as meaning : "for every number $n$, $n$ is even if it is divisible by $2$", which amount to the same statement.


Question (1) :

when trying to prove "$x$ is even" what exactly should I do ?

$Even(n)$ is defined as : $\exists y(n = 2 \times y)$; thus, proving that e.g. $6 = 2 \times 3$, by rule of logic we can derive : $\exists y(6 = 2 \times y)$, which - by definition - is :

$Even(6)$.

Question (2) :

suppose $R$ is a partial order on a set $A, B⊆A$, and $b∈B$. Then $b$ is called an $R$-smallest element of $B$ (or just a smallest element if $R$ is clear from the context) if $∀x∈B(bRx)$. How do I express this definiton in logical symbols(are $A,b,B,R$ free or bound?)?

See Tourlakis, cit, page 114 :

In this case we have to add a new $n$-ary function symbol $f$ into $L_k$ by a definition. That is, we add $f$ to $L_k$ and also add the following formula to $\Gamma_k$ as a new nonlogical axiom:

$y = f(y_1, ... y_n) ↔ \varphi(y, y_1, ... y_n)$

provided we have a proof in $\Gamma_k$ of the formula : $(∃!y) \varphi(y, y_1, ... y_n)$.

In our example, assuming for simplicity that we have already introduced with a definition the symbol $PO(x,y)$ as an abbreviation for "$x$ is a Partial Order on $y$", we can introduce the following symbol $min(x,y,z)$ as an abbreviation for "the smallest element of $z$ for the relation $x$ on $y$" by the definition :

$\forall R \forall A \forall B \forall b \quad [ b = min(R,A,B) \leftrightarrow (R \subseteq A \times A \land PO(R,A) \land B \subseteq A \land b \in B \land \forall x (x\in B \rightarrow bRx)) ]$

Now, according to this definition, the answer to the question :

what should I do if I want to prove that $z$ is a $H$-smallest element of $M$ ?

is straightforward. You have to prove that, for $z \in M$ :

$\forall x (x\in M \rightarrow zHx)$.

$\endgroup$
13
  • $\begingroup$ Great Answer but here is a couple of points I don't understand: 1) $R⊆A×A∧PO(R,A)∧B⊆A∧b∈B→∀x(x∈B→bRx)$ OR $(R⊆A×A∧PO(R,A)∧B⊆A∧b∈B)→∀x(x∈B→bRx)$ 2)why $→∀x(x∈B→bRx)$ not $\leftrightarrow ∀x(x∈B→bRx)$. I thought if in definitions meant if and only if $\endgroup$
    – Nameless
    Jun 5 '14 at 13:06
  • $\begingroup$ @Nameless - you are right for 1) : it is better to group between parentheses all the conjuncts [but note that $(A \land B) \rightarrow C$ is equivalent to : $A \rightarrow (B \rightarrow C)$]. Regarding 2) : NO, the $\leftrightarrow$ of the definition is that between the definiendum (i.e.$b=min(R,A,B)$) and the definiens (i.e.the "big" sub-formula on the right). $\endgroup$ Jun 5 '14 at 13:14
  • $\begingroup$ Ok. Lets say we have this Definition: Every integer is even if it is divisible by 2. is same as If n is an integer then n is even if it is divisible by 2. means $\forall n (Even(n)\leftrightarrow $ (**n is integer** $\land \exists k(n=2k)))$ (right ?) is it the same as $\forall n (Even(n)\leftrightarrow $ (**n is integer** $\rightarrow \exists k(n=2k)))$ ?? $\endgroup$
    – Nameless
    Jun 5 '14 at 13:28
  • 1
    $\begingroup$ Also why $→∀x(x∈B→bRx) $ and not $\land ∀x(x∈B→bRx)$. Just to clarify it: you put the precondition before the $\rightarrow$ because these are always given, because without them the definition will not apply to the object we want. And the thing we want to prove after the $\rightarrow$. In this case this ∀n(Even(n)↔ (n is integer →∃k(n=2k))) is right while the other one wrong(is this correct ?). Right ? $\endgroup$
    – Nameless
    Jun 5 '14 at 13:34
  • $\begingroup$ 1) Why did you change ∀x(x∈B→bRx) to ∀x(x∈B∧bRx). The first one is right when we have a universal quantifier ? $\endgroup$
    – Nameless
    Jun 5 '14 at 14:31

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.