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
163 views

Maximal consistent set. Decomposition lemma

Let $\Gamma$ be a maximal consistent set. Prove: $\varphi \lor \psi \in \Gamma \iff \varphi \in \Gamma $ or $ \psi \in \Gamma$. Now define $V_{\Gamma}: Q \to \{ 0, 1 \}$ as follows: ...
3
votes
1answer
140 views

Struggling with writing logical proofs

I am struggling with the way to write a clear and mathematical proof of logical theorems. Take for example the theorem $\Gamma \models A, \Gamma \subseteq \Delta$ implies $\Delta \models A$. I can ...
1
vote
1answer
318 views

Difference between Rician distribution and Gaussian distribution

could any one please tell me the difference between Rician and Gaussian Distribution and the advantages of using one over other please.With some mathematical proof would be truly appreciated Thank ...
5
votes
2answers
134 views

What holds in a deductively complete system?

I read an article which presented some system with axioms and inference rules (I don't know if that type of system have a term for in English). The article stated that the system is "deductively ...
2
votes
4answers
815 views

Transitivity of union of two transitive relations

I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union ...
2
votes
2answers
79 views

Analytic method for number theory-do we have to assert second-order logic?

I am an undergraduate. I am just starting to study logic and analytic number theory at the same time, so please forgive me if I made an elementary misunderstanding. A lot of theorem in number theory ...
1
vote
1answer
44 views

Appearance of sentence parameters in a theorem

Is it true that if $A$ is a formula in a Hilbert system $H$, then if $B_1,B_2,\ldots,B_n$ is a proof of $A$ in $H$, any sentence parameter not appearing in $A$ doesn't appear in $B_1,\ldots,B_n$? If ...
3
votes
1answer
47 views

Preimages of a function: Is the following proposition true or false?

Let $g: ℤ \times ℤ → ℤ \times ℤ$ be defined by $g(m,n) = (2m, m – n)$. Is the following proposition true or false? Justify your conclusion. For each $(s, t) ∈ ℤ \times ℤ$, there exists an $(m, n) ∈ ℤ ...
2
votes
2answers
1k views

Is there a difference between 'inconsistent', 'contrary', and 'contradictory'

Is there a difference between 'inconsistent' 'contrary' and 'contradictory'? As far as I understand, two statements are inconsistent when they can not both be true; two statements are contradictory ...
5
votes
3answers
162 views

Using $p\supset q$ instead of $p\implies q$

I saw that a use for the notation $p\supset q$ instead of $p\implies q$ that got me a bit confused. One occurrences is in this Wikipedia link. It seems to me opposite than what it should be, let me ...
3
votes
1answer
61 views

Is it a standard to say that $a \oplus a_{\small 1}=0$ or $a \veebar a_{\small 1}=0$?

I am trying to express the following: $a$ or $a_{\small 1}=0$ but only one of them equals zero. so if $a=0$ then $a_{\small 1}\neq 0$ and if $a\neq 0$ then $a_{\small 1}=0$. And I'm ...
3
votes
1answer
89 views

Substitution - what's the technical name of the inference rule?

Suppose the following are written down in some context. $$3x^2 < y$$ $$x^2=xy-1$$ Then we may deduce (also within that context) that $$3(xy-1) < y$$ What is the technical name of this ...
12
votes
2answers
329 views

Is second order logic even a logic?

Second order logic is a language, but, is it a logic? My understanding is that a logic (or "logical system") is an ordered pair; it is a formal system together with a semantics. However, the language ...
1
vote
1answer
108 views

Implication: F $\implies$ T

Why is F $\implies$ T taken as true? Why is this the "convention"?
3
votes
0answers
60 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
1
vote
1answer
149 views

Question about a puzzle in to mock a mockingbird

In to mock a mockingbird, we have the following puzzle: There are four people: A is an accurate truth teller B is an inaccurate truth teller C is an accurate liar D is an inaccurate liar Smullyan ...
3
votes
0answers
127 views

Definition(s) for variable binding in first-order logic

The following statement made me realize that variable binding can be defined in first-order logic: The same holds for λ terms to define functions. There is no reason that they could not be ...
5
votes
2answers
773 views

Deriving A implies B from Not A

My logic textbook has the following example showing how to derive $A \to B$ from $\neg A$: First we assume $A$ and use the conjunction introduction rule which results in a contradiction $[A] \land ...
5
votes
2answers
89 views

Is there a theory of extensible definitions?

We can define $+$ as a function $\mathbb{N}^2 \rightarrow \mathbb{N}$, and then prove: Theorem 1. The range of $+$ is $\mathbb{N}$. If we later wish to extend $+$ to a function $\mathbb{Z}^2 ...
2
votes
3answers
142 views

prove: $\dfrac{2^{n+1}+(-1)^n}{3}$

I am asked to prove this notation with induction for $n\in \mathbb{N}$: real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
3
votes
1answer
141 views

Can we use proper classes in this way, to define a new infinity larger than |Ord|?

I believe there is a way to do this that makes sense, and I explain it below. I would like to know if I did some obvious mistake, or if the idea doesn't make sense for some reason I didn't figure it ...
1
vote
2answers
164 views

Do the premises logically imply the conclusion?

$$b\rightarrow a,\lnot c\rightarrow\lnot a\models\lnot(b\land \lnot c)$$ I have generated an 8 row truth table, separating it into $b\rightarrow a$, $\lnot c\rightarrow\lnot a$ and $\lnot ...
1
vote
4answers
147 views

Writing an expression using logic

Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table: $$\begin{array}{ccc|c} P&Q&R&???\\ \hline T&T&T&F\\ T&T&F&T\\ ...
2
votes
1answer
105 views

Declarative statements

Is there some branch of mathematics that works with truth bearing statements instead of variables, and defines operations between them? Basically I am looking for some well known system that defines ...
1
vote
1answer
53 views

CNF/ Create a cnf variable from some forumals of CNF

I have the next CNF: $(A \lor C) \land (B \lor C)$ and also: $(D \lor E) \land (F \lor G)$ Now, I want to be sure that only one of the CNF is true. Meaning, I want to declare two new variable, T ...
10
votes
2answers
126 views

Growth-rate vs totality

How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
2
votes
1answer
106 views

$xy$ itself square in this particular logic

I would like to know the solution or procedure to find the exact analysis/solution of one of my observation. let $x = a^2$ and $y = b^2$, then can we express $xy$ (concatenation of $x$ and $y$) as ...
17
votes
3answers
772 views

What is dual to “There exists unique?”

I know that "for all" $(\forall)$ and "there exists" $(\exists)$ are dual, in the sense that $$\neg \forall \neg = \exists,\quad \neg \exists \neg = \forall$$ What is dual to "there exists unique"? ...
0
votes
3answers
86 views

what is the relation between not A and everything but A

I am examining Bayes' Theorem, and wondering about the alternative interpretations of ~A, as being: not A, ¬ A everything but A, ∀-A And how this will affect the use of probabilities. ...
6
votes
2answers
133 views

Axiom of Choice-esque argument to show that a proof of a statement exists without actually giving a proof

What if the set of all well-formed statements in ZFC formed a kind of pseudo-category where a morphism f between objects A, B represented a formal proof that A implied B? What if that category could ...
6
votes
1answer
254 views

An Axiomatic Treatment of Mathematics from First Principles to the Major Subjects?

I'm looking for a book - more likely, books - that could take me from the axioms of mathematical logic up to the major subjects of mathematics, like analysis, algebra, geometry, etc. For example, a ...
2
votes
2answers
92 views

Are these propositions equivalent?

Statement 1: Maria will find job if she learns mathematics. Statement 2: Maria will find a job unless she does not learn mathematics. I know the answer is probably that these are same, but ...
4
votes
1answer
58 views

Special undecidability situation

Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). Can one construct two statements $\phi_1$ and $\phi_2$ such that $$ ZFC' \vdash ((ZFC \vdash \phi_1) \ \text{or} \ (ZFC \vdash \phi_2)) $$ ...
26
votes
4answers
1k views

Is $\mathbb{N}$ impossible to pin down?

I don't know if this is appropriate for math.stackexchange, or whether philosophy.stackexchange would have been a better bet, but I'll post it here because the content is somewhat technical. In ZFC, ...
3
votes
1answer
183 views

Why every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$

Let $\mathbb{Q}$ be the set of rational numbers. Show that every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$. This is an exercise on page 180, A ...
3
votes
1answer
116 views

Boolean Algebra Transform

I am revisiting Boolean algebra after a long while. Can somebody help show me how to simplify the LHS to get the RHS? $$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
5
votes
2answers
157 views

Does this qualify as a statement?

Is this a statement? All positive integers with negative squares are prime. What do we need to qualify as such?
4
votes
6answers
560 views

Symmetric, non-reflexive relation

I'm looking for an example of a mathematical relation that is symmetric but not reflexive. A standard non-mathematical example is siblinghood.
2
votes
3answers
167 views

Logic Negation Symbols

$\def\nn{\mathord{\sim}}$ This is a rather simple question but I can't find an exact answer on it. In examples, I've seen $\nn$ and $\lnot$. These fall under ‘negation’. If they both fall under ...
1
vote
2answers
43 views

Can the results of an problem invalidate the process and therefore themselves?

For example, suppose that to solve an equation, one must divide both sides by x, and it is later discovered that x = 0 (and zero was a permissible value in the original equation). What would this mean ...
1
vote
1answer
91 views

Is it interesting to consider satisfiability modulo theory in the context of modal logic?

Recently lot of work has been done considering satisfiability of formulas in specific theory (array theory, bit-vector theory). But I did not find any results about satisfiability modulo theory in ...
2
votes
1answer
102 views

Are the following two first-order logic statements correct?

I am doing questions to revise for an exam. Here is the question: Convert "Elder gods do not like Hello Kitty" to first-order logic. Here is the answer they give: ...
4
votes
4answers
501 views

the role of logic in math and education

My question is somewhat related to this discussion: Is Mathematics one big tautology? I have a computer science background and I have always approached math from the logic point of view ...
4
votes
1answer
108 views

The manuscript Summa Logicae (William of Ockham)

The Summa Logicae (Latin, in English it's the Sum of Logic) is a textbook on logic by William of Ockham. There are articles about the Summa Logicae in Wikipedia and in Logicmuseum. It was published ...
0
votes
1answer
76 views

How to prove $∀x ∀y (P(x) → Q(y)) ↔ (∃x P(x) → ∀y Q(y))$ using Fitch Intro and Elim rules

$∀x ∀y (P(x) → Q(y)) ↔ (∃x P(x) → ∀y Q(y))$ We are only permitted to use Intro and Elim rules, and I am stuck on how to even begin this proof. Any help would be appreciated. Thanks!
2
votes
1answer
737 views

How to calculate the “difference between X and Y”

I feel like this is the silliest question ever, so I apologize in advance! a statement reads: Z is the difference between X and Y. Which of these is true? Z = X - Y Z = Y - X Z = |X - Y| I want ...
1
vote
1answer
36 views

Boolean Equation Transformation

Can someone show me the steps in getting from $f = (ab + c')(d' + e + f')$ to $f = abe +ab(df)' + c'e + c'(df)'$? I am trying to relearn Boolean algebra after a long hiatus.
2
votes
2answers
71 views

formalized provability predicate and implication relation

$\DeclareMathOperator{\pvbl}{pvbl}$ Let $\pvbl$ be the formalized provability predicate. Sentences $A$, $B$, $C$, $D$ have the following relation. $\pvbl ( A \rightarrow B)$ $\pvbl ( C \rightarrow ...
12
votes
2answers
794 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
4
votes
1answer
67 views

Determine whether two primitive recursive functions are equal

Is there an algorithm to determine whether two primitive recursive functions are equal (as mathematical functions)?