Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
1answer
54 views

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ...
1
vote
3answers
203 views

Is -1 less than 0.1?

In a High School Maths Test, I presumed that since -1 has as much mathematical mass as a whole unit [-1 x -1 = 1, 1 x 1 = 1] and 0.1 represents one tenth of a unit, that -1 is greater than 0.1 -1 is ...
-1
votes
3answers
109 views

logical negation of a statement: any mammal that has long ears has at least [closed]

Write the negation of the following statement: Any mammal that has long ears has at least one of its predators with yellow eyes having all of its cubs that cannot fly. Write it in the logical ...
1
vote
3answers
70 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
80 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
0
votes
0answers
40 views

Help with formulating a mathematical logic formula

I need to write a precise mathematical expression to formulate an algorithm that could be implemented in software. It has the following simple logic: An Internet user of the software in a ...
1
vote
1answer
266 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
0
votes
0answers
90 views

Proving that all noncommutative groups have at least six elements

By Gödel's Completeness Theorem, any first order sentence expressible by the language of group theory that is true in all groups must be provable from the group theory axioms. I would like to see a ...
1
vote
1answer
119 views

First-Order Languages and Circular Reasoning

I'm reading a book on Mathematical Logic (on my own) and from the beginning there are terms such as "functions" and "relations", but the only definitions of these words that I know are in terms of ...
4
votes
4answers
145 views

When do free variables occur? Why allow them? What is the intuition behind them?

In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound. Why would one write such a formula? Why are free variables allowed? What is the intuition for allowing free variables?
0
votes
1answer
39 views

Two questions about the lattice derived from 0th-order formulas

It's not clear to me if the definitions I've been given are common. Therefore I will give a brief overview of the constructions I'll need to talk about the objects I want to. Prerequisite: Given ...
0
votes
1answer
37 views

Logical form of this statement?

In logical form, how would you express : Take any two fractions, add them together, and the result will be an integer
0
votes
1answer
25 views

How to describe a set of coordinates of variable length?

I need to describe a set of coordinates with up to 8 dimensions. A problem is asking me to describe an event from a experiment involving sampling. The catch is that the experiment doesn't end until a ...
3
votes
0answers
150 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
0
votes
1answer
37 views

How to express in Propositional Logic

If A(S;C) is the propositional function (predicate) and student S who takes course C receives an A grade and the domain is a set of student belonging to university x. How to express "There are ...
2
votes
3answers
34 views

Put $(a \leftrightarrow b) \wedge c$ in DNF

$$(a \leftrightarrow b) \wedge c$$ I'm having problems with this. If I do: $$(a \rightarrow b) \wedge (b \rightarrow a) \wedge c$$ then $$(\neg a \vee b) \wedge (\neg b \vee a) \wedge c$$ But now I'm ...
1
vote
3answers
48 views

Question about the FT, FF cases in the conditional:

The conditional operator, $\phi \implies \psi$, is True for the values $TT, FT, FF$ and false for $TF$. I can easily understand why it's true for $TT$ and false for $TF$, but why is it for $FT$ and ...
1
vote
2answers
75 views

A quick question about a logical negation

I just want to make sure I'm negating the following logical statement correctly (for a contradiction proof): For every set $A$, there exists a well ordered set $V$ such that there exists no ...
0
votes
3answers
60 views

For $x+y+z=0$, if $x$ and $y$ are divisible by some integer $k$, then so is $z$.

If k|x and k|y and x+y+z = 0, then k|z. Here, "k|x" means that $k$ is a divisor of $x$ and $x,y,z,k \in \mathbb{Z}$ What strategy would you employ to prove this?
0
votes
1answer
112 views

Determine whether each of the following sets is well ordered?

A set is well ordered if every nonempty subset of this set has a least element. Determine whether each of the following sets is well ordered. a) the set of integers b) the set of integers greater ...
0
votes
1answer
76 views

Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
1
vote
3answers
262 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
0
votes
1answer
62 views

find integral values k such that sum of expression is minimized

Given n values $X_1 , X_2 , ...., X_n$ , where $X_i$ can be positive or negative. The absolute values of $X_i$ will be less than $100000$ , also $n<=100000$ . What should be the possible value(s) ...
3
votes
1answer
125 views

A Question Regarding Forcing in Gödel's Constructible Universe in Infinitary Logics

In his answer to the MathOverflow question Gödel's Constructible Universe in Infinitary Logics, Prof. Hamkins gives a very interesting answer and proof to user46667's second question: (2) What is ...
1
vote
1answer
74 views

Constructive proof for: P => ((P => Q) => Q)

I'm trying to find a constructive proof for the proposition: P => ((P => Q) => Q) given P and Q to nullary proposition symbols but I can't find a proof without using the excluded middle rule. Anyone ...
2
votes
1answer
85 views

Why can negation pass through multiple quantifiers? [Chartrand P52-53, Velleman P65]

I'm mindful of the Quantifier Negation Laws and Negating a statement that ... several quantifiers. $\neg \; \exists \; P(x) \equiv \forall \; x \; \neg \; P(x) $ $ \neg \; \forall \; x \; ...
2
votes
1answer
39 views

Every truth function of the inderterminates X and Y is an iterated composition of negations and disjunctions.

I'm reading K.T.Leung and Doris L.C.Chen's Elementary set theory.I can't solve exercise 10: Prove that every truth function of the inderterminates X and Y is an iterated composition of negations and ...
3
votes
1answer
133 views

Are there classes with different sizes?

Are there classes with different sizes ? I will put a precise statement of my question below: Are there two well formed formulas $P,Q$ each with one free variable such that there is no well formed ...
0
votes
1answer
95 views

Building an axiomatic theory

I am using an expert system inferring some logical rules on a knowledge base to produce some new statements. I would like to formalize the logical mechanisms used by the inference engine. As a novice ...
1
vote
1answer
26 views

Is it possible to prove an argument is not satiable with equivalences?

I am trying to prove is this argument: (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) is satiable with equivalence. Is what I said below valid for this? (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) q ∨ (p ∧ ¬p) ...
0
votes
1answer
263 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
1
vote
1answer
49 views

How to express this truth set?

How would you express this truth set in mathematical terms? $4 < x^2 \le 9, X \in \mathbb{R}$
0
votes
1answer
62 views

Rules of Inference…From the following premises, conclude that p → q.

1. (r ∧ ¬s) ∨ (q ∧ ¬s) 2. ¬s → ((p ∧ r) → u) 3. u → (s ∧ ¬t) ----------------------- Prove from the previous arguments. p → q Hey guys, I am really lost, so far I ...
1
vote
1answer
49 views

Equivalence Proof (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r).

I am trying to prove (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r) ≡ ¬r ∨ (q → p). So far I have done the following: (p ∧ q) ∨ ¬(¬p ∨ q) ∨ ¬(q ∧ r) Implication Definition (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∨ ¬r) De ...
0
votes
2answers
86 views

Can logic and mathematics be used together?

I have been wondering if logical symbols ($\to$, $\sim$, etc.) can be used with traditional mathematical notation ($+$, $/$, etc.) in the same equation. For example, would the following equation be ...
0
votes
2answers
127 views

if p then q unless r — do i understand this?

the statement is: if p, then q, unless r I'm to convert it into a compound proposition. I've reasoned that: when p is true AND r is true, q is false when p is true AND r is false, q is true when p ...
0
votes
2answers
83 views

not p whenever q — do i understand this?

The phrase is not p whenever q. I take this to mean the same thing as not p if q. When p is false, q can be true or false. When p is true, q is false. When q is true, p is false. When q is false, p ...
0
votes
1answer
33 views

Need to check if these logic answers are correct

Im doing a few practice questions but it didn't come with answer sheets. Are my answers correct? Sorry if i can't put actually symbols as i'm new here and don't know how to implement them. $$\tag{S1} ...
6
votes
0answers
122 views

Skolem Hulls in $H_{\omega_2}$

Consider a model of the form $\mathfrak{A} = (H_{\omega_2}, \epsilon, \prec, f_0, f_1, ...)$, some expansion of $H_{\omega_2}$ in a countable language, with $\prec$ giving a well-order. Does there ...
1
vote
1answer
49 views

Name for DNF simplification rule / prime implicants under closure?

I was reading this question which links to this list of propositional equivalences. One of the equivalences shown (T5a) is: $$ A \wedge B \vee A \wedge \neg B \equiv A $$ I have used this rule by ...
1
vote
1answer
76 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
1
vote
3answers
90 views

Do I have to use induction to prove a statement that holds for all natural numbers?

If I have a statement $P$ and I wanna prove that $P$ is true for all $n \in \Bbb N$, do I have to use induction or can I just take an arbitrary $k \in \Bbb N $ and prove that $P$ is true for $k$? ...
2
votes
0answers
27 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
0
votes
2answers
257 views

For all x there exists a y such that x+y=0

I know this statement is true but I am having trouble actually proving it. I know that if x=5 then y=-5. How can you prove that properly.
0
votes
1answer
50 views

For studying properties of natural number, do we only need to study finite set of numbers to prove a particular property?

Let's say we want to study whether the set of natural numbers satisfy a particular property. Then we may think of induction, or whatever. My question, is it true that there exists $X \in \mathbb{N}$ ...
0
votes
1answer
78 views

Applying Compactness Theorem in Predicate Logic

$A$ is a first-order sentence over the language $L = [; R, =]$ where $R$ is a binary predicate symbol. Suppose that for each $n \geq 3$, $A$ has a model consisting of a directed cycle with n nodes, ...
1
vote
1answer
87 views

Prove $A $ \ $B $ = $A \cap B^c $

I see the use of $A $ \ $B $ = $A \cap B^c $ being used in bigger problems but how do you prove this? Is the proof as simple as: $A $ \ $B $ $\iff$ $ x \in (A \setminus B) \iff x\in A \cap ...
0
votes
4answers
74 views

Proving a proposition is a tautology

I have to prove $P \lor ( Q$ XOR $R) \lor (R \rightarrow Q)$ is always true. I got $P \lor ( R \rightarrow \lnot Q ) \lor (R \rightarrow Q)$. Now I'm stuck at this part. I have no idea how to ...
0
votes
1answer
66 views

Propositional Calculus basic rules

I've been learning propositional calculus and proofs and I'm not sure if we are able to write $(P \lor Q) \leftrightarrow (\lnot P \rightarrow Q)$. If I am doing a proof will i be able to replace (P v ...
4
votes
3answers
156 views

A question about Implicational Propositional Calculus

My question is motivated by a previous post about Implicational calculus Having showed that Mendelson (A1) and (A2) axioms plus Peirce's law are a complete axiom set for implicational fragment of ...