3
$\begingroup$

I try to express the following statements in first order logic:

  1. X is a subset of Y.
  2. A set can be uniquely characterised by its elements.
  3. The power set p(X) contains all subsets of X.
  4. A set X is the union of all its subsets containing just one element.

Thus far I managed:

  1. $\forall x \in X \Rightarrow x \in Y$
  2. $X=Y \Leftrightarrow (\forall x \in X \Rightarrow x \in Y \land \forall y \in Y \Rightarrow y \in X)$
  3. $ x \in p(X) \Leftrightarrow (\forall y \in x \Rightarrow y \in X) $

However now I don't know to express the 4th problem via FOL.

I tried: $ X = \cup x.(\forall z \in X \exists t. z \in t \land t = x \land z \not \in \forall y. y \neq t)$

If possible I would also like to convert 3. in an expressing $p(X)$ with $=$ rather than $\Leftrightarrow$

Any form of constructive comments are welcome. Thanks in advance.

EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

$ X = \underset{|x| = 1, x \subset X} \cup \Leftrightarrow \forall y \in X \exists x . (y \in x \land \lnot \exists z .(z \lnot = x \land y \in z) ) $

On the LHS of $\Leftrightarrow $ I simply tried to express the property given in the problem above and on its RHS I tried to express this property in terms of FOL.

$\endgroup$
  • $\begingroup$ The usual language of set theory includes only two relations: equality and set containment ($\epsilon$). That mean that you have to tell us how you represent the operation of set union. $\endgroup$ – Yuval Filmus Mar 19 '17 at 15:30
  • $\begingroup$ This is not a question for us, it is a question for your instructor. $\endgroup$ – Yuval Filmus Mar 19 '17 at 15:46
  • $\begingroup$ The instructors are not reliable, they may answer anytime between 1 day to two weeks. Thus I try to do as much as possible by myself, then try to rely find material other sources online and if nothing helps, I post here. $\endgroup$ – Imago Mar 19 '17 at 15:49
  • $\begingroup$ Unfortunately we are not able to help you cope with your instructors. You can try contacting a TA. $\endgroup$ – Yuval Filmus Mar 19 '17 at 15:52
1
$\begingroup$

It might be useful to take a look at the ZFC axioms. The existence of one element sets is guaranteed by the Axiom of pairing.

The axiom of pairing says that given $A$,$B$ sets, one can construct a third set $C = \{A, B\}$. Formally: $$ \forall A. \forall B. \exists C.\forall D. (D \in C \iff D = A ~\lor~ D = B) $$

A singleton set is just the pairing $\{A,A\} = \{A\}$.

The axiom of union says that for any set $A$ there is a set $U$ whose elements are exactly the elements of the elements of $A$. That is:

$$ \forall A. \exists U. \forall c. (c \in U \implies \exists D.(c \in D ~ \land ~ D \in A)) $$

A set $X$ is the union of all its subsets containing just one element.

Let's look at some example, let $X = \{a, b\}^\star$ be a set, take $X^\prime = \{\{a\},\{b\}\} $, which is also a set by the axiom of pairing. By the axiom of union there exists a set $\cup X^\prime$ such that:

$$ \cup X^\prime = \{a,b\} = X$$

So you can look at the Union Axiom and try to modify to fit your problem, you have to make a union on a set of singleton sets, which means you have to find a way to define $X^\prime$.

$\star$: I'm assuming $a$ and $b$ are also sets.


EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

Well, from your previous answers it seems you're only allowed to use basic operations like membership and equality, if more stuff is allowed you can literally just write something that looks like natural language while still being formal.

$\endgroup$

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.