Tagged Questions

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
2answers
16 views

Good Sources for Lecture Movies in Set Theory, Logic and Philosophy of Maths

Of course as any other researcher I'm not able to attend any scientific event in my research area. But it is always interesting and useful to watch the lecture movies of these events. I will ...
1
vote
1answer
14 views

Formulate a condition that function f(x,y) must hold in order to be considered as “associative”.

Let $f(x,y)\colon\{0,1\}^2\to\{0,1\}$ be a Boolean function. Answer the following "warm-up" questions: Prove or dispute: The function $f$ can be one-to-one. Formulate a condition that function ...
0
votes
0answers
5 views

formulate a condition that function f(x,y) must hold in order to be considered as “associative” [duplicate]

Let f(x,y):{0,1}^2->{0,1} be a Boolean function. Answer the following "warm-up" questions: a. Prove or dispute: The function f can be one-to-one. b. Formulate a condition that function f(x,y) must ...
1
vote
2answers
16 views

How do I prove converse of these two claims?

Prove or disprove the claim, and prove or disprove the converse: Claim 1: ∀n ∈ ℕ, (Ǝk ∈ ℕ, n = 5k + 2) ⇒ (Ǝj ∈ ℕ, n^2 = 5j + 4) Claim 2: ∀m,n ∈ ℕ, (Ǝk ∈ ℕ, m = 7k + 3) ∧ (Ǝj ∈ ℕ, n = 7j + 4) ⇒ ...
-1
votes
0answers
23 views

Logical Geometry Challenge [on hold]

d the asd numdsber of easdddges be thasdat such a asdadaigure casdll asdn
1
vote
0answers
10 views

Summation explanation and help [on hold]

I am confused about how summations work... I understand a bit but what if u had to skip like 1-3-5-7-infinity could someone clear this up and explain it to me
1
vote
1answer
19 views

What is the conjunctive normal form of the boolean constant TRUE?

I have the following problem: Is TRUE (or 1) a logically equivalent formel in conjuctive normal form to a tautology? How can I build the conjunctive normal form ...
1
vote
3answers
39 views

Robinson arithmetic and its incompleteness

Wikipedia in Italian has a sketch-of-proof that Robinson arithmetic is not complete, since commutativity of addition is undecidable. The sketch of proof creates a model that adds two elements, $a$ and ...
0
votes
0answers
56 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
2
votes
1answer
20 views

How to prove that a set of connectives is adequate

I have this Table: $$\begin{array} {|c|} \hline A & B & A*B\\ \hline 1 & 1 & 0\\ \hline 1 & 0 & 1\\ \hline 0 & 1 & 1\\ \hline 0 & 0 & 0\\ \hline \end{array}$$ ...
4
votes
0answers
32 views

Type-definable Forcing or forcing in a non-first order setting

Roughly speaking, in set forcing the forcing notion is a set from ground model's perspective and in class forcing its a definable subset of the ground model given by solutions of some formula with ...
2
votes
0answers
26 views

Is it true that each large cardinal which is not first order expressible has no extender characterization?

It is well-known that Reinhardt cardinal (i.e. The critical point of a non-trivial self-elementary embedding of the universe in $ZF$) is not first order expressible. Does this imply that Reinhardt ...
3
votes
1answer
186 views

Is there any category theoretic proof for independence of Continuum Hypothesis?

Both of set theory and category theory could be a foundation for mathematics. Many set theoretic arguments could be translated to a category theoretic argument and vice versa. Question: Is there ...
2
votes
1answer
35 views

How can universal quantifier manipulation rules be made redundant by the generalization rule (metatheorem)?

On the Wikipedia page for Hilbert style axioms, in the "Logical axioms" section, it gives the axioms to manipulate universal quantifiers : $Q5. \forall x(\phi)\rightarrow \phi[x:=t] $ $Q6. ...
1
vote
1answer
25 views

using the elimination rule in natural deduction

Prove that $$(A ∧ B) \to C ⊢ A \to (B \to C)$$ Am I using the conjuction elimination rule correctly? Or am I assuming too much? $(A ∧ B) \to C$ (Given) $A \to C , B -> C$ (∧E 1) $A ...
2
votes
4answers
54 views

Prove $Q \rightarrow \neg(Q \rightarrow \neg P)$

I have an exercise about proving statements: Suppose that P is true. Prove that Q → ¬(Q → ¬P ) is true Givens: $P$ $Q \rightarrow \neg P$ Goal: $\neg Q$ which I simply prove ...
1
vote
3answers
50 views

If true for the general element, then true for all. What's this?

In mathematics often (always) one proves that a property is true for the general element of a set. From that, one can say that that property is true for all the elements of that set. Is that a ...
1
vote
1answer
33 views

Reference request basic logic/model theory

I'm taking a knowledge representation class and need more perspective on basic model theory. We're currently using Levesque and Brachman. Specifically, a question on the midterm was something like, ...
3
votes
1answer
22 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
1
vote
3answers
96 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
2
votes
3answers
59 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
1
vote
3answers
47 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
4
votes
4answers
59 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
3answers
50 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
2
votes
2answers
23 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
2
votes
2answers
45 views

Syntax of an epsilon delta proof/why is this version incorrect [duplicate]

So we have the regular $\delta$-$\epsilon$ definition of continuity as: (1) For all $\epsilon>0$, there exists a $\delta>0$ such that, if $|x-a|<\delta$, then $|f(x)-f(a)|<\epsilon$. My ...
1
vote
1answer
21 views

proof checking - power set and family set

Decide if it is true that $P(A) \subseteq P(B) \implies \bigcup A \subseteq \bigcup B $ where $P(A), P(B)$ are power set and $A,B$ are family of sets My proof: Let $x \in P(A)$ then we have ...
1
vote
1answer
21 views

find URM program for the following function

find URM program for the following functions: a)$(m,n) \longrightarrow 2m+5n$ b)$(m,n) \longrightarrow m\times n $ answer: this program showes $(m,n) \longrightarrow m+n$ 1)$J(2,3,5)$ 2)$S(1)$ ...
1
vote
1answer
25 views

Generic in Boolean-Valued-Models

Let $M$ be a transitive $\in$-interpretation of a extension $T$ of $ZF$ in $ZF$,and let $B$ such that $$T\vdash B\in M\wedge B\text{ is a complete Boolean algebra}$$ Then, using the fact that any set ...
1
vote
1answer
38 views

Bases of complex vector spaces and the axiom of choice

In Zermelo-Fraenkel set theory $ZF$ consider the following statement defined for every field $K$: $B_K$ : Every vector space over $K$ has a basis. It is well-known that $AC \Rightarrow \forall K ...
0
votes
3answers
44 views

Recommendation on Quine's text

I'm planning to study logic seriously and I think Quine's style is fine to me so i'm going to read his book. There are two famous books by him. Namely, "Methods of logic" and "Mathematical logic". I ...
0
votes
1answer
40 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
3
votes
0answers
91 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
3
votes
1answer
46 views

What is a list of book that i need to read as a prerequisite before start reading “lectures of logic and set theory vol.1 by George Tourlakas”?

What is a list of formal textbook that i need to impose myself to read as a prerequisite before start reading a book called lectures of logic and set theory vol.1 by George Tourlakas? That book is ...
0
votes
1answer
19 views

How does the following example prove that this set of axioms for a probability field is consistent?

This is froms Kolmogorovs Foundations of probability theory. He gives the following five axioms. Let $E $ be a set and $\mathcal F $ be a set of subsets of $E $. I $\mathcal F $ is closed under ...
0
votes
1answer
37 views

Cardinality of the set of non isomorphic structures of fixed cardinality

Let $L$, be a language and $\alpha$ be a cardinal; let $\Gamma:= \{\text{set of non isomorphic $L$ structures, having cardinality $\alpha$}\}$. Prove that $\operatorname{Card}(\Gamma)\leq ...
1
vote
1answer
35 views

Set theory, operation with products, union and intersection

I need to show the following using logical connectives: $B\setminus (B \setminus A)=A \cap B $ $(A \setminus B)\cup(B\setminus A)=(A \cup B)\setminus(A \cap B)$ $(A\times B\setminus C )=(A\times ...
1
vote
2answers
27 views

logical associative expressiveness with no negation operator

Let's suppose we can only use $\wedge$ and $\vee$ operators (we have no negation operator), and by default we have associativity to the left. Is this subset of logic as expressive as the one with the ...
1
vote
1answer
33 views

Translate the following argument into propositional logic, and then assess it for validity.

This is question 9 from exercise 6.5.1 in Smith and Cusbert's Logic: The Drill. It wants a translation and test of validity for the following: Catch Billy a fish, and you will feed him for a ...
0
votes
1answer
49 views

What is the formal way to define “class” in ZFC?

Unlike axiomatic systems deal with classes such as NBG, the term "class" is not a word in ZFC. How do I formally treat classes? Here is an example of what I'm exactly talking about. Example ...
1
vote
1answer
92 views

There are any known example of independence proofs about independence result?

(This question is inspired by deleted question, and the questioner who write the deleted question wrote new question.) It is well-known that consistency of "ZF + DC + every set of reals are Lebesgue ...
3
votes
3answers
66 views

Which texts do you recommend to study universal algebra and lattice theory?

As I'm planning to study some algebraic logic (a lot of!), I found that some knowledge of universal algebra, lattice theory and boolean algebras is a must. I wonder if you have any recommendation to ...
3
votes
1answer
35 views

Suppose a $\in \mathbb{Z}$. $a^{2}|a$ if and only if $a \in \{-1,0,1\}$

Suppose a $\in \mathbb{Z}$. Then $a^{2}|a$ if and only if $a \in \{-1,0,1\}$ So, I have started and this is what I have so far: Case 1: If $a^{2}|a$, then $a \in \{-1,0,1\}$. For the sake of ...
3
votes
2answers
45 views

Can this expression $(\neg B \land \neg D) \lor (\neg A \land B \land C) \lor (A \land C \land D)$ be further simplified?

I have assignment for computer architecture where I have to simplify a big boolean function: f(a, b, c, d) = a'b'c'd + a'bcd' + abcd + a'bcd + a'b'cd' + ab'cd' + ab'c'd' + ab'cd + a'b'c'd' ...
0
votes
2answers
45 views

How to prove $p \vee q \vdash \neg(\neg p \wedge \neg q)$?

I'm trying to complete a list of exercises but this question I still can not solve. Somebody could help me? updated: this is my conclusion 1 - $p\vee q$ Premise 2 - p Assume 3 - $\neg p\wedge\neg q$ ...
0
votes
0answers
39 views

What's the difference between a costant $k$ and $arity = 0$?

What kind of mathematical entities can have $arity = 0$ without being a constant ? Or there is a concept that generalize the concept of constant and I can't see it ? Background: I am having some ...
1
vote
2answers
86 views

Proving the non-derivability of formula using the of the kripke model

I try proving the non-derivability of $(p\to q) \to \lnot p \lor q$, using the of the kripke model. I tried using different combinations of $Wi$, but I get fail.
1
vote
1answer
29 views

How can I further simplify this $A$ + $\neg A B$?

I know there's a rule to simplify this formula $A$ + $\neg A B$, but I am not seeing it. Can someone tell me the name and how to do it?
0
votes
1answer
43 views

Show that $(A \oplus B) \oplus B = A$

I having some trouble proving $(A \oplus B)\oplus B = A$, I understand the truth table logic but can someone example to me in theory what the equation mean in set theory?
1
vote
1answer
58 views

How to better understand “ x occurs free in a wff ” in first order logic?

On page 121 of Herbert Enderton's A Mathematical Introduction to Logic, the author gives a proof of the following example : If x does not occur free in $\alpha$, then $$ \vdash ( \alpha \rightarrow ...